{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:02Z","timestamp":1750307582430,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["E005039"],"award-info":[{"award-number":["E005039"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We study the problem of deciding the satisfiability of first-order logic queries over views, with our aim to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occupy a central place in database research due to their role in applications such as information integration and data warehousing. Our main result is the identification of a decidable class of first-order queries over unary conjunctive views that generalizes the decidability of the classical class of first-order sentences over unary relations known as the L\u00f6wenheim class. We then demonstrate how various extensions of this class lead to undecidability and also provide some expressivity results. Besides its theoretical interest, our new decidable class is potentially interesting for use in applications such as deciding implication of complex dependencies, analysis of a restricted class of active database rules, and ontology reasoning.<\/jats:p>","DOI":"10.1145\/1656242.1656243","type":"journal-article","created":{"date-parts":[[2010,1,19]],"date-time":"2010-01-19T20:14:58Z","timestamp":1263932098000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Logical queries over views"],"prefix":"10.1145","volume":"11","author":[{"given":"James","family":"Bailey","sequence":"first","affiliation":[{"name":"The University of Melbourne, Australia"}]},{"given":"Guozhu","family":"Dong","sequence":"additional","affiliation":[{"name":"Wright State University"}]},{"given":"Anthony WIDJAJA","family":"To","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]}],"member":"320","published-online":{"date-parts":[[2010,1,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_2_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Longman Publishing Co. Inc.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Longman Publishing Co. Inc."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004275029985"},{"volume-title":"The Description Logic Handbook: Theory, Implementation, and Applications","author":"Baader F.","key":"e_1_2_1_4_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511711787"},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). Springer, 83--99","author":"Bailey J.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275517"},{"volume-title":"Extremal Graph Theory","author":"Bollobas B.","key":"e_1_2_1_7_1","doi-asserted-by":"crossref","DOI":"10.1201\/b16132-57"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Boolos G. S. Burgess J. P. and Jeffrey R. C. 2002. Computability and Logic. Cambridge University Press.   Boolos G. S. Burgess J. P. and Jeffrey R. C. 2002. Computability and Logic. Cambridge University Press.","DOI":"10.1017\/CBO9781139164931"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer-Verlag.  B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Springer-Verlag.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275504"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/78935.78937"},{"volume-title":"Graph Theory","author":"Diestel R.","key":"e_1_2_1_12_1"},{"volume-title":"A Mathematical Introduction To Logic","author":"Enderton H. B.","key":"e_1_2_1_13_1"},{"volume-title":"Procedings of the Logic Colloquium","author":"Gaifman H.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the 2nd International Workshop on Next Generation Information Technologies and Systems.","author":"Garcia-Molina H.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100054"},{"volume-title":"A Shorter Model Theory","author":"Hodges W.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015178417181"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11524564_5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2003.07.001"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153860"},{"volume-title":"Proceedings of 22th International Conference on Very Large Data Bases. 251--262","author":"Levy A.","key":"e_1_2_1_22_1"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin L.","key":"e_1_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01458217"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_5"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/647518.727513"},{"volume-title":"Proceedings of the 6th International Conference on Database Theory","series-title":"Lecture Notes in Computer Science","author":"Ullman J. D.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/221270.221319"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1656242.1656243","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1656242.1656243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:18Z","timestamp":1750250478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1656242.1656243"}},"subtitle":["Decidability and expressiveness"],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1145\/1656242.1656243"],"URL":"https:\/\/doi.org\/10.1145\/1656242.1656243","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2010,1]]},"assertion":[{"value":"2008-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}