{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T07:45:18Z","timestamp":1789976718617,"version":"4.0.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,5,11]],"date-time":"2017-05-11T00:00:00Z","timestamp":1494460800000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61421003,"],"award-info":[{"award-number":["61421003,"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shenzhen Peacock Program","award":["105100030834361"],"award-info":[{"award-number":["105100030834361"]}]},{"DOI":"10.13039\/501100012166","name":"973 Program","doi-asserted-by":"crossref","award":["2014CB340302, 2012CB316200"],"award-info":[{"award-number":["2014CB340302, 2012CB316200"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/J015377\/1, P\/M025268\/1"],"award-info":[{"award-number":["EP\/J015377\/1, P\/M025268\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012540","name":"Guangdong Innovative Research Team Program","doi-asserted-by":"crossref","award":["2011D005"],"award-info":[{"award-number":["2011D005"]}],"id":[{"id":"10.13039\/100012540","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["652976"],"award-info":[{"award-number":["652976"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["III 1302212"],"award-info":[{"award-number":["III 1302212"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shenzhen Science and Technology Fund","award":["JCYJ20150529164656096"],"award-info":[{"award-number":["JCYJ20150529164656096"]}]},{"name":"Guangdong Applied R&D Program","award":["2015B010131006"],"award-info":[{"award-number":["2015B010131006"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2016,6,30]]},"abstract":"<jats:p>\n                    Databases in real life are often neither entirely closed-world nor entirely open-world. Databases in an enterprise are typically\n                    <jats:italic toggle=\"yes\">partially closed<\/jats:italic>\n                    , in which a part of the data is constrained by master data that contains complete information about the enterprise in certain aspects. It has been shown that, despite missing tuples, such a database may turn out to have complete information for answering a query.\n                  <\/jats:p>\n                  <jats:p>\n                    This article studies partially closed databases from which\n                    <jats:italic toggle=\"yes\">both tuples and attribute values<\/jats:italic>\n                    may be missing. We specify such a database in terms of conditional tables constrained by master data, referred to as\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    -instances. We first propose three models to characterize whether a\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    -instance\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    is\n                    <jats:italic toggle=\"yes\">complete<\/jats:italic>\n                    for a query\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    <jats:italic toggle=\"yes\">relative to<\/jats:italic>\n                    master data. That is, depending on how missing values in\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    are instantiated, the answer to\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    in\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    remains unchanged when new tuples are added. We then investigate three problems, to determine (a) whether a given\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    -instance is complete for a query\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    , (b) whether there exists a\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    -instance that is complete for\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    relative to master data available, and (c) whether a\n                    <jats:italic toggle=\"yes\">c<\/jats:italic>\n                    -instance is a minimal-size database that is complete for\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    . We establish matching lower and upper bounds on these problems for queries expressed in a variety of languages in each of the three models for specifying relative completeness.\n                  <\/jats:p>","DOI":"10.1145\/2901737","type":"journal-article","created":{"date-parts":[[2016,5,13]],"date-time":"2016-05-13T10:30:58Z","timestamp":1463135458000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Capturing Missing Tuples and Missing Values"],"prefix":"10.1145","volume":"41","author":[{"given":"Ting","family":"Deng","sequence":"first","affiliation":[{"name":"RCBD and SKLSDE, Beihang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenfei","family":"Fan","sequence":"additional","affiliation":[{"name":"Informatics, University of Edinburgh, and RCBD and SKLSDE, Beihang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Antwerp"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,5,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(51)90007-2"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1815933.1815938"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.04.001"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_1"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298557"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376940"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559811"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807109"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862924"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00439ED1V01Y201207DTM030"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645915.671794"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54919-6"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612176"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153860"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645922.673332"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645919.672674"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594561"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1457711"},{"key":"e_1_2_2_25_1","volume-title":"SQL Server 2008 R2 Master Data Services. Retrieved","year":"2016","unstructured":"Microsoft. 2008. SQL Server 2008 R2 Master Data Services. Retrieved April 3, 2016 from http:\/\/www.microsoft.com\/sqlserver\/2008\/en\/us\/MDS.aspx."},{"key":"e_1_2_2_26_1","volume-title":"AMIA Annual Symposium Proceedings (AMIA\u201905)","author":"Miller Donald W.","unstructured":"Donald W. Miller Jr., John D. Yeast, and Robin L. Evans. 2005. Missing prenatal records at a birth center: A communication problem quantified. In AMIA Annual Symposium Proceedings (AMIA\u201905). 535--539."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/76902.76904"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.004"},{"key":"e_1_2_2_29_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","unstructured":"Christos H. Papadimitriou. 1994. Computational Complexity. Addison-Wesley, New York, NY."},{"key":"e_1_2_2_30_1","volume-title":"Key issues for Master Data Management. Gartner. Retrieved","author":"Radcliffe John","year":"2016","unstructured":"John Radcliffe and Andrew White. 2008. Key issues for Master Data Management. Gartner. Retrieved April 3, 2016 from https:\/\/www.gartner.com\/doc\/590507\/key-issues-master-data-management."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065174"},{"key":"e_1_2_2_32_1","unstructured":"Mark Spielmann. 2000. Abstract State Machines: Verification Problems and Complexity. Ph.D. Dissertation. RWTH Aachen University Aachen Germany."},{"key":"e_1_2_2_33_1","first-page":"569","article-title":"The impossibility of an algorithm for the decidability problem on finite classes","volume":"70","author":"Trakhtenbrot Boris","year":"1950","unstructured":"Boris Trakhtenbrot. 1950. The impossibility of an algorithm for the decidability problem on finite classes. Doklady Akademii Nauk SSSR 70, 4, 569--572.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/294135.294145"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/6012.15419"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.002"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2901737","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2901737","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2901737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:19:03Z","timestamp":1763457543000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2901737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,11]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,6,30]]}},"alternative-id":["10.1145\/2901737"],"URL":"https:\/\/doi.org\/10.1145\/2901737","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,11]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}