{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:32:47Z","timestamp":1761611567540},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540009573"},{"type":"electronic","value":"9783540365969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36596-6_11","type":"book-chapter","created":{"date-parts":[[2007,10,24]],"date-time":"2007-10-24T21:23:52Z","timestamp":1193261032000},"page":"200-228","source":"Crossref","is-referenced-by-count":0,"title":["Semantic Classifications of Queries to Relational Databases"],"prefix":"10.1007","author":[{"given":"Jos\u00e9 Mar\u00eda Turull","family":"Torres","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,4,1]]},"reference":[{"key":"11_CR1","unstructured":"Abiteboul, S., Hull, R. and Vianu, V.: Foundations of Databases. Addison-Wesley (1994)"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/inco.1998.2701","volume":"143","author":"S. Abiteboul","year":"1998","unstructured":"Abiteboul, S., Papadimitriou, C. and Vianu, V.: Reflective Relational Machines. Information and Computation 143 (1998) 110\u2013136","journal-title":"Information and Computation"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1006\/jcss.1995.1025","volume":"50","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S. and Vianu, V.: Computing with first-order logic. Journal of Computer and System Sciences 50(2) (1995) 309\u2013335","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"11_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0304-3975(95)00027-T","volume":"149","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Vardi, M. and Vianu, V.: Computing with Infinitary Logic. Theoretical Computer Science 149(1) (1995) 101\u2013128","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/256292.256295","volume":"44","author":"S. Abiteboul","year":"1997","unstructured":"Abiteboul, S., Vardi, M. and Vianu, V.: Fixpoint Logics, Relational Machines, and Computational Complexity. Journal of ACM 44(1) (1997) 30\u201356","journal-title":"Journal of ACM"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"292","DOI":"10.2307\/2272133","volume":"42","author":"J. Barwise","year":"1977","unstructured":"Barwise, J.: On Moschovakis Closure Ordinals. Journal of Symbolic Logic 42 (1977) 292\u2013296","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar, J., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I, 2nd ed. Springer (1995)","DOI":"10.1007\/978-3-642-79235-9"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1137\/0209047","volume":"9","author":"L. Babai","year":"1980","unstructured":"Babai, L., Erd\u00f6s, P. and Selkow, S.: Random Graph Isomorphism. SIAM Journal on Computing 9 (1980) 628\u2013635","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"11_CR9","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Y. Cai","year":"1992","unstructured":"Cai, J. Y., F\u00fcrer, M. and Immerman, N.: An Optimal Lower Bound on the Number of Variables for Graph Identification. Combinatorica 12(4) (1992) 389\u2013410","journal-title":"Combinatorica"},{"issue":"2","key":"11_CR10","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. K. Chandra","year":"1980","unstructured":"Chandra, A. K. and Harel, D.: Computable Queries for Relational Data Bases. Journal of Computer and System Sciences 21(2) (1980) 156\u2013178","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR11","unstructured":"Chang, C. and Keisler, H.: Model Theory, 3rd ed. Elsevier North Holland (1992)"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/S0019-9958(86)80006-7","volume":"70","author":"L. Denenberg","year":"1986","unstructured":"Denenberg, L., Gurevich, Y., Shelah, S.: Definability by Constant Depth Polinomial Size Circuits. Information and Control 70 (1986) 216\u2013240","journal-title":"Information and Control"},{"key":"11_CR13","unstructured":"Ebbinghaus, H. and Flum, J.: Finite Model Theory, 2nd ed. Springer (1999)"},{"key":"11_CR14","unstructured":"Ebbinghaus, H., Flum, J., Thomas, W.: Mathematical Logic. Springer (1984)"},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"Ehrenfeucht, A.: An Application of Games to the Completeness Problem for Formalized Theories. Fundamenta Mathematicae 49 (1961) 129\u2013141","journal-title":"Fundamenta Mathematicae"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/2272945","volume":"41","author":"R. Fagin","year":"1976","unstructured":"Fagin, R.: Probabilities on Finite Models. Journal of Symbolic Logic 41 (1976) 50\u201358","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR17","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"Fra\u00efss\u00e9, R.: Sur Quelques Classifications des Syst\u00e8mes de Relations (english summary). Universit\u00e9 d\u2019Alger, Publications Scientifiques, S\u00e9rie A 1 (1954) 35\u2013182","journal-title":"Sur Quelques Classifications des Syst\u00e8mes de Relations (english summary)"},{"key":"11_CR18","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/BF01071084","volume":"5","author":"Y. V. Glebskij","year":"1969","unstructured":"Glebskij, Y. V., Kogan, D. I., Liogon'kij, M. I., Talanov, V. A.: Range and Degree of Realizability of Formulas in the Restricted Predicate Calculus. Cybernetics 5 (1969) 142\u2013154","journal-title":"Cybernetics"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Equivalence in Finite Variable Logics is Complete for Polynomial Time. Proc. of 37th IEEE Symposium on Foundations of Computer Science (1996) 264\u2013273","DOI":"10.1109\/SFCS.1996.548485"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Finite Variable Logics in Descriptive Complexity Theory. Preliminary version (1998)","DOI":"10.2307\/420954"},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed Point Logics on Planar Graphs. Proc. of 13th IEEE Symposium on Logic in Computer Science (1998) 6\u201315","DOI":"10.1109\/LICS.1998.705639"},{"issue":"1","key":"11_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0070","volume":"129","author":"L. Hella","year":"1996","unstructured":"Hella, L.: Logical Hierarchies in PTIME. Information and Computation 129(1) (1996) 1\u201319","journal-title":"Information and Computation"},{"issue":"4","key":"11_CR23","doi-asserted-by":"publisher","first-page":"422","DOI":"10.2307\/421173","volume":"2","author":"L. Hella","year":"1996","unstructured":"Hella, L., Kolaitis, P. and Luosto, K.: Almost Everywhere Equivalence of Logics in Finite Model Theory. The Bulletin of Symbolic Logic 2(4) (1996) 422\u2013443","journal-title":"The Bulletin of Symbolic Logic"},{"key":"11_CR24","unstructured":"Immerman, N. and Lander, E.: Describing Graphs: A First Order Approach to Graph Canonization. Complexity Theory Retrospective, A. Selman, ed. Springer (1990) 59\u201381"},{"issue":"1","key":"11_CR25","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"Immerman, N.: Upper and Lower Bounds for First Order Expressibility. Journal of Computer and System Sciences 25(1) (1982) 76\u201398","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Descriptive Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"11_CR27","unstructured":"Koponen, A. and Luosto, K.: Definability of Group Theoretic notions. Research Report 227 of the Department of Mathematics of the University of Helsinki (1999)"},{"key":"11_CR28","unstructured":"Koponen, A. and Luosto, K.: personal comunication (2000)"},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., Vardi, M.: On the Expressive Power of Datalog: Tools and a Case Study. Proceedings of the 9th ACM Symposium on Principles of Database Systems (1990) 61\u201371","DOI":"10.1145\/298514.298542"},{"key":"11_CR30","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P. Kolaitis","year":"1992","unstructured":"Kolaitis, P. and Vardi, M.: Infinitary Logic and 0-1 Laws. Information and Computation 98 (1992) 258\u2013294","journal-title":"Information and Computation"},{"key":"11_CR31","unstructured":"Otto, M.: Symmetry and First Order: Explicitly Presentation-Invariant Circuits. Preliminary report (1994)"},{"issue":"1","key":"11_CR32","doi-asserted-by":"publisher","first-page":"147","DOI":"10.2307\/2275602","volume":"61","author":"M. Otto","year":"1996","unstructured":"Otto, M.: The Expressive Power of Fixed Point Logic with Counting. Journal of Symbolic Logic 61, 1 (1996) 147\u2013176","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR33","doi-asserted-by":"crossref","unstructured":"Otto, M.: Bounded Variable Logics and Counting. Springer (1997)","DOI":"10.1007\/978-3-662-21676-7"},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"641","DOI":"10.2307\/2273594","volume":"47","author":"B. Poizat","year":"1982","unstructured":"Poizat, B.: Deux ou trois choses que je sais de Ltnn. Journal of Symbolic Logic 47 (1982) 641\u2013658","journal-title":"Journal of Symbolic Logic"},{"key":"11_CR35","series-title":"Lect Notes Comput Sci","first-page":"480","volume-title":"Preservation Theorems in Finite Model Theory","author":"E. Rosen","year":"1994","unstructured":"Rosen, E., Weinstein, S.: Preservation Theorems in Finite Model Theory. Proceedings of the International Workshop on Logic and Computational Complexity, Springer LNCS 960 (1994) 480\u2013502"},{"key":"11_CR36","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BFb0057715","volume-title":"Untyped Reflective Machines and Conditional Quantifiers","author":"J.M. Turull Torres","year":"1998","unstructured":"Turull Torres, J.M.: Untyped Queries, Untyped Reflective Machines and Conditional Quantifiers. Proceedings of the 2nd East European Symposium on Advances in Database and Information Systems, ADBIS\u201998, Springer, LNCS 1475 (1998) 35\u201345"},{"key":"11_CR37","series-title":"Lect Notes Comput Sci","first-page":"288","volume-title":"Reflective Relational Machines Working on Homogeneous Databases","author":"J. M. Turull Torres","year":"2001","unstructured":"Turull Torres, J.M.: Reflective Relational Machines Working on Homogeneous Databases. Proceedings of the First International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2000, Springer, LNCS 1762 (2000) 288\u2013303"},{"key":"11_CR38","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/S0168-0072(00)00055-5","volume":"108","author":"J.M. Turull Torres","year":"2001","unstructured":"Turull Torres, J.M.: On the Expressibility and the Computability of Untyped Queries. Annals of Pure and Applied Logic 108 (2001) 345\u2013371","journal-title":"Annals of Pure and Applied Logic"},{"key":"11_CR39","unstructured":"Turull Torres, J. M.: A Study of Homogeneity in Relational Databases. To appear in Annals of Mathematics and Artificial Intelligence (2001)"},{"key":"11_CR40","doi-asserted-by":"crossref","unstructured":"Turull Torres, J.M.: Relational Databases and Homogeneity in Logics with Counting. Draft (2001)","DOI":"10.1007\/3-540-45758-5_14"}],"container-title":["Lecture Notes in Computer Science","Semantics in Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36596-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T00:03:02Z","timestamp":1556928182000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36596-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540009573","9783540365969"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-36596-6_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}