Finitely representable databases (extended abstract)

ABSTRACT

We study classes of infinite but finitely representable databases based on constraints, motivated by new database applications such as geographical databases. The mathematical framework is based on classical decidable first-order theories. We investigate the theory of finitely representable models and prove that it differs strongly from both classical model theory and finite model theory. In particular, we show that most of the well known theorems of either one fail (compactness, completeness, locality, 0/1 laws, etc.). An immediate consequence is the lack of tools to consider the definability of queries in the relational calculus over finitely representable databases. We illustrate this very challenging problem through some classical examples.

REFERENCES

• Ajt83: M. Ajtai. # formulae on finite structures. Ann. of Pure and Applied Logic, 24:1-48, 1983.
• AHV92: S. Abiteboul, R. Hull, and V. Vianu. Database Theory. Draft, 1992.
• AU79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• CH80: A. Chandra and D. Harel. Computable Queries for Relational Data Bases. Journal of Computer and System Sciences, 21(2):156-178, Oct. 1980.
• CK73: C.C. Chang and H.J. Keisler. Model Theory, volume 73 of Studies in Logic. North-Holland, 1973.
• Cod70: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• Com88: K. Compton. 0-1 laws in logic and combinatorics. In I. Rival, editor, Proc. NATO Advanced Study institute on Algorithms and Order, pages 353-383. Reidel, Dordrecht, 1988.
• Ehr61: A. Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math, 49, 1961.
• Fag76: R. Fagin. Probabilities on finite models. Journal of Symbolic Logic, 41(1):50-58, 1976.
• Fag93: Ronald Fagin, Finite-model theory—a personal perspective, Theoretical Computer Science, v.116 n.1, p.3-31, Aug. 2, 1993
• FSS84: M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory, 17:13-27, 1984.
• Fra54: R. Fraisse#. Sur les classifications des syst#mes de relations. Publ. Sci. Univ Alger, I:l, 1954.
• Gai81: H. Gaifman. On local and non local properties. In J. Stern, editor, Proc. Herbrand Symposium Logic Colloquium, pages 105- 135. North Holland, 1981.
• HH93: Tirza Hirst , David Harel, Completeness results for recursive data bases, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.244-252, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153905]
• Hul86: Richard Hull, Relative information capacity of simple relational database schemata, SIAM Journal on Computing, v.15 n.3, p.856-886, August 1986 [doi>10.1137/0215061]
• Imm87: Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
• KG94: Paris C. Kanellakis , Dina Q. Goldin, Constraint Programming and Database Query Languages, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.96-120, April 19-22, 1994
• KKR90: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• KRVV93: Paris C. Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey S. Vitter, Indexing for data models with constraints and classes (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.233-243, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153884]
• Kup90: Gabriel M. Kuper, On the expressive power of the relational calculus with arithmetic constraints (extended abstract), Proceedings of the third international conference on database theory on Database theory, p.202-211, November 1990, Paris, France
• Kup93: G.M. Kuper. Aggregation in constraint databases. In Proc. First Workshop on Principles and Practice of Constraint Programming, 1993.
• Kup93a: G.M. Kuper. Personal communications, 1993.
• Rev90: Peter Z. Revesz, A closed form for Datalog queries with integer order (preliminary version), Proceedings of the third international conference on database theory on Database theory, p.187-201, November 1990, Paris, France
• Tar51: A. Tarski. A Decision method for elementary algebra and geometry. Univ. of California Press, Berkeley, California, 1951.
• Tra50: B.A. Trakhtenbrot. Impossibility of an algorithm for the decision problem in finite classes. Doklady Akademii Nauk SSSR, 70:569-572, 1950.
• Vau60: R.L. Vaught. Sentences true in all constructive models. Journal of Symbolic Logic, 25(1):39-53, March 1960.
• vdD82: L. van den Dries. Remarks on Tarski's problem concerning (R, +, ~, exp). In Logic Colloquium. Elsevier, North-Holland, 1982.
• Via93: V. Vianu. Personal communications, 1993.
• Yao90: F. Frances Yao, Computational geometry, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  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:
Languages, Theory, Verification