Evaluating Top-k Queries with Inconsistency Degrees

Summary: Proposes inconsistency-aware top-k evaluation under denial constraints, with two inconsistency measures (single/multi) quantified by why-provenance and provenance polynomials. Presents a top-k algorithm for monotone/non-monotone scoring, with gains over full ranking. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12293
Venue: VLDB
Year: 2020
Pagerank: 5.4813895e-05
Overall Rank: 8,133 | 44.21%
DOI: 10.14778/3407790.3407815

Incoming Non-self Citations Over Time

Authors

1. Ousmane Issa (University Clermont Auvergne)
2. Angela Bonifati (Lyon 1 University)
3. Farouk Toumani (University Clermont Auvergne)

BibTeX Citation

@article{issa_vldb20,
        title = {{Evaluating Top-k Queries with Inconsistency Degrees}},
        author = {Issa, Ousmane and Bonifati, Angela and Toumani, Farouk},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {2146--2158},
        doi = {10.14778/3407790.3407815},
        url = {https://doi.org/10.14778/3407790.3407815},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,611	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.1504635e-05
7,396	Fast Detection of Denial Constraint Violations	2022	VLDB	5.6257228e-05
10,818	Evaluating Continuous Queries with Inconsistency Annotations	2025	VLDB	5.093636e-05
11,660	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
17	Provenance Semirings	2007	PODS	0.00059843817
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
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
806	Provenance for Aggregate Queries	2011	PODS	0.00013890398
874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00013481551
2,565	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.4116912e-05
2,585	Evaluating Rank Joins with Optimal Cost	2008	PODS	8.3774452e-05
3,500	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.3597562e-05
3,706	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.1819534e-05
5,258	Counting Database Repairs under Primary Keys Revisited	2019	PODS	6.2967016e-05
5,312	Explaining Repaired Data with CFDs	2018	VLDB	6.2698779e-05
8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.502256e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	635	Evaluating Top-k Selection Queries	1999	VLDB
2	2,895	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB
3	7,550	Processing Top-k Join Queries	2010	VLDB
4	6,587	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB
5	5,648	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
6	33	Consistent Query Answers in Inconsistent Databases	1999	PODS
7	11,183	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD
8	11,660	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD
9	874	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
10	6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD