ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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}
}
BibTeX

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.

Copyright © 1978 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

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 BibTeX

References

[1]
Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Data Bases (Extended Abstract). FOCS 1977: 107-113 BibTeX
[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
BibTeX
[3]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[4]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions (Abstract). SIGMOD Conference 1978: 39 BibTeX
[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) BibTeX
[7]
William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX
[8]
...
[9]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[10]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[11]
E. F. Codd: A Database Sublanguage Founded on the Relational Calculus. SIGFIDET Workshop 1971: 35-68 BibTeX
[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) BibTeX
[13]
Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 BibTeX
[14]
...
[15]
Ronald Fagin: Multivalued Dependencies and a New Normal Form for Relational Databases. ACM Trans. Database Syst. 2(3): 262-278(1977) BibTeX
[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
BibTeX
[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) BibTeX
[18]
...
[19]
Jack Minker: Performing Inferences over Relation Data Bases. SIGMOD Conference 1975: 79-91 BibTeX
[20]
...
[21]
Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 BibTeX
[22]
Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX
[23]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
[24]
...
[25]
...
[26]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[27]
...

Referenced by

  1. Joachim Biskup, Uwe Räsch: The Equivalence Problem For Relational Database Schemes. MFDBS 1987: 42-70
  2. Anthony C. Klug: Calculating Constraints on Relational Expressions. ACM Trans. Database Syst. 5(3): 260-290(1980)
  3. Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:04 2009