Equivalences among Relational Expressions

TLDR

Many database queries can be expressed using relational operations such as select, project, and join on tables of information. The study investigates the equivalence problem for relational expressions to aid query optimization. The authors introduce a tableau matrix to represent expression values and present a polynomial‑time algorithm for testing equivalence of tableaux for a key subset of expressions. They demonstrate that tableaux can encode functional dependencies among attributes and show that equivalence is NP‑complete in general but solvable in polynomial time for the considered subset.

Abstract

Many database queries can be formulated in terms of expressions whose operands represent tables of information (relations) and whose operators are the relational operations select, project, and join. This paper studies the equivalence problem for these relational expressions, with expression optimization in mind. A matrix, called a tableau, is proposed as a natural representative for the value of an expression. It is shown how tableaux can be made to reflect functional dependencies among attributes. A polynomial time algorithm is presented for the equivalence of tableaux that correspond to an important subset of expressions, although the equivalence problem is shown to be NP-complete under slightly more general circumstances.