2017/08/30 by Ester Livshits, Livshits, Ester, Benny Kimelfeld +1
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.1708.09140
openalex publication_date 2017/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a relation that violates a set of functional dependencies, we consider\nthe task of finding a maximum number of pairwise-consistent tuples, or what is\nknown as a "cardinality repair." We present a polynomial-time algorithm that,\nfor certain fixed relation schemas (with functional dependencies), computes a\ncardinality repair. Moreover, we prove that on any of the schemas not covered\nby the algorithm, finding a cardinality repair is, in fact, an NP-hard problem.\nIn particular, we establish a dichotomy in the complexity of computing a\ncardinality repair, and we present an efficient algorithm to determine whether\na given schema belongs to the positive side or the negative side of the\ndichotomy.\n