{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:01:25Z","timestamp":1747173685265,"version":"3.40.5"},"reference-count":41,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T00:00:00Z","timestamp":1701129600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>To answer database queries over incomplete data, the gold standard is finding certain answers: those that are true regardless of how incomplete data is interpreted. Such answers can be found efficiently for conjunctive queries and their unions, even in the presence of constraints. With negation added, the problem becomes intractable however. We concentrate on the complexity of certain answers under constraints and on effficiently answering queries outside the usual classes of (unions) of conjunctive queries by means of rewriting as Datalog and first-order queries. We first notice that there are three different ways in which query answering can be cast as a decision problem. We complete the existing picture and provide precise complexity bounds on all versions of the decision problem, for certain and best answers. We then study a well-behaved class of queries that extends unions of conjunctive queries with a mild form of negation. We show that for them, certain answers can be expressed in Datalog with negation, even in the presence of functional dependencies, thus making them tractable in data complexity. We show that in general, Datalog cannot be replaced by first-order logic, but without constraints such a rewriting can be done in first order.<\/jats:p>","DOI":"10.1017\/s1471068423000364","type":"journal-article","created":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T04:37:36Z","timestamp":1701146256000},"page":"279-309","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Querying Incomplete Data: Complexity and Tractability via Datalog and First-Order Rewritings"],"prefix":"10.1017","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8936-9829","authenticated-orcid":false,"given":"AM\u00c9LIE","family":"GHEERBRANT","sequence":"first","affiliation":[]},{"given":"LEONID","family":"LIBKIN","sequence":"additional","affiliation":[]},{"given":"ALEXANDRA","family":"ROGOVA","sequence":"additional","affiliation":[]},{"given":"CRISTINA","family":"SIRANGELO","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,11,28]]},"reference":[{"key":"S1471068423000364_ref31","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"volume-title":"Synthesis Lectures on Data Management","year":"2011","author":"Bertossi","key":"S1471068423000364_ref6"},{"key":"S1471068423000364_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201031"},{"volume-title":"Foundations of Databases","year":"1995","author":"Abiteboul","key":"S1471068423000364_ref1"},{"key":"S1471068423000364_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90075-D"},{"key":"S1471068423000364_ref7","doi-asserted-by":"crossref","unstructured":"Bienvenu, M. and Bourgaux, C. 2016. Inconsistency-tolerant querying of description logic knowledge bases. In Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering - 12th International Summer School 2016, Aberdeen, UK, 5\u20139 September 2016, Tutorial Lectures, J. Z. Pan, D. Calvanese, T. Eiter, I. Horrocks, M. Kifer, F. Lin and Y. Zhao, Eds. Lecture Notes in Computer Science, vol. 9885. Springer, 156\u2013202.","DOI":"10.1007\/978-3-319-49493-7_5"},{"key":"S1471068423000364_ref13","unstructured":"Calvanese, D. , Giacomo, G. D. , Lembo, D. , Lenzerini, M. and Rosati, R. 2006. Epistemic first-order queries over description logic knowledge bases. In Proceedings of the 2006 International Workshop on Description Logics (DL2006), Windermere, Lake District, UK, 30 May\u20131 June 2006, B. Parsia, U. Sattler and D. Toman, Eds. CEUR Workshop Proceedings, vol. 189. CEUR-WS.org."},{"key":"S1471068423000364_ref4","first-page":"28:1","article-title":"Data exchange beyond complete data","volume":"4","author":"Arenas","year":"2013","journal-title":"Journal of the ACM 60"},{"key":"S1471068423000364_ref14","unstructured":"Calvanese, D. , Giacomo, G. D. , Lenzerini, M. and Vardi, M. Y. 2000. What is view-based query rewriting? In Proceedings of the 7th International Workshop on Knowledge Representation meets Databases (KRDB 2000), Berlin, Germany, 21 August 2000, M. Bouzeghoub, M. Klusch, W. Nutt and U. Sattler, Eds. CEUR Workshop Proceedings, vol. 29. CEUR-WS.org, 17\u201327."},{"key":"S1471068423000364_ref17","doi-asserted-by":"crossref","unstructured":"Eiter, T. and Gottlob, G. 1997. The complexity class theta2p: Recent results and applications in AI and modal logic. In Fundamentals of Computation Theory, 11th International Symposium, FCT\u201997, Krak\u00f3w, Poland, 1\u20133 September 1997, Proceedings, B. S. Chlebus and L. Czaja, Eds. Lecture Notes in Computer Science, vol. 1279. Springer, 1\u201318.","DOI":"10.1007\/BFb0036168"},{"key":"S1471068423000364_ref22","unstructured":"Gheerbrant, A. , Libkin, L. , Rogova, A. and Sirangelo, C. 2022. Certain answers of extensions of conjunctive queries by datalog and first-order rewriting. In Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022) Co-located with the 16th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2022), Genova-Nervi, Italy, 5 September 2022, M. Alviano and A. Pieris, Eds. Workshop Proceedings, CEUR , vol. 3203. CEUR-WS.org, 14\u201326."},{"key":"S1471068423000364_ref32","doi-asserted-by":"crossref","unstructured":"Lenzerini, M. 2002. Data integration: A theoretical perspective. In Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 3\u20135 June, Madison, Wisconsin, USA, Popa, L. , Abiteboul, S. and Kolaitis, P. G. , Eds. ACM, 233\u2013246.","DOI":"10.1145\/543613.543644"},{"key":"S1471068423000364_ref34","first-page":"1:1","article-title":"Sql\u2019s three-valued logic and certain answers","volume":"1","author":"Libkin","year":"2016","journal-title":"ACM Transactions on Database Systems 41"},{"key":"S1471068423000364_ref35","doi-asserted-by":"crossref","unstructured":"Libkin, L. 2018. Certain answers meet zero-one laws. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, 10\u201315 June 2018, den Bussche, J. V. and Arenas, M. , Eds. ACM, 195\u2013207.","DOI":"10.1145\/3196959.3196983"},{"key":"S1471068423000364_ref28","doi-asserted-by":"crossref","unstructured":"Guagliardo, P. and Libkin, L. 2016. Making SQL queries correct on incomplete databases: A feasibility study. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, 26 June\u201301 July 2016, Milo, T. and Tan, W. , Eds. ACM, 211\u2013223.","DOI":"10.1145\/2902251.2902297"},{"key":"S1471068423000364_ref5","doi-asserted-by":"publisher","DOI":"10.1137\/130911731"},{"key":"S1471068423000364_ref36","unstructured":"Lipski, W. J. 1984. On relational algebra with marked nulls. In Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 2\u20134 April 1984, Waterloo, Ontario, Canada, Rosenkrantz, D. J. and Fagin, R. , Eds. ACM, 201\u2013203."},{"key":"S1471068423000364_ref2","first-page":"158","article-title":"On the representation and querying of sets of possible worlds","volume":"1","author":"Abiteboul","year":"1991","journal-title":"Theoretical Computer Science 78"},{"key":"S1471068423000364_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"S1471068423000364_ref40","doi-asserted-by":"crossref","unstructured":"van der Meyden, R. 1998. Logical approaches to incomplete information: A survey. In Logics for Databases and Information Systems (the book grow out of the Dagstuhl Seminar 9529: Role of Logics in Information Systems, 1995), Chomicki, J. and Saake, G. , Eds. Kluwer, 307\u2013356.","DOI":"10.1007\/978-1-4615-5643-5_10"},{"volume-title":"Synthesis Lectures on Data Management","year":"2012","author":"Greco","key":"S1471068423000364_ref27"},{"key":"S1471068423000364_ref12","unstructured":"Cal, A. , Lembo, D. and Rosati, R. 2003b. Query rewriting and answering under constraints in data integration systems. In IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 9\u201315 August 2003, G. Gottlob and T. Walsh, Eds. Morgan Kaufmann, 16\u201321."},{"key":"S1471068423000364_ref8","doi-asserted-by":"crossref","unstructured":"Bienvenu, M. and Ortiz, M. 2015. Ontology-mediated query answering with data-tractable description logics. In Reasoning Web. Web Logic Rules - 11th International Summer School 2015, Berlin, Germany, 31 July\u20134 August 2015, Tutorial Lectures, W. Faber and A. Paschke, Eds. Lecture Notes in Computer Science, vol. 9203. Springer, 218\u2013307.","DOI":"10.1007\/978-3-319-21768-0_9"},{"key":"S1471068423000364_ref20","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"S1471068423000364_ref10","doi-asserted-by":"crossref","unstructured":"Cal, A. , Calvanese, D. and Lenzerini, M. 2013 . Rewrite and conquer: Dealing with integrity constraints in data integration. In Seminal Contributions to Information Systems Engineering, 25 Years of CAiSE, J. Bubenko Jr., J. Krogstie, O. Pastor, B. Pernici, C. Rolland and A. S\u00f8lvberg, Eds. Springer, 353\u2013359.","DOI":"10.1007\/978-3-642-36926-1_28"},{"key":"S1471068423000364_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139060158"},{"key":"S1471068423000364_ref11","doi-asserted-by":"crossref","unstructured":"Cal, A. , Lembo, D. and Rosati, R. 2003a. On the decidability and complexity of query answering over inconsistent and incomplete databases. In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 9\u201312 June 2003, San Diego, CA, USA, F. Neven, C. Beeri and T. Milo, Eds. ACM, 260\u2013271.","DOI":"10.1145\/773153.773179"},{"key":"S1471068423000364_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9596-y"},{"key":"S1471068423000364_ref16","doi-asserted-by":"crossref","unstructured":"Coelho, F. 2013. https:\/\/blog.coelho.net\/database\/2013\/08\/17\/turing-sql-1.html.","DOI":"10.1109\/ENBENG.2013.6518389"},{"key":"S1471068423000364_ref23","first-page":"31:1","article-title":"Na\u00efve evaluation of queries over incomplete databases","volume":"4","author":"Gheerbrant","year":"2014","journal-title":"ACM Transactions on Database Systems 39"},{"key":"S1471068423000364_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.006"},{"key":"S1471068423000364_ref30","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"S1471068423000364_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00736-3"},{"key":"S1471068423000364_ref37","first-page":"55","volume-title":"Logic and Data Bases, Symposium on Logic and Data Bases, Centre d\u2019\u00e9tudes et de recherches de Toulouse, France, 1977","author":"Reiter","year":"1977"},{"key":"S1471068423000364_ref25","unstructured":"Gierth, A. 2011. https:\/\/wiki.postgresql.org\/wiki\/Cyclic_Tag_System."},{"key":"S1471068423000364_ref39","doi-asserted-by":"crossref","unstructured":"Schaefer, M. and Umans, C. 2002. Completeness in the polynomial-time hierarchy a compendium. Sigact News - SIGACT 33, 32\u201349.","DOI":"10.1145\/582475.582484"},{"key":"S1471068423000364_ref24","doi-asserted-by":"crossref","unstructured":"Gheerbrant, A. and Sirangelo, C. 2019. Best answers over incomplete data: Complexity and first-order rewritings. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, 10\u201316 August 2019, S. Kraus, Ed. ijcai.org, 1704\u20131710.","DOI":"10.24963\/ijcai.2019\/236"},{"key":"S1471068423000364_ref38","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00229-1"},{"key":"S1471068423000364_ref41","doi-asserted-by":"publisher","DOI":"10.1137\/0219058"},{"key":"S1471068423000364_ref19","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1100"},{"key":"S1471068423000364_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502100"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068423000364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:36:43Z","timestamp":1730680603000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068423000364\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,28]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S1471068423000364"],"URL":"https:\/\/doi.org\/10.1017\/s1471068423000364","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2023,11,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}