{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:30:15Z","timestamp":1750307415761,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,7,30]],"date-time":"2008-07-30T00:00:00Z","timestamp":1217376000000},"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. Database Syst."],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>\n            The\n            <jats:italic>Closed World Assumption<\/jats:italic>\n            (CWA) on databases expresses the assumption that an atom not in the database is false. This assumption is applicable only in cases where the database has complete knowledge about the domain of discourse. In this article, we investigate\n            <jats:italic>locally closed<\/jats:italic>\n            databases, that is: databases that are sound but partially incomplete about their domain. Such databases consist of a standard database instance, augmented with a collection of\n            <jats:italic>Local Closed World Assumptions<\/jats:italic>\n            (LCWAs). A LCWA is a \u201clocal\u201d form of the CWA, expressing that a database relation is complete in a certain area, called a\n            <jats:italic>window of expertise<\/jats:italic>\n            . In this work, we study locally closed databases both from a knowledge representation and from a computational perspective. At the representation level, the approach taken in this article distinguishes between the data that is conveyed by a database and the metaknowledge about the area in which the data is complete. We study the semantics of the LCWA's and relate it to several knowledge representation formalisms. At the reasoning level, we study the complexity of, and algorithms for two basic reasoning tasks: computing\n            <jats:italic>certain<\/jats:italic>\n            and\n            <jats:italic>possible<\/jats:italic>\n            answers to queries and determining whether a database has complete knowledge on a query. As the complexity of these tasks is unacceptably high, we develop efficient\n            <jats:italic>approximate<\/jats:italic>\n            methods for query answering. We also prove that for useful classes of queries and locally closed databases, these methods are\n            <jats:italic>optimal<\/jats:italic>\n            , and thus they solve the original query in a tractable way. As a result, we obtain classes of queries and locally closed databases for which query answering is tractable.\n          <\/jats:p>","DOI":"10.1145\/1806907.1806914","type":"journal-article","created":{"date-parts":[[2010,8,2]],"date-time":"2010-08-02T13:15:22Z","timestamp":1280754922000},"page":"1-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Towards a logical reconstruction of a theory for locally closed databases"],"prefix":"10.1145","volume":"35","author":[{"given":"Marc","family":"Denecker","sequence":"first","affiliation":[{"name":"Katholieke Universiteit Leuven, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c1lvaro","family":"Cort\u00e9s-Calabuig","sequence":"additional","affiliation":[{"name":"Katholieke Universiteit Leuven, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maurice","family":"Bruynooghes","sequence":"additional","affiliation":[{"name":"Katholieke Universiteit Leuven, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Arieli","sequence":"additional","affiliation":[{"name":"The Academic College of Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"volume-title":"Proceedings of the 11th International Conference on Very Large Data Bases (VLDB). 1--12","author":"Abiteboul S.","key":"e_1_2_2_2_1"},{"key":"e_1_2_2_3_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132869"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/6012.15399"},{"volume-title":"Proceedings of the International Logic Programming Symposium. 181--198","author":"Baral C.","key":"e_1_2_2_6_1"},{"volume-title":"Proceedings of the 5th International Conference on Logic Programming, R. Kowalski and K. Bowen, Eds. MIT Press.","year":"1988","author":"Chan D.","key":"e_1_2_2_7_1"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153862"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182602"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11916277_28"},{"volume-title":"Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI). AAAI Press, 397--402","author":"Cort\u00e9s-Calabuig A.","key":"e_1_2_2_12_1"},{"volume-title":"Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR). AAAI Press, 81--91","author":"Cort\u00e9s-Calabuig A.","key":"e_1_2_2_13_1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11546207_12"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/4236.877487"},{"volume-title":"Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR). D. Dubois and C. Welty, Eds. 545--553","author":"Denecker M.","key":"e_1_2_2_16_1"},{"key":"e_1_2_2_17_1","series-title":"Lecture Notes in Computer Science","volume-title":"Artificial Intelligence: Methodology, Systems, and Applications","author":"Doherty P.","year":"2000"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00026-4"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061323"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"volume-title":"Proceedings of the 14th International Conference on Very Large Data Bases (VLDB). 50--61","author":"Gottlob G.","key":"e_1_2_2_21_1"},{"volume-title":"Proceedings of the International Confeference on Very Large Data Bases (VLDB). 37--45","year":"1984","author":"Grahne G.","key":"e_1_2_2_22_1"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73728"},{"key":"e_1_2_2_24_1","first-page":"46","article-title":"Information integration and incomplete information","volume":"25","author":"Grahne G.","year":"2002","journal-title":"IEEE Data Engin. Bull."},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 332--347","author":"Grahne G.","key":"e_1_2_2_25_1"},{"volume-title":"Proceedings of the 8th International Workshop on Knowledge Representation meets Databases (KRDB).","author":"Grahne G.","key":"e_1_2_2_26_1"},{"volume-title":"Proceedings of the International Confeference on Very Large Data Bases (VLDB). 388--397","year":"1981","author":"Imielinski T.","key":"e_1_2_2_27_1"},{"volume-title":"Proceedings of the 5th International Conference on Computer Vision (ICCV). IEEE, 672--678","author":"Intille S.","key":"e_1_2_2_28_1"},{"volume-title":"Introduction to Metamathematics. Bibliotheca Mathematica","author":"Kleene S.","key":"e_1_2_2_29_1"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Levesque H. 1982. The logic of incomplete knowledge bases. In On Conceptual Modelling (Intervale). 165--189.  Levesque H. 1982. The logic of incomplete knowledge bases. In On Conceptual Modelling (Intervale). 165--189.","DOI":"10.1007\/978-1-4612-5196-5_7"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/645922.673332"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin L.","key":"e_1_2_2_34_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00090-X"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142360"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376937"},{"volume-title":"Handbook of Logic in AI and Logic Programming","author":"Lifschitz V.","key":"e_1_2_2_38_1"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.04.005"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90011-9"},{"volume-title":"Formalizing Common Sense: Papers by John McCarthy","author":"McCarthy J.","key":"e_1_2_2_41_1"},{"volume-title":"On indefinite databases and the closed world assumption","series-title":"Lecture Notes in Computer Science","author":"Minker J.","key":"e_1_2_2_42_1"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/76902.76904"},{"volume-title":"Proceedings of the 22nd AAAI Conference on Artificial Intelligence. 1434--1439","author":"Pan J.","key":"e_1_2_2_44_1"},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Reiter R. 1977. Deductive question-answering on relational data bases. In Logic and Data Bases 149--177.  Reiter R. 1977. Deductive question-answering on relational data bases. In Logic and Data Bases 149--177.","DOI":"10.1007\/978-1-4684-3384-5_6"},{"volume-title":"On closed world data bases","author":"Reiter R.","key":"e_1_2_2_46_1"},{"key":"e_1_2_2_47_1","unstructured":"Reiter R. 1982. Towards a logical reconstruction of relational database theory. In On Conceptual Modelling Perspectives from Artificial Intelligence Databases and Programming Languages (Intervale) 191--233.  Reiter R. 1982. Towards a logical reconstruction of relational database theory. In On Conceptual Modelling Perspectives from Artificial Intelligence Databases and Programming Languages (Intervale) 191--233."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5388"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(92)90049-9"},{"volume-title":"Proceedings of the 5th International Conference Flexible Query Answering Systems. 329--343","author":"Stuckenschmidt H.","key":"e_1_2_2_50_1"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018990308362"},{"key":"e_1_2_2_52_1","doi-asserted-by":"crossref","unstructured":"Topor R. W. and Sonenberg L. 1988. On domain independent databases. In Foundations of Deductive Databases and Logic Programming Morgan Kaufmann 217--240.   Topor R. W. and Sonenberg L. 1988. On domain independent databases. In Foundations of Deductive Databases and Logic Programming Morgan Kaufmann 217--240.","DOI":"10.1016\/B978-0-934613-40-8.50010-5"},{"key":"e_1_2_2_53_1","first-page":"1","article-title":"Impossibility of an algorithm for the decision problem in finite classes","volume":"3","author":"Trakhtenbrot B.","year":"1963","journal-title":"Amer. Math. Soc. Trans."},{"volume-title":"Principles of Database and Knowledge-Base Systems","author":"Ullman J. D.","key":"e_1_2_2_54_1"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.2307\/2024549"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90024-Q"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"volume-title":"Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR). AAAI Press.","author":"Wittocx J.","key":"e_1_2_2_58_1"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806907.1806914","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806907.1806914","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806907.1806914"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,30]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1145\/1806907.1806914"],"URL":"https:\/\/doi.org\/10.1145\/1806907.1806914","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2008,7,30]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}