% ---------------------------------------------------------------------------
% keyword = {provsql-foundation} : foundational works on which ProvSQL builds
% keyword = {provsql-paper} : papers about ProvSQL itself
% ---------------------------------------------------------------------------
% ---------------------------------------------------------------------------
% Foundational Works
% ---------------------------------------------------------------------------
@inproceedings{DBLP:conf/icdt/BunemanKT01,
author = {Peter Buneman and
Sanjeev Khanna and
Wang Chiew Tan},
title = {Why and Where: {A} Characterization of Data Provenance},
booktitle = {Database Theory - {ICDT} 2001, 8th International Conference, London,
UK, January 4-6, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
pages = {316--330},
publisher = {Springer},
year = {2001},
doi = {10.1007/3-540-44503-X_20},
keyword = {provsql-foundation},
annote = {The paper that introduced the concepts of why-provenance and where-provenance.
Why-provenance tracks which source tuples contribute to a result; where-provenance
tracks which specific attribute values (locations in the source) a result value
was copied from. ProvSQL implements where-provenance via project and eq gates that
record the column-level origin of each output value.},
}
@inproceedings{DBLP:conf/pods/GreenKT07,
author = {Todd J. Green and
Gregory Karvounarakis and
Val Tannen},
title = {Provenance semirings},
booktitle = {Proceedings of the Twenty-Sixth {ACM} {SIGACT-SIGMOD-SIGART} Symposium
on Principles of Database Systems, June 11-13, 2007, Beijing, China},
pages = {31--40},
publisher = {{ACM}},
year = {2007},
doi = {10.1145/1265530.1265535},
keyword = {provsql-foundation},
annote = {The foundational paper introducing provenance semirings. Defines annotated
relations over commutative semirings and shows that the standard relational algebra
operators correspond to semiring operations, unifying many existing provenance
formalisms (why-provenance, lineage, trio, bag semantics) as instances of a single
algebraic framework. ProvSQL’s core data model is a direct implementation of this
theory.},
}
@inproceedings{DBLP:conf/pods/AmsterdamerDT11,
author = {Yael Amsterdamer and
Daniel Deutch and
Val Tannen},
title = {Provenance for aggregate queries},
booktitle = {Proceedings of the 30th {ACM} {SIGMOD-SIGACT-SIGART} Symposium on
Principles of Database Systems, {PODS} 2011, June 12-16, 2011, Athens,
Greece},
pages = {153--164},
publisher = {{ACM}},
year = {2011},
doi = {10.1145/1989284.1989302},
keyword = {provsql-foundation},
annote = {Extends semiring provenance to SQL aggregate queries (COUNT, SUM, AVG, etc.),
which fall outside the positive relational algebra covered by Green et al. Introduces
a semimodule structure over semirings to handle aggregation provenance. ProvSQL's
support for provenance of GROUP BY queries and aggregation gates is grounded in
this work.},
}
@article{DBLP:journals/japll/GeertsP10,
author = {Floris Geerts and
Antonella Poggi},
title = {On database query languages for {K}-relations},
journal = {J. Appl. Log.},
volume = {8},
number = {2},
pages = {173--185},
year = {2010},
doi = {10.1016/J.JAL.2009.09.001},
keyword = {provsql-foundation},
annote = {Introduces m-semirings (semirings equipped with a monus operator ⊖) to extend
the provenance semiring framework to the full relational algebra including set
difference and negation. Defines the corresponding notion of K-relations for
m-semirings. ProvSQL's handling of EXCEPT queries and its monus gate type are
direct implementations of this framework.},
}
@inproceedings{DBLP:conf/edbtw/GreenT06,
author = {Todd J. Green and
Val Tannen},
title = {Models for Incomplete and Probabilistic Information},
booktitle = {Current Trends in Database Technology - {EDBT} 2006, {EDBT} 2006 Workshops,
Munich, Germany, March 26-31, 2006, Revised Selected Papers},
series = {Lecture Notes in Computer Science},
pages = {278--296},
publisher = {Springer},
year = {2006},
doi = {10.1007/11896548_24},
keyword = {provsql-foundation},
annote = {Proposes a unified model for incomplete and probabilistic databases based on
c-tables annotated with provenance expressions over a Boolean semiring. Shows how
probabilistic query evaluation reduces to evaluating the provenance expression of a
result tuple over a probability distribution. This connection between provenance
and probabilistic databases is the theoretical basis for ProvSQL's probability
computation features.},
}
@article{DBLP:journals/jacm/DalviS12,
author = {Nilesh N. Dalvi and
Dan Suciu},
title = {The Dichotomy of Probabilistic Inference for Unions of Conjunctive
Queries},
journal = {J. {ACM}},
volume = {59},
number = {6},
pages = {30:1--30:87},
year = {2012},
doi = {10.1145/2395116.2395119},
keyword = {provsql-foundation},
annote = {Establishes the complexity dichotomy for probabilistic query evaluation over
tuple-independent databases: every union of conjunctive queries is either in PTIME
(computable by a “safe plan” using extensional probability propagation) or
#P-hard. The safe class includes hierarchical CQs, which admit a read-once
rewriting. ProvSQL's safe-query rewriter (the
provsql.boolean_provenance optimisation) implements the read-once rewriting for
self-join-free hierarchical CQs and UCQs derived from this theory; circuits it
emits are evaluated in linear time by the independent-probability method.},
}
@inproceedings{DBLP:conf/icdt/DeutchMRT14,
author = {Daniel Deutch and
Tova Milo and
Sudeepa Roy and
Val Tannen},
title = {Circuits for Datalog Provenance},
booktitle = {Proc. 17th International Conference on Database Theory ({ICDT}),
Athens, Greece, March 24-28, 2014},
pages = {201--212},
publisher = {OpenProceedings.org},
year = {2014},
doi = {10.5441/002/ICDT.2014.22},
keyword = {provsql-foundation},
annote = {Shows how to represent provenance of Datalog queries compactly as arithmetic
circuits rather than as (potentially exponential) polynomials or sets. Establishes
circuit-based provenance as a practical representation for recursive queries, with
efficient evaluation algorithms. ProvSQL's circuit-based provenance representation
for all gate types is directly inspired by this work, and it is the basis of
ProvSQL's absorptive provenance scheme: under
provsql.provenance = 'absorptive' a recursive query over cyclic
data stops at the absorptive value fixpoint of this circuit semantics, where
longer (cycle-revisiting) derivations are absorbed, instead of failing to
converge.},
}
@inproceedings{DBLP:conf/sigmod/BourhisDM20,
author = {Pierre Bourhis and
Daniel Deutch and
Yuval Moskovitch},
title = {Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries},
booktitle = {Proceedings of the 2020 International Conference on Management of
Data, {SIGMOD} Conference 2020, online conference [Portland, OR, USA],
June 14-19, 2020},
pages = {415--429},
publisher = {{ACM}},
year = {2020},
doi = {10.1145/3318464.3380578},
keyword = {provsql-foundation},
annote = {Introduces an algebraic provenance framework for hyperplane update queries
(INSERT, DELETE, UPDATE via linear constraints), defining a semiring that tracks
provenance through data-modification operations in an equivalence-invariant manner.
This work provides the theoretical foundation for ProvSQL's update provenance
support.},
}
@article{DBLP:journals/vldb/DalviS07,
author = {Nilesh N. Dalvi and
Dan Suciu},
title = {Efficient query evaluation on probabilistic databases},
journal = {{VLDB} J.},
volume = {16},
number = {4},
pages = {523--544},
year = {2007},
doi = {10.1007/s00778-006-0004-3},
keyword = {provsql-foundation},
annote = {Introduces the safe-plan framework for probabilistic query evaluation: a
syntactic characterisation of conjunctive queries whose probability is computable in
PTIME by an extensional plan, together with the induced functional dependencies set
Γp(q) that lets the framework recognise more queries as safe. Constant selections
induce empty-determinant FDs (used by ProvSQL's constant-selection elimination) and
primary keys induce schema FDs (used by the PK-FD pass). The textbook treatment is in
Suciu, Olteanu, Re and Koch 2011, chapter 4. ProvSQL's FD-aware safe-query rewriter
implements the project-safety condition of this paper, with the union-find-based
hierarchicality check operating on the FD closure.},
}
@article{DBLP:journals/vldb/ReS09,
author = {Christopher R{\'e} and
Dan Suciu},
title = {The trichotomy of {HAVING} queries on a probabilistic database},
journal = {{VLDB} J.},
volume = {18},
number = {5},
pages = {1091--1116},
year = {2009},
doi = {10.1007/s00778-009-0151-4},
keyword = {provsql-foundation},
annote = {Classifies the complexity of evaluating a HAVING predicate
aggregate(y) θ k over a tuple-independent probabilistic database, for
aggregate in {EXISTS, MIN, MAX, COUNT, SUM, AVG, COUNT(DISTINCT)} and θ a
comparison. Exact evaluation is complement-symmetric and depends only on a
per-aggregate “α-safety” plan property (equal to skeleton-safety for
MIN/MAX/COUNT): PTIME if α-safe, else #P-hard. Approximation is direction-
asymmetric (relative-error FPTRAS of p is not one of 1 − p), yielding the
trichotomy safe / apx-safe (an FPTRAS exists) / hazardous (no FPRAS). The
conference version (DBPL 2007) covers the exact dichotomy; this journal version
adds the approximation results. ProvSQL's closed-form HAVING-COUNT / MIN-MAX / SUM
probability evaluators realise the α-safe (PTIME-exact) corner for independent
contributors, and the skeleton-safety detector exposes the α-safety axis. See the probability-evaluation
developer documentation for the per-(aggregate, θ) table.},
}
@inproceedings{DBLP:conf/icde/OlteanuHK10,
author = {Dan Olteanu and
Jiewen Huang and
Christoph Koch},
title = {Approximate confidence computation in probabilistic databases},
booktitle = {Proceedings of the 26th International Conference on Data Engineering,
{ICDE} 2010, March 1-6, 2010, Long Beach, California, {USA}},
pages = {145--156},
publisher = {{IEEE} Computer Society},
year = {2010},
doi = {10.1109/ICDE.2010.5447826},
keyword = {provsql-foundation},
annote = {Introduces the d-tree, an anytime decomposition for computing
interval bounds on the probability of a propositional lineage formula: each
node is an independent-or, independent-and, or Shannon-expansion of its
sub-formula, and a cheap per-leaf bound (the “independent” heuristic of
Fig. 3) is tightened by recursing into the widest interval until the additive
or relative target is met. Bounds are valid at every node (Prop. 5.1/5.4), so
the recursion can stop early with a certified interval. ProvSQL's “d-tree”
probability method implements this over
the materialised circuit's monotone-DNF lineage, memoised over the shared DAG
so bounded-treewidth lineage stays polynomial; it serves the high-treewidth
exact corner and the deterministic / low-δ approximate paths.},
}
@inproceedings{DBLP:conf/icde/SouihliS13,
author = {Asma Souihli and
Pierre Senellart},
title = {Optimizing approximations of {DNF} query lineage in probabilistic {XML}},
booktitle = {29th {IEEE} International Conference on Data Engineering, {ICDE}
2013, Brisbane, Australia, April 8-12, 2013},
pages = {721--732},
publisher = {{IEEE} Computer Society},
year = {2013},
doi = {10.1109/ICDE.2013.6544869},
pdf = {https://pierre.senellart.com/publications/souihli2013optimizing.pdf},
keyword = {provsql-foundation},
annote = {The ProApproX query processor: rather than committing to a single
confidence-computation algorithm, it maintains a portfolio of exact and
approximate methods (naive, Monte-Carlo / Karp-Luby style samplers, compilation)
and a cost model that picks, per lineage formula and per requested
(ε, δ) tolerance, the cheapest method expected to meet the bound. This
portfolio + cost-model principle is the design behind ProvSQL's
probability-method catalog and its cost-based chooser: tolerance grants
(exact / relative / additive) nest, and the chooser returns the cheapest
admissible member.},
}
@article{DBLP:journals/pvldb/GatterbauerS15,
author = {Wolfgang Gatterbauer and
Dan Suciu},
title = {Approximate Lifted Inference with Probabilistic Databases},
journal = {Proc. {VLDB} Endow.},
volume = {8},
number = {5},
pages = {629--640},
year = {2015},
doi = {10.14778/2735479.2735494},
keyword = {provsql-foundation},
annote = {Develops the dissociation framework for probabilistic query evaluation:
dissociating tuples in an atom (replacing a single shared input with multiple
independent copies) gives an upper bound on the query's probability, and dissociating
in a deterministic relation leaves the probability unchanged. The latter observation
grounds ProvSQL's deterministic-relation transparency pass: a relation whose rows
carry no provenance can be made transparent for atom-set analysis without affecting
soundness. The journal version (VLDB J. 26(1):31-59, 2017,
doi:10.1007/s00778-016-0434-5) extends the framework with propagation.},
}
@book{DBLP:series/synthesis/2011Suciu,
author = {Dan Suciu and
Dan Olteanu and
Christopher R{\'{e}} and
Christoph Koch},
title = {Probabilistic Databases},
series = {Synthesis Lectures on Data Management},
publisher = {Morgan {\&} Claypool Publishers},
year = {2011},
doi = {10.2200/S00362ED1V01Y201105DTM016},
isbn = {978-3-031-00751-4},
keyword = {provsql-foundation},
annote = {Textbook treatment of probabilistic databases. Chapter 4 covers the safe-plan
framework and the FD-aware extensions (constant-selection FDs, primary-key FDs,
deterministic-relation transparency, the FD-closure on the union-find) that ProvSQL's
safe-query rewriter implements. The textbook is the most accessible reference for
the framework's correctness arguments.},
}
@inproceedings{DBLP:conf/pods/JhaRS08,
author = {Abhay Kumar Jha and
Vibhor Rastogi and
Dan Suciu},
title = {Query evaluation with soft-key constraints},
booktitle = {Proceedings of the Twenty-Seventh {ACM} {SIGMOD-SIGACT-SIGART} Symposium
on Principles of Database Systems, {PODS} 2008, June 9-11, 2008,
Vancouver, BC, Canada},
pages = {119--128},
publisher = {{ACM}},
year = {2008},
doi = {10.1145/1376916.1376934},
}
@inproceedings{DBLP:conf/edbt/JhaOS10,
author = {Abhay Kumar Jha and
Dan Olteanu and
Dan Suciu},
title = {Bridging the gap between intensional and extensional query evaluation
in probabilistic databases},
booktitle = {{EDBT} 2010, 13th International Conference on Extending Database Technology,
Lausanne, Switzerland, March 22-26, 2010, Proceedings},
series = {{ACM} International Conference Proceeding Series},
pages = {323--334},
publisher = {{ACM}},
year = {2010},
doi = {10.1145/1739041.1739082},
}
@inproceedings{DBLP:conf/icdt/JhaS11,
author = {Abhay Kumar Jha and
Dan Suciu},
title = {Knowledge Compilation Meets Database Theory: Compiling Queries
to Decision Diagrams},
booktitle = {Database Theory - {ICDT} 2011, 14th International Conference,
Uppsala, Sweden, March 21-24, 2011, Proceedings},
pages = {162--173},
publisher = {{ACM}},
year = {2011},
doi = {10.1145/1938551.1938574},
pdf = {https://openproceedings.org/2011/conf/icdt/JhaS11.pdf},
keyword = {provsql-foundation},
annote = {Maps the lineage of a UCQ to four compilation targets of strictly
increasing power -- read-once, OBDD, FBDD, d-DNNF -- and shows that over UCQ
(unlike self-join-free CQ, where Olteanu-Huang collapse them all to read-once)
they form a strict hierarchy. Gives exact syntactic characterisations of the
first two: UCQ(OBDD) is precisely the inversion-free queries (with a linear-size
OBDD construction using a query-derived variable order), and UCQ(RO) the
inversion-free queries in which every relation symbol occurs at most once.
Relevant to ProvSQL because it explains why a knowledge compiler working on the
materialized circuit alone cannot in general recover the tractability a
query-level analysis exposes.},
}
@article{DBLP:journals/pvldb/JhaS12,
author = {Abhay Kumar Jha and
Dan Suciu},
title = {Probabilistic Databases with MarkoViews},
journal = {Proc. {VLDB} Endow.},
volume = {5},
number = {11},
pages = {1160--1171},
year = {2012},
doi = {10.14778/2350229.2350236},
pdf = {https://vldb.org/pvldb/vol5/p1160_abhayjha_vldb2012.pdf},
keyword = {provsql-foundation},
annote = {Represents tuple correlations as MarkoViews -- UCQ views that
attach a weight to each output tuple (a weight above 1 makes the contributing
tuples positively correlated, below 1 negatively, 1 independent, and 0 a hard
constraint) -- and reduces query evaluation on such a database to ordinary
tuple-independent evaluation plus a single conditioning step (their Theorem 1):
the answer probability is the original
query conditioned on the event that no constraint is violated. This is the
discrete precedent for ProvSQL's conditioning
operator: a denial constraint becomes a violation query W, and conditioning a
query on its non-occurrence (Q | !W) is exactly the MarkoViews reduction.},
}
@article{DBLP:journals/jal/KarpLM89,
author = {Richard M. Karp and
Michael Luby and
Neal Madras},
title = {Monte-Carlo Approximation Algorithms for Enumeration Problems},
journal = {J. Algorithms},
volume = {10},
number = {3},
pages = {429--448},
year = {1989},
doi = {10.1016/0196-6774(89)90038-2},
}
@inproceedings{DBLP:conf/ecai/Darwiche04,
author = {Adnan Darwiche},
title = {New Advances in Compiling {CNF} into Decomposable Negation Normal
Form},
booktitle = {Proceedings of the 16th Eureopean Conference on Artificial Intelligence,
{ECAI}'2004, including Prestigious Applicants of Intelligent Systems,
{PAIS} 2004, Valencia, Spain, August 22-27, 2004},
pages = {328--332},
publisher = {{IOS} Press},
year = {2004},
keyword = {provsql-foundation},
annote = {Introduces the c2d compiler, which translates {CNF} formulas into
deterministic decomposable {NNF} (specifically, Decision-{DNNF}) under the guidance
of a decomposition tree (dtree). ProvSQL invokes c2d as one of the external
knowledge compilers behind probability_evaluate(..., 'compilation', 'c2d') and
behind the Studio “Compile” feature.},
}
@inproceedings{DBLP:conf/ijcai/Darwiche11,
author = {Adnan Darwiche},
title = {{SDD:} {A} New Canonical Representation of Propositional Knowledge
Bases},
booktitle = {{IJCAI} 2011, Proceedings of the 22nd International Joint Conference
on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22,
2011},
pages = {819--826},
publisher = {{IJCAI/AAAI}},
year = {2011},
doi = {10.5591/978-1-57735-516-8/IJCAI11-143},
keyword = {provsql-foundation},
annote = {Introduces Sentential Decision Diagrams ({SDDs}), a canonical
representation of propositional knowledge bases structured by a fixed v-tree.
SDDs generalise {OBDDs}, support polynomial Apply, and underlie ProvSQL's
miniC2D-based compilation route. The Decision-{SDD} variant on which miniC2D
is built is a structural specialisation of this language.},
}
@inproceedings{DBLP:conf/ai/MuiseMBH12,
author = {Christian J. Muise and
Sheila A. McIlraith and
J. Christopher Beck and
Eric I. Hsu},
title = {{Dsharp:} Fast d-{DNNF} Compilation with sharp{SAT}},
booktitle = {Advances in Artificial Intelligence - 25th Canadian Conference on
Artificial Intelligence, Canadian {AI} 2012, Toronto, ON, Canada,
May 28-30, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7310},
pages = {356--361},
publisher = {Springer},
year = {2012},
doi = {10.1007/978-3-642-30353-1_36},
keyword = {provsql-foundation},
annote = {The Dsharp compiler: a top-down {DPLL}-style {CNF} to Decision-{DNNF}
compiler built on the sharp{SAT} model counter, with component caching as the
key efficiency mechanism. ProvSQL exposes Dsharp as one of the external compilers
behind probability_evaluate(..., 'compilation', 'dsharp').},
}
@inproceedings{DBLP:conf/ijcai/OztokD15,
author = {Umut Oztok and
Adnan Darwiche},
title = {A Top-Down Compiler for Sentential Decision Diagrams},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI} 2015, Buenos Aires, Argentina,
July 25-31, 2015},
pages = {3141--3148},
publisher = {{AAAI} Press},
year = {2015},
keyword = {provsql-foundation},
annote = {Introduces miniC2D, a top-down {CNF}-to-{SDD} compiler. The paper
isolates a subclass of {SDDs} called Decision-{SDDs} that admit a top-down
compilation strategy analogous to that of c2d / Dsharp. ProvSQL invokes miniC2D
as the structural-target external compiler in its probability evaluation pipeline.},
}
@inproceedings{DBLP:conf/ijcai/LagniezM17,
author = {Jean{-}Marie Lagniez and
Pierre Marquis},
title = {An Improved Decision-{DNNF} Compiler},
booktitle = {Proceedings of the Twenty-Sixth International Joint Conference on
Artificial Intelligence, {IJCAI} 2017, Melbourne, Australia, August
19-25, 2017},
pages = {667--673},
publisher = {ijcai.org},
year = {2017},
doi = {10.24963/ijcai.2017/93},
keyword = {provsql-foundation},
annote = {Introduces d4, a top-down {CNF}-to-Decision-{DNNF} compiler with
dynamic hypergraph decomposition, component caching and conflict-driven
backtracking. The paper unifies the descriptions of c2d, Dsharp and d4 as
Decision-{DNNF} compilers and reports significant size and runtime improvements
over its predecessors. ProvSQL uses d4 as the default external compiler behind
probability_evaluate(..., 'compilation') and as the final
fallback of its compilation pipeline.},
}
@inproceedings{LagniezM21d4v2,
author = {Jean{-}Marie Lagniez and
Pierre Marquis},
title = {About Caching in {D4} 2.0},
booktitle = {Workshop on Counting and Sampling 2021},
address = {Barcelona, Spain},
year = {2021},
month = jul,
url = {https://hal.science/hal-04252723},
pdf = {https://hal.science/hal-04252723v1/file/abstract-wks-model-counting.pdf},
keyword = {provsql-foundation},
annote = {Workshop note from the d4 authors describing d4 2.0 (a.k.a.
d4v2): a rewrite of the d4 Decision-{DNNF} compiler with improved
caching, a library-first architecture and tree-decomposition-guided
branching heuristics by default. ProvSQL exposes d4v2 as the 'd4v2'
compiler option via probability_evaluate(..., 'compilation', 'd4v2')
and the Studio compile dropdown.},
}
@article{DBLP:journals/jair/LaiLY17,
author = {Yong Lai and
Dayou Liu and
Minghao Yin},
title = {New Canonical Representations by Augmenting {OBDDs} with
Conjunctive Decomposition},
journal = {J. Artif. Intell. Res.},
volume = {58},
pages = {453--521},
year = {2017},
doi = {10.1613/JAIR.5271},
keyword = {provsql-foundation},
annote = {Introduces {OBDD[AND]} (and its smooth variant): augmenting
ordered binary decision diagrams with explicit decomposable
conjunction nodes. {OBDDs} are the canonical structured BDD class
in the knowledge-compilation map; this paper defines a strict
super-language that retains many of {OBDDs}' tractability properties
while admitting more compact circuits. ProvSQL exposes Panini's
{OBDD} and {OBDD[AND]} target languages via the 'panini-obdd' /
'panini-obdd-and' compiler options.},
}
@inproceedings{DBLP:conf/cav/LaiMY25,
author = {Yong Lai and
Kuldeep S. Meel and
Roland H. C. Yap},
editor = {Ruzica Piskac and
Zvonimir Rakamaric},
title = {Panini: An Efficient and Flexible Knowledge Compiler},
booktitle = {Computer Aided Verification - 37th International Conference, {CAV}
2025, Zagreb, Croatia, July 23-25, 2025, Proceedings, Part {III}},
series = {Lecture Notes in Computer Science},
pages = {92--105},
publisher = {Springer},
year = {2025},
doi = {10.1007/978-3-031-98682-6_6},
keyword = {provsql-foundation},
annote = {Introduces Panini, the knowledge-compilation tool of the
KCBox toolbox developed
by the Meel group. It compiles {CNF} formulas into one of five target
languages: {OBDD}, {OBDD[AND]}, Decision-{DNNF}, R2-D2 (a restricted
Decision-{DNNF}), or {CCDD}. ProvSQL exposes the first three through the
'panini-obdd' / 'panini-obdd-and' / 'panini-decdnnf' compiler options of
probability_evaluate and the Studio compile dropdown; R2-D2
and {CCDD} are intentionally omitted because both emit kernelize nodes
that break decomposability. Panini's output is translated to standard
d-DNNF form for probability evaluation.},
}
@inproceedings{DBLP:conf/ijcai/SharmaRSM19,
author = {Shubham Sharma and
Subhajit Roy and
Mate Soos and
Kuldeep S. Meel},
title = {{GANAK:} {A} Scalable Probabilistic Exact Model Counter},
booktitle = {Proceedings of the Twenty-Eighth International Joint Conference on
Artificial Intelligence, {IJCAI} 2019, Macao, China, August 10-16,
2019},
pages = {1169--1176},
publisher = {ijcai.org},
year = {2019},
doi = {10.24963/IJCAI.2019/163},
keyword = {provsql-foundation},
annote = {Introduces Ganak, an exact (probabilistically-cached)
model counter that won every track of the 2024 and 2025 Model
Counting Competitions. Ganak reads weighted DIMACS in the {MCC}
2024 format (c p weight <lit> <w> 0 lines) and reports the
count on c s exact ... lines. ProvSQL invokes Ganak via
probability_evaluate(..., 'wmc', 'ganak'), with Tseytin'd CNF +
appended weight lines for each input gate.},
}
@inproceedings{DBLP:conf/cp/KorhonenJ21,
author = {Tuukka Korhonen and
Matti J{\"{a}}rvisalo},
title = {Integrating Tree Decompositions into Decision Heuristics
of Propositional Model Counters (Short Paper)},
booktitle = {27th International Conference on Principles and Practice
of Constraint Programming, {CP} 2021, Montpellier, France
(Virtual Conference), October 25-29, 2021},
series = {LIPIcs},
pages = {8:1--8:11},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
doi = {10.4230/LIPICS.CP.2021.8},
keyword = {provsql-foundation},
annote = {Introduces SharpSAT-TD: an exact (weighted) model counter
built on SharpSAT that uses tree-decomposition guided decision
heuristics. Conceptually parallel to ProvSQL's in-process
tree-decomposition d-DNNF builder, but as a stand-alone SOTA exact
counter. ProvSQL invokes it via probability_evaluate(..., 'wmc',
'sharpsat-td'), with the sharpsat-td and flow_cutter_pace17
binaries on PATH.},
}
@inproceedings{DBLP:conf/cp/DudekPV20,
author = {Jeffrey M. Dudek and
Vu H. N. Phan and
Moshe Y. Vardi},
title = {{DPMC:} Weighted Model Counting by Dynamic Programming on
Project-Join Trees},
booktitle = {Principles and Practice of Constraint Programming - 26th
International Conference, {CP} 2020, Louvain-la-Neuve,
Belgium, September 7-11, 2020, Proceedings},
series = {Lecture Notes in Computer Science},
pages = {211--230},
publisher = {Springer},
year = {2020},
doi = {10.1007/978-3-030-58475-7_13},
keyword = {provsql-foundation},
annote = {Introduces DPMC: an exact weighted model counter that
runs as a two-stage pipeline. A planner (htb) produces a
project-join tree from the {CNF}; an executor (dmc) traverses
the tree using Algebraic Decision Diagrams ({ADDs}) to compute the
count. Algorithmically distinct from the search-based exact
counters (Ganak / SharpSAT-TD), giving the benchmark table a
third axis. ProvSQL exposes it via probability_evaluate(..., 'wmc', 'dpmc').},
}
@inproceedings{DBLP:conf/icalp/AmarilliBS15,
author = {Antoine Amarilli and
Pierre Bourhis and
Pierre Senellart},
title = {Provenance Circuits for Trees and Treelike Instances},
booktitle = {Automata, Languages, and Programming - 42nd International Colloquium,
{ICALP} 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part {II}},
series = {Lecture Notes in Computer Science},
pages = {56--68},
publisher = {Springer},
year = {2015},
doi = {10.1007/978-3-662-47666-6_5},
pdf = {https://pierre.senellart.com/publications/amarilli2015provenance.pdf},
slides = {https://pierre.senellart.com/publications/amarilli2015provenance_slides.pdf},
keyword = {provsql-paper},
annote = {The provenance refinement of Courcelle's theorem: for a fixed
MSO query over an instance of bounded treewidth, a provenance circuit of
treewidth independent of the instance size can be built in linear time
along a tree decomposition of the data. ProvSQL's recursive-reachability
route implements this construction for two-terminal network reliability:
the s-t reachability query is compiled along a tree decomposition of the
edge relation's graph into a d-D (a deterministic, decomposable circuit,
not in negation normal form) of linear size, giving exact linear-time
evaluation of a \#P-hard problem on bounded-treewidth probabilistic
graphs.},
}
@phdthesis{Amarilli2016thesis,
author = {Antoine Amarilli},
title = {Leveraging the Structure of Uncertain Data},
school = {T{\'{e}}l{\'{e}}com ParisTech},
year = {2016},
url = {https://theses.hal.science/tel-01345836},
note = {tel-01345836},
keyword = {provsql-paper},
annote = {Chapter 4 (cc/pcc-instances and joint width) is the
theoretical basis of ProvSQL's joint-width
UCQ compiler: a fixed conjunctive query that is \#P-hard under the
Dalvi--Suciu dichotomy is still evaluated exactly in time linear in the
data whenever the joint treewidth of the data and its correlation
structure is bounded (Thm. 4.2.7, Prop. 4.2.11).},
}
% ---------------------------------------------------------------------------
% Papers about ProvSQL
% ---------------------------------------------------------------------------
@inproceedings{DBLP:conf/icdt/ManiuSJ19,
author = {Silviu Maniu and
Pierre Senellart and
Suraj Jog},
title = {An Experimental Study of the Treewidth of Real-World Graph Data},
booktitle = {22nd International Conference on Database Theory, {ICDT} 2019,
March 26-28, 2019, Lisbon, Portugal},
series = {LIPIcs},
volume = {127},
pages = {12:1--12:18},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
doi = {10.4230/LIPIcs.ICDT.2019.12},
pdf = {https://pierre.senellart.com/publications/maniu2019experimental.pdf},
keyword = {provsql-paper},
annote = {An experimental study of treewidth lower and upper bounds on
real-world graph data. ProvSQL follows its findings in choosing the
treewidth heuristics of its bounded-treewidth machinery: the degeneracy
lower bound (cheap, to abort a hopeless decomposition early) and the
min-fill upper bound (the elimination ordering that builds the tree
decomposition the knowledge compiler and the recursive-reachability route
run along).},
}
@article{DBLP:journals/sigmod/Senellart17,
author = {Pierre Senellart},
title = {Provenance and Probabilities in Relational Databases},
journal = {{SIGMOD} Rec.},
volume = {46},
number = {4},
pages = {5--15},
year = {2017},
doi = {10.1145/3186549.3186551},
pdf = {https://pierre.senellart.com/publications/senellart2017provenance.pdf},
keyword = {provsql-paper},
annote = {An accessible overview of provenance and probabilistic query evaluation in
relational databases, covering the semiring framework, knowledge compilation to
d-DNNF, and the connection to probabilistic databases. Serves as a concise
introduction to the theoretical and practical ideas behind ProvSQL.},
}
@inproceedings{sen2026provsql,
author = {Aryak Sen and
Silviu Maniu and
Pierre Senellart},
title = {{ProvSQL}: A General System for Keeping Track of the Provenance
and Probability of Data},
booktitle = {Proc. {IEEE} 42nd International Conference on Data Engineering ({ICDE}),
Montr{\'e}al, Canada, May 2026},
year = {2026},
note = {Also arXiv abs/2504.12058},
pdf = {https://pierre.senellart.com/publications/sen2026provsql.pdf},
poster = {https://pierre.senellart.com/publications/sen2026provsql_poster.pdf},
slides = {https://pierre.senellart.com/publications/sen2026provsql_slides.pdf},
keyword = {provsql-paper},
annote = {The primary reference for the ProvSQL system. Presents the complete data model
(multiset-based relational algebra with semiring provenance), the circuit-based
provenance representation stored in memory-mapped files, and the full query
evaluation architecture. Includes TPC-H-inspired benchmarks comparing ProvSQL to
GProM and MayBMS, demonstrating competitive performance and broader SQL coverage.},
}
@article{DBLP:journals/pvldb/SenellartJMR18,
author = {Pierre Senellart and
Louis Jachiet and
Silviu Maniu and
Yann Ramusat},
title = {{ProvSQL}: Provenance and Probability Management in {PostgreSQL}},
journal = {Proc. {VLDB} Endow.},
volume = {11},
number = {12},
pages = {2034--2037},
year = {2018},
note = {Demonstration},
doi = {10.14778/3229863.3236253},
pdf = {https://pierre.senellart.com/publications/senellart2018provsql.pdf},
poster = {https://pierre.senellart.com/publications/senellart2018provsql_poster.pdf},
video = {https://www.youtube.com/watch?v=iqzSNfGHbEE},
keyword = {provsql-paper},
annote = {The original demonstration paper introducing ProvSQL. Describes the core design:
transparent query rewriting via a PostgreSQL planner hook, the provenance term
algebra circuit as a uniform representation for semiring provenance,
where-provenance, and m-semiring provenance, and knowledge compilation to d-DNNF
for probabilistic query evaluation.},
}
@inproceedings{DBLP:conf/pw/WidiaatmajaDDS25,
author = {Albert Ariel Widiaatmaja and
Belkis Djeffal and
Ashish Dandekar and
Pierre Senellart},
title = {Demonstration of {ProvSQL} Update Provenance through Temporal Databases},
booktitle = {Proceedings of the Provenance Week 2025, {PW}'25, Berlin, Germany,
June 22-27, 2025},
pages = {71--76},
publisher = {{ACM}},
year = {2025},
note = {Demonstration},
doi = {10.1145/3736229.3736253},
pdf = {https://pierre.senellart.com/publications/widiaatmaja2025demonstration.pdf},
poster = {https://pierre.senellart.com/publications/widiaatmaja2025demonstration_poster.pdf},
keyword = {provsql-paper},
annote = {Extends ProvSQL to track provenance for data modification operations (INSERT,
UPDATE, DELETE) by introducing monus gates for deleted tuples and times gates for
inserted ones. Demonstrates the utility of update provenance by implementing
temporal database features -- time travel, history tracking, and undo -- using the
union-of-intervals m-semiring.},
}
@inproceedings{DBLP:conf/birthday/Senellart24,
author = {Pierre Senellart},
title = {On the Impact of Provenance Semiring Theory on the Design of a
Provenance-Aware Database System},
booktitle = {The Provenance of Elegance in Computation - Essays Dedicated to Val
Tannen, Tannen's Festschrift, University of Pennsylvania, Philadelphia,
PA, USA, May 24-25, 2024},
series = {OASIcs},
pages = {9:1--9:10},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024},
doi = {10.4230/OASICS.TANNEN.9},
pdf = {https://pierre.senellart.com/publications/senellart2024impact.pdf},
slides = {https://pierre.senellart.com/talks/valfest-20240525.pdf},
keyword = {provsql-paper},
annote = {A reflective essay on how the provenance semiring framework of Green,
Karvounarakis, and Tannen directly shaped ProvSQL's design. Discusses where theory
translates cleanly into implementation (e.g., the universality of the polynomial
semiring motivating UUID-based annotations), where SQL's multiset semantics and
aggregation required deviations, and where ProvSQL's development still lags behind
theory.},
}
@article{DBLP:journals/mst/AmarilliCMS20,
author = {Antoine Amarilli and
Florent Capelli and
Mika{\"{e}}l Monet and
Pierre Senellart},
title = {Connecting Knowledge Compilation Classes and Width Parameters},
journal = {Theory Comput. Syst.},
volume = {64},
number = {5},
pages = {861--914},
year = {2020},
doi = {10.1007/S00224-019-09930-2},
pdf = {https://pierre.senellart.com/publications/amarilli2019connecting.pdf},
keyword = {provsql-paper},
annote = {Establishes formal connections between knowledge compilation classes (OBDDs,
d-DNNFs, SDDs…) and graph width parameters (treewidth, pathwidth, cliquewidth).
Section 5.1 of this paper provides the algorithm directly implemented in ProvSQL's
internal tree-decomposition-based knowledge compiler (tdkc), which converts
a provenance circuit into a d-DNNF for tractable probability evaluation.},
}
@inproceedings{DBLP:conf/rweb/Senellart19,
author = {Pierre Senellart},
title = {Provenance in Databases: Principles and Applications},
booktitle = {Reasoning Web. Explainable Artificial Intelligence - 15th International
Summer School 2019, Bolzano, Italy, September 20-24, 2019, Tutorial
Lectures},
series = {Lecture Notes in Computer Science},
pages = {104--109},
publisher = {Springer},
year = {2019},
doi = {10.1007/978-3-030-31423-1_3},
pdf = {https://pierre.senellart.com/publications/senellart2019provenance.pdf},
slides = {https://pierre.senellart.com/talks/rw-20190920.pdf},
keyword = {provsql-paper},
annote = {A concise tutorial on database provenance covering Boolean provenance, semiring
provenance, and key applications including probabilistic databases, view
maintenance, and query explanation. Also surveys provenance beyond the relational
setting (XML, graph, triple-store databases). Serves as an accessible introduction
to the theoretical foundations underlying ProvSQL.},
}
@inproceedings{DBLP:conf/edbt/YunusKSAB25,
author = {Fajrian Yunus and
Pratik Karmakar and
Pierre Senellart and
Talel Abdessalem and
St{\'{e}}phane Bressan},
title = {Using {A} Probabilistic Database in an Image Retrieval Application},
booktitle = {Proceedings 28th International Conference on Extending Database Technology,
{EDBT} 2025, Barcelona, Spain, March 25-28, 2025},
pages = {1106--1109},
publisher = {OpenProceedings.org},
year = {2025},
doi = {10.48786/EDBT.2025.100},
pdf = {https://pierre.senellart.com/publications/yunus2025using.pdf},
video = {https://www.youtube.com/watch?v=n_aFl0olTG4},
keyword = {provsql-paper},
annote = {Demonstrates ProvSQL as the probabilistic database backend for an image
retrieval application. Images are indexed by uncertain feature vectors; queries
return ranked results with tuple-independent probabilities computed via ProvSQL's
knowledge compilation pipeline. Shows that ProvSQL's provenance-based probability
management integrates naturally with a real-world multimedia retrieval use case.},
}
@article{DBLP:journals/pacmmod/KarmakarMSB24,
author = {Pratik Karmakar and
Mika{\"{e}}l Monet and
Pierre Senellart and
St{\'{e}}phane Bressan},
title = {Expected Shapley-Like Scores of Boolean Functions: Complexity and
Applications to Probabilistic Databases},
journal = {Proc. {ACM} Manag. Data},
volume = {2},
number = {2},
pages = {92},
year = {2024},
note = {Presented at the PODS 2024 conference in Santiago, Chile. Also arXiv abs/2401.06493},
doi = {10.1145/3651593},
pdf = {https://pierre.senellart.com/publications/karmakar2024expected.pdf},
poster = {https://pierre.senellart.com/publications/karmakar2024expected_poster.pdf},
slides = {https://pierre.senellart.com/publications/karmakar2024expected_slides.pdf},
keyword = {provsql-paper},
annote = {Studies the complexity of expected Shapley and Banzhaf values for Boolean
functions in probabilistic database settings, showing that their computation is
interreducible in polynomial time with probabilistic query evaluation. Designs a
polynomial-time algorithm for Boolean functions represented as d-DNNF circuits.
Implements and experimentally validates this algorithm within the ProvSQL system,
enabling Shapley value computation directly from provenance circuits.},
}