{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T00:46:16Z","timestamp":1791074776066,"version":"4.1.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n                    Conditional functional dependencies (CFDs) have recently been proposed as a useful integrity constraint to summarize data semantics and identify data inconsistencies. A CFD augments a functional dependency (FD) with a\n                    <jats:italic>pattern tableau<\/jats:italic>\n                    that defines the context (i.e., the subset of tuples) in which the underlying FD holds. While many aspects of CFDs have been studied, including static analysis and detecting and repairing violations, there has not been prior work on generating pattern tableaux, which is critical to realize the full potential of CFDs.\n                  <\/jats:p>\n                  <jats:p>\n                    This paper is the first to formally characterize a \"good\" pattern tableau, based on naturally desirable properties of support, confidence and parsimony. We show that the problem of generating an optimal tableau for a given FD is NP-complete but can be approximated in polynomial time via a greedy algorithm. For large data sets, we propose an \"on-demand\" algorithm providing the same approximation bound, that outperforms the basic greedy algorithm in running time by an order of magnitude. For ordered attributes, we propose the\n                    <jats:italic>range tableau<\/jats:italic>\n                    as a generalization of a pattern tableau, which can achieve even more parsimony. The effectiveness and efficiency of our techniques are experimentally demonstrated on real data.\n                  <\/jats:p>","DOI":"10.14778\/1453856.1453900","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T08:17:57Z","timestamp":1403597877000},"page":"376-390","source":"Crossref","is-referenced-by-count":121,"title":["On generating near-optimal tableaux for conditional functional dependencies"],"prefix":"10.14778","volume":"1","author":[{"given":"Lukasz","family":"Golab","sequence":"first","affiliation":[{"name":"AT&amp;T Labs - Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Howard","family":"Karloff","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Flip","family":"Korn","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bei","family":"Yu","sequence":"additional","affiliation":[{"name":"Nat'l University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281197"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170072"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/646229.681551"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367920"},{"key":"e_1_2_1_5_1","volume-title":"VLDB","author":"Bravo L.","year":"2007","unstructured":"L. Bravo , W. Fan , and S. Ma . Extending dependencies with conditions . In VLDB , 2007 . L. Bravo, W. Fan, and S. Ma. Extending dependencies with conditions. In VLDB, 2007."},{"key":"e_1_2_1_6_1","volume-title":"VLDB","author":"Brown P.","year":"2003","unstructured":"P. Brown , P. Haas . BHUNT : Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data . In VLDB , 2003 . P. Brown, P. Haas. BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data. In VLDB, 2003."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/581751.581752"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206049.1206055"},{"key":"e_1_2_1_9_1","volume-title":"VLDB","author":"Cong G.","year":"2007","unstructured":"G. Cong , W. Fan , F. Geerts , X. Jia , and S. Ma . Improving data quality: consistency and accuracy . In VLDB , 2007 . G. Cong, W. Fan, F. Geerts, X. Jia, and S. Ma. Improving data quality: consistency and accuracy. In VLDB, 2007."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.336059"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.002"},{"key":"e_1_2_1_12_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP---Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP---Completeness . Freeman , San Francisco , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP---Completeness. Freeman, San Francisco, 1979."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2003.10.006"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007641"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/200548"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1155\/S117391260300004X"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00028-U"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017093"},{"key":"e_1_2_1_20_1","first-page":"42","volume-title":"VLDB","author":"Sarawagi S.","year":"1999","unstructured":"S. Sarawagi . Explaining differences in multidimensional aggregates . In VLDB , pp 42 -- 53 , 1999 . S. Sarawagi. Explaining differences in multidimensional aggregates. In VLDB, pp 42--53, 1999."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233311"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T06:07:04Z","timestamp":1672207624000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453900"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453900","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}