{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:44:05Z","timestamp":1787017445047,"version":"build-2736575974"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n                    We address a fundamental question concerning spatio-temporal database systems: \u201cWhat are exactly spatio-temporal queries?\u201d We define spatio-temporal queries to be computable mappings that are also\n                    <jats:italic>generic<\/jats:italic>\n                    , meaning that the result of a query may only depend to a limited extent on the actual internal representation of the spatio-temporal data. Genericity is defined as invariance under groups of geometric transformations that preserve certain characteristics of spatio-temporal data (e.g., collinearity, distance, velocity, acceleration, \u2026). These groups depend on the notions that are relevant in particular spatio-temporal database applications. These transformations also have the distinctive property that they respect the monotone and unidirectional nature of time.\n                  <\/jats:p>\n                  <jats:p>We investigate different genericity classes with respect to the constraint database model for spatio-temporal databases and we identify sound and complete languages for the first-order and the computable queries in these genericity classes. We distinguish between genericity determined by time-invariant transformations, genericity notions concerning physical quantities and genericity determined by time-dependent transformations.<\/jats:p>","DOI":"10.1145\/1342991.1342997","type":"journal-article","created":{"date-parts":[[2008,4,8]],"date-time":"2008-04-08T11:40:00Z","timestamp":1207654800000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["First-order complete and computationally complete query languages for spatio-temporal databases"],"prefix":"10.1145","volume":"9","author":[{"given":"Floris","family":"Geerts","sequence":"first","affiliation":[{"name":"University of Edinburgh, Scotland, UK, Hasselt University, Diepenbeek, Belgium, Transnational University of Limburg"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sofie","family":"Haesevoets","sequence":"additional","affiliation":[{"name":"Hasselt University, Diepenbeek, Belgium, Transnational University of Limburg"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bart","family":"Kuijpers","sequence":"additional","affiliation":[{"name":"Hasselt University, Diepenbeek, Belgium, Transnational University of Limburg"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,4,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Advances in Spatial Databases---3rd Symposium (SSD'93)","volume":"692","author":"Abel D.","unstructured":"Abel , D. and Ooi , B. C. , Eds . 1993 . Advances in Spatial Databases---3rd Symposium (SSD'93) . Lecture Notes in Computer Science , vol. 692 . Springer-Verlag, New York. Abel, D. and Ooi, B. C., Eds. 1993. Advances in Spatial Databases---3rd Symposium (SSD'93). Lecture Notes in Computer Science, vol. 692. Springer-Verlag, New York."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/4.5.531"},{"key":"e_1_2_1_4_1","unstructured":"Bochnak J. Coste M. and Roy M. 1987. G\u00e9om\u00e9trie Alg\u00e9brique R\u00e9elle. Springer-Verlag Berlin Germany.  Bochnak J. Coste M. and Roy M. 1987. G\u00e9om\u00e9trie Alg\u00e9brique R\u00e9elle. Springer-Verlag Berlin Germany."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the International Workshop on Spatio Temporal Database Management (STDBM'99)","volume":"1678","author":"B\u00f6hlen M. H.","unstructured":"B\u00f6hlen , M. H. , Jensen , C. S. , and Scholl , M. , Eds . 1999 . Proceedings of the International Workshop on Spatio Temporal Database Management (STDBM'99) . Lecture Notes in Computer Science , vol. 1678 . Springer-Verlag, New York. B\u00f6hlen, M. H., Jensen, C. S., and Scholl, M., Eds. 1999. Proceedings of the International Workshop on Spatio Temporal Database Management (STDBM'99). Lecture Notes in Computer Science, vol. 1678. Springer-Verlag, New York."},{"key":"e_1_2_1_6_1","volume-title":"Design and Implementation of Large Spatial Databases---1st Symposium (SSD'89)","volume":"409","author":"Buchmann A., Ed.","year":"1989","unstructured":"Buchmann , A., Ed. 1989 . Design and Implementation of Large Spatial Databases---1st Symposium (SSD'89) . Lecture Notes in Computer Science , vol. 409 . Springer-Verlag, New York. Buchmann, A., Ed. 1989. Design and Implementation of Large Spatial Databases---1st Symposium (SSD'89). Lecture Notes in Computer Science, vol. 409. Springer-Verlag, New York."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90032-X"},{"key":"e_1_2_1_8_1","volume-title":"19th International Conference on Conceptual Modeling (ER'00)","volume":"1920","author":"Chen C. X.","unstructured":"Chen , C. X. and Zaniolo , C . 2000. SQLST: A spatio-temporal data model and query language. In Conceptual Modeling , 19th International Conference on Conceptual Modeling (ER'00) , A. H. F. Laender, S. W. Liddle, and V. C. Storey, Eds. Lecture Notes in Computer Science , vol. 1920 . Springer-Verlag, New York, 96--111. Chen, C. X. and Zaniolo, C. 2000. SQLST: A spatio-temporal data model and query language. In Conceptual Modeling, 19th International Conference on Conceptual Modeling (ER'00), A. H. F. Laender, S. W. Liddle, and V. C. Storey, Eds. Lecture Notes in Computer Science, vol. 1920. Springer-Verlag, New York, 96--111."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 5th International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science","volume":"1262","author":"Chomicki J.","unstructured":"Chomicki , J. and Revesz , P . 1997. Constraint-based interoperability of spatio-temporal databases . In Proceedings of the 5th International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science , vol. 1262 . Springer-Verlag, New York, 142--161. Chomicki, J. and Revesz, P. 1997. Constraint-based interoperability of spatio-temporal databases. In Proceedings of the 5th International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science, vol. 1262. Springer-Verlag, New York, 142--161."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 6th International Workshop on Temporal Representation and Reasoning. IEEE Computer Society","author":"Chomicki J.","unstructured":"Chomicki , J. and Revesz , P . 1999. A geometric framework for specifying spatiotemporal objects . In Proceedings of the 6th International Workshop on Temporal Representation and Reasoning. IEEE Computer Society , Press, Los Alamitos, CA, 41--46. Chomicki, J. and Revesz, P. 1999. A geometric framework for specifying spatiotemporal objects. In Proceedings of the 6th International Workshop on Temporal Representation and Reasoning. IEEE Computer Society, Press, Los Alamitos, CA, 41--46."},{"key":"e_1_2_1_11_1","unstructured":"Desloge E. 1982. Classical Mechanics. Wiley New York.  Desloge E. 1982. Classical Mechanics. Wiley New York."},{"key":"e_1_2_1_12_1","volume-title":"Advances in Spatial Databases---4th Symposium (SSD'95)","volume":"951","author":"Egenhofer M. J.","unstructured":"Egenhofer , M. J. and Herring , J. R. , Eds . 1995 . Advances in Spatial Databases---4th Symposium (SSD'95) . Lecture Notes in Computer Science , vol. 951 . Springer-Verlag, New York. Egenhofer, M. J. and Herring, J. R., Eds. 1995. Advances in Spatial Databases---4th Symposium (SSD'95). Lecture Notes in Computer Science, vol. 951. Springer-Verlag, New York."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009805532638"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/333607.333609"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/288692.288712"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00194-6"},{"key":"e_1_2_1_17_1","volume-title":"-J., Eds","author":"Gunther O.","year":"1991","unstructured":"Gunther , O. and Schek , H . -J., Eds . 1991 . Advances in Spatial Databases---2nd Symposium SSD'91. Lecture Notes in Computer Science, vol. 525 . Springer-Verlag , New York. Gunther, O. and Schek, H.-J., Eds. 1991. Advances in Spatial Databases---2nd Symposium SSD'91. Lecture Notes in Computer Science, vol. 525. Springer-Verlag, New York."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48482-5"},{"key":"e_1_2_1_19_1","unstructured":"G\u00fcting R. and Schneider M. 2005. Moving Object Databases. Morgan Kaufmann San Francisco CA.  G\u00fcting R. and Schneider M. 2005. Moving Object Databases. Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/352958.352963"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1630"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298582"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 7th International Workshop on Temporal Representation and Reasoning. IEEE Computer Society","author":"Kuijpers B.","unstructured":"Kuijpers , B. , Paredaens , J. , and Gucht , D. V . 2000. Towards a theory of movie database queries . In Proceedings of the 7th International Workshop on Temporal Representation and Reasoning. IEEE Computer Society , Press, Los Alamitos, CA, 95--102. Kuijpers, B., Paredaens, J., and Gucht, D. V. 2000. Towards a theory of movie database queries. In Proceedings of the 7th International Workshop on Temporal Representation and Reasoning. IEEE Computer Society, Press, Los Alamitos, CA, 95--102."},{"key":"e_1_2_1_25_1","first-page":"175","article-title":"Geographic information systems. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York","volume":"2","author":"Kuper G.","year":"2000","unstructured":"Kuper , G. and Scholl , M. 2000 . Geographic information systems. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York , Chapter 2 , 175 -- 198 . Kuper, G. and Scholl, M. 2000. Geographic information systems. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York, Chapter 2, 175--198.","journal-title":"Chapter"},{"key":"e_1_2_1_26_1","volume-title":"27th International Colloquium (ICALP","volume":"1853","author":"Libkin L.","year":"2000","unstructured":"Libkin , L. 2000 . Variable independence, quantifier elimination, and constraint representation. In Automata, Languages and Programming , 27th International Colloquium (ICALP 2000), U. Montanari, J. D. P. Rolim, and E. Welzl, Eds. Lecture Notes in Computer Science , vol. 1853 . Springer-Verlag, New York, 260--271. Libkin, L. 2000. Variable independence, quantifier elimination, and constraint representation. In Automata, Languages and Programming, 27th International Colloquium (ICALP 2000), U. Montanari, J. D. P. Rolim, and E. Welzl, Eds. Lecture Notes in Computer Science, vol. 1853. Springer-Verlag, New York, 260--271."},{"key":"e_1_2_1_27_1","volume-title":"Hilbert's Tenth Problem","author":"Matijasevich Y. V.","unstructured":"Matijasevich , Y. V. 1993. Hilbert's Tenth Problem . MIT Press , Cambridge, MA . Matijasevich, Y. V. 1993. Hilbert's Tenth Problem. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_28_1","volume-title":"Eds","author":"Paredaens J.","year":"2000","unstructured":"Paredaens , J. , Kuper , G. , and Libkin , L. , Eds . 2000 . Constraint databases. Springer-Verlag , New York. Paredaens, J., Kuper, G., and Libkin, L., Eds. 2000. Constraint databases. Springer-Verlag, New York."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182640"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/288692.288715"},{"key":"e_1_2_1_31_1","volume-title":"Introduction to Constraint Databases","author":"Revesz P.","unstructured":"Revesz , P. 2002. Introduction to Constraint Databases . Springer-Verlag , New York . Revesz, P. 2002. Introduction to Constraint Databases. Springer-Verlag, New York."},{"key":"e_1_2_1_32_1","volume-title":"Spatial Databases: Applications to GIS. Morgan Kaufmann","author":"Rigaux P.","year":"2000","unstructured":"Rigaux , P. , Scholl , M. , and Voisard , A . 2000 . Introduction to Spatial Databases: Applications to GIS. Morgan Kaufmann , Reading, MA . Rigaux, P., Scholl, M., and Voisard, A. 2000. Introduction to Spatial Databases: Applications to GIS. Morgan Kaufmann, Reading, MA."},{"key":"e_1_2_1_33_1","volume-title":"Advances in Spatial Databases---5th Symposium (SSD'97)","volume":"1262","author":"Scholl M.","unstructured":"Scholl , M. and Voisard , A. , Eds . 1997 . Advances in Spatial Databases---5th Symposium (SSD'97) . Lecture Notes in Computer Science , vol. 1262 . Springer-Verlag, New York. Scholl, M. and Voisard, A., Eds. 1997. Advances in Spatial Databases---5th Symposium (SSD'97). Lecture Notes in Computer Science, vol. 1262. Springer-Verlag, New York."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Schwabh\u00e4user W. Szmielew W. and Tarski A. 1983. Metamathematische Methoden in der Geometrie. Springer-Verlag New York.  Schwabh\u00e4user W. Szmielew W. and Tarski A. 1983. Metamathematische Methoden in der Geometrie. Springer-Verlag New York.","DOI":"10.1007\/978-3-642-69418-9"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 13th International Conference on Data Engineering. IEEE Computer Society, Press","author":"Sistla A. P.","unstructured":"Sistla , A. P. , Wolfson , O. , Chamberlain , S. , and Dao , S . 1997. Modeling and querying moving objects . In Proceedings of the 13th International Conference on Data Engineering. IEEE Computer Society, Press , Los, Alamitos, CA, 422--432. Sistla, A. P., Wolfson, O., Chamberlain, S., and Dao, S. 1997. Modeling and querying moving objects. In Proceedings of the 13th International Conference on Data Engineering. IEEE Computer Society, Press, Los, Alamitos, CA, 422--432."},{"key":"e_1_2_1_36_1","volume-title":"Lecture Notes in Computer Science","volume":"2121","author":"Su J.","unstructured":"Su , J. , Xu , H. , and Ibarra , O . 2001. Moving objects: Logical relationships and queries. In Advances in Spatial and Temporal Databases (SSTD'01) . Lecture Notes in Computer Science , vol. 2121 . Springer-Verlag, New York, 3--19. Su, J., Xu, H., and Ibarra, O. 2001. Moving objects: Logical relationships and queries. In Advances in Spatial and Temporal Databases (SSTD'01). Lecture Notes in Computer Science, vol. 2121. Springer-Verlag, New York, 3--19."},{"key":"e_1_2_1_37_1","first-page":"21","article-title":"Constraint Databases, queries and query languages. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York","volume":"2","author":"Van den Bussche J.","year":"2000","unstructured":"Van den Bussche , J. 2000 . Constraint Databases, queries and query languages. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York , Chapter 2 , 21 -- 54 . Van den Bussche, J. 2000. Constraint Databases, queries and query languages. In Constraint Databases, J. Paredaens, G. Kuper, and L. Libkin, Eds. Springer-Verlag, New York, Chapter 2, 21--54.","journal-title":"Chapter"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/646412.692552"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1342991.1342997","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1342991.1342997","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:39:03Z","timestamp":1750239543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1342991.1342997"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1342991.1342997"],"URL":"https:\/\/doi.org\/10.1145\/1342991.1342997","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2006-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}