×

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
PDF BibTeX XML Cite
Full Text: DOI Link

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, (), 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, () · Zbl 0296.68041
[5] Chandra, A.K., Programming primitives for database languages, (), 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, (), 333-347
[8] Chandra, A.K.; Harel, D., Horn clauses and the fixpoint query hierarchy, ()
[9] Chandra, A.K.; Merlin, P.M., Optimal implementation of conjunctive queries in relational data bases, ()
[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, (), 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] {\scH. Gaifman}. Private Communication.
[15] ()
[16] Immerman, N., Relational queries computable in polynomial time, () · Zbl 0612.68086
[17] Kowalski, R.A., Predicate logic as a programming language, (), 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, (), Project MAC
[20] Rogers, H., Theory of recursive functions and effective computability, (1967), 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, (), 421-439 · Zbl 0384.68080
[23] Vardi, M., The complexity of relational query languages, (), 137-146
[24] Zloof, M., Query by example, RC4917, (July 1974), IBM Research Yorktown Heights
[25] Zloof, M., Query by example, operations on the transitive closure, (Oct. 1976), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.