Efficient Querying of Inconsistent Databases with Binary Integer Programming

Summary: EQUIP computes consistent answers to conjunctive queries under primary-key constraints without materializing repairs, using iterative Binary Integer Programming to eliminate candidates. It is especially effective when answers are not first-order rewritable and scales robustly. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10893
Venue: VLDB
Year: 2013
Pagerank: 8.4290374e-05
Overall Rank: 2,551 | 82.50%
DOI: 10.14778/2536336.2536337

Incoming Non-self Citations Over Time

Authors

1. Phokion G. Kolaitis (IBM; University of California Santa Cruz)
2. Enela Pema (University of California Santa Cruz)
3. Wang-Chiew Tan (University of California Santa Cruz)

BibTeX Citation

@article{kolaitis_vldb13,
        title = {{Efficient Querying of Inconsistent Databases with Binary Integer Programming}},
        author = {Kolaitis, Phokion G. and Pema, Enela and Tan, Wang-Chiew},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {6},
        pages = {397--408},
        doi = {10.14778/2536336.2536337},
        url = {https://doi.org/10.14778/2536336.2536337},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,361	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.4872032e-05
4,811	Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers	2019	SIGMOD	6.4983069e-05
5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS	6.0926349e-05
6,674	Benchmarking Approximate Consistent Query Answering	2021	PODS	5.8066263e-05
7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS	5.5993651e-05
8,103	The Computation of Optimal Subset Repairs	2020	VLDB	5.4867244e-05
8,228	CAvSAT: A System for Query Answering over Inconsistent Databases	2019	SIGMOD	5.4621278e-05
9,480	CAvSAT: Answering Aggregation Queries over Inconsistent Databases via SAT Solving	2021	SIGMOD	5.2634238e-05
11,121	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS	5.093636e-05
11,146	Computing Range Consistent Answers to Aggregation Queries via Rewriting	2024	PODS	5.093636e-05
11,384	LinCQA: Faster Consistent Query Answering with Linear Time Guarantees	2023	SIGMOD	5.093636e-05
11,524	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS	5.093636e-05
12,210	Certain Query Answering in Partially Consistent Databases	2014	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
344	On the Power of Magic	1987	PODS	0.00020659405
586	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD	0.00016124396
734	QAGen: Generating Query-Aware Test Databases	2007	SIGMOD	0.00014525584

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,558	Consistent Query Answering for Primary Keys on Path Queries	2021	PODS
2	5,619	An Operational Approach to Consistent Query Answering	2018	PODS
3	11,524	A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys	2022	PODS
4	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
5	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
6	5,773	Consistent Query Answering for Primary Keys and Conjunctive Queries with Negated Atoms	2018	PODS
7	5,648	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
8	586	ConQuer: Efficient Management of Inconsistent Databases	2005	SIGMOD
9	6,674	Benchmarking Approximate Consistent Query Answering	2021	PODS
10	33	Consistent Query Answers in Inconsistent Databases	1999	PODS