Equivalence among Relational Expressions with the Union and Difference Operation.

Yehoshua Sagiv, Mihalis Yannakakis: Equivalence among Relational Expressions with the Union and Difference Operation. VLDB 1978: 535-548

@inproceedings{DBLP:conf/vldb/SagivY78,
  author    = {Yehoshua Sagiv and
               Mihalis Yannakakis},
  editor    = {S. Bing Yao},
  title     = {Equivalence among Relational Expressions with the Union and Difference
               Operation},
  booktitle = {Fourth International Conference on Very Large Data Bases, September
               13-15, 1978, West Berlin, Germany},
  publisher = {IEEE Computer Society},
  year      = {1978},
  pages     = {535-548},
  ee        = {db/conf/vldb/SagivY78.html},
  crossref  = {DBLP:conf/vldb/78},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

S. Bing Yao (Ed.): Fourth International Conference on Very Large Data Bases, September 13-15, 1978, West Berlin, Germany. IEEE Computer Society 1978
Contents

References

[1]: Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Data Bases (Extended Abstract). FOCS 1977: 107-113
[2]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
[3]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)
[4]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions (Abstract). SIGMOD Conference 1978: 39
[5]: ...
[6]: Alfred V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, Jeffrey D. Ullman: Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions. SIAM J. Comput. 10(3): 405-421(1981)
[7]: William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583
[8]: ...
[9]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[10]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970)
[11]: E. F. Codd: A Database Sublanguage Founded on the Relational Calculus. SIGFIDET Workshop 1971: 35-68
[12]: E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972)
[13]: Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158
[14]: ...
[15]: Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977)
[16]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[17]: Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976)
[18]: ...
[19]: Jack Minker: Performing Inferences over Relation Data Bases. SIGMOD Conference 1975: 79-91
[20]: ...
[21]: Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49
[22]: Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977)
[23]: John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975)
[24]: ...
[25]: ...
[26]: Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976)
[27]: ...