×

Structure and complexity of relational queries. (English) Zbl 0511.68073


MSC:

68P20 Information storage and retrieval of data
03C13 Model theory of finite structures
68Q25 Analysis of algorithms and problem complexity
68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Sagiv, Y.; Ullman, J. D., Equivalences among relational expressions, SIAM J. Comput., 8, 218-246 (1979) · Zbl 0412.68041
[2] Aho, A. V.; Ullman, J. D., Universality of data retrieval languages, (Proceedings, 6th ACM Symp. on Principles of Programming Languages. Proceedings, 6th ACM Symp. on Principles of Programming Languages, San Antonio, Texas (Jan. 1979)), 110-117
[3] Cord, E. F., A relational model of data for large shared data banks, Comm. ACM, 13, 6, 377-387 (1970) · Zbl 0207.18003
[4] Codd, E. F., Relational completeness of data base sublanguages, (Rustin, Data Base Systems (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J) · Zbl 0296.68041
[5] Chandra, A. K., Programming primitives for database languages, (Proc. 8th ACM Symp. on POPL. Proc. 8th ACM Symp. on POPL, Williamsburg, Virginia (Jan. 1981)), 50-62
[6] Chandra, A. K.; Harel, D., Computable queries for relational data bases, J. Comp. System Sci., 21, 156-178 (1980) · Zbl 0456.68128
[7] Chandra, A. K.; Harel, D., Structure and complexity of relational queries, (Proc. 21st FOCS. Proc. 21st FOCS, Syracuse, New York (Oct. 1980)), 333-347
[8] Chandra, A. K.; Harel, D., Horn clauses and the fixpoint query hierarchy, (Proc. ACM Symp. on Principles of Database Systems (March 1982))
[9] Chandra, A. K.; Merlin, P. M., Optimal Implementation of Conjunctive Queries in Relational Data Bases, (Proceedings, 9th ACM Symp. on Theory of Computing. Proceedings, 9th ACM Symp. on Theory of Computing, Boulder, Colorado (May 1977))
[10] Ehrenfeucht, A., An application of games to the completeness problem for formalized theores, Fund. Math, 49, 129-141 (1961) · Zbl 0096.24303
[11] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (Proc. SIAM-AMS, 7 (1974)), 43-73
[12] Fagin, R., Monadic generalized spectra, Z. Math. Logic Grundlag. Math., 21, 89-96 (1975) · Zbl 0317.02054
[13] Fraïssé, R., Sur les classifications des systèmes de relations, Publications Sc. d l’Université D’Alger, 1, no. 1 (1954)
[14] H. Gaifman. Private Communication.; H. Gaifman. Private Communication.
[15] (Gallaire, H.; Minker, J., Logic and Data Bases (1978), Plenum: Plenum N.Y) · Zbl 0412.68089
[16] Immerman, N., Relational queries computable in polynomial time, (Proc., ACM Symp. on Theory of Computing (May 1982)) · Zbl 0612.68086
[17] Kowalski, R. A., Predicate logic as a programming language, (Proc., IFIP (1974), North-Holland: North-Holland Amsterdam), 556-574
[18] Keisler, H. J.; Walkoe, W., The diversity of quantifier prefixes, J. Symbolic Logic, 38, 1, 79-85 (1973) · Zbl 0259.02007
[19] Lind, J. C., Computing in Logarithmic Space, (Tech. Memo. 52 (1974), M.I.T: M.I.T Cambridge, Mass), Project MAC
[20] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill N.Y · Zbl 0183.01401
[21] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[22] van Emden, M. H., Computation and deductive information retrieval, (Neuhold, E., Formal Description of Programming Concepts (1978), North-Holland: North-Holland Amsterdam), 421-439 · Zbl 0384.68080
[23] Vardi, M., The complexity of relational query languages, (Proceedings, 14th ACM Symp. on Theory of Computing. Proceedings, 14th ACM Symp. on Theory of Computing, San Francisco (May 1982)), 137-146
[24] Zloof, M., Query by example, RC4917 (July 1974), IBM Research: IBM Research Yorktown Heights
[25] Zloof, M., Query by example, Operations on the transitive closure (Oct. 1976), IBM Research: IBM Research Yorktown Heights, RC5526
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.