{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T06:40:04Z","timestamp":1721544004642},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T00:00:00Z","timestamp":1561939200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T00:00:00Z","timestamp":1561939200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J. Comput. Sci. Technol."],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s11390-019-1943-7","type":"journal-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T20:02:35Z","timestamp":1563566555000},"page":"795-817","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Expressive Power of Logics on Constraint Databases with Complex Objects"],"prefix":"10.1007","volume":"34","author":[{"given":"Hong-Cheu","family":"Liu","sequence":"first","affiliation":[]},{"given":"Jixue","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,19]]},"reference":[{"key":"1943_CR1","doi-asserted-by":"crossref","unstructured":"Revesz P. Big data and spatial constraint databases. In Encyclopedia of GIS, Shekhar S, Xiong H, Zhou X (eds.), Springer, 2017, pp.118-122.","DOI":"10.1007\/978-3-319-17885-1_1602"},{"issue":"1","key":"1943_CR2","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1006\/jcss.1995.1051","volume":"51","author":"P Kanellakis","year":"1995","unstructured":"Kanellakis P, Kuper G, Revesz P. Constraint query languages. Journal of Computer and System Sciences, 1995, 51(1): 26-52.","journal-title":"Journal of Computer and System Sciences"},{"key":"1943_CR3","doi-asserted-by":"crossref","unstructured":"Libkin L. Embedded finite models and constraint databases. In Finite Model Theory and Its Applications, Gr\u00e4del E, Kolaitis P G, Libkin L, Marx M, Spencer J, Vardi M Y (eds.), Springer, 2007, pp.257-337.","DOI":"10.1007\/3-540-68804-8_5"},{"issue":"4","key":"1943_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/337885.337894","volume":"30","author":"L Libkin","year":"1999","unstructured":"Libkin L. Query languages with arithmetic and constraint databases. SIGACT News, 1999, 30(4): 41-50.","journal-title":"SIGACT News"},{"issue":"6","key":"1943_CR5","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/BF01213204","volume":"31","author":"R Hull","year":"1994","unstructured":"Hull R, Su J. Domain independence and the relational calculus. Acta Informatica, 1994, 31(6): 513-524.","journal-title":"Acta Informatica"},{"key":"1943_CR6","unstructured":"Moschovakisl Y. Elementary Induction on Abstract Structures. North-Holland, 1974."},{"issue":"1","key":"1943_CR7","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A Chandra","year":"1982","unstructured":"Chandra A, Harel D. Structure and complexity of relational queries. Journal of Computer and System Sciences, 1982, 25(1): 99-128.","journal-title":"Journal of Computer and System Sciences"},{"key":"1943_CR8","doi-asserted-by":"crossref","unstructured":"Kuper G, Libkin L, Paredaens J. Constraint Databases. Springer, 2000.","DOI":"10.1007\/978-3-662-04031-7"},{"issue":"1","key":"1943_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/273865.273870","volume":"45","author":"M Benedikt","year":"1998","unstructured":"Benedikt M, Dong G, Libkin L, Wong L. Relational expressive power of constraint query languages. Journal of the ACM, 1998, 45(1): 1-34.","journal-title":"Journal of the ACM"},{"issue":"4","key":"1943_CR10","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1145\/320211.320240","volume":"46","author":"S Basu","year":"1999","unstructured":"Basu S. New results on quantifier elimination over real closed fields and application to constraint databases. Journal of the ACM, 1999, 46(4): 537-555.","journal-title":"Journal of the ACM"},{"key":"1943_CR11","doi-asserted-by":"crossref","unstructured":"Tarski A. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.","DOI":"10.1525\/9780520348097"},{"key":"1943_CR12","doi-asserted-by":"crossref","unstructured":"van den Dries L. O-minimal structures. In Logic: From Foundations to Applications: European Logic Colloquium, Hodges W, Hyland M, Steinhorn C, Truss J (eds.), Oxford Science Publications, 1996, pp.99-108.","DOI":"10.1093\/oso\/9780198538622.003.0007"},{"key":"1943_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-72905-8","volume-title":"Mathematics of Ramsey Theory","author":"J Ne\u0161et\u0159il","year":"1990","unstructured":"Ne\u0161et\u0159il J, R\u00f6dl V. Mathematics of Ramsey Theory. Springer-Verlag Berlin Heidelberg, 1990."},{"key":"1943_CR14","unstructured":"Graham R L, Rothschild B L, Spencer J H. Ramsey Theory (2nd edition). Wiley-Interscience, 1990."},{"issue":"4","key":"1943_CR15","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1145\/347476.347477","volume":"47","author":"M Benedikt","year":"2000","unstructured":"Benedikt M, Libkin L. Relational queries over interpreted structures. Journal of the ACM, 2000, 47(4): 644-680.","journal-title":"Journal of the ACM"},{"issue":"4","key":"1943_CR16","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/BF01354881","volume":"4","author":"S Abiteboul","year":"1995","unstructured":"Abiteboul S, Beeri C. The power of languages for the manipulation of complex values. The Very Large Data Bases Journal, 1995, 4(4): 727-794.","journal-title":"The Very Large Data Bases Journal"},{"issue":"1","key":"1943_CR17","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1006\/inco.1997.2675","volume":"140","author":"E Gr\u00e4del","year":"1998","unstructured":"Gr\u00e4del E, Gurevich Y. Metafinite model theory. Information and Computation, 1998, 140(1): 26-81.","journal-title":"Information and Computation"},{"key":"1943_CR18","unstructured":"Rose E, Segev A. TOODM \u2014 A temporal object-oriented data model with temporal constraints. In Proc. the 10th International Conference on the Entity Relationship Approach, October 1991, pp.205-229."},{"issue":"1","key":"1943_CR19","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/288086.288088","volume":"23","author":"P Revesz","year":"1998","unstructured":"Revesz P. Safe query languages for constraint databases. Transactions on Database Systems, 1998, 23(1): 58-99.","journal-title":"Transactions on Database Systems"},{"key":"1943_CR20","unstructured":"Abiteboul S, Hull R, Vianu V. Foundations of Databases. Addison-Wesley, 1995."},{"issue":"5","key":"1943_CR21","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(02)00508-2","volume":"86","author":"L Libkin","year":"2003","unstructured":"Libkin L. A collapse result for constraint queries over structures of small degree. Information Processing Letter, 2003, 86(5): 277-281.","journal-title":"Information Processing Letter"},{"issue":"1\/2","key":"1943_CR22","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF00143878","volume":"1","author":"D Goldin","year":"1996","unstructured":"Goldin D, Kanellakis P C. Constraint query algebras. Constraints, 1996, 1(1\/2): 45-83.","journal-title":"Constraints"},{"key":"1943_CR23","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del E, Kreutzer S. Descriptive complexity theory for constraint databases. In Proc. the 13th International Workshop on Computer Science Logic, September 1999, pp.67-81.","DOI":"10.1007\/3-540-48168-0_6"},{"key":"1943_CR24","doi-asserted-by":"crossref","unstructured":"Kuijpers B, Paredaens J, van den Bussche J. Lossless representation of topological spatial data. In Proc. the 4th Symposium on Spatial Databases, August 1995, pp.1-13.","DOI":"10.1007\/3-540-60159-7_1"},{"key":"1943_CR25","doi-asserted-by":"crossref","unstructured":"Segoufin L, Vianu V. Querying spatial databases via topological invariants. In Proc. the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1998, pp.89-98.","DOI":"10.1145\/275487.275498"},{"key":"1943_CR26","doi-asserted-by":"crossref","unstructured":"Wong L. A dichotomy in the intensional expressive power of nested relational calculi augmented with aggregate functions and a powerset operator. In Proc. the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, June 2013, pp.285-295.","DOI":"10.1145\/2463664.2463670"},{"issue":"1","key":"1943_CR27","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0020-0190(96)00140-8","volume":"60","author":"M Otto","year":"1996","unstructured":"Otto M, van den Bussche J. First-order queries on databases embedded in an infinite structure. Information Processing Letters, 1996, 60(1): 37-41.","journal-title":"Information Processing Letters"},{"issue":"2","key":"1943_CR28","first-page":"308","volume":"286","author":"AK Aylamazyan","year":"1986","unstructured":"Aylamazyan A K, Gilula M M, Stolboushkin A P, Schwartz G F. Reduction of the relational model with infinite domains to the case of finite domains. Doklady Akademii Nauk SSSR, 1986, 286(2): 308-311. (in Russian)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"1","key":"1943_CR29","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0022-0000(02)00034-X","volume":"66","author":"M Benedikt","year":"2003","unstructured":"Benedikt M, Grohe M, Libkin L, Segoufin L. Reachability and connectivity queries in constraint databases. Journal of Computer and System Sciences, 2003, 66(1): 169-206.","journal-title":"Journal of Computer and System Sciences"},{"key":"1943_CR30","doi-asserted-by":"crossref","unstructured":"Arora S, Barak B. Computational Complexity: A Modern Approach (1st edition). Cambridge University Press, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"1943_CR31","doi-asserted-by":"crossref","unstructured":"Kanellakis P C, Goldin D Q. Constraint programming and database query languages. In Proc. the 1994 International Conference on Theoretical Aspects of Computer Software, April 1994, pp.96-120.","DOI":"10.1007\/3-540-57887-0_92"},{"key":"1943_CR32","doi-asserted-by":"crossref","unstructured":"Karp R, Ramachandran V. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science: Volume A: Algorithm and Complexity, van Leeuween J (ed.), 1990, pp.869-941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"1943_CR33","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.artint.2012.10.001","volume":"195","author":"P Jonsson","year":"2013","unstructured":"Jonsson P, L\u00f6\u00f6w T. Computational complexity of linear constraints over the integers. Artificial Intelligence, 2013, 195: 44-62.","journal-title":"Artificial Intelligence"},{"issue":"5","key":"1943_CR34","doi-asserted-by":"publisher","first-page":"1652","DOI":"10.1137\/S0097539798342484","volume":"29","author":"M Benedikt","year":"2000","unstructured":"Benedikt M, Libkin L. Safe constraint queries. SIAM Journal on Computing, 2000, 29(5): 1652-1682.","journal-title":"SIAM Journal on Computing"},{"key":"1943_CR35","doi-asserted-by":"crossref","unstructured":"Escobar-Molano M, Hull R, Jacobs D. Safety and translation of calculus queries with scalar functions. In Proc. the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 1993, pp.253-264.","DOI":"10.1145\/153850.153909"},{"key":"1943_CR36","unstructured":"Avron A, Lev S, Levi N. Safety, absoluteness, and computability. In Proc. the 27th EACSL Annual Conference on Computer Science Logic, September 2018, Article No. 8."},{"issue":"12","key":"1943_CR37","doi-asserted-by":"publisher","first-page":"2507","DOI":"10.1016\/j.ins.2008.02.005","volume":"178","author":"HC Liu","year":"2008","unstructured":"Liu H C, Yu J X, Liang W F. Safety, domain independence and translation of complex value database queries. Inf. Sci., 2008, 178(12): 2507-2533.","journal-title":"Inf. Sci."},{"key":"1943_CR38","doi-asserted-by":"crossref","unstructured":"Stolboushkin A, Taitslin M. Finite queries do not have effective syntax. In Proc. the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 1995, pp.277-285.","DOI":"10.1145\/212433.212477"},{"issue":"2","key":"1943_CR39","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1090\/S0002-9947-1988-0943306-9","volume":"309","author":"A Pillary","year":"1988","unstructured":"Pillary A, Steinhorn C. Definable sets in ordered structures. III. Transactions of the American Mathematical Society, 1988, 309(2): 469-476.","journal-title":"Transactions of the American Mathematical Society"},{"key":"1943_CR40","doi-asserted-by":"crossref","unstructured":"Ebbinghaus H D, Flum J. Finite Model Theory (2nd edition). Springer-Verlag Berlin Heidelberg, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"1943_CR41","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman N. Descriptive Complexity. Springer-Verlag New York, 1999."},{"key":"1943_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L Libkin","year":"2004","unstructured":"Libkin L. Elements of Finite Model Theory. Springer-Verlag Berlin Heidelberg, 2004."},{"issue":"6","key":"1943_CR43","doi-asserted-by":"publisher","first-page":"1747","DOI":"10.1137\/S009753979629766","volume":"27","author":"J Paredaens","year":"1998","unstructured":"Paredaens J, van den Bussche J, van Gucht D. First-order queries on finite structures over the reals. SIAM Journal on Computing, 1998, 27(6): 1747-1763.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"1943_CR44","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1090\/S0273-0979-1984-15249-2","volume":"11","author":"A Pillay","year":"1984","unstructured":"Pillay A, Steinhorn C. Definable sets in ordered structures. Bulletin of the American Mathematical Society, 1984, 11(1): 159-162.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"1943_CR45","doi-asserted-by":"crossref","unstructured":"van den Dries L. Tame Aopology and O-Minimality Structures. Cambridge University Press, 1998.","DOI":"10.1017\/CBO9780511525919"},{"issue":"4","key":"1943_CR46","doi-asserted-by":"publisher","first-page":"1530","DOI":"10.2307\/2695063","volume":"65","author":"B Kuijpers","year":"2000","unstructured":"Kuijpers B, Paredaens J, van den Bussche J. Topological elementary equivalence of closed semi-algebraic sets in the real plane. Journal of Symbolic Logic, 2000, 65(4): 1530-1555.","journal-title":"Journal of Symbolic Logic"},{"key":"1943_CR47","doi-asserted-by":"crossref","unstructured":"Kuijpers B, van den Bussche J. On capturing first-order topological properties of planar spatial databases. In Proc. the 7th International Conference on Database Theory, January 1999, pp.187-198.","DOI":"10.1007\/3-540-49257-7_13"},{"key":"1943_CR48","doi-asserted-by":"crossref","unstructured":"Papadimitriou C, Suciu D, Vianu V. Topological queries in spatial databases. Journal of Computer and System Sciences, 1999, 58(1): 29-53.","DOI":"10.1006\/jcss.1998.1597"},{"issue":"2","key":"1943_CR49","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1006\/jcss.2000.1712","volume":"61","author":"L Segoufin","year":"2000","unstructured":"Segoufin L, Vianu V. Querying spatial databases via topological invariants. Journal of Computer and System Sciences, 2000, 61(2): 270-301.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\/2","key":"1943_CR50","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/S0304-3975(99)00316-3","volume":"254","author":"L Vandeurzen","year":"2001","unstructured":"Vandeurzen L, Gyssens M, van Gucht D. On the expressiveness of linear-constraint query languages for spatial databases. Theoretical Computer Sciences, 2001, 254(1\/2): 423-463.","journal-title":"Theoretical Computer Sciences"}],"container-title":["Journal of Computer Science and Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11390-019-1943-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11390-019-1943-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11390-019-1943-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T06:19:21Z","timestamp":1721542761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11390-019-1943-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["1943"],"URL":"https:\/\/doi.org\/10.1007\/s11390-019-1943-7","relation":{},"ISSN":["1000-9000","1860-4749"],"issn-type":[{"value":"1000-9000","type":"print"},{"value":"1860-4749","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7]]},"assertion":[{"value":"1 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}