Equivalence among relational expressions with the union and difference operation
Yehoshua Sagiv, Mihalis Yannakakis · Very Large Data Bases · 1978
A generalization of tableaux as a method for representing queries in relational databases, called sets of tableaux, is proposed. Every relational expression with the operators select, project, join and union can be represented by a set of tableaux. This paper studies the equivalence problem for sets of tableaux. It is shown that the theory of tableaux is easily extended to sets of tableaux, but the equivalence problem for sets of tableaux (as well as the containment problem for single tableaux) is NP-complete even in very restricted cases. Polynomial time algorithms for testing equivalence of sets of tableaux (and containment of tableaux) in three special cases are presented. Sets of tableaux are further generalized to sets of elementary differences in order to include also the difference operator. The equivalence problem for sets of elementary differences is investigated.