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: hac21922a648014b1
Venue: VLDB
Year: 2015
Pagerank: 5.70009e-05
Overall Rank: 6,712 | 54.89%
DOI: 10.14778/2824032.2824040
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Daniel Deutch (Tel Aviv University)
2. Amir Gilad (Tel Aviv University)
3. Yuval Moskovitch (Tel Aviv University)

BibTeX Citation

@article{deutch_vldb15,
        title = {{Selective Provenance for Datalog Programs Using Top-K Queries}},
        author = {Deutch, Daniel and Gilad, Amir and Moskovitch, Yuval},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {12},
        pages = {1394--1405},
        doi = {10.14778/2824032.2824040},
        url = {https://doi.org/10.14778/2824032.2824040},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,684	Provenance for Natural Language Queries	2017	VLDB	6.4692258e-05
4,937	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.3443901e-05
6,734	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.6919385e-05
7,235	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.5765963e-05
7,321	NLProveNAns: Natural Language Provenance for Non-Answers	2018	VLDB	5.5521254e-05
8,083	Provenance-Enabled Explainable AI	2024	SIGMOD	5.3917406e-05
9,947	NLProv: Natural Language Provenance	2016	VLDB	5.1038803e-05
10,636	Causal Explanations for Disparate Trends: Where and Why?	2026	SIGMOD	4.9769913e-05
12,182	Datalignment: Ontology Schema Alignment Through Datalog Containment	2019	VLDB	4.9769913e-05
12,243	Provenance Summaries for Answers and Non-Answers	2018	VLDB	4.9769913e-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
17	Provenance Semirings	2007	PODS	0.00059813669
671	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00014948069
943	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD	0.00012939577
1,000	Declarative Networking: Language, Execution and Optimization	2006	SIGMOD	0.00012601156
1,051	Tiresias: The Database Oracle for How-To Queries	2012	SIGMOD	0.00012274277
1,611	Efficient Provenance Storage	2008	SIGMOD	0.00010072076
1,827	Querying Data Provenance	2010	SIGMOD	9.5518797e-05
2,950	Reverse Data Management	2011	VLDB	7.817636e-05
3,133	Matching Twigs in Probabilistic XML	2007	VLDB	7.6103114e-05
3,664	On Probabilistic Fixpoint and Markov Chain Query Languages	2010	PODS	7.115538e-05
4,176	Aggregation in Probabilistic Databases via Knowledge Compilation	2012	VLDB	6.7541079e-05
4,766	Probabilistic Databases with MarkoViews	2012	VLDB	6.424681e-05
6,719	TRAMP: Understanding the Behavior of Schema Mappings through Provenance	2010	VLDB	5.6973551e-05
8,201	Labeling Recursive Workflow Executions On-the-Fly	2011	SIGMOD	5.3778252e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,153	Datalog with First-Class Facts	2025	VLDB
2	8,323	Computing How-Provenance for SPARQL Queries via Query Rewriting	2021	VLDB
3	811	Provenance for Aggregate Queries	2011	PODS
4	7,235	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD
5	10,888	Computing Why-Provenance for Property Graph Queries	2026	VLDB
6	4,684	Provenance for Natural Language Queries	2017	VLDB
7	6,459	On Provenance Minimization	2011	PODS
8	1,827	Querying Data Provenance	2010	SIGMOD
9	8,281	The Complexity of Why-Provenance for Datalog Queries	2024	PODS
10	11,496	Below and Above Why-Provenance for Datalog Queries	2024	PODS