research-article

Determining the Currency of Data

Authors:

Wenfei Fan,

Floris Geerts,

Jef WijsenAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 37, Issue 4

Article No.: 25, Pages 1 - 46

https://doi.org/10.1145/2389241.2389244

Published: 01 December 2012 Publication History

Get Access

Abstract

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.

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.

References

[1]

Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley.

Digital Library

Google Scholar

[2]

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.

Google Scholar

[3]

Bertossi, L. 2006. Consistent query answering in databases. SIGMOD Rec. 35, 2, 68--76.

Digital Library

Google Scholar

[4]

Bodirsky, M. and Kára, J. 2010. The complexity of temporal constraint satisfaction problems. J. ACM 57, 2.

Digital Library

Google Scholar

[5]

Buneman, P., Cheney, J., Tan, W., and Vansummeren, S. 2008. Curated databases. In Proceedings of the 27th Symposium on Principles of Database Systems. 1--12.

Digital Library

Google Scholar

[6]

Cheney, J., Chiticariu, L., and Tan, W. C. 2009. Provenance in databases: Why, how, and where. Found. Trends Datab. 1, 4, 379--474.

Digital Library

Google Scholar

[7]

Chomicki, J. 2007. Consistent query answering: Five easy pieces. In Proceedings of the 11th International Conference on Database Theory. 1--17.

Digital Library

Google Scholar

[8]

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.

Google Scholar

[9]

Clifford, J., Dyreson, C. E., Isakowitz, T., Jensen, C. S., and Snodgrass, R. T. 1997. On the semantics of “now” in databases. ACM Trans. Datab. Syst. 22, 2, 171--214.

Digital Library

Google Scholar

[10]

Codd, E. F. 1979. Extending the database relational model to capture more meaning. ACM Trans. Datab. Syst. 4, 4, 397--434.

Digital Library

Google Scholar

[11]

Deutsch, A., Nash, A., and Remmel, J. B. 2008. The chase revisited. In Proceedings of the 27th Symposium on Principles of Database Systems. 149--158.

Digital Library

Google Scholar

[12]

Dong, X., Berti-Equille, L., and Srivastava, D. 2009. Truth discovery and copying detection in a dynamic world. Proc. VLDB Endov. 2, 1, 562--573.

Digital Library

Google Scholar

[13]

Dong, X., Berti-Equille, L., Hu, Y., and Srivastava, D. 2010. Global detection of complex copying relationships between sources. Proc. VLDB Endov. 3, 1, 1358--1369.

Digital Library

Google Scholar

[14]

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. Özsu Eds., Springer.

Google Scholar

[15]

Eckerson, W. W. 2002. Data quality and the bottom line: Achieving business success through a commitment to high quality data. Data Warehousing Institute.

Google Scholar

[16]

Elmagarmid, A. K., Ipeirotis, P. G., and Verykios, V. S. 2007. Duplicate record detection: A survey. IEEE Trans. Knowl. Data Engin. 19, 1, 1--16.

Digital Library

Google Scholar

[17]

Fan, W. and Geerts, F. 2011. Relative information completeness. ACM Trans. Datab. Syst. 35, 4.

Digital Library

Google Scholar

[18]

Fan, W., Geerts, F., Jia, X., and Kementsietsidis, A. 2008. Conditional functional dependencies for capturing data inconsistencies. ACM Trans. Datab. Syst. 33, 1.

Digital Library

Google Scholar

[19]

Fan, W., Geerts, F., Li, J., and Xiong, M. 2011a. Discovering conditional functional dependencies. IEEE Trans. Knowl. Data Engin. 23, 5, 683--698.

Digital Library

Google Scholar

[20]

Fan, W., Geerts, F., and Wijsen, J. 2011b. Determining the currency of data. In Proceedings of the 30th Symposium on Principles of Database Systems. 71--82.

Digital Library

Google Scholar

[21]

Garey, M. and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.

Digital Library

Google Scholar

[22]

Grahne, G. 1991. The Problem of Incomplete Information in Relational Databases. Springer.

Digital Library

Google Scholar

[23]

Grohe, M. and Schwandtner, G. 2009. The complexity of datalog on linear orders. Logical Methods Comput. Sci. 5, 1.

Crossref

Google Scholar

[24]

Imieliński, T. and Lipski Jr, W. 1984. Incomplete information in relational databases. J. ACM 31, 4, 761--791.

Digital Library

Google Scholar

[25]

Knowledge Integrity. 2003. Two sides to data decay. DM Review.

Google Scholar

[26]

Kolaitis, P. G. 2005. Schema mappings, data exchange, and metadata management. In Proceedings of the 24th Symposium on Principles of Database Systems. 61--75.

Digital Library

Google Scholar

[27]

Koubarakis, M. 1994. Database models for infinite and indefinite temporal information. Inf. Syst. 19, 2, 141--173.

Digital Library

Google Scholar

[28]

Koubarakis, M. 1997. The complexity of query evaluation in indefinite temporal constraint databases. Theor. Comput. Sci. 171, 1--2, 25--60.

Digital Library

Google Scholar

[29]

Lenzerini, M. 2002. Data integration: A theoretical perspective. In Proceedings of the 21st Symposium on Principles of Database Systems. 233--246.

Digital Library

Google Scholar

[30]

Li, P., Dong, X. L., Mauricio, A., and Srivastava, D. 2011. Linking temporal records. Proc. VLDB Endow. 4, 11, 956--967.

Digital Library

Google Scholar

[31]

Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley.

Google Scholar

[32]

Schwalb, E. and Vila, L. 1998. Temporal constraints: A survey. Constraints 3, 2--3, 129--149.

Digital Library

Google Scholar

[33]

Snodgrass, R. T. 1999. Developing Time-Oriented Database Applications in SQL. Morgan Kaufmann.

Digital Library

Google Scholar

[34]

Stockmeyer, L. J. 1976. The polynomial-time hierarchy. Theor. Comput. Sci. 3, 1, 1--22.

Crossref

Google Scholar

[35]

van der Meyden, R. 1997. The complexity of querying indefinite data about linearly ordered domains. J. Comput Syst. Sci. 54, 1, 113--135.

Digital Library

Google Scholar

[36]

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.

Digital Library

Google Scholar

[37]

Vianu, V. 1987. Dynamic functional dependencies and database aging. J. ACM 34, 1, 28--59.

Digital Library

Google Scholar

[38]

Zhang, H., Diao, Y., and Immerman, N. 2010. Recognizing patterns in streams with imprecise timestamps. Proc. VLDB Endow. 3, 1, 244--255.

Digital Library

Google Scholar

Cited By

View all

Xing AWang HBian BGuo X(2024)Contract Theory-Based Collection, Updating, and Packaging Combination Strategies in Data TradingService Science10.1287/serv.2023.001816:4(297-318)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1287/serv.2023.0018
Zhu ZFeng XFan DZhang YHu DDing XJiang Y(2024)Data Currency Quality Assessment Based on Multi-sensorAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5618-6_30(359-370)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-5618-6_30
Xie QTao GXie CWen Z(2023)Abnormal Data Detection Based on Adaptive Sliding Window and Weighted Multiscale Local Outlier Factor for Machinery Health MonitoringIEEE Transactions on Industrial Electronics10.1109/TIE.2022.323127970:11(11725-11734)Online publication date: Nov-2023
https://doi.org/10.1109/TIE.2022.3231279
Show More Cited By

Index Terms

Determining the Currency of Data
1. Information systems
  1. Data management systems
    1. Query languages
2. Theory of computation
  1. Logic
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Data currency in replicated DHTs
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Distributed Hash Tables (DHTs) provide a scalable solution for data sharing in P2P systems. To ensure high data availability, DHTs typically rely on data replication, yet without data currency guarantees. Supporting data currency in replicated DHTs is ...
Determining the currency of data
PODS '11: Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

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 ...
A Model of Economy Operation Under Currency Market Rate
Abstract
A model of functioning of an open economy with a currency market is presented. It allows determining macroeconomic indicators in the medium term with the Central Bank monetary regulation of the amount of money in circulation, interest rates, and ...

Reviews

Reviewer: Elizabeth A. Unger

Dirty data refers to inaccurate, incomplete, or erroneous data in a computer system. One form of dirty data is created when relational databases contain multiple relations for an entity. Determining which of the entity attribute values are correct or most probably correct, especially when the values do not carry timestamps, is the subject of this theoretical study. The authors propose a model using simple constraints to specify partial currency orders in the presence of copy functions. A simple copy function from one relation to another is assumed. Exploring the issues that occur when the copy function is used to create one or more tuples is the primary focus of the paper. The authors discuss what information and functions are needed to decide whether the imported information is sufficient to answer a query, and if it is not, to determine whether the copy function can be extended to bring in necessary current data for a query. Of course, this is done while assuring the constraints are met and the query set is size bounded. The paper identifies seven problems associated with data currency and currency preservation. The upper and lower bounds of these problems are determined for a variety of query languages. These results are of theoretic value and may be useful to database programmers as questions of the currency of data arise. However, most of the problems explored are intractable. The authors propose further studies using heuristic algorithms and incremental analysis to lower the complexity. A final concern is raised regarding the fundamental differences between data consistency and data currency. This paper is very readable and well organized, and the authors have made a significant intellectual addition to the study of the challenges faced in managing databases that are modified over their lifetimes. Data and database researchers and data administrators will find this paper worthwhile. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 37, Issue 4

December 2012

345 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/2389241

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2012

Accepted: 01 April 2012

Revised: 01 February 2012

Received: 01 October 2011

Published in TODS Volume 37, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
988
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)4

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xing AWang HBian BGuo X(2024)Contract Theory-Based Collection, Updating, and Packaging Combination Strategies in Data TradingService Science10.1287/serv.2023.001816:4(297-318)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1287/serv.2023.0018
Zhu ZFeng XFan DZhang YHu DDing XJiang Y(2024)Data Currency Quality Assessment Based on Multi-sensorAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5618-6_30(359-370)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-5618-6_30
Xie QTao GXie CWen Z(2023)Abnormal Data Detection Based on Adaptive Sliding Window and Weighted Multiscale Local Outlier Factor for Machinery Health MonitoringIEEE Transactions on Industrial Electronics10.1109/TIE.2022.323127970:11(11725-11734)Online publication date: Nov-2023
https://doi.org/10.1109/TIE.2022.3231279
Duan XXiao ZLiu YLi ZZhu QLang S(2023)Data relative currency repair and anomaly detection based on rulesExpert Systems with Applications10.1016/j.eswa.2023.122923(122923)Online publication date: Dec-2023
https://doi.org/10.1016/j.eswa.2023.122923
Block SBlock S(2023)Data Quality—Lifeblood of DigitalizationLarge-Scale Agile Frameworks10.1007/978-3-662-67782-7_8(295-315)Online publication date: 18-Aug-2023
https://doi.org/10.1007/978-3-662-67782-7_8
Block SBlock S(2023)Datenqualität – Lebenselixier der DigitalisierungLarge-Scale Agile Frameworks10.1007/978-3-662-62048-9_8(311-332)Online publication date: 5-Apr-2023
https://doi.org/10.1007/978-3-662-62048-9_8
Liu ZDing XJiang YHu D(2023)A Method for Identifying the Timeliness of Manufacturing Data Based on Weighted Timeliness GraphAdvanced Data Mining and Applications10.1007/978-3-031-46661-8_5(64-72)Online publication date: 27-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-46661-8_5
R. Dahlan KA. Badawi AMegahed A(2022)Perspective Chapter: Data as Currency - On the Impact of ICTs and Data on the Saudi Economy and Industrial SectorDigital Transformation - Towards New Frontiers and Business Opportunities10.5772/intechopen.103962Online publication date: 5-Oct-2022
https://doi.org/10.5772/intechopen.103962
Ding XWang HSu JWang MLi JGao H(2022)Leveraging Currency for Repairing Inconsistent and Incomplete DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.299245634:3(1288-1302)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TKDE.2020.2992456
Lortie C(2021)The early bird gets the return: The benefits of publishing your data soonerEcology and Evolution10.1002/ece3.785311:16(10736-10740)Online publication date: 6-Jul-2021
https://doi.org/10.1002/ece3.7853
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Data currency in replicated DHTs