Optimal implementation of conjunctive queries in relational data bases

ABSTRACT

We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal. The main lemma used to show this is that each conjunctive query has a unique minimal equivalent query (much like minimal finite automata).

References

1. 1.M. M. Aastrahan, E. B. Altman, P. L. Fehder and M. F. Senko, "Concepts of a data independent accessing model", Proc. 1972 ACM-SIGFIDET Conference, Denver (Nov. 1972).
2. 2.V. L. Arlazarov, E. A. Denic, M. A. Kronrad and I. A. Faradzev, "On economical construction of the transitive closure of a directed graph", Dokl. Akad. Nauk SSSR 194 (1970) 487-488. English translation in Soviet Math. Dokl. 11 , 5, 1209-1210.
3. 3.R. F. Boyce, D. D. Chamberlin, W. F. King and M. M. Hammer, "Specifying queries as relational expressions", Proc. of ACM SIGPLAN/SIGIR Interface Meeting on Programming Languages and Information Retrieval, Gaithersburg (Nov. 73).
4. 4.E. F. Codd, "A relational model of data for large shared data banks", CACM 13, 6 (June 1970) 377-387.
5. 5.E. F. Codd, "Further normalization of the data base relational model", Courant CS Symposia, 6, Data Base Systems, Prentice-Hall (May 1971).
6. 6.E. F. Codd, "Relational completeness of data base sublanguages", Courant CS Symposia, 6, Data Base Systems, Prentice-Hall, (May 1971).
7. 7.E. F. Codd, "A data base sublanguage founded on the relational calculus", PROC. 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego (Nov. 1971).
8. 8.E. F. Codd, "Recent investigations in relational data base systems", IFIP74, North Holland, 1974, 1017-1021.
9. 9.E. F. Codd, Ed., "Implementation of relational data base management systems", Panel Discussion, NCC (AFIPS) 75, Anaheim (May 1975).
10. 10.D. D. Chamberlin and R. F. Boyce, "SEQUEL" "A structured English query language", IBM Technical Report RJ1394 (May 1974).
11. 11.L. Clough, W. D. Haseman and Y. H. So, "Designing optimal data structures", AFIPS 76, 45 829-837.
12. 12.C. J. Date and E. F. Codd, "The relational and network approaches: comparison of the application programming interfaces", Proc. 1974 ACM-SIGFIDET Workshop on Data Description Access, and Control, Ann Arbor, (May 1974).
13. 13.C. Deheneffe, H. Hennebert, W. Paulus, "Relational model for a data base", IFIP 74, North Holland, 1974, 1022-1025.
14. 14.M. J. Fischer and A. R. Meyer, "Boolean matrix multiplication and transitive closure," 12th SWAT, IEEE (1971), 129-131.
15. 15.L. R. Gotlieb, "Computing joins of relations" Proc. ACM SIGMOD Conf. (May 75) 55-63.
16. 16.I. J. Heath, "Unacceptable file operations in relational data base", Proc. 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego (Nov. 1971).
17. 17.A. D. Held, M. R. Stonebraker and E. Wong, "INGRES - A relational data base system", AFIPS 75, 44 409-416.
18. 18.D. Kozen, "Complexity of finitely presented algebras", Tech. Rep. Cornell Univ., Comp. Sci., TR76-294.
19. 19.D. McLeod and M. Meldman, "RISS - A generalized minicomputer relational data base management system", AFIPS 1975, 44, 397-402.
20. 20.J. Mylopoulos, J. S. Schuster, D. Tsichritzis, "A multi-level relational system", AFIPS 1975, 44, 403-408.
21. 21.K. E. Niebuhr and S. E. Smith, "Initial implementation of Query by Example", IBM Technical Report (to appear).
22. 22.J. B. Rothnie, Jr., "Evaluating inter-entry retrieval expressions in a relational data base management system", AFIPS 75, 44, 417-423.
23. 23.V. Strassen, "Gaussian elimination is not optimal", Numerische Mathematik 13 (1969) 354-356.
24. 24.J. M. Smith and P. Y. Chang, "Optimizing the performance of a relational algebra database interface", CACM 8, 10 (Oct. 1975) 568-579.
25. 25.S.J.P. Todd, "Implementation of the join operator in relational data bases", IBM U.K. Scientific Centre, Technical Note 15, Peterlee (1974).
26. 26.S.J.P. Todd, "The Peterlee Relational Test Vehicle - a system overview", IBM Systems Journal 15, 4, 1976, 285-308.
27. 27.J. C. Thomas and J. D. Gould, "A psychological study of query by example", AFIPS 75, 44, 439-445.
28. 28.M. M. Zloof, "Query by Example", AFIPS 75, 44, 431-438.

Index Terms

• Information systems

  • Data management systems

    • Database design and models

      • Relational database model

    • Query languages

      • Relational database query languages

• Theory of computation

  • Randomness, geometry and discrete structures