{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T11:17:40Z","timestamp":1773314260751,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,6,29]],"date-time":"2017-06-29T00:00:00Z","timestamp":1498694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61572272, 61325008, 61370055 and 61202008"],"award-info":[{"award-number":["61572272, 61325008, 61370055 and 61202008"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Tsinghua University Initiative Scientific Research Program"},{"name":"National Key Research Program of China","award":["2016YFB1001101"],"award-info":[{"award-number":["2016YFB1001101"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,11,30]]},"abstract":"<jats:p>\n            <jats:italic>Matching dependencies<\/jats:italic>\n            (MDs) have recently been proposed to make data dependencies tolerant to various information representations, and found useful in data quality applications such as record matching. Instead of the strict equality function used in traditional dependency syntax (e.g., functional dependencies), MDs specify constraints based on similarity and identification. However, in practice, MDs may still be too strict and applicable only in a subset of tuples in a relation. Thereby, we study the\n            <jats:italic>conditional matching dependencies<\/jats:italic>\n            (CMDs), which bind matching dependencies only in a certain part of a table, i.e., MDs conditionally applicable in a subset of tuples. Compared to MDs, CMDs have more expressive power that enables them to satisfy wider application needs. In this article, we study several important theoretical and practical issues of CMDs, including irreducible CMDs with respect to the implication, discovery of CMDs from data, reliable CMDs agreed most by a relation, approximate CMDs almost satisfied in a relation, and finally applications of CMDs in record matching and missing value repairing. Through an extensive experimental evaluation in real data sets, we demonstrate the efficiency of proposed CMDs discovery algorithms and effectiveness of CMDs in real applications.\n          <\/jats:p>","DOI":"10.1145\/3070647","type":"journal-article","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T12:36:19Z","timestamp":1498826179000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Discovering Conditional Matching Rules"],"prefix":"10.1145","volume":"11","author":[{"given":"Yihan","family":"Wang","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaoxu","family":"Song","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, N. T., Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, N. T., Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856328"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_1_3_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646419.693645"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398580"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11733836_45"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2003.1234765"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Annual IEEE International Conference on Data Engineering (ICDE\u201989)","author":"Bitton Dina","year":"1989","unstructured":"Dina Bitton , Jeffrey Millman , and Solveig Torgersen . 1989 . A feasibility and performance study of dependency inference . In Proceedings of the Annual IEEE International Conference on Data Engineering (ICDE\u201989) . 635--641. Dina Bitton, Jeffrey Millman, and Solveig Torgersen. 1989. A feasibility and performance study of dependency inference. In Proceedings of the Annual IEEE International Conference on Data Engineering (ICDE\u201989). 635--641."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367920"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497460"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201907)","author":"Bravo Loreto","year":"2007","unstructured":"Loreto Bravo , Wenfei Fan , and Shuai Ma . 2007 . Extending dependencies with conditions . In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201907) . 243--254. Loreto Bravo, Wenfei Fan, and Shuai Ma. 2007. Extending dependencies with conditions. In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201907). 243--254."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2472010"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247530"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453980"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201907)","author":"Cong Gao","year":"2007","unstructured":"Gao Cong , Wenfei Fan , Floris Geerts , Xibei Jia , and Shuai Ma . 2007 . Improving data quality: Consistency and accuracy . In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201907) . 315--326. Gao Cong, Wenfei Fan, Floris Geerts, Xibei Jia, and Shuai Ma. 2007. Improving data quality: Consistency and accuracy. In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201907). 315--326."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465327"},{"key":"e_1_2_1_18_1","volume-title":"Ives","author":"Doan AnHai","year":"2012","unstructured":"AnHai Doan , Alon Y. Halevy , and Zachary G . Ives . 2012 . Principles of Data Integration. Morgan Kaufmann . AnHai Doan, Alon Y. Halevy, and Zachary G. Ives. 2012. Principles of Data Integration. Morgan Kaufmann."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376940"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0206-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.208"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687674"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453901"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_27_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2003.10.006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687693"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453900"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824122"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732240.2732248"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223807"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/645483.656220"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007641"},{"key":"e_1_2_1_38_1","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","unstructured":"R. M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations , R. E. Miller and J. W. Thatcher (Eds.), Plenum Press , 85--103. R. M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.), Plenum Press, 85--103."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747646"},{"key":"e_1_2_1_40_1","first-page":"49","article-title":"Discovery of functional and approximate functional dependencies in relational databases","volume":"7","author":"King Ronald S.","year":"2003","unstructured":"Ronald S. King and James J. Legendre . 2003 . Discovery of functional and approximate functional dependencies in relational databases . JAMDS 7 , 1 (2003), 49 -- 59 . Ronald S. King and James J. Legendre. 2003. Discovery of functional and approximate functional dependencies in relational databases. JAMDS 7, 1 (2003), 49--59.","journal-title":"JAMDS"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00028-U"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514901"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201903)","author":"Korn Flip","year":"2003","unstructured":"Flip Korn , S. Muthukrishnan , and Yunyue Zhu . 2003 . Checks and balances: Monitoring data quality problems in network traffic databases . In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201903) . 536--547. Flip Korn, S. Muthukrishnan, and Yunyue Zhu. 2003. Checks and balances: Monitoring data quality problems in network traffic databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201903). 536--547."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.219"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD\u201996)","author":"Kramer Stefan","year":"1996","unstructured":"Stefan Kramer and Bernhard Pfahringer . 1996 . Efficient search for strong partial determinations . In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD\u201996) . 371--374. Stefan Kramer and Bernhard Pfahringer. 1996. Efficient search for strong partial determinations. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD\u201996). 371--374."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB\u201987)","author":"Mannila Heikki","year":"1987","unstructured":"Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4 . 1987 . Dependency inference . In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201987) . 155--158. Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4. 1987. Dependency inference. In Proceedings of the International Conference on Very Large Data Bases (VLDB\u201987). 155--158."},{"key":"e_1_2_1_47_1","volume-title":"Design of Relational Databases","author":"Mannila Heikki","unstructured":"Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4 . 1992. Design of Relational Databases . Addison-Wesley . Heikki Mannila and Kari-Jouko R\u00e4ih\u00e4. 1992. Design of Relational Databases. Addison-Wesley."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0169-023X(94)90023-X"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD\u201995)","author":"Pfahringer Bernhard","year":"1995","unstructured":"Bernhard Pfahringer and Stefan Kramer . 1995 . Compression-based evaluation of partial determinations . In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD\u201995) . 234--239. Bernhard Pfahringer and Stefan Kramer. 1995. Compression-based evaluation of partial determinations. In Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD\u201995). 234--239."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/3091529.3091566"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI\u201905)","author":"Shen Warren","year":"2005","unstructured":"Warren Shen , Xin Li , and AnHai Doan . 2005 . Constraint-based entity matching . In Proceedings of the National Conference on Artificial Intelligence (AAAI\u201905) . 862--867. Warren Shen, Xin Li, and AnHai Doan. 2005. Constraint-based entity matching. In Proceedings of the National Conference on Artificial Intelligence (AAAI\u201905). 862--867."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646135"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000826"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2013.06.003"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732991"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 8th International Workshop on Quality in Databases.","author":"Song Shaoxu","year":"2010","unstructured":"Shaoxu Song , Lei Chen , and Jeffrey Xu Yu . 2010 . Extending matching rules with conditions . In Proceedings of the 8th International Workshop on Quality in Databases. Shaoxu Song, Lei Chen, and Jeffrey Xu Yu. 2010. Extending matching rules with conditions. In Proceedings of the 8th International Workshop on Quality in Databases."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767857"},{"key":"e_1_2_1_59_1","unstructured":"C. J. van Rijsbergen. 1979. Information Retrieval. Butterworth.   C. J. van Rijsbergen. 1979. Information Retrieval. Butterworth."},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the WebDB Workshop.","author":"Wang Daisy Zhe","unstructured":"Daisy Zhe Wang , Xin Luna Dong , Anish Das Sarma , Michael J. Franklin , and Alon Y. Halevy . 2009. Functional dependency generation and applications in pay-as-you-go data integration systems . In Proceedings of the WebDB Workshop. Daisy Zhe Wang, Xin Luna Dong, Anish Das Sarma, Michael J. Franklin, and Alon Y. Halevy. 2009. Functional dependency generation and applications in pay-as-you-go data integration systems. In Proceedings of the WebDB Workshop."},{"key":"e_1_2_1_61_1","volume-title":"Robertson","author":"Wyss Catharine M.","year":"2001","unstructured":"Catharine M. Wyss , Chris Giannella , and Edward L . Robertson . 2001 . FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances -- Extended abstract. In Proceedings of the DaWaK. 101--110. Catharine M. Wyss, Chris Giannella, and Edward L. Robertson. 2001. FastFDs: A heuristic-driven, depth-first algorithm for mining functional dependencies from relation instances -- Extended abstract. In Proceedings of the DaWaK. 101--110."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070647","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3070647","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:27Z","timestamp":1750217427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070647"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,29]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11,30]]}},"alternative-id":["10.1145\/3070647"],"URL":"https:\/\/doi.org\/10.1145\/3070647","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,29]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}