Towards a theory of spatial database queries (extended abstract)

ABSTRACT

A general model for spatial databases is considered, which extends the relational model by allowing as tuple components not only atomic values but also geometrical figures. The model, which is inspired by the work of Kanellakis, Kuper and Revesz on constraint query languages, includes a calculus and an algebra which are equivalent. Given this framework, the concept of spatial database query is investigated. Thereto, Chandra and Harel's well-known consistency criterion for classical relational queries is adapted. Various adaptations are proposed, depending on the kinds of geometry in which the spatial information in the database is to be interpreted. The consistency problem for calculus queries is studied. Expressiveness issues are examined. The main purpose of the paper is to open up new grounds for theoretical research in the area of spatial database systems. Consequently, many open problems are indicated.

REFERENCES

• AO93: Proceedings of the Third International Symposium on Advances in Spatial Databases, June 1993
• Arn88: Dennis S. Arnon, Geometric reasoning with logic and algebra, Artificial Intelligence, v.37 n.1-3, p.37-60, Dec. 1988 [doi>10.1016/0004-3702(88)90049-5]
• ASU79: A.V. Aho, Y. Sagiv, and J.D. Ullman. Equivalences among relational expressions. SIAM Journal on Computing, 8(2):218-246, 1979.
• 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]
• BCR87: J. Bochnak, M. Coste, and M.-F. Roy. Ggomgtrie alggbrique rgelle. Springer- Verlag, 1987.
• Buc89: Proceedings of the first symposium on Design and implementation of large spatial databases, February 1990
• CH80: A. Chandra and D. Harel. Computable queries for relational database systems. Journal of Computer and System Sciences, 21(2):156-178, 1980.
• Col75: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• EF91: M.J. Egenhofer and R.D. Franzosa. Point-set topological spatial relations. Int. J. Geographical Information Systems, 5(2):161-174, 1991.
• Eng93: E. Engeler. Foundations of Mathematics. Springer-Verl#g, 1993.
• GS: Stéphane Grumbach , Jianwen Su, Finitely representable databases (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182654]
• GS91: Proceedings of the 2nd symposium on Advances in spatial databases, June 1991
• HRR91: J. Heintz, T. Recio, and M.-F. Roy. Algorithms in re#l algebraic geometry and applications to computational geometry. In W. Steiger J. Goodman, R. Pollack, editor, Discrete and computational geometry, volume 6 of DIMA CS Series in Discrete Mathematics and Theoretical Computer Science. AMS-ACM, 1991.
• HY84: Richard Hull , Chee K. Yap, The Format Model: A Theory of database Organization, Journal of the ACM (JACM), v.31 n.3, p.518-544, July 1984 [doi>10.1145/828.832]
• KKR90: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• Ren92: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
• Sch79: W. Schwabh~user. Addendum. Fund. Math., 103:101, 1979.
• T+93: Abdullah Uz Tansel , James Clifford , Shashi Gadia , Sushil Jajodia , Arie Segev , Richard Snodgrass, Temporal databases: theory, design, and implementation, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• Tar51: A. Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.
• Tar86: A. Tarski. Wh# #re logicM no#ions? History and Philosophy of Logic, 7:143- 154, 1986. Edited by J. Corcoran.

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.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