Completeness results for recursive data bases

ABSTRACT

We consider infinite recursive (i.e., computable) relational data bases. Since the set of computable queries on such data bases is not closed under even simple relational operations, one must either make do with a very humble class of queries or considerably restrict the class of allowed data bases. We define two query languages, one for each of these possibilities, and prove their completeness. The first is the language of quantifier-free first-order logic, which is shown to be complete for the non-restricted case. The second is an appropriately modified version of Chandra and Harel's complete language QL, which is proved complete for the case of “highly symmetric” data bases, i.e., ones whose set of automorphisms is of finite index for each tuple-width. We also address the related notion of BP-completeness.

REFERENCES

• AV: Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
• B: F. Bancilhon, "On the completeness of query languages for relational data bases", in Proceeding, 7th Symp. on Mathematical Foundation of Computer Science, Zakopane, Poland, Lecture Notes in Computer Science, Springer- Verlag, Berlin/New York/Heidelberg, 1978.
• Be1: D.R. Bean, "Effective Coloration", J. Sym. Logic 41 (1976), 469-480.
• Be2: D.R. Bean, "Recursive Euler and I-Iamiltonian Paths", Proc. Amer. Math. Soc. 55 (1976), 385-394.
• BG: R. Beigel and W. I. Gasarch, "On the Complexity of Finding the Chromatic Number of a Recursive Graph", Parts I & II, Ann. Pure and Appl. Logic 45 (1989), 1-38, 227-247.
• CH: A.K. Candra and D. Harel, "Computable Queries for Relational Data Bases", J. Comp. Syst. Sci. 21, (1980), 156-178.
• CK: C.C. Chang and H. J. Keisler, Model Theory (3rd edn.), North-Holland, AMsterdam, 1990.
• H: David Harel, Hamiltonian paths in infinite graphs, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.220-229, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103445]
• HH: T. Hirst and D. Harel, "Taking it to the Limit: On Infinite Variants of NP-Complete Problems", Proc. 8t# IEEE Conf. on Structure in Complexity Theory, IEEE Press, New York, 1993.
• NR: A. N erode and J. Remmel, "A Survey of Lattices of R. E. Substructures", In Recursion Theory, Proc. Symp. in Pure Math. Vol. 42 (A. Nerode and R. A. Shore, eds.), Amer. Math. Soc., Providence, R. I., 1985, pp. 323- 375.
• P: J. Paredaens, "On the Expressive Power of the Relational Algebra", inf. Proc. Let. 7 (1978), 107-111.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Theory, Verification