{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:41:34Z","timestamp":1760708494132,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/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":["61133002"],"award-info":[{"award-number":["61133002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2012CB316200"],"award-info":[{"award-number":["2012CB316200"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/J015377\/1"],"award-info":[{"award-number":["EP\/J015377\/1"]}],"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. Database Syst."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>Data in real-life databases become obsolete rapidly. One often finds that multiple values of the same entity reside in a database. While all of these values were once correct, most of them may have become stale and inaccurate. Worse still, the values often do not carry reliable timestamps. With this comes the need for studying data currency, to identify the current value of an entity in a database and to answer queries with the current values, in the absence of reliable timestamps.<\/jats:p>\n          <jats:p>This article investigates the currency of data. (1) We propose a model that specifies partial currency orders in terms of simple constraints. The model also allows us to express what values are copied from other data sources, bearing currency orders in those sources, in terms of copy functions defined on correlated attributes. (2) We study fundamental problems for data currency, to determine whether a specification is consistent, whether a value is more current than another, and whether a query answer is certain no matter how partial currency orders are completed. (3) Moreover, we identify several problems associated with copy functions, to decide whether a copy function imports sufficient current data to answer a query, whether a copy function can be extended to import necessary current data for a query while respecting the constraints, and whether it suffices to copy data of a bounded size. (4) We establish upper and lower bounds of these problems, all matching, for combined complexity and data complexity, and for a variety of query languages. We also identify special cases that warrant lower complexity.<\/jats:p>","DOI":"10.1145\/2389241.2389244","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Determining the Currency of Data"],"prefix":"10.1145","volume":"37","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 Antwerp"}]},{"given":"Jef","family":"Wijsen","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Mons"}]}],"member":"320","published-online":{"date-parts":[[2012,12]]},"reference":[{"key":"e_1_2_1_1_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."},{"volume-title":"Proceedings of the 4th Biennial Conference on Innovative Data Systems Research.","author":"Berti-Equille L.","key":"e_1_2_1_2_1","unstructured":"Berti-Equille , L. , Sarma , A. D. , Dong , X. , Marian , A. , and Srivastava , D . 2009. Sailing the information ocean with awareness of currents: Discovery and application of source dependence . In Proceedings of the 4th Biennial Conference on Innovative Data Systems Research. Berti-Equille, L., Sarma, A. D., Dong, X., Marian, A., and Srivastava, D. 2009. Sailing the information ocean with awareness of currents: Discovery and application of source dependence. In Proceedings of the 4th Biennial Conference on Innovative Data Systems Research."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147376.1147391"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376918"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_1"},{"key":"e_1_2_1_8_1","unstructured":"Chomicki J. and Toman D. 2005. Time in database systems. In Handbook of Temporal Reasoning in Artificial Intelligence M. Fisher D. Gabbay and L. Vila Eds. Elsevier. Chomicki J. and Toman D. 2005. Time in database systems. In Handbook of Temporal Reasoning in Artificial Intelligence M. Fisher D. Gabbay and L. Vila Eds. Elsevier."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/249978.249980"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320109"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376938"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687691"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921008"},{"key":"e_1_2_1_14_1","unstructured":"Dyreson C. E. Jensen C. S. and Snodgrass R. T. 2009. Now in temporal databases. In Encyclopedia of Database Systems L. Liu and M. T. \u00d6zsu Eds. Springer. Dyreson C. E. Jensen C. S. and Snodgrass R. T. 2009. Now in temporal databases. In Encyclopedia of Database Systems L. Liu and M. T. \u00d6zsu Eds. Springer."},{"volume-title":"Data quality and the bottom line: Achieving business success through a commitment to high quality data","author":"Eckerson W. W.","key":"e_1_2_1_15_1","unstructured":"Eckerson , W. W. 2002. Data quality and the bottom line: Achieving business success through a commitment to high quality data . Data Warehousing Institute . Eckerson, W. W. 2002. Data quality and the bottom line: Achieving business success through a commitment to high quality data. Data Warehousing Institute."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862924"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.154"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989295"},{"key":"e_1_2_1_21_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":"The Problem of Incomplete Information in Relational Databases","author":"Grahne G.","key":"e_1_2_1_22_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_1_23_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-5(1:4)2009"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_25_1","unstructured":"Knowledge Integrity. 2003. Two sides to data decay. DM Review. Knowledge Integrity . 2003. Two sides to data decay. DM Review."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(94)90008-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00124-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402733"},{"volume-title":"Computational Complexity","author":"Papadimitriou C. H.","key":"e_1_2_1_31_1","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison-Wesley . Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009717525330"},{"key":"e_1_2_1_33_1","unstructured":"Snodgrass R. T. 1999. Developing Time-Oriented Database Applications in SQL. Morgan Kaufmann. Snodgrass R. T. 1999. Developing Time-Oriented Database Applications in SQL . Morgan Kaufmann."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1455"},{"volume-title":"Logics for Databases and Information Systems","author":"van der Meyden R.","key":"e_1_2_1_36_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_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7918"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920875"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2389241.2389244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:58Z","timestamp":1750239298000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2389241.2389244"],"URL":"https:\/\/doi.org\/10.1145\/2389241.2389244","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}