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: 12106
Venue: VLDB
Year: 2020
Pagerank: 4.5717374e-05
Overall Rank: 8,148 | 43.38%
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,470	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0439835e-05
7,666	Fast Detection of Denial Constraint Violations	2022	VLDB	4.6792751e-05
10,555	Evaluating Continuous Queries with Inconsistency Annotations	2025	VLDB	4.1905499e-05
11,465	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	4.1905499e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
31	Provenance Semirings	2007	PODS	0.00078516827
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067607389
192	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00035692958
556	Discovering Denial Constraints	2013	VLDB	0.00020214701
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
1,101	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014037952
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
2,574	Database Repairs and Consistent Query Answering: Origins and Further Developments	2019	PODS	8.5126812e-05
2,965	Evaluating Rank Joins with Optimal Cost	2008	PODS	7.8049517e-05
3,809	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.7413981e-05
3,911	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6343292e-05
5,370	Counting Database Repairs under Primary Keys Revisited	2019	PODS	5.5427744e-05
5,626	Explaining Repaired Data with CFDs	2018	VLDB	5.4032498e-05
7,701	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6690279e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
3,100	Answering Why-not Questions on Reverse Top-k Queries	2015	VLDB	7.5625111e-05
7,660	Processing Top-k Join Queries	2010	VLDB	4.6814547e-05
6,665	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB	4.9657158e-05
6,707	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD	4.9500448e-05
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067607389
10,973	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.1905499e-05
11,465	INCA: Inconsistency-Aware Data Profiling and Querying	2021	SIGMOD	4.1905499e-05
1,101	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014037952
6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.013741e-05