Selective Provenance for Datalog Programs Using Top-K Queries

Summary: Top-k how-provenance for Datalog via a tree-pattern selection and ranking over derivations. An instrumented, bottom-up evaluation generates only relevant provenance, achieving polynomial data complexity and linear-time top-k construction, with scalable experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11018
Venue: VLDB
Year: 2015
Pagerank: 4.9704872e-05
Overall Rank: 6,662 | 53.66%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,851	Provenance for Natural Language Queries	2017	VLDB	5.8768322e-05
5,209	Explaining Outputs in Modern Data Analytics	2016	VLDB	5.629362e-05
6,975	NLProveNAns: Natural Language Provenance for Non-Answers	2018	VLDB	4.8772572e-05
7,066	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8445108e-05
7,482	Provenance-Enabled Explainable AI	2024	SIGMOD	4.7180617e-05
8,394	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.527807e-05
9,622	NLProv: Natural Language Provenance	2016	VLDB	4.3163112e-05
10,147	Causal Explanations for Disparate Trends: Where and Why?	2026	SIGMOD	4.1945683e-05
11,681	Datalignment: Ontology Schema Alignment Through Datalog Containment	2019	VLDB	4.1945683e-05
11,733	Provenance Summaries for Answers and Non-Answers	2018	VLDB	4.1945683e-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
31	Provenance Semirings	2007	PODS	0.0007857786
778	Declarative Networking: Language, Execution and Optimization	2006	SIGMOD	0.00016791276
923	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD	0.0001527609
942	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015155714
1,371	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012323502
1,861	Efficient Provenance Storage	2008	SIGMOD	0.00010287053
2,173	Querying Data Provenance	2010	SIGMOD	9.3676609e-05
2,978	Matching Twigs in Probabilistic XML	2007	VLDB	7.7845728e-05
3,218	Reverse Data Management	2011	VLDB	7.3592173e-05
3,251	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3215694e-05
4,706	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9820914e-05
5,266	Probabilistic Databases with MarkoViews	2012	VLDB	5.5972559e-05
6,943	TRAMP: Understanding the Behavior of Schema Mappings through Provenance	2010	VLDB	4.8916728e-05
8,054	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	4.5947587e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,145	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5761263e-05
9,813	Datalog with First-Class Facts	2025	VLDB	4.2783272e-05
8,960	Computing How-Provenance for SPARQL Queries via Query Rewriting	2021	VLDB	4.4206222e-05
1,106	Provenance for Aggregate Queries	2011	PODS	0.0001398766
8,394	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.527807e-05
4,851	Provenance for Natural Language Queries	2017	VLDB	5.8768322e-05
6,186	On Provenance Minimization	2011	PODS	5.166082e-05
2,173	Querying Data Provenance	2010	SIGMOD	9.3676609e-05
8,125	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5797807e-05
10,922	Below and Above Why-Provenance for Datalog Queries	2024	PODS	4.1945683e-05