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: 11019
Venue: VLDB
Year: 2015
Pagerank: 4.9657158e-05
Overall Rank: 6,665 | 53.68%
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,853	Provenance for Natural Language Queries	2017	VLDB	5.8711821e-05
5,212	Explaining Outputs in Modern Data Analytics	2016	VLDB	5.6239563e-05
6,974	NLProveNAns: Natural Language Provenance for Non-Answers	2018	VLDB	4.8725777e-05
7,062	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	4.8398632e-05
7,481	Provenance-Enabled Explainable AI	2024	SIGMOD	4.7135369e-05
8,392	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.5234647e-05
9,622	NLProv: Natural Language Provenance	2016	VLDB	4.3121745e-05
10,147	Causal Explanations for Disparate Trends: Where and Why?	2026	SIGMOD	4.1905499e-05
11,686	Datalignment: Ontology Schema Alignment Through Datalog Containment	2019	VLDB	4.1905499e-05
11,740	Provenance Summaries for Answers and Non-Answers	2018	VLDB	4.1905499e-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.00078516827
774	Declarative Networking: Language, Execution and Optimization	2006	SIGMOD	0.00016775162
921	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD	0.00015261463
943	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015140995
1,376	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012315734
1,864	Efficient Provenance Storage	2008	SIGMOD	0.00010277171
2,182	Querying Data Provenance	2010	SIGMOD	9.3596252e-05
2,981	Matching Twigs in Probabilistic XML	2007	VLDB	7.7783189e-05
3,224	Reverse Data Management	2011	VLDB	7.3523336e-05
3,256	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.3135363e-05
4,708	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	5.9763416e-05
5,270	Probabilistic Databases with MarkoViews	2012	VLDB	5.5925747e-05
6,947	TRAMP: Understanding the Behavior of Schema Mappings through Provenance	2010	VLDB	4.8869805e-05
8,056	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	4.5903524e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,148	Evaluating Top-k Queries with Inconsistency Degrees	2020	VLDB	4.5717374e-05
9,812	Datalog with First-Class Facts	2025	VLDB	4.2742278e-05
8,965	Computing How-Provenance for SPARQL Queries via Query Rewriting	2021	VLDB	4.4163852e-05
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
8,392	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.5234647e-05
4,853	Provenance for Natural Language Queries	2017	VLDB	5.8711821e-05
6,187	On Provenance Minimization	2011	PODS	5.1611195e-05
2,182	Querying Data Provenance	2010	SIGMOD	9.3596252e-05
8,129	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5753896e-05
10,926	Below and Above Why-Provenance for Datalog Queries	2024	PODS	4.1905499e-05