Efficient Optimization of a Class of Relational Expressions.

@article{DBLP:journals/tods/AhoSU79,
  author    = {Alfred V. Aho and
               Yehoshua Sagiv and
               Jeffrey D. Ullman},
  title     = {Efficient Optimization of a Class of Relational Expressions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {4},
  year      = {1979},
  pages     = {435-454},
  ee        = {http://doi.acm.org/10.1145/320107.320112, db/journals/tods/AhoSU79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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/An3-1 or /cdrom

• 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/aDVD2 or /dvd

Conference Abstract

References

[1]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) 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, 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

[5]

William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX

[6]

Catriel Beeri, Ronald Fagin, John H. Howard: A Complete Axiomatization for Functional and Multivalued Dependencies in Database Relations. SIGMOD Conference 1977: 47-61 BibTeX

[7]

Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151 BibTeX

[8]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[9]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[10]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX

[11]

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

[12]

Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 BibTeX

[13]

...

[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]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[20]

Jack Minker: Performing Inferences over Relation Data Bases. SIGMOD Conference 1975: 79-91 BibTeX

[21]

...

[22]

Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 BibTeX

[23]

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

[24]

John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX

[25]

Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

[26]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

[27]

...

[28]

Moshé M. Zloof: Query-by-Example: the Invocation and Definition of Tables and Forms. VLDB 1975: 1-24 BibTeX

Referenced by

1. Felix Naumann, Ulf Leser, Johann Christoph Freytag: Quality-driven Integration of Heterogenous Information Systems. VLDB 1999: 447-458
2. Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999: 459-470
3. Sara Cohen, Werner Nutt, Alexander Serebrenik: Rewriting Aggregate Queries Using Views. PODS 1999: 155-166
4. Werner Nutt, Yehoshua Sagiv, Sara Shurin: Deciding Equivalences Among Aggregate Queries. PODS 1998: 214-223
5. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158
6. Serge Abiteboul, Oliver M. Duschka: Complexity of Answering Queries Using Materialized Views. PODS 1998: 254-263
7. Nieves R. Brisaboa, Héctor J. Hernández, José R. Paramá, Miguel R. Penabad: Containment of Conjunctive Queries with Built-in Predicates with Variables and Constants over any Ordered Domain. ADBIS 1998: 46-57
8. Xubo Zhang, Z. Meral Özsoyoglu: Implication and Referential Constraints: A New Formal Reasoning. IEEE Trans. Knowl. Data Eng. 9(6): 894-910(1997)
9. Oscar H. Ibarra, Jianwen Su: On the Containment and Equivalence of Database Queries with Linear Constraints. PODS 1997: 32-43
10. Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70
11. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
12. Sha Guo, Wei Sun, Mark Allen Weiss: On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems. IEEE Trans. Knowl. Data Eng. 8(4): 604-616(1996)
13. Alon Y. Levy: Obtaining Complete Answers from Incomplete Databases. VLDB 1996: 402-412
14. Xiaolei Qian: Query Folding. ICDE 1996: 48-55
15. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
16. Martin F. van Bommel, Grant E. Weddell: Reasoning About Equations and Functional Dependencies on Complex Objects. IEEE Trans. Knowl. Data Eng. 6(3): 455-469(1994)
17. Surajit Chaudhuri, Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993: 59-70
18. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
19. Paolo Atzeni, Riccardo Torlone: Updating Relational Databases Through Weak Instance Interfaces. ACM Trans. Database Syst. 17(4): 718-745(1992)
20. Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Formal Semantics of SQL Queries. ACM Trans. Database Syst. 16(3): 513-534(1991)
21. Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990)
22. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
23. Yatin P. Saraiya: Polynomial-Time Program Transformations in Deductive Databases. PODS 1990: 132-144
24. Pratul Dublish, Joachim Biskup, Yehoshua Sagiv: Optimizatioin of a Subclass of Conjunctive Queries. ICDT 1990: 455-469
25. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
26. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
27. Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351
28. Kazimierz Subieta, Wiktor Rzeczkowski: Query Optimization by Stored Queries. VLDB 1987: 369-380
29. Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330
30. Kazimierz Subieta, Marek Missala: Data Manipulation in NETUL. ER 1987: 391-407
31. Stefan Böttcher, Matthias Jarke, Joachim W. Schmidt: Adaptive Predicate Managers in Database Systems. VLDB 1986: 21-29
32. José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71
33. Matthias Jarke, Yannis Vassiliou: A Framework for Choosing a Database Query Language. ACM Comput. Surv. 17(3): 313-340(1985)
34. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
35. Ashok Pahwa, Adarsh K. Arora: Automatic Database Navigation: Towards a High Level User Interface. ER 1985: 36-43
36. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
37. Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
38. Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163
39. Mihalis Yannakakis: Querying Weak Instances. PODS 1984: 275-280
40. Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983)
41. David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983)
42. David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78
43. Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206
44. Alessandro D'Atri, Marina Moscarini, Nicolas Spyratos: Answering Queries in Relational Databases. SIGMOD Conference 1983: 173-177
45. David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: The Revenge of the JD. PODS 1983: 279-287
46. Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136
47. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
48. Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245
49. Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22
50. Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157
51. David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies. PODS 1982: 164-169
52. Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123
53. Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94
54. Anthony C. Klug: Abe: A Query Language for Constructing Aggregates-by-Example. SSDBM 1981: 190-205
55. Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120