Abstract
In 1980, Chandra and Harel investigated, in the context of the relational database model, which queries are “reasonable”. They characterized this class of queries by means of the concept of genericity, which has since taken a central position in the theory of computable queries. A query in the relational model is called computable if and only if it is a Turing-computable function on some representation of the database that is also generic. By a generic function Q, we mean here a function whose result is invariant under any permutation π of the universal domain of the database. Informally, this means that the value of a generic query is independent of the internal representation of the data and only depends on the logical structure of the database. Formally, on the other hand, this means that if A and B are two relational databases such that B = π(A), for some isomorphism π, then Q(B) π(Q(A)).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Bibliographical Notes
A. K. Chandra and D. Harel. Computable queries for relational data bases. Journal of Computer and System Sciences (JCSS), 21 (2): 156–178, 1980.
T. Hirst and D. Harel. Completeness results for recursive data bases. In Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’93), pages 244–252. ACM Press, 1993.
J. Paredaens, J. Van den Bussche, and D. Van Gucht. Towards a theory of spatial database queries. In Proceedings of the 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’94)pages 279–288. ACM Press, 1994.
B. Kuijpers, J. Paredaens, and D. Suciu. Unpublished results. Antwerp, 1995.
M. Gyssens, J. Van den Bussche, and D. Van Gucht. Complete geometrical query languages. In Proceedings of the 16th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems (PODS’97), pages 62–67. ACM Press, 1997.
B. Kuijpers, J. Paredaens, and D. Suciu. Unpublished results. Antwerp, 1995.
C. H. Papadimitriou, D. Suciu, and V. Vianu. Topological queries in spatial databases. In Proceedings of the 15th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems (PODS’96)pages 81–92. ACM Press, 1996.
B. Kuijpers, J. Paredaens, M. Smits, and J. Van den Bussche. Termination properties of spatial Datalog programs. In International Workshop on Logic in Databases (LID’96), volume 1154 of Lecture Notes in Computer Science, pages 101–116. Springer-Verlag, 1996.
B. Kuijpers and M. Smits. On expressing topological connectivity in spatial Datalog. In Proceedings of the 2nd Workshop on Constraint Databases and Applications (CDB’97), volume 1191 of Lecture Notes in Computer Science, pages 116–133. Springer-Verlag, 1997.
B. Kuijpers, J. Paredaens, and J. Van den Bussche. Lossless representation of topological spatial data. In 4th Symposium on Large Spatial Databases (SSD’95), volume 951 of Lecture Notes in Computer Science, pages 1–13. Springer-Verlag, 1995.
L. Arge, V. Samoladas, and J. S. Vitter. On two-dimensional indexability and optimal range search indexing. In Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’99), pages 346–357. ACM Press, 1999.
A. V. Aho and J. D. Ullman. The universality of data retrieval languages. In Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages (POPL’79), pages 110–120. ACM Press, 1979.
L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Scalable sweeping-based spatial join. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB’98), pages 570–581. Morgan Kaufmann, 1998.
L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA’98), pages 685–694. ACM Press, 1998.
M. Ashworth. Information Technology - Database Languages–SQL Multimedia and Application Packages - Part 3: Spatial, ISO/IEC 13249–3, 1999.
B. Kuijpers, J. Paredaens, and J. Van den Bussche. On topological elementary equivalence of spatial databases. In 6th International Conference on Database Theory (ICDT’97), volume 1186 of Lecture Notes in Computer Science, pages 432–446. Springer-Verlag, 1997.
B. Kuijpers. Topological Properties of Spatial Databases in the Polynomial Constraint Model. PhD thesis, University of Antwerp (UTA ), 1998.
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kuijpers, B., Van Gucht, D. (2000). Genericity in Spatial Databases. In: Kuper, G., Libkin, L., Paredaens, J. (eds) Constraint Databases. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-04031-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-662-04031-7_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-08542-0
Online ISBN: 978-3-662-04031-7
eBook Packages: Springer Book Archive