Chandra, Ashok; Harel, David Structure and complexity of relational queries. (English) Zbl 0511.68073 J. Comput. Syst. Sci. 25, 99-128 (1982). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 4 ReviewsCited in 105 Documents MSC: 68P20 Information storage and retrieval of data 03C13 Model theory of finite structures 68Q25 Analysis of algorithms and problem complexity 68P05 Data structures Keywords:relational database; queries languages; expressiveness; computational complexity; logical queries; algebraic queries PDF BibTeX XML Cite \textit{A. Chandra} and \textit{D. Harel}, J. Comput. Syst. Sci. 25, 99--128 (1982; Zbl 0511.68073) Full Text: DOI Link OpenURL 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.