{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:00:43Z","timestamp":1761580843437,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T00:00:00Z","timestamp":1286841600000},"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,11]]},"abstract":"<jats:p>\n            This article investigates the question of whether a partially closed database has complete information to answer a query. In practice an enterprise often maintains master data\n            <jats:italic>\n              D\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            , a closed-world database. We say that a database\n            <jats:italic>D<\/jats:italic>\n            is\n            <jats:italic>partially closed<\/jats:italic>\n            if it satisfies a set\n            <jats:italic>V<\/jats:italic>\n            of containment constraints of the form\n            <jats:italic>q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) \u2286\n            <jats:italic>p<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            <jats:italic>\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ), where\n            <jats:italic>q<\/jats:italic>\n            is a query in a language L\n            <jats:italic>\n              <jats:sub>C<\/jats:sub>\n            <\/jats:italic>\n            and\n            <jats:italic>p<\/jats:italic>\n            is a projection query. The part of\n            <jats:italic>D<\/jats:italic>\n            not constrained by (\n            <jats:italic>D<\/jats:italic>\n            <jats:italic>\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            ) is open, from which some tuples may be missing. The database\n            <jats:italic>D<\/jats:italic>\n            is said to be\n            <jats:italic>complete<\/jats:italic>\n            for a query\n            <jats:italic>Q<\/jats:italic>\n            relative to (\n            <jats:italic>D<\/jats:italic>\n            <jats:italic>\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            ) if for all partially closed extensions\n            <jats:italic>D<\/jats:italic>\n            ' of\n            <jats:italic>D<\/jats:italic>\n            ,\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ') =\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ), i.e., adding tuples to\n            <jats:italic>D<\/jats:italic>\n            either violates some constraints in\n            <jats:italic>V<\/jats:italic>\n            or does not change the answer to\n            <jats:italic>Q<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We first show that the proposed model can also capture the consistency of data, in addition to its relative completeness. Indeed, integrity constraints studied for data consistency can be expressed as containment constraints. We then study two problems. One is to decide, given\n            <jats:italic>D<\/jats:italic>\n            <jats:italic>\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            , a query\n            <jats:italic>Q<\/jats:italic>\n            in a language L\n            <jats:italic>\n              <jats:sub>Q<\/jats:sub>\n            <\/jats:italic>\n            , and a partially closed database\n            <jats:italic>D<\/jats:italic>\n            , whether\n            <jats:italic>D<\/jats:italic>\n            is complete for\n            <jats:italic>Q<\/jats:italic>\n            relative to (\n            <jats:italic>D<\/jats:italic>\n            <jats:italic>\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            ). The other is to determine, given\n            <jats:italic>D<\/jats:italic>\n            <jats:italic>\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            and\n            <jats:italic>Q<\/jats:italic>\n            , whether there exists a partially closed database that is complete for\n            <jats:italic>Q<\/jats:italic>\n            relative to (\n            <jats:italic>D<\/jats:italic>\n            <jats:italic>\n              <jats:sub>m<\/jats:sub>\n            <\/jats:italic>\n            ,\n            <jats:italic>V<\/jats:italic>\n            ). We establish matching lower and upper bounds on these problems for a variety of languages L\n            <jats:italic>\n              <jats:sub>Q<\/jats:sub>\n            <\/jats:italic>\n            and L\n            <jats:italic>\n              <jats:sub>C<\/jats:sub>\n            <\/jats:italic>\n            . We also provide characterizations for a database to be relatively complete, and for a query to allow a relatively complete database, when L\n            <jats:italic>\n              <jats:sub>Q<\/jats:sub>\n            <\/jats:italic>\n            and L\n            <jats:italic>\n              <jats:sub>C<\/jats:sub>\n            <\/jats:italic>\n            are conjunctive queries.\n          <\/jats:p>","DOI":"10.1145\/1862919.1862924","type":"journal-article","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T15:55:04Z","timestamp":1292860504000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Relative information completeness"],"prefix":"10.1145","volume":"35","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh and Harbin Institute of Technology"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Edinburgh, UK"}]}],"member":"320","published-online":{"date-parts":[[2010,10,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_2_2_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_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_2_4_1","volume-title":"Data Quality: Concepts, Methodologies and Techniques","author":"Batini C.","year":"2006","unstructured":"Batini , C. and Scannapieco , M . 2006 . Data Quality: Concepts, Methodologies and Techniques . Springer . Batini, C. and Scannapieco, M. 2006. Data Quality: Concepts, Methodologies and Techniques. Springer."},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB). 243--254","author":"Bravo L.","key":"e_1_2_2_5_1","unstructured":"Bravo , L. , Fan , W. , and Ma , S . 2007. Extending dependencies with conditions . In Proceedings of International Conference on Very Large Databases (VLDB). 243--254 . Bravo, L., Fan, W., and Ma, S. 2007. Extending dependencies with conditions. In Proceedings of International Conference on Very Large Databases (VLDB). 243--254."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773179"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.006"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_1"},{"volume-title":"Proceedings of the International Symposium Logical Foundations of Computer Science (LFCS). 56--66","author":"Dantsin E.","key":"e_1_2_2_10_1","unstructured":"Dantsin , E. and Voronkov , A . 1997. Complexity of query answering in logic databases with complex values . In Proceedings of the International Symposium Logical Foundations of Computer Science (LFCS). 56--66 . Dantsin, E. and Voronkov, A. 1997. Complexity of query answering in logic databases with complex values. In Proceedings of the International Symposium Logical Foundations of Computer Science (LFCS). 56--66."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.008"},{"key":"e_1_2_2_12_1","unstructured":"Dreibelbis A. Hechler E. Mathews B. Oberhofer M. and Sauter G. 2007. Master data management architecture patterns. Tech. rep. IBM.  Dreibelbis A. Hechler E. Mathews B. Oberhofer M. and Sauter G. 2007. Master data management architecture patterns. Tech. rep. IBM."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298557"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376940"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559811"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807109"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_2_2_18_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.   Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB). 50--61","author":"Gottlob G.","key":"e_1_2_2_19_1","unstructured":"Gottlob , G. and Zicari , R . 1988. Closed world databases opened through null values . In Proceedings of International Conference on Very Large Databases (VLDB). 50--61 . Gottlob, G. and Zicari, R. 1988. Closed world databases opened through null values. In Proceedings of International Conference on Very Large Databases (VLDB). 50--61."},{"volume-title":"The Problem of Incomplete Information in Relational Databases","author":"Grahne G.","key":"e_1_2_2_20_1","unstructured":"Grahne , G. 1991. The Problem of Incomplete Information in Relational Databases . Springer . Grahne, G. 1991. The Problem of Incomplete Information in Relational Databases. Springer."},{"key":"e_1_2_2_21_1","unstructured":"Herzog T. N. Scheuren F. J. and Winkler W. E. 2007. Data Quality and Record Linkage Techniques. Springer.   Herzog T. N. Scheuren F. J. and Winkler W. E. 2007. Data Quality and Record Linkage Techniques. Springer."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of International Conference on Very Large Databases (VLDB). 402--412","author":"Levy A. Y.","year":"1996","unstructured":"Levy , A. Y. 1996 . Obtaining complete answers from incomplete databases . In Proceedings of International Conference on Very Large Databases (VLDB). 402--412 . Levy, A. Y. 1996. Obtaining complete answers from incomplete databases. In Proceedings of International Conference on Very Large Databases (VLDB). 402--412."},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB). 171--181","author":"Levy A. Y.","key":"e_1_2_2_24_1","unstructured":"Levy , A. Y. and Sagiv , Y . 1993. Queries independent of updates . In Proceedings of International Conference on Very Large Databases (VLDB). 171--181 . Levy, A. Y. and Sagiv, Y. 1993. Queries independent of updates. In Proceedings of International Conference on Very Large Databases (VLDB). 171--181."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0085-6"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Loshin D. 2008. Master Data Management. Morgan Kaufmann.   Loshin D. 2008. Master Data Management. Morgan Kaufmann.","DOI":"10.1016\/B978-0-12-374225-4.00001-1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/76902.76904"},{"volume-title":"Computational Complexity","author":"Papadimitriou C. H.","key":"e_1_2_2_28_1","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison-Wesley . Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_2_29_1","unstructured":"Radcliffe J. and White A. 2008. Key issues for master data management. Tech. rep. Gartner.  Radcliffe J. and White A. 2008. Key issues for master data management. Tech. rep. Gartner."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065174"},{"volume-title":"Logics for Databases and Information Systems","author":"van der Meyden R.","key":"e_1_2_2_32_1","unstructured":"van der Meyden , R. 1998. Logical approaches to incomplete information: A survey . In Logics for Databases and Information Systems , J. Chomicki and G. Saake, Eds., Kluwer . van der Meyden, R. 1998. Logical approaches to incomplete information: A survey. In Logics for Databases and Information Systems, J. Chomicki and G. Saake, Eds., Kluwer."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/6012.15419"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862924","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1862919.1862924","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:51Z","timestamp":1750281291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,12]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1145\/1862919.1862924"],"URL":"https:\/\/doi.org\/10.1145\/1862919.1862924","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2010,10,12]]},"assertion":[{"value":"2009-09-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":"2010-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}