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: hb6cb00662c41cff3
Venue: SIGMOD
Year: 2021
Pagerank: 5.9663944e-05
Overall Rank: 5,864 | 60.58%
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 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,067	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.8216078e-05
6,699	Toward Interpretable and Actionable Data Analysis with Explanations and Causality	2022	VLDB	5.7058728e-05
7,463	Time Series Data Validity	2023	SIGMOD	5.5204457e-05
9,004	The Cost of Representation by Subset Repairs	2025	VLDB	5.2389669e-05
10,195	Evaluating Continuous Queries with Inconsistency Annotations	2025	VLDB	5.0623376e-05
10,618	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	4.9793485e-05
10,795	Measuring Database Unfairness via Dependency Quantification Under Differential Privacy	2026	VLDB	4.9793485e-05
10,832	ReSequel: Robust LLM-assisted Query Rewriting and Optimization using Templatization and Sampling	2026	VLDB	4.9793485e-05
11,202	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.9793485e-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.00049349003
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033690989
350	Discovering Denial Constraints	2013	VLDB	0.00020253521
526	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00016886621
767	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00014114806
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011771949
1,344	Detecting Data Errors: Where are we and what needs to be done?	2016	VLDB	0.00010956518
1,361	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010917917
1,619	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	0.00010055625
1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.7545681e-05
1,971	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2873596e-05
2,443	Approximate Denial Constraints	2020	VLDB	8.4586656e-05
6,152	NADEEF: A Generalized Data Cleaning System	2013	VLDB	5.8693135e-05
8,194	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.379983e-05

Semantically Similar Papers

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