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 111 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 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) [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. 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.