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: 12105
Venue: VLDB
Year: 2020
Pagerank: 4.5761263e-05
Overall Rank: 8,145 | 43.34%
DOI: 10.14778/3407790.3407815

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
7,667	Fast Detection of Denial Constraint Violations	2022	VLDB	4.683767e-05
10,546	Evaluating Continuous Queries with Inconsistency Annotations	2025	VLDB	4.1945683e-05
11,462	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	4.1945683e-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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
31	Provenance Semirings	2007	PODS	0.0007857786
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035728858
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
2,566	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5243847e-05
2,961	Evaluating Rank Joins with Optimal Cost	2008	PODS	7.8110394e-05
3,807	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.747576e-05
3,908	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6392878e-05
5,360	Counting Database Repairs under Primary Keys Revisited	2019	PODS	5.5481038e-05
5,618	Explaining Repaired Data with CFDs	2018	VLDB	5.4079415e-05
7,702	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6736471e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
3,095	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.5692859e-05
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05
6,662	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB	4.9704872e-05
6,705	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9549359e-05
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067660624
10,970	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1945683e-05
11,462	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	4.1945683e-05
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364
6,546	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.0185588e-05