Properties of Inconsistency Measures for Databases

Summary: Systematic investigation of properties for database inconsistency measures. Analyzes classical measures from KR and DB literature with experiments, proposes a property-driven framework for measure design, and introduces a polynomial-time measure that satisfies all properties. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6262
Venue: SIGMOD
Year: 2021
Pagerank: 5.8461093e-05
Overall Rank: 6,544 | 55.11%
DOI: 10.1145/3448016.3457310

Incoming Non-self Citations Over Time

Authors

1. Ester Livshits (Technion 2mdash Israel Institute of Technology)
2. Rina Kochirgan (Technion 2mdash Israel Institute of Technology)
3. Segev Tsur (Technion 2mdash Israel Institute of Technology)
4. Ihab F. Ilyas (University of Waterloo)
5. Benny Kimelfeld (Technion 2mdash Israel Institute of Technology)
6. Sudeepa Roy (Duke University)

BibTeX Citation

@inproceedings{livshits_sigmod21,
        title = {{Properties of Inconsistency Measures for Databases}},
        author = {Livshits, Ester and Kochirgan, Rina and Tsur, Segev and Ilyas, Ihab F. and Kimelfeld, Benny and Roy, Sudeepa},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457310},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457310},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.1504635e-05
6,576	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.8364729e-05
7,314	Time Series Data Validity	2023	SIGMOD	5.6471526e-05
8,838	The Cost of Representation by Subset Repairs	2025	VLDB	5.3592132e-05
10,429	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	5.093636e-05
10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	5.093636e-05
10,818	Evaluating Continuous Queries with Inconsistency Annotations	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
33	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00049907763
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
376	Discovering Denial Constraints	2013	VLDB	0.00019677674
533	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.0001705859
800	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013911223
1,143	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011999403
1,351	Detecting Data Errors: Where are we and what needs to be done?	2016	VLDB	0.00011064851
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.9625097e-05
1,741	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	9.8755846e-05
1,955	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.4166032e-05
2,685	Approximate Denial Constraints	2020	VLDB	8.2594662e-05
6,050	NADEEF: A Generalized Data Cleaning System	2013	VLDB	5.9945626e-05
8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.502256e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,591	Knowledge-based Integrity Constraint Validation	1986	VLDB
2	6,674	Benchmarking Approximate Consistent Query Answering	2021	PODS
3	5,648	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
4	9,025	Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems	1992	PODS
5	10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD
6	8,133	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB
7	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
8	8,506	Checking Consistency of Database Constraints: a Logical Basis	1986	VLDB
9	533	Improving Data Quality: Consistency and Accuracy	2007	VLDB
10	33	Consistent Query Answers in Inconsistent Databases	1999	PODS