{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T15:15:44Z","timestamp":1777130144440,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["GR\/S63205\/01GR\/T27433\/01EP\/E029213BB\/D006473\/1EP\/E029213"],"award-info":[{"award-number":["GR\/S63205\/01GR\/T27433\/01EP\/E029213BB\/D006473\/1EP\/E029213"]}],"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":[[2008,6]]},"abstract":"<jats:p>\n            We propose a class of integrity constraints for relational databases, referred to as\n            <jats:italic>conditional functional dependencies<\/jats:italic>\n            (CFDs), and study their applications in data cleaning. In contrast to traditional functional dependencies (FDs) that were developed mainly for schema design, CFDs aim at capturing the consistency of data by enforcing bindings of semantically related values. For static analysis of CFDs we investigate\n            <jats:italic>the consistency problem<\/jats:italic>\n            , which is to determine whether or not there exists a nonempty database satisfying a given set of CFDs, and\n            <jats:italic>the implication problem<\/jats:italic>\n            , which is to decide whether or not a set of CFDs entails another CFD. We show that while any set of transitional FDs is trivially consistent, the consistency problem is NP-complete for CFDs, but it is in PTIME when either the database schema is predefined or no attributes involved in the CFDs have a finite domain. For the implication analysis of CFDs, we provide an inference system analogous to Armstrong's axioms for FDs, and show that the implication problem is coNP-complete for CFDs in contrast to the linear-time complexity for their traditional counterpart. We also present an algorithm for computing a minimal cover of a set of CFDs. Since CFDs allow data bindings, in some cases CFDs may be physically large, complicating the detection of constraint violations. We develop techniques for detecting CFD violations in SQL as well as novel techniques for checking multiple constraints by a single query. We also provide incremental methods for checking CFDs in response to changes to the database. We experimentally verify the effectiveness of our CFD-based methods for inconsistency detection. This work not only yields a constraint theory for CFDs but is also a step toward a practical constraint-based method for improving data quality.\n          <\/jats:p>","DOI":"10.1145\/1366102.1366103","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":275,"title":["Conditional functional dependencies for capturing data inconsistencies"],"prefix":"10.1145","volume":"33","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh, Scotland and Bell Laboratories"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Scotland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xibei","family":"Jia","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Scotland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anastasios","family":"Kementsietsidis","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Hawthorne, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,6,24]]},"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.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068403001832"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the IFIP World Computer Congress. 580--583","author":"Armstrong W. W.","year":"1974","unstructured":"Armstrong , W. W. 1974 . Dependency structures of data base relationships . In Proceedings of the IFIP World Computer Congress. 580--583 .]] Armstrong, W. W. 1974. Dependency structures of data base relationships. In Proceedings of the IFIP World Computer Congress. 580--583.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1632"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Bertossi L. and Chomicki J. 2003. Query answering in inconsistent databases. In Logics for Emerging Applications of Databases. 43--83.]]  Bertossi L. and Chomicki J. 2003. Query answering in inconsistent databases. In Logics for Emerging Applications of Databases. 43--83.]]","DOI":"10.1007\/978-3-642-18690-5_2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066175"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 746--755","author":"Bohannon P.","unstructured":"Bohannon , P. , Fan , W. , Geerts , F. , Jia , X. , and Kementsietsidis , A . 2007. Conditional functional dependencies for data cleaning . In Proceedings of the International Conference on Data Engineering (ICDE). 746--755 .]] Bohannon, P., Fan, W., Geerts, F., Jia, X., and Kementsietsidis, A. 2007. Conditional functional dependencies for data cleaning. In Proceedings of the International Conference on Data Engineering (ICDE). 746--755.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Bra P. D. and Paredaens J. 1983. Conditional dependencies for horizontal decompositions. In Colloquium on Automata Languages and Programming. 67--82.]]   Bra P. D. and Paredaens J. 1983. Conditional dependencies for horizontal decompositions. In Colloquium on Automata Languages and Programming. 67--82.]]","DOI":"10.1007\/BFb0036898"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence. 10--15","author":"Bravo L.","unstructured":"Bravo , L. and Bertossi , L . 2003. Logic programs for consistently querying data integration systems . In Proceedings of the International Joint Conference on Artificial Intelligence. 10--15 .]] Bravo, L. and Bertossi, L. 2003. Logic programs for consistently querying data integration systems. In Proceedings of the International Joint Conference on Artificial Intelligence. 10--15.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497460"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 243--254","author":"Bravo L.","unstructured":"Bravo , L. , Fan , W. , and Ma , S . 2007. Extending dependencies with conditions . In Proceedings of the International Conference on Very Large Databases (VLDB). 243--254 .]] Bravo, L., Fan, W., and Ma, S. 2007. Extending dependencies with conditions. In Proceedings of the International Conference on Very Large Databases (VLDB). 243--254.]]"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Advances in Intelligent Data Analysis (IDA). 84--94","author":"Bruni R.","unstructured":"Bruni , R. and Sassano , A . 2001. Errors detection and correction in large scale data collecting . In Proceedings of the International Conference on Advances in Intelligent Data Analysis (IDA). 84--94 .]] Bruni, R. and Sassano, A. 2001. Errors detection and correction in large scale data collecting. In Proceedings of the International Conference on Advances in Intelligent Data Analysis (IDA). 84--94.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773179"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence. 16--21","author":"Cali A.","unstructured":"Cali , A. , Lembo , D. , and Rosati , R . 2003b. Query rewriting and answering under constraints in data integration systems . In Proceedings of the International Joint Conference on Artificial Intelligence. 16--21 .]] Cali, A., Lembo, D., and Rosati, R. 2003b. Query rewriting and answering under constraints in data integration systems. In Proceedings of the International Joint Conference on Artificial Intelligence. 16--21.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Chomicki J. and Marcinkowski J. 2005b. On the computational complexity of minimal-change integrity maintenance in relational databases. In Inconsistency Tolerance. 119--150.]]   Chomicki J. and Marcinkowski J. 2005b. On the computational complexity of minimal-change integrity maintenance in relational databases. In Inconsistency Tolerance. 119--150.]]","DOI":"10.1007\/978-3-540-30597-2_5"},{"key":"e_1_2_1_19_1","series-title":"Database Systems: Courant Computer Science Symposia Series 6","volume-title":"Relational completeness of data base sublanguages","author":"Codd E. F.","unstructured":"Codd , E. F. 1972. Relational completeness of data base sublanguages . In Database Systems: Courant Computer Science Symposia Series 6 . Prentice-Hall , 65--98.]] Codd, E. F. 1972. Relational completeness of data base sublanguages. In Database Systems: Courant Computer Science Symposia Series 6. Prentice-Hall, 65--98.]]"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 315--326","author":"Cong G.","unstructured":"Cong , G. , Fan , W. , Geerts , F. , Jia , X. , and Ma , S . 2007. Improving data quality: Consistency and accuracy . In Proceedings of the International Conference on Very Large Databases (VLDB). 315--326 .]] Cong, G., Fan, W., Geerts, F., Jia, X., and Ma, S. 2007. Improving data quality: Consistency and accuracy. In Proceedings of the International Conference on Very Large Databases (VLDB). 315--326.]]"},{"key":"e_1_2_1_21_1","volume-title":"Data quality and the bottom line: Achieving business success through a commitment to high quality data. Tech. rep","author":"Eckerson W. W.","unstructured":"Eckerson , W. W. 2002. Data quality and the bottom line: Achieving business success through a commitment to high quality data. Tech. rep ., The Data Warehousing Institute . http:\/\/www.tdwi.org\/research\/display.aspx?ID=6064.]] Eckerson, W. W. 2002. Data quality and the bottom line: Achieving business success through a commitment to high quality data. Tech. rep., The Data Warehousing Institute. http:\/\/www.tdwi.org\/research\/display.aspx?ID=6064.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1976.10481472"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10501049"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Artificial Intelligence on Logic for Programming (LPAR). 561--578","author":"Franconi E.","unstructured":"Franconi , E. , Palma , A. L. , Leone , N. , Perri , S. , and Scarcello , F . 2001. Census data repair: a challenging application of disjunctive logic programming . In Proceedings of the Artificial Intelligence on Logic for Programming (LPAR). 561--578 .]] Franconi, E., Palma, A. L., Leone, N., Perri, S., and Scarcello, F. 2001. Census data repair: a challenging application of disjunctive logic programming. In Proceedings of the Artificial Intelligence on Logic for Programming (LPAR). 561--578.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.336568"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 371--380","author":"Galhardas H.","unstructured":"Galhardas , H. , Florescu , D. , Shasha , D. , Simon , E. , and Saita , C . -A. 2001. Declarative data cleaning: Language, model and algorithms . In Proceedings of the International Conference on Very Large Databases (VLDB). 371--380 .]] Galhardas, H., Florescu, D., Shasha, D., Simon, E., and Saita, C.-A. 2001. Declarative data cleaning: Language, model and algorithms. In Proceedings of the International Conference on Very Large Databases (VLDB). 371--380.]]"},{"key":"e_1_2_1_27_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.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/40283.40291"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the International Workshop on Principles of Diagnosis (DX). 65--72","author":"Gertz M.","unstructured":"Gertz , M. and Lipeck , U . 1995. A diagnostic approach to repairing constraint violations in databases . In Proceedings of the International Workshop on Principles of Diagnosis (DX). 65--72 .]] Gertz, M. and Lipeck, U. 1995. A diagnostic approach to repairing constraint violations in databases. In Proceedings of the International Workshop on Principles of Diagnosis (DX). 65--72.]]"},{"key":"e_1_2_1_30_1","volume-title":"The Problem of Incomplete Information in Relational Databases","author":"Grahne G.","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_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1245280"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009761603038"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(95)00185-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00193-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/237661.237693"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322223"},{"key":"e_1_2_1_38_1","volume-title":"The Theory of Relational Databases","author":"Maier D.","unstructured":"Maier , D. 1983. The Theory of Relational Databases . Computer Science Press .]] Maier, D. 1983. The Theory of Relational Databases. Computer Science Press.]]"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the Conference on Information Quality (IQ). 200--209","author":"Maletic J. I.","unstructured":"Maletic , J. I. and Marcus , A . 2000. Data cleansing: Beyond integrity analysis . In Proceedings of the Conference on Information Quality (IQ). 200--209 .]] Maletic, J. I. and Marcus, A. 2000. Data cleansing: Beyond integrity analysis. In Proceedings of the Conference on Information Quality (IQ). 200--209.]]"},{"key":"e_1_2_1_40_1","first-page":"14","article-title":"Matching algorithms within a duplicate detection system","volume":"23","author":"Monge A. E.","year":"2000","unstructured":"Monge , A. E. 2000 . Matching algorithms within a duplicate detection system . IEEE Data Eng. Bull. 23 , 4, 14 -- 20 .]] Monge, A. E. 2000. Matching algorithms within a duplicate detection system. IEEE Data Eng. Bull. 23, 4, 14--20.]]","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_41_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","unstructured":"Papadimitriou , C. H. 1994. Computational Complexity . Addison Wesley .]] Papadimitriou, C. H. 1994. Computational Complexity. Addison Wesley.]]"},{"key":"e_1_2_1_42_1","first-page":"3","article-title":"Data cleaning: Problems and current approaches","volume":"23","author":"Rahm E.","year":"2000","unstructured":"Rahm , E. and Do , H. H. 2000 . Data cleaning: Problems and current approaches . IEEE Data Eng. Bull. 23 , 4, 3 -- 13 .]] Rahm, E. and Do, H. H. 2000. Data cleaning: Problems and current approaches. IEEE Data Eng. Bull. 23, 4, 3--13.]]","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB). 381--390","author":"Raman V.","unstructured":"Raman , V. and Hellerstein , J. M . 2001. Potter's wheel: An interactive data cleaning system . In Proceedings of the International Conference on Very Large Databases (VLDB). 381--390 .]] Raman, V. and Hellerstein, J. M. 2001. Potter's wheel: An interactive data cleaning system. In Proceedings of the International Conference on Very Large Databases (VLDB). 381--390.]]"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322312"},{"key":"e_1_2_1_46_1","unstructured":"Shilakes C. C. and Tylman J. 1998. Enterprise information portals. Tech. rep. Merrill Lynch Inc. New York NY.]]  Shilakes C. C. and Tylman J. 1998. Enterprise information portals. Tech. rep. Merrill Lynch Inc. New York NY.]]"},{"key":"e_1_2_1_47_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2003. Approximation Algorithms . Springer .]] Vazirani, V. V. 2003. Approximation Algorithms. Springer.]]"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1093382.1093385"},{"key":"e_1_2_1_49_1","volume-title":"Statistical Research Division","author":"Winkler W. E.","unstructured":"Winkler , W. E. 1994. Advanced methods for record linkage. Tech. rep ., Statistical Research Division , U.S. Bureau of the Census.]] Winkler, W. E. 1994. Advanced methods for record linkage. Tech. rep., Statistical Research Division, U.S. Bureau of the Census.]]"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the American Statistical Association. Section on Survey Research Methods. 564--569","author":"Winkler W. E.","year":"1997","unstructured":"Winkler , W. E. 1997 . Set-covering and editing discrete data . In Proceedings of the American Statistical Association. Section on Survey Research Methods. 564--569 .]] Winkler, W. E. 1997. Set-covering and editing discrete data. In Proceedings of the American Statistical Association. Section on Survey Research Methods. 564--569.]]"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2003.12.003"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1366102.1366103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1366102.1366103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:39Z","timestamp":1750255059000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1366102.1366103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1366102.1366103"],"URL":"https:\/\/doi.org\/10.1145\/1366102.1366103","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}