SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits

arXiv:2611.00128v1 [cs.DB] 29 Oct 2026

SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits Jingcheng Wu

Ratan Bahadur Thapa

University of Stuttgart Stuttgart, Germany jingcheng.wu@ki.uni-stuttgart.de

University of Stuttgart Stuttgart, Germany ratan.thapa@ki.uni-stuttgart.de

Daniel Hernández

Steffen Staab∗

University of Stuttgart Stuttgart, Germany daniel.hernandez@ki.uni-stuttgart.de

University of Stuttgart Stuttgart, Germany steffen.staab@ki.uni-stuttgart.de

Abstract Probabilistic query evaluation (PQE) computes the probability of every answer of a query over a tuple-independent probabilistic knowledge graph. We study exact PQE for SPARQL over graphs accessed through SPARQL 1.1 endpoints. Shared triples among the derivations of an answer make exact PQE #P-hard in general. Knowledge compilation of the Boolean provenance of every answer yields exact probabilities, and the provenance formulas of different answers can share subformulas. We propose SPARQLcirc, which rewrites a SPARQL query into CONSTRUCT queries that name every gate by its content, so that the results of independent queries form one Boolean provenance circuit for all answers. The rewriting covers joins, unions, projection, filters, OPTIONAL, difference and transitive closures. SPARQLcirc compiles the circuit and computes the exact probability of every answer by weighted model counting. For the evaluation, we draw random probabilities for the triples of WatDiv and gMark and the statements of Wikidata and evaluate the CONSTRUCT queries on GraphDB, Fuseki and Oxigraph. The ratio of the end-to-end time of PQE with SPARQLcirc to that of PQE by compiling the provenance expressions of the SPARQL provenance rewriting NPCS decreases with the number of derivations.

CCS Concepts • Information systems → Resource Description Framework (RDF); Data provenance; • Theory of computation → Incomplete, inconsistent, and uncertain databases.

Keywords probabilistic knowledge graphs, probabilistic query evaluation, SPARQL, provenance circuits, knowledge compilation

1

Introduction

Information extraction and link prediction produce triples with confidence scores [10, 13, 21, 22], and statistical signal detection derives drug interactions with association scores from adverseevent reports [55]. A probabilistic knowledge graph treats every score as the probability that the triple holds [12]. In RDF, the probability annotates the triple through standard reification, named graphs, RDF-star or Wikidata statement nodes [9, 11, 35, 38, 43]. In Figure 1, every :interactsWith triple carries an identifier 𝑝𝑖 ∗ Also with University of Southampton.

and a probability. Knowledge graphs with annotated triples, such as Wikidata, are queried through SPARQL endpoints [43, 62]. A SPARQL query can return the probabilities of the matched triples, but the SPARQL semantics assigns no probability to an answer [34]. A public SPARQL endpoint accepts only SPARQL requests, and the endpoint administrator alone can extend the query engine. For a probabilistic knowledge graph accessed only through a public endpoint on the Web, the probability of every answer must therefore be computed from the results of SPARQL queries. Clopidogrel

𝒑 7 (0.60)

𝒑 8 (0.55) 𝒑 1 (0.92)

Lisinopril

𝒑 6 (0.65)

Warfarin

Metformin 𝒑 2 (0.87) 𝒑 5 (0.71)

Aspirin 𝒑 4 (0.78)

𝒑 3 (0.85)

Ibuprofen Omeprazole

triple off the cycle

triple on the cycle

Figure 1: Probabilistic drug-interaction graph. Every edge is an :interactsWith triple with its identifier and probability. In the tuple-independent model of probabilistic databases, every subgraph of a probabilistic knowledge graph is a possible world, and every triple occurs independently with its probability [12, 54]. The marginal probability of an answer is the total probability of the worlds in which the answer occurs. Probabilistic query evaluation (PQE) computes the marginal probability of every answer. Top-k query evaluation ranks the answers by marginal probability [48]. The Boolean provenance of an answer is the Boolean function over the triples that is true exactly in the worlds in which the answer occurs, so the marginal probability is the probability that the Boolean provenance is true [54]. The identifiers 𝑝𝑖 of Figure 1 also denote the Boolean variables of their triples. The query SELECT ?z WHERE { :Aspirin :interactsWith ?x . ?x :interactsWith ?y . ?y :interactsWith ?z } retrieves the drugs that Aspirin reaches in three :interactsWith steps. The Boolean provenance is 𝑝 1 ∧ 𝑝 6 ∧ 𝑝 7 for Clopidogrel and (𝑝 1 ∧ 𝑝 2 ∧ 𝑝 3 ) ∨ (𝑝 4 ∧ 𝑝 5 ∧ 𝑝 3 ) for Omeprazole. A derivation of an answer is the conjunction of the triples of one match. Omeprazole has two derivations and Clopidogrel one. Derivations that share triples are correlated events. The two derivations of Omeprazole have probabilities 0.680 and 0.471 and

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

both contain 𝑝 3 . Treating the derivations as independent events gives 1 − (1 − 0.680)(1 − 0.471) = 0.831, whereas factoring out 𝑝 3 gives the correct marginal probability 0.85 · (1 − (1 − 0.800)(1 − 0.554)) = 0.774. Even for some fixed basic graph patterns, exact PQE is #P-hard in the size of the graph [15, 61]. Knowledge compilation translates the Boolean provenance into a compiled form, from which weighted model counting computes the marginal probability in time linear in the size of the form [17, 54]. A provenance circuit is a directed acyclic graph that represents Boolean provenance with triples as leaves and with products (∧), sums (∨) and differences (𝑎 ∧ ¬𝑏) as gates [19, 52]. Derivations of different answers can also share triples and subformulas. A single circuit represents a shared subformula once and gives every answer a root gate [19, 52]. SPARQL property paths with the operator + or * compute transitive closures. On a graph with a cycle, a closure can connect two nodes by infinitely many walks. In Figure 1, the walks of :Aspirin :interactsWith+ ?y from Aspirin to Warfarin can repeat the cycle. Provenance that counts the walks becomes a power series with infinitely many terms [33], and the series for Warfarin is 𝑝 1 + 𝑝 12 𝑝 6 𝑝 7 𝑝 8 + · · · . In contrast, by the absorption law 𝑥 ∨ (𝑥 ∧ 𝑦) = 𝑥, the Boolean provenance of every answer equals a disjunction over finitely many walks [19]. The law removes the conjunction of every walk that contains all triples of a shorter walk between the same nodes, and for Warfarin the disjunction 𝑝 1 ∨ (𝑝 1 ∧𝑝 6 ∧𝑝 7 ∧𝑝 8 ) ∨· · · equals 𝑝 1 . For transitive closure, positive provenance formulas require super-polynomial size in the worst case, whereas polynomial-size circuits exist for every graph [19, 23]. SPARQLprov and NPCS rewrite a query into SPARQL queries, so that an endpoint without extensions returns the provenance of every answer [6, 36]. SPARQLprov returns tables that encode expression structure and node identifiers. NPCS constructs and aggregates expression strings inside the endpoint. Both rewritings return one provenance expression per answer, and a subexpression that several answers share is therefore repeated in each expression. The probability of every answer is then computed by compiling its expression outside the endpoint. A SPARQL property path returns only the pairs of nodes that its walks connect, and SPARQLprov and NPCS cover only patterns without transitive closures. In relational databases, ProvSQL covers recursive reachability queries, builds one circuit for all answers and names every inner gate by hashing its operator and operands [50–52]. ProvSQL runs inside PostgreSQL as an engine extension, but engine extensions on a public endpoint can be installed only by its administrator. SPARQL construct queries can return the gates of a circuit as triples, but a blank node in the template denotes a fresh node for every solution. Two gates that different solutions or queries emit therefore coincide only if both receive the same IRI. The name of a gate is a canonical syntactic description of the gate. A SPARQL 1.1 query can hash the name of a gate into its IRI with built-in hash functions, and equal names yield equal IRIs in every query and on every engine. The results of independent construct queries then form one circuit, because the triples that two queries emit for one gate share the IRI of the gate. Repeated edges occur once in the merged RDF graph, and by Boolean idempotence (𝑎 ∨ 𝑎 = 𝑎 and 𝑎 ∧ 𝑎 = 𝑎) the merge preserves the Boolean function of every gate. We propose SPARQLcirc , a rewriting method for exact PQE. SPARQLcirc translates a SPARQL query into a plan of SPARQL 1.1

construct queries whose results form one Boolean provenance circuit for all answers. For a transitive closure from a start node that a constant or a preceding pattern fixes, each round of SPARQL 1.1 requests emits the gates of one walk length. SPARQLcirc compiles the root of every answer with an existing knowledge compiler and computes the probability of the answer by weighted model counting. With random probabilities for the triples of WatDiv [1], gMark [7] and the 1.78 billion statements of Wikidata [62], we compare SPARQLcirc on GraphDB [44], Fuseki [56] and Oxigraph [45] with plain query evaluation and NPCS. We make three contributions: • Gate names that SPARQL 1.1 queries compute from the content of the gates, so that independent construct queries yield one circuit on any engine (Section 4.1). • A rewriting of queries with optional, difference and transitive closures into plans of construct queries, a factored plan in which derivations share the gates of common parts, and a proof that every answer has a root and that the root denotes its Boolean provenance (Sections 4.2–4.5). • An evaluation on WatDiv, gMark and Wikidata in which the ratio of the end-to-end time of PQE with one circuit for all answers to that with per-answer provenance expressions decreases with the number of derivations (Section 5). Section 6 relates SPARQLcirc to probabilistic relational and RDF databases, SPARQL provenance and provenance under recursion.

2

Preliminaries

RDF and SPARQL. Following Pérez et al. [46], we define a fragment S of SPARQL as follows. The set I contains the IRIs, B the blank nodes, L the literals and V the variables, and T = I ∪ B ∪ L. An RDF graph is a finite subset of (I ∪ B) × I × T, a triple pattern tp belongs to (I ∪ L ∪ V) × (I ∪ V) × (I ∪ L ∪ V), and a solution mapping is a partial function 𝜇 : V ⇀ T with domain dom(𝜇). A blank node in a query acts as a variable [34]. Mappings 𝜇 1 and 𝜇 2 are compatible (𝜇 1 ∼ 𝜇2 ) when both agree on dom(𝜇 1 ) ∩ dom(𝜇2 ). A path-free pattern is generated by 𝑃 ::= tp | Join(𝑃 1, . . . , 𝑃𝑛 ) | Union(𝑃1, . . . , 𝑃𝑛 ) | Proj𝑌 (𝑃) | Filter𝜑 (𝑃) | Diff(𝑃 1, 𝑃2 ). A basic graph pattern (BGP) {tp1, . . . , tp𝑚 } is represented by Join(tp1, . . . , tp𝑚 ) [34, 46], so the empty BGP Join() returns only the empty mapping. The condition 𝜑 combines Boolean connectives, comparisons and arithmetic operators with the SPARQL 1.1 builtins of Appendix B. In Filter𝜑 (𝑃), the condition 𝜑 mentions only variables that every mapping of 𝑃 binds. A query is a pattern 𝑄 = Proj𝑌 (𝑃) with 𝑌 ⊆ V. Evaluation of 𝑃 on an RDF graph 𝐺 returns a multiset [[𝑃]]𝐺 [4, 34], and supp( [[𝑃]]𝐺 ) denotes the mappings with positive multiplicity. The difference Diff(𝑃 1, 𝑃2 ) [40] retains a mapping of 𝑃 1 exactly when no mapping of 𝑃2 is compatible with it, and Opt(𝑃 1, 𝑃2 ) without a filter abbreviates Union(Join(𝑃1, 𝑃2 ), Diff(𝑃1, 𝑃2 )) [34]. A closure-free property-path expression is generated by 𝑒 ::= 𝑝 | '^'𝑒 | 𝑒 1 '/' 𝑒 2 | 𝑒 1 '|' 𝑒 2 , with 𝑝 ∈ I (inverse, sequence and alternative). Rel𝑒 (𝐺) is the binary relation that SPARQL assigns to 𝑒 on 𝐺 [34], and Rel𝑒 + (𝐺) is its transitive closure. For ⋄ ∈ {+, ∗}, a closure atom is a pattern 𝐶 = (𝛼, 𝑒 ⋄ , ?𝑦) with closure-free 𝑒, source 𝛼 ∈ I ∪ L ∪ V and target variable ?𝑦. For a source 𝑠 and a target 𝑣, the

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

𝐶 is {?𝑦 ↦→ 𝑣 } when 𝛼 is a constant and {𝛼 ↦→ 𝑠, ?𝑦 ↦→ 𝑣 } mapping 𝜇𝑠,𝑣 𝐶 once for every when 𝛼 is a variable. For ⋄ = +, the atom returns 𝜇𝑠,𝑣 + pair (𝑠, 𝑣) ∈ Rel𝑒 (𝐺) with 𝑠 = 𝛼 when 𝛼 is a constant and 𝑠 = 𝑣 𝐶 once for every such when 𝛼 is ?𝑦. For ⋄ = ∗, the atom returns 𝜇𝑠,𝑣 pair of Rel𝑒 + (𝐺) ∪ Δ, where the set Δ of zero-length pairs contains (𝛼, 𝛼) when 𝛼 is a constant and (𝑠, 𝑠) for every subject or object 𝑠 of a triple of 𝐺 when 𝛼 is a variable [34]. A closure atom 𝐶 with a variable source is source-bound when 𝐶 is an operand of a join or the right operand of a difference and, on every graph, every mapping of the join of the operands before 𝐶 binds the source. The fragment S extends this grammar with closure atoms whose source is a constant or that are source-bound. A construct query pairs a pattern 𝑃 with a template 𝑇 , a finite set of triple patterns. On an RDF graph 𝐺, we call the mappings in supp( [[𝑃]]𝐺 ) the rows of the query, and the query returns the RDF graph that contains the instance 𝜇 (𝑇 ) of every row 𝜇. The instance 𝜇 (𝑇 ) consists of the RDF triples among the triples that result from 𝑇 when every variable of dom(𝜇) is replaced by its value [34]. Reification. Four encodings give every triple 𝑡 = (𝑠, 𝑝, 𝑜) of an RDF graph 𝐺 an identifier 𝑖: an RDF-star annotation ⟨⟨𝑠 𝑝 𝑜⟩⟩ occurrenceOf 𝑖 [35], a standard reification 𝑖 [9], a named graph 𝑖 that holds 𝑡 [11], or a Wikidata statement node 𝑖 of best rank [43]. SPARQL-star queries read the RDF-star annotation through quoted triple patterns [35], and SPARQL 1.1 queries read the other three encodings. The reified graph 𝐺 reif replaces every blank node of 𝐺 by a fresh Skolem IRI [14], contains the resulting triples and represents each of them in one of the encodings. Following SPARQLprov and NPCS [6, 36], the reification reif (tp, ?𝑡) of a triple pattern tp matches the encoding of every triple that matches tp and binds ?𝑡 to the identifier of the triple. Possible worlds and PQE. A probabilistic knowledge graph is an RDF graph 𝐺 in which every triple 𝑡 carries a Boolean variable 𝑥𝑡 and a probability Pr(𝑥𝑡 ) [12, 54]. Each triple 𝑡 has one distinct identifier 𝑖𝑡 in 𝐺 reif . Under tuple independence, a possible world Î Î 𝑊 ⊆ 𝐺 has probability Pr(𝑊 ) = 𝑡 ∈𝑊 Pr(𝑥𝑡 ) 𝑡 ∈𝐺\𝑊 (1 − Pr(𝑥𝑡 )). A mapping 𝜇 is an answer of a query 𝑄 when 𝜇 ∈ supp([[𝑄]]𝑊 ) for some world 𝑊 ⊆ 𝐺. The marginal probability of the answer is Í Pr(𝜇) = 𝑊 ⊆𝐺, 𝜇 ∈supp( [[𝑄 ]]𝑊 ) Pr(𝑊 ). Boolean provenance. Geerts et al. define the provenance of SPARQL over spm-semirings, which extend commutative semirings with a difference ⊖ [32]. The homomorphism that maps ⊕ to ∨, ⊗ to ∧ and 𝑎 ⊖ 𝑏 to 𝑎 ∧ ¬𝑏 yields the Boolean provenance BProv𝑃 (𝜇) of a mapping 𝜇 for a pattern 𝑃. Over 𝑋 = {𝑥𝑡 | 𝑡 ∈ 𝐺 }, the Boolean provenance has the following cases. For a triple pattern tp, BProvtp (𝜇) = 𝑥 𝜇 (tp) when dom(𝜇) contains exactly the variables of tp and 𝜇 (tp) ∈ 𝐺, and ⊥ otherwise. The other cases are Ô Ó BProvJoin(𝑃1 ,...,𝑃𝑛 ) (𝜇) = 𝜇=𝜇1 ∪···∪𝜇𝑛 𝑖 BProv𝑃𝑖 (𝜇𝑖 ), Ô BProvUnion(𝑃1 ,...,𝑃𝑛 ) (𝜇) = 𝑖 BProv𝑃𝑖 (𝜇), Ô BProvProj𝑌 (𝑃 ) (𝜇) = 𝜇 ′ |𝑌 =𝜇 BProv𝑃 (𝜇 ′ ), Ô BProvDiff(𝑃1 ,𝑃2 ) (𝜇) = BProv𝑃1 (𝜇) ∧ ¬ 𝜈∼𝜇 BProv𝑃2 (𝜈),

𝐶 on 𝑊 , and BProv (𝜇) = ⊥ for every other 𝜇. For every returns 𝜇𝑠,𝑣 𝐶 𝑊 ⊆ 𝐺, the commutation of the provenance with spm-semiring homomorphisms [32] and the definition of BProv𝐶 (·) yield

where the join ranges over decompositions into pairwise compatible mappings, and BProvFilter𝜑 (𝑃 ) (𝜇) is BProv𝑃 (𝜇) when 𝜇 satisfies 𝜑 and ⊥ otherwise. Let val𝑊 denote the valuation that assigns ⊤ to 𝐶 ) is the 𝑥𝑡 exactly when 𝑡 ∈ 𝑊 . For a closure atom, BProv𝐶 (𝜇𝑠,𝑣 Boolean function 𝑓 over 𝑋 with val𝑊 (𝑓 ) = ⊤ exactly when 𝐶

In this section, we rewrite a query into a plan of SPARQL 1.1 construct queries whose results form one Boolean provenance circuit for all answers. Let tp1 , tp2 and tp3 be the triple patterns of the running query in their order of occurrence. The rewriting 𝛾 maps the algebra expression Proj {?𝑧 } (Join(tp1, tp2, tp3 )) to a plan

val𝑊 (BProv𝑃 (𝜇)) = ⊤ ⇐⇒ 𝜇 ∈ supp([[𝑃]]𝑊 ).

(1)

Provenance circuits. Following Deutch et al. [19] and ProvSQL [52], a provenance circuit over 𝑋 is a finite set of gates whose child relation is acyclic. A gate 𝑔 is a leaf 𝑥 ∈ 𝑋 , a sum gate (⊕) or a product gate (⊗) with a finite set ch(𝑔) of children, or a difference gate (⊖) with a finite set pos(𝑔) of minuend children and one subtrahend child neg(𝑔). ProvSQL restricts difference gates to one minuend. A partial function root maps solution mappings to gates, and root(𝜇) is the root of 𝜇. By recursion over the child relation, the Boolean semantics [[𝑔]] of a gate is 𝑥 for a Ô Ó leaf 𝑥, 𝑐 ∈ch(𝑔) [[𝑐]] for an ⊕-gate, 𝑐 ∈ch(𝑔) [[𝑐]] for an ⊗-gate, and  Ü  [[𝑔]] = [[𝑐]] ∧ ¬[[neg(𝑔)]] (2) 𝑐 ∈pos (𝑔)

for an ⊖-gate, so 𝑔⊥ = ⊕(∅) and 𝑔⊤ = ⊗(∅) denote ⊥ and ⊤. Knowledge compilation and weighted model counting. The weighted model count WMC(𝑓 ) of a Boolean function 𝑓 sums over the satisfying assignments of 𝑓 the product of the weights of their literals [49]. With the weights Pr(𝑥𝑡 ) on 𝑥𝑡 and 1 − Pr(𝑥𝑡 ) on ¬𝑥𝑡 , Equation (1) yields Pr(𝜇) = WMC(BProv𝑄 (𝜇)). Knowledge compilation translates a Boolean function into a deterministic decomposable negation normal form (d-DNNF) or an ordered binary decision diagram (OBDD), and every OBDD is a d-DNNF [17]. A d-DNNF is a circuit in which negation occurs only on variables, the children of every conjunction have pairwise disjoint sets of variables and the children of every disjunction are mutually exclusive [17]. With the weights above, the weighted model counts of the children therefore multiply at a conjunction and add at a disjunction, and one bottom-up pass computes the weighted model count of a d-DNNF in linear time. The d-DNNF
𝑝 3 ∧ (𝑝 1 ∧ (𝑝 2 ∨ (¬𝑝 2 ∧ 𝑝 4 ∧ 𝑝 5 ))) ∨ (¬𝑝 1 ∧ 𝑝 4 ∧ 𝑝 5 ) represents the Boolean provenance of Omeprazole, and the pass yields the marginal probability 0.774.

3

Problem Definition

Definition 3.1 (Problem). Given a query 𝑄 of S and the probability Pr(𝑥𝑡 ) for the identifier 𝑖𝑡 of every 𝑡 ∈ 𝐺, the problem is to compute Pr(𝜇) for every answer 𝜇 of 𝑄 from the results of SPARQL 1.1 requests, or SPARQL-star requests for the RDF-star annotation, to an endpoint that stores 𝐺 reif . By Equation (1), Pr(𝜇) equals WMC(BProv𝑄 (𝜇)), so it suffices that the results of such requests form a provenance circuit in which the root of every answer 𝜇 denotes BProv𝑄 (𝜇).

4

Provenance Circuits from SPARQL 1.1 Queries

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

with one query for the join and one for the projection. The two queries share the where clause and appear as one query below. CONSTRUCT { ?g a c:Times ; c:in ?t1, ?t2, ?t3 . ?r a c:Plus ; c:in ?g ; c:answerRoot "vars:z" ; c:bind:z ?z } WHERE { << :Aspirin :interactsWith ?x >> :occurrenceOf ?t1 . << ?x :interactsWith ?y >> :occurrenceOf ?t2 . << ?y :interactsWith ?z >> :occurrenceOf ?t3 . BIND(KEY_TIMES(?t1, ?t2, ?t3) AS ?g) BIND(KEY_PLUS(A, "Proj{z}(...)", ?z) AS ?r) }

(3)

The shared where clause matches the reifications of the three triple patterns and binds the identifiers ?t1, ?t2 and ?t3 of the matched triples. The two bind expressions name the product gate ?g and the root ?r by KEY_TIMES and KEY_PLUS of Definition 4.1. For every row, the template emits one triple per gate for its kind (c:Times or c:Plus) and one c:in triple per edge to a child. The last template line marks ?r as a root and records the value of ?z. Over 𝐺 reif , the plan emits the product gates ⊗(𝑝 1, 𝑝 2, 𝑝 3 ) and ⊗(𝑝 4, 𝑝 5, 𝑝 3 ) below the root of Omeprazole and the product gate ⊗(𝑝 1, 𝑝 6, 𝑝 7 ) below the root of Clopidogrel. The merged RDF graph of the emitted triples is the circuit of Figure 2, and two product gates share each of the leaves 𝑝 1 and 𝑝 3 . The plan depends on the query alone, and the circuit on the query and the data. SPARQLcirc reads the circuit, compiles every root and computes its weighted model count: 0.774 for Omeprazole and 0.359 for Clopidogrel. Omeprazole

Clopidogrel

⊕

⊕

⊗ 𝑝4

𝑝5

⊗ 𝑝3

𝑝2

⊗ 𝑝1

𝑝6

𝑝7

Figure 2: The circuit that the plan of the running query emits. The shared leaves 𝑝 1 and 𝑝 3 (orange) occur once. Section 4.1 names the gates. Sections 4.2 to 4.4 give the plans for the operators, for basic graph patterns and for transitive closures, and Section 4.5 defines sound and complete plans, gives the Boolean functions of the named gates, states that the plans are sound and complete and compiles the circuit to compute the probabilities. Appendix A proves the lemmas and theorems of this section.

4.1

one derivation, and the rows can belong to several queries. All rows of one mapping bind the same values, so a sum or difference gate is named after its subpattern and the bindings of its mapping. Definition 4.1 adapts the gate names of ProvSQL [50] and the node identifiers of SPARQLprov [36] to SPARQL 1.1 queries, and hashconsing names the nodes of terms in the same way [25]. Definition 4.1 (Gate names). Let 𝜏 (𝑣) encode an RDF term 𝑣 by its term kind, lexical form, datatype and lower-cased language tag, and let 𝜏 (unbound) be a distinct token for an unbound variable. Let 𝜃 (𝑃) be a serialization of a subpattern 𝑃 such that two subpatterns have equal serializations exactly when they are equal up to the order of the operands of joins and unions and up to repeated operands of a union. A leaf is named by the identifier of its triple. The key expressions for a letter 𝐿, a tag 𝜃 , variables ?𝑐 1, . . . , ?𝑐𝑛 and variables ?𝑥 1 < · · · <?𝑥𝑘 in the lexicographic order of their names are KEY_TIMES(?𝑐 1, . . . , ?𝑐𝑛 ) = IRI(ℎ(T, sort(?𝑐 1, . . . , ?𝑐𝑛 ))), KEY_PLUS(𝐿, 𝜃, ?𝑥 1, . . . , ?𝑥𝑘 ) = IRI(ℎ(𝐿, 𝜃, 𝜏ˆ (?𝑥 1 ), . . . , 𝜏ˆ (?𝑥𝑘 ))), KEY_MINUS(𝜃, ?𝑥 1, . . . , ?𝑥𝑘 ) = IRI(ℎ(M, 𝜃, 𝜏ˆ (?𝑥 1 ), . . . , 𝜏ˆ (?𝑥𝑘 ))), where ℎ hashes its arguments, sort orders them by the lexicographic order of their hashes, 𝜏ˆ (?𝑥) computes 𝜏 of the value of ?𝑥, and 𝐿 ∈ {U, P, A, S} marks the sum gate of a union, a projection, the outer projection and the subtrahend of a difference, respectively. The name of a gate on a row is the tuple of the arguments of ℎ, and its IRI is the value of the key expression. Since ⊗ is commutative but ℎ depends on the order of its arguments, KEY_TIMES sorts the children before hashing, so the name of a product gate is invariant under permutations of the operands of a join. In the plan (3), the row that binds ?t1, ?t2 and ?t3 to 𝑝 1 , 𝑝 2 and 𝑝 3 names its product gate (T, sort(𝑝 1, 𝑝 2, 𝑝 3 )), and a query that lists the triple patterns in the order tp3 , tp2 , tp1 names the same gate. The root of Omeprazole is named (A, 𝜃 (Proj {?𝑧 } (Join(tp1, tp2, tp3 ))), 𝜏 (Omeprazole)). The query Proj {?𝑧 } (tp3 ) names the root of Omeprazole with another tag, and that root denotes 𝑝 3 . A name without the tag merges the two roots and gives Omeprazole the function 𝑝 3 in the running query instead of (𝑝 1 ∧ 𝑝 2 ∧ 𝑝 3 ) ∨ (𝑝 4 ∧ 𝑝 5 ∧ 𝑝 3 ). Conversely, gates with the same Boolean function can have distinct names, because a bind expression computes a name from the values of one row, whereas the function of a gate depends on all gates below it. For example, Proj {?𝑧 } (tp3 ) and Proj {?𝑧 } (Join(tp3, tp3 )) have the same Boolean provenance, but their sum gates have distinct tags.

Gate names and merging

SPARQLcirc merges the results of all queries of the plan into one RDF graph. All triples with one gate IRI describe one gate. An RDF graph contains every triple at most once, so an edge emitted by several rows or queries occurs once. One copy of an edge preserves the value of every gate exactly when sum and product are idempotent. Boolean functions are idempotent, whereas the provenance polynomials of N[𝑋 ] satisfy 𝑎 + 𝑎 = 2𝑎 [33]. The IRI of every gate other than a leaf is the value of a bind expression, which reads one row. The row of a join binds the gates of all operands, so a product gate is named after the list of its children, in which a gate repeats when two operands match the same triple. The edges into a sum or difference gate come from the rows that carry one mapping. Each of these rows contributes

4.2

Path-free patterns

The rewriting 𝛾 translates a select query 𝑄 into a plan 𝛾 (𝑄) of construct queries, as in (3). For every subpattern 𝑃, Definition 4.2 defines a rewritten pattern rw(𝑃, 𝑔𝑃 ) and the queries of 𝑃. The rows of rw(𝑃, 𝑔𝑃 ) bind the mappings of 𝑃 and their gates. The queries of 𝑃 output these gates and their edges to the gates of the operands. Definition 4.2 (Rewriting). Let 𝑃 be a subpattern of a query that is not a closure atom, and let 𝑔𝑃 be a variable, called the gate variable of 𝑃. The rewritten pattern rw(𝑃, 𝑔𝑃 ), the construct queries of 𝑃 and the plan 𝛾 (𝑃) are defined by recursion on 𝑃. (1) If 𝑃 is a triple pattern tp, then rw(𝑃, 𝑔𝑃 ) = reif (tp, 𝑔𝑃 ) and 𝛾 (𝑃) = ∅.

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

(2) If 𝑃 = Join(𝑃1, . . . , 𝑃𝑛 ), then, for fresh variables 𝑔𝑃1 , . . . , 𝑔𝑃𝑛 , rw(𝑃, 𝑔𝑃 ) = { rw(𝑃 1, 𝑔𝑃1 ) } · · · { rw(𝑃𝑛 , 𝑔𝑃𝑛 ) } bind(KEY_TIMES(𝑔𝑃1 , . . . , 𝑔𝑃𝑛 ) as 𝑔𝑃 ), 𝑞𝑃 = construct { 𝑔𝑃 a c:Times ; c:in 𝑔𝑃1 , . . . , 𝑔𝑃𝑛 } where { rw(𝑃, 𝑔𝑃 ) }, 𝛾 (𝑃) = {𝑞𝑃 } ∪ 𝛾 (𝑃 1 ) ∪ · · · ∪ 𝛾 (𝑃𝑛 ). (3) If 𝑃 = Union(𝑃1, . . . , 𝑃𝑛 ), then, for fresh variables 𝑔𝑃1 , . . . , 𝑔𝑃𝑛 , the tuple 𝑣¯𝑃 of the variables in scope at 𝑃 in lexicographic order and 𝑖 ∈ {1, . . . , 𝑛}, rw(𝑃, 𝑔𝑃 ) = { rw(𝑃 1, 𝑔𝑃1 ) } union · · · union { rw(𝑃𝑛 , 𝑔𝑃𝑛 ) } bind(KEY_PLUS(U, 𝜃 (𝑃), 𝑣¯𝑃 ) as 𝑔𝑃 ), 𝑞𝑃,𝑖 = construct { 𝑔𝑃 a c:Plus ; c:in 𝑔𝑃𝑖 } where { rw(𝑃𝑖 , 𝑔𝑃𝑖 ) bind(KEY_PLUS(U, 𝜃 (𝑃), 𝑣¯𝑃 ) as 𝑔𝑃 ) }, 𝛾 (𝑃) = {𝑞𝑃,1, . . . , 𝑞𝑃,𝑛 } ∪ 𝛾 (𝑃 1 ) ∪ · · · ∪ 𝛾 (𝑃𝑛 ). (4) If 𝑃 = Proj𝑌 (𝑃 ′ ), then, for a fresh variable 𝑔𝑃 ′ and the tuple 𝑌¯ of the variables in 𝑌 in lexicographic order, rw(𝑃, 𝑔𝑃 ) = { select 𝑌¯ where { rw(𝑃 ′, 𝑔𝑃 ′ ) } } bind(KEY_PLUS(P, 𝜃 (𝑃), 𝑌¯ ) as 𝑔𝑃 ), 𝑞𝑃 = construct { 𝑔𝑃 a c:Plus ; c:in 𝑔𝑃 ′ } where { rw(𝑃 ′, 𝑔𝑃 ′ ) bind(KEY_PLUS(P, 𝜃 (𝑃), 𝑌¯ ) as 𝑔𝑃 ) }, 𝛾 (𝑃) = {𝑞𝑃 } ∪ 𝛾 (𝑃 ′ ). (5) If 𝑃 = Filter𝜑 (𝑃 ′ ), then 𝑔𝑃 ′ = 𝑔𝑃 , rw(𝑃, 𝑔𝑃 ) = rw(𝑃 ′, 𝑔𝑃 ′ ) filter(𝜑) and 𝛾 (𝑃) = 𝛾 (𝑃 ′ ). (6) If 𝑃 = Diff(𝑃1, 𝑃2 ), then, for fresh variables 𝑔𝑃1 , 𝑔𝑃2 and 𝑠𝑃 and the tuple 𝑣¯𝑃1 of the variables in scope at 𝑃1 in lexicographic order, rw(𝑃, 𝑔𝑃 ) = rw(𝑃 1, 𝑔𝑃1 ) bind(KEY_MINUS(𝜃 (𝑃), 𝑣¯𝑃1 ) as 𝑔𝑃 ), 𝑞𝑃− = construct { 𝑠𝑃 a c:Plus ; c:in 𝑔𝑃2 } where {{ rw(𝑃1, 𝑔𝑃1 ) bind(KEY_PLUS(S, 𝜃 (𝑃), 𝑣¯𝑃1 ) as 𝑠𝑃 ) } { rw(𝑃2, 𝑔𝑃2 ) } }, 𝑞𝑃+ = construct { 𝑔𝑃 a c:Minus ; c:minuend 𝑔𝑃1 ; c:subtrahend 𝑠𝑃 . 𝑠𝑃 a c:Plus } where { rw(𝑃, 𝑔𝑃 ) bind(KEY_PLUS(S, 𝜃 (𝑃), 𝑣¯𝑃1 ) as 𝑠𝑃 ) }, 𝛾 (𝑃) = {𝑞𝑃− , 𝑞𝑃+ } ∪ 𝛾 (𝑃 1 ) ∪ 𝛾 (𝑃 2 ). For a query 𝑄 = Proj𝑌 (𝑃 ′ ), item (4) applies with 𝑃 = 𝑄 and the letter A in place of the letter P. For every row of 𝑞𝑄 with restriction 𝜇 to 𝑌 , the gate 𝑔𝑄 is the root of 𝜇, and the template of 𝑞𝑄 additionally contains the c:answerRoot and c:bind: triples of (3).

We call the plan 𝛾 (𝑄) of Definition 4.2 the flat plan. It creates one product gate per derivation and therefore repeats every part that derivations share. A basic graph pattern with 𝑚 triple patterns has up to |𝐺 |𝑚 derivations. In Figure 2, the product gates ⊗(𝑝 1, 𝑝 2, 𝑝 3 ) and ⊗(𝑝 4, 𝑝 5, 𝑝 3 ) of Omeprazole both contain 𝑝 3 . For a query that projects a basic graph pattern, the factored plan instead builds the circuit by variable elimination [18] so that derivations share the gates of their common parts.

We highlight the difference Diff(𝑃1, 𝑃2 ) of item (6). An optional without a filter abbreviates a union of a join and a difference (Section 2), and the identities of Appendix A reduce minus to differences. For a mapping 𝜇 of 𝑃 1 , the difference negates the disjunction over all mappings of 𝑃2 that are compatible with 𝜇. The negation does not distribute over the disjunction and must therefore cover all rows of the join of 𝑃1 and 𝑃2 that extend 𝜇. SPARQLprov [36] combines the rows of 𝜇 in a post-processing step that decodes the results, and NPCS [5] groups them by 𝜇 inside the endpoint. SPARQLcirc instead splits the difference into two construct queries. The subtrahend query 𝑞𝑃− names the sum gate 𝑠𝑃 after 𝜇 alone and binds 𝑠𝑃 in every row before the join with

Definition 4.4 (Factored plan). Let 𝑄 = Proj𝑌 (Join(tp1, . . . , tp𝑚 )), and let 𝑍 contain the variables of 𝑄 outside 𝑌 . A factor with scope 𝑆 maps some mappings of 𝑆 to gates, and its value at a mapping of a superset of 𝑆 is its value at the restriction to 𝑆. The base factor 𝐹 𝑗 has the set var(tp 𝑗 ) of the variables of tp 𝑗 as its scope and maps every mapping 𝜌 with 𝜌 (tp 𝑗 ) ∈ 𝐺 to the leaf 𝑥 𝜌 (tp 𝑗 ) . Eliminating a variable 𝑧 ∈ 𝑍 replaces the set A𝑧 of the factors whose scopes contain 𝑧 by a factor 𝐻𝑧 whose scope 𝑈𝑧 contains their other variables. For a mapping 𝜈 of 𝑈𝑧 , let 𝐴𝑧 (𝜈) contain the values 𝑎 such that every factor of A𝑧 is defined at 𝜈 ∪ {𝑧 ↦→ 𝑎}. If 𝐴𝑧 (𝜈) ≠ ∅, then É Ë 𝐻𝑧 (𝜈) = 𝑎∈𝐴𝑧 (𝜈 ) 𝐹 ∈ A𝑧 𝐹 (𝜈 ∪ {𝑧 ↦→ 𝑎}).

𝑃2 , so the edges of all rows of 𝜇 merge at 𝑠𝑃 . The minuend query 𝑞𝑃+ evaluates only rw(𝑃1, 𝑔𝑃1 ) and makes 𝑠𝑃 the subtrahend of the difference gate 𝑔𝑃 . Example 4.3 (Difference). The query SELECT ?x WHERE { :Aspirin :interactsWith ?x MINUS { ?x :interactsWith ?y } } returns the drugs with which Aspirin interacts and which interact with no drug. Since both operands of minus bind ?𝑥, the minus pattern equals the difference 𝐷 = Diff(tp1, tp4 ) for tp4 = (?𝑥, interactsWith, ?𝑦), in which Warfarin has the Boolean provenance 𝑝 1 ∧ ¬(𝑝 2 ∨ 𝑝 6 ). The join of tp1 and tp4 has the rows (𝑝 1, 𝑝 2 ) and (𝑝 1, 𝑝 6 ) for Warfarin. A single query that emits one ⊖-gate per row of the join yields the circuit of Figure 3(a), which denotes (𝑝 1 ∧ ¬𝑝 2 ) ∨ (𝑝 1 ∧ ¬𝑝 6 ) and is therefore true in a world with the triples of 𝑝 1 and 𝑝 2 but without the triple of 𝑝 6 , although 𝐷 removes Warfarin in this world. Under item (6), the subtrahend query collects both rows in 𝑠𝐷 = ⊕(𝑝 2, 𝑝 6 ), and the minuend query emits 𝑔𝐷 = ⊖({𝑝 1 }, 𝑠𝐷 ), so Figure 3(b) denotes 𝑝 1 ∧ ¬(𝑝 2 ∨ 𝑝 6 ). ⊕ ⊖ 𝑝2

𝑔𝐷 ⊖

𝑝1

⊕

𝑝1 𝑝6

(a) (𝑝 1 ∧ ¬𝑝 2 ) ∨ (𝑝 1 ∧ ¬𝑝 6 ) child or minuend

⊖

𝑝2

𝑠𝐷 𝑝6

(b) 𝑝 1 ∧ ¬(𝑝 2 ∨ 𝑝 6 ) subtrahend

Figure 3: Circuits for Warfarin in Example 4.3: (a) one ⊖-gate per row of the join, (b) the two queries of item (6). The plan 𝛾 (𝑄) contains one query for every join and every projection, one for every branch of a union and two for every difference. Every query reads only 𝐺 reif at the endpoint, so the queries are independent and can run concurrently.

4.3

Factored basic graph patterns

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

The factored plan eliminates the variables of 𝑍 in some order. The root of an answer 𝜇 is the sum gate over the product of the remaining factors at 𝜇. The gate 𝐻𝑧 (𝜈) is named by a tag of 𝑄 and 𝑧 and the values of 𝜈, and the other gates as in Definitions 4.1 and 4.2.

𝑝6 𝑝1

W

I 1

For the running query, 𝑍 = {?𝑥, ?𝑦}. Eliminating ?𝑥 first multiplies 𝐹 1 and 𝐹 2 , so 𝐻𝑥 has the scope {?𝑦} and maps Metformin to ℎ𝑥 = ⊕(⊗(𝑝 1, 𝑝 2 ), ⊗(𝑝 4, 𝑝 5 )) and Lisinopril to ℎ𝑥′ = ⊕(⊗(𝑝 1, 𝑝 6 )). Eliminating ?𝑦 then multiplies 𝐻𝑥 and 𝐹 3 , so 𝐻 𝑦 has the scope {?𝑧} and maps Omeprazole to ⊕(⊗(ℎ𝑥 , 𝑝 3 )) and Clopidogrel to ⊕(⊗(ℎ𝑥′ , 𝑝 7 )). The induced width of an elimination order is the largest |𝑈𝑧 |, so the order (?𝑥, ?𝑦) has induced width 1. The root of Omeprazole denotes 𝑝 3 ∧ ((𝑝 1 ∧ 𝑝 2 ) ∨ (𝑝 4 ∧ 𝑝 5 )). Lemma 4.5. Assume that distinct names have distinct IRIs.1 For every elimination order and every mapping 𝜇, the roots of 𝜇 in the factored plan and in the flat plan denote the same Boolean function. With an elimination order of induced width 𝑤, the factored plan creates 𝑂 (𝑚 |𝐺 | 𝑤+1 ) gates below the roots for fixed 𝑤 [18], whereas the flat plan creates up to |𝐺 |𝑚 product gates. For example, if Aspirin reaches Metformin through 𝑘 drugs and Metformin interacts with 𝑙 drugs, the flat plan creates 𝑘 · 𝑙 product gates for these walks and the factored plan 𝑘 + 𝑙 (Appendix F). SPARQLcirc writes the rows of every factor into a private namespace with SPARQL 1.1 Update, and every elimination reads the factors that earlier queries wrote there. The eliminations therefore run in sequence and need a writable endpoint.

4.4

Transitive closures

For a closure-free 𝑒, an 𝑒-step is a pair (𝑢, 𝑣) ∈ Rel𝑒 (𝐺). The joins of Definition 4.2 match a fixed number of triples, whereas a closure atom matches walks of 𝑒-steps of unbounded length. As in the factored plan, SPARQLcirc applies variable elimination along the walks, eliminates one node per step and builds one level per walk length. The levels form a variant of the Bellman–Ford circuit of 𝑒 built by recursion Fan et al. [23]. For nodes 𝑢 and 𝑣, a gate 𝑏𝑢𝑣 𝑒 on 𝑒 satisfies val𝑊 ( [[𝑏𝑢𝑣 ]]) = ⊤ exactly when (𝑢, 𝑣) ∈ Rel𝑒 (𝑊 ) (Appendix G). For a source 𝑠, let 𝑉𝑠 contain 𝑠 and every node that 𝑒-steps reach from 𝑠, let 𝐸𝑠 contain the 𝑒-steps between nodes of 𝑉𝑠 , and let 𝑛 = |𝑉𝑠 |. Level 1 maps every node 𝑣 to a gate 𝑟 1 (𝑣) for the walks of length 1 from 𝑠 to 𝑣, and level 𝑖 + 1 sums out the last node 𝑢 of the walks of level 𝑖 from the product of 𝑟𝑖 and 𝑏 𝑒 :
𝑒 𝑟 1 (𝑣) = ⊕ {𝑏𝑠𝑣 | (𝑠, 𝑣) ∈ 𝐸𝑠 } , (4)
𝑒 𝑟𝑖+1 (𝑣) = ⊕ {⊗({𝑟𝑖 (𝑢), 𝑏𝑢𝑣 }) | (𝑢, 𝑣) ∈ 𝐸𝑠 , 𝑟𝑖 (𝑢) ≠ 𝑔⊥ } . (5) The closure gate of 𝑣 is
𝑅(𝑣) = ⊕ {𝑟𝑖 (𝑣) | 1 ≤ 𝑖 ≤ 𝜆} ,

𝑝8 C

𝑝1

𝑝5

𝑝6 W

A

𝑝2

Aspirin 𝑝4

𝑝7 L

2

𝑝3

I

O 3

4

C

𝑝2

𝑝4 M

𝑝7 L

5

𝑝5

M

𝑝3

6

O 7

Figure 4: Levels 1 to 7 of :Aspirin :interactsWith+ ?y. by the gate of one step. At level 2, the sum gate of Metformin adds the product of the level-1 gate of Warfarin with 𝑝 2 and the product of the level-1 gate of Ibuprofen with 𝑝 5 , and denotes (𝑝 1 ∧ 𝑝 2 ) ∨ (𝑝 4 ∧ 𝑝 5 ). The cycle through Warfarin, Lisinopril and Clopidogrel returns to Aspirin at level 4 and keeps every level nonempty, so the construction runs 𝑛 = 7 levels. The closure gate of Warfarin sums the levels 1 and 5, and 𝑝 1 absorbs the level-5 product 𝑝 1 ∧𝑝 6 ∧𝑝 7 ∧𝑝 8 for the walk around the cycle. For a source-bound closure atom 𝐶 (Section 2), the input relation I𝐶 contains the mappings of the rows of the operands before 𝐶. The set 𝑆𝐶 contains the sources that I𝐶 binds, or only 𝛼 when the source is a constant, and the plan runs the construction once for every source 𝑠 ∈ 𝑆𝐶 . For a target 𝑣 returned from 𝑠, the mapping 𝐶 has the gate 𝑔 (𝑠, 𝑣) = 𝑅(𝑣). For ⋄ = ∗, 𝑔 (𝑠, 𝑠) is instead the 𝜇𝑠,𝑣 𝐶 𝐶 zero-length gate of 𝑠, which is 𝑔⊤ for a constant source and the sum gate 𝑜𝑠 over the leaves of the triples of 𝐺 with subject or object 𝑠 for a variable source. The plan materializes the mappings and their gates as a relation, and rw(𝐶, 𝑔𝐶 ) reads the relation in place of the reification of a triple pattern. In the pattern { :Aspirin :interactsWith ?x . ?x :interactsWith+ ?y }, the triple pattern binds the source ?𝑥, so 𝑆𝐶 = {Warfarin, Ibuprofen}, and the row with ?𝑥 = Warfarin and ?𝑦 = Lisinopril has the product gate ⊗(𝑝 1, 𝑔𝐶 (Warfarin, Lisinopril)). A path pattern with a constant target reduces to a closure atom (Appendix A). Theorem 4.6. Assume that distinct names have distinct IRIs. Let 𝐶 be a closure atom in a query of S, let 𝑠 ∈ 𝑆𝐶 , and let 𝑣 be a target that the construction returns from 𝑠, with 𝑣 = 𝑠 when 𝛼 is ?𝑦. For every possible world 𝑊 ⊆ 𝐺, val𝑊 ([[𝑔𝐶 (𝑠, 𝑣)]]) = ⊤ exactly when 𝐶 𝐶 on 𝑊 , so 𝑔 (𝑠, 𝑣) denotes BProv (𝜇𝐶 ). returns 𝜇𝑠,𝑣 𝐶 𝐶 𝑠,𝑣 For every source, the levels form an acyclic circuit with 𝑂 (𝑛(𝑛 + 𝑒 and level 1 with |𝐸𝑠 |)) gates. SPARQLcirc emits the gates 𝑏𝑢𝑣 construct queries and every further level with one more round. By default, every round writes its level into a private namespace with SPARQL 1.1 Update, where the next round reads it. If 𝐶 forms the whole query, every round can instead send the previous level in a values clause, so that the construction runs on a readonly endpoint. If 𝐶 is a proper subpattern of the query, the materialization of its relation requires a writable endpoint.

(6)

where 𝜆 is the last level. The construction stops at the first empty level and runs at most 𝑛 levels, because a longer walk repeats a node and is absorbed by the walk without the repeated segment. For the query SELECT ?y WHERE { :Aspirin :interactsWith+ ?y } over the graph of Figure 1, 𝑉𝑠 contains the seven drugs, and Figure 4 shows the levels, where a circle is the sum gate of a drug at one level, labeled by the initial of the drug, and an arrow multiplies 1 Distinct names share an IRI only if their 128-bit hashes collide. For 𝑁 gates, the

probability of a collision is below 𝑁 2 /2128 in the random-oracle model (Appendix B).

4.5

Correctness and probabilities

Definition 4.7 (Soundness and completeness). A plan for a query 𝑄 is sound if every mapping 𝜇 with a root in its circuit over 𝐺 reif satisfies [[root(𝜇)]] = BProv𝑄 (𝜇),

(7)

and complete if this circuit has a root for every answer of 𝑄. In the circuit of a sound and complete plan, the weighted model count of the root of every answer is the marginal probability of the answer, and every mapping without a root has probability 0.

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

The plan evaluates its queries once over 𝐺 reif , and every world is a subset of 𝐺. By induction on the subpatterns of 𝑄, every answer 𝜇 of 𝑄 is therefore the restriction of a row of rw(𝑄, 𝑔𝑄 ) and receives a root. Conversely, other rows can restrict to mappings that 𝑄 returns in no world, because item (6) of Definition 4.2 keeps every row of the minuend in the rewritten pattern of a difference. For Diff(𝑃, 𝑃), every mapping 𝜇 of 𝑃 is compatible with itself, and the difference gate of 𝜇 denotes ⊥. A mapping that is not an answer can therefore receive a root, and soundness requires this root to denote ⊥. Section 2 defines the function of a gate by recursion over the child relation, so this relation must be acyclic. The gates of a triple pattern are the leaves that its matches bind, and the gates of any other subpattern 𝑃 are the gates that its queries emit. Every child of a gate of 𝑃 is a gate of a proper subpattern of 𝑃, except that the child 𝑠𝑃 of a difference gate 𝑔𝑃 is a gate of 𝑃 itself and has children only among the gates of 𝑃2 . Within a closure atom, every edge leads to a lower level, and every factor of the factored plan is built from earlier factors. The child relation is therefore acyclic. Lemma 4.8. Assume that distinct names have distinct IRIs. Let 𝑄 be a query of S, let 𝑃 be a union, a projection or a difference in 𝑄, and let 𝜇 be a mapping whose domain consists of variables in scope at 𝑃. In the circuit of 𝛾 (𝑄) over 𝐺 reif , the gate 𝑔𝑃 named after 𝑃 and 𝜇 denotes BProv𝑃 (𝜇). If 𝑃 = Diff(𝑃 1, 𝑃2 ), the gate 𝑠𝑃 named after 𝑃 Ô and 𝜇 denotes 𝜈∼𝜇 BProv𝑃2 (𝜈).

Baselines. The plain query (Base) runs on 𝐺, and the reified query (Reification) runs on 𝐺 reif without provenance. We compare with NPCS [5], the state-of-the-art SPARQL provenance rewriting. For PQE, we merge the identical subexpressions of all answers into one DAG and compile it with CUDD 3.0.0. We run our reimplementation of the rewriting rules of NPCS, since its published JAR deviates from these rules beyond basic graph patterns (Appendix C). Protocol. The endpoint time of a method ends when the response or the circuit is stored, and the end-to-end time ends when all probabilities are written. We report the median of five runs after a warm-up run, medians over sets of queries and medians of paired ratios. The time budget is the same for every method and ranges from 600 to 5000 s (Appendix J).

5.1

Following the evaluation of NPCS [5], we measure the overhead of provenance on WatDiv relative to the plain query and the reified query. With 10.9 million triples on GraphDB, the reified query takes 8.7 times as long as the plain query, NPCS 1.9 times as long as the reified query and the flat plan 2.6 times as long as NPCS (Figure 5), or 0.87 s against 0.46 s end to end. The factored plan takes 4.3 times as long as NPCS. On the templates with minus, the flat plan takes 3.4 to 7.8 times as long as NPCS across the engines and sizes and exceeds the budget more often. Appendix J.1 gives all 30 templates on all three engines, sizes and encodings.

The root of a mapping 𝜇 is the gate 𝑔𝑄 named after 𝑄 and 𝜇, so Lemma 4.8 yields Equation (7), and Lemma 4.5 carries Equation (7) over to the factored plan.

The theorem and the computation of Pr(𝜇) extend to a triple with several identifiers (Appendix B). Finally, SPARQLcirc compiles every root into an OBDD with CUDD [53] or into a d-DNNF with d4 [41] and computes the weighted model count of the result (Appendix H).

5

Evaluation

In this section, we measure the overhead of circuit construction (Section 5.1), the growth of the endpoint time and of the provenance size with the number of derivations per answer (Section 5.2) and the end-to-end time of PQE (Section 5.3). Data. WatDiv [1] generates graphs of 10.9 and 109 million triples and queries from 20 templates of basic graph patterns, to which we add five optional and five minus templates. We report the WatDiv times under RDF-star annotations. gMark [7] generates chain queries with 𝑘 triple patterns and branching factor 𝑊 , the number of choices at every step, over graphs of 500,000 triples. On the 1.78 billion statements of Wikidata [62], each identified by its statement node, we run the 136 WDBench queries [3] that NPCS publishes and 45 property-path queries from WDBench. All probabilities are drawn uniformly from (0, 1). Engines. GraphDB 10.7.6 [44], Fuseki 5.4.0 with TDB2 [56] and Oxigraph 0.5.9 [45] run locally without extensions and receive SPARQL 1.1 requests and, for RDF-star, SPARQL-star requests.

Base

Reification

NPCS

linear

star

SPARQLcirc (flat)

SPARQLcirc (factored)

102

endpoint time (s)

Theorem 4.9. Assume that distinct names have distinct IRIs. For every query 𝑄 = Proj𝑌 (𝑃) of S, the plan 𝛾 (𝑄) is sound and complete, and so is the factored plan when 𝑃 is a basic graph pattern.

Overhead of circuit construction

100

10−2 snowflake complex

optional

minus

Figure 5: Endpoint time on WatDiv (GraphDB, 10.9M triples). One circuit saves time only when the answers share subexpressions. On WatDiv, merging the identical subexpressions of NPCS does not reduce the median size of its provenance, so the flat plan pays only the overhead of a construct query per operator and of storing the returned triples, whereas NPCS sends one select query. Most of this overhead is fixed per query, because with ten times as many triples, the plain query takes 3.9 times as long and the flat plan 1.5 times as long. The factored plan also writes every factor and runs the eliminations in sequence, and for minus, the subtrahend query evaluates the join of both operands.

5.2

Scalability with the number of derivations

We control the number of derivations per answer through the chain length 𝑘 and the branching factor 𝑊 of gMark and compare the endpoint time and the output size of NPCS and the factored plan (Figure 6). At 𝑊 = 4, the response of NPCS grows about fivefold per triple pattern, and the circuit grows linearly. At 𝑘 = 6, the response reaches 15.9 GiB, 101 times the size of the circuit. NPCS is faster for 𝑘 ≤ 5 at 𝑊 = 4 and for 𝑊 ≤ 16 at 𝑘 = 3, and the factored plan

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

Table 1: End-to-end comparison on Wikidata. GraphDB

6

Oxigraph

Derivations

Flat

NPCS

Ratio

Flat

NPCS

Ratio

Fewer than 102 102 to 104 At least 104

0 12 28

17 21 4

1.20 1.06 0.57

0 18 23

17 14 2

1.11 0.99 0.58

All

40

42

1.01

41

33

0.98

is faster for larger values, by a factor of about three at 𝑘 = 6. At 𝑘 = 7 and at 𝑊 = 32, NPCS exceeds the budget of 5000 s, whereas the factored plan completes.

output (MiB) time (s)

NPCS 10

3

10

1

10

4

10

2

1

2

3

SPARQLcirc (factored)

4

5

6

chain length k (W = 4)

7

1

2

4

timeout

8

16

32

branching factor W (k = 3)

Figure 6: Endpoint time and output size on gMark (GraphDB). NPCS lists every derivation of an answer, so its response grows with the number of derivations. The factored plan shares the common parts of the derivations, so its circuit grows only with the number of triple patterns. To share gates, the factored plan writes a factor from all matches of every triple pattern to the endpoint and takes 313 to 418 s in total at 𝑘 = 3. This time hardly depends on 𝑊 , because with a fixed number of triples, a larger 𝑊 yields fewer nodes, and each elimination creates at most one sum gate per node.

5.3

End-to-end PQE on Wikidata

We measure the end-to-end time of PQE on the WDBench queries and the property-path queries of Wikidata. We report the flat plan, which completes more queries than the factored plan (Appendix J.3). On the WDBench queries, the flat plan is faster than NPCS on 40 of the 82 queries that both methods complete on GraphDB and on 41 of 74 on Oxigraph, depending on the total number of derivations of the answers of a query. For each range of this number, Table 1 gives the number of faster queries per method and the median ratio of the time of the flat plan to that of NPCS. NPCS is faster on every query with fewer than 100 derivations, and the flat plan is faster on most queries with at least 10,000 derivations, where it takes 0.57 times as long as NPCS at the median. NPCS does not support transitive closures, whereas SPARQLcirc completes 35 of the 45 property-path queries on both engines, in a median of 3.4 s on GraphDB. The largest of these circuits has 1.2 million gates for 38,757 answers. The advantage of the flat plan on queries with many derivations stems from the preprocessing that NPCS requires before compilation. NPCS parses its expressions, which grow with the number of derivations, and merges them into one DAG. On the queries with at least 10,000 derivations, this takes about five times as long as reading the circuit of the flat plan.

Related Work

Probabilistic relational databases. Exact PQE has PTIME versus #P-hard dichotomies for unions of conjunctive queries [15] and for two classes of queries with negation [27], where even a difference of tractable queries can be #P-hard [39]. On a standard database system, Gatterbauer and Suciu compute exact probabilities or upper bounds for conjunctive queries without self-joins with SQL queries that obtain products through sums of logarithms [29]. SPARQL 1.1 offers no logarithm, exponential or product aggregate [34], so SPARQLcirc compiles the circuit that the endpoint returns. SPROUT approximates, in a PostgreSQL extension, the probability of the lineage that rewritten SQL queries compute [26], and ProvSQL builds provenance circuits as a PostgreSQL extension [52]. Unlike ProvSQL, SPARQLcirc computes gate names in SPARQL 1.1 queries. Probabilistic RDF. Earlier systems attach distributions to object values [60] or to node labels [42] and test triples or matches against a probability threshold. Huang and Liu compile the lineage of each answer of a conjunctive SPARQL query into a binary decision diagram and approximate the probability of transitive properties on acyclic graphs [37]. HAPPI computes the probability of each answer of a conjunctive query from a symbolic provenance expression [30]. These systems use dedicated processors and treat every answer separately. SPARQLcirc builds one circuit for all answers with SPARQL 1.1 queries and computes exact probabilities also for nonmonotone queries and transitive closures on cyclic graphs. Provenance for SPARQL. Semiring provenance [33] with monus [31] captures optional and minus [16], and spm-semirings in addition preserve the equivalences of SPARQL queries [32]. Dividino et al. annotate every SPARQL answer with a Boolean formula that also covers optional and difference through an extended SPARQL syntax [20], and TripleProv computes provenance in a dedicated engine [63]. Ganepola et al. compute the why-provenance of monotone Core-GQL queries by rewriting [28]. SPARQLprov and NPCS return one provenance expression per answer [5, 6, 36], whereas SPARQLcirc returns one circuit for all answers, and the gate names agree across queries and engines. Provenance under recursion. Deutch et al. build one layered Datalog provenance circuit for all derived tuples [19]. Bellman– Ford-style circuits [23] and algorithms [47] compute single-source provenance. ProvSQL 1.10 compiles recursive reachability queries into deterministic decomposable circuits [51]. There is a regular path query whose provenance has no d-DNNF or OBDD of size polynomial in the graph [2]. The circuit of a closure atom has polynomial size, but computing the probability of its root is #P-hard [61]. SPARQLcirc builds a Bellman–Ford-style circuit level by level with SPARQL 1.1 requests and stops at the first empty level.

7

Conclusion

We presented SPARQLcirc , a rewriting method for exact PQE on SPARQL 1.1 endpoints. The plans name every gate by its content, so independent construct queries build one provenance circuit for all answers. The plans are sound and complete for joins, unions, projection, filters, optional, difference and transitive closures. The ratio of the end-to-end time of PQE with one circuit to that with per-answer provenance expressions decreases with the number of derivations. Future work includes federated provenance circuits.

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

Acknowledgments The project was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - SFB 1574 - Project number 471687386 (“Circular Factory”). The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Jingcheng Wu.

References [1] Güneş Aluç, Olaf Hartig, M. Tamer Özsu, and Khuzaima Daudjee. 2014. Diversified Stress Testing of RDF Data Management Systems. In The Semantic Web – ISWC 2014 (LNCS, Vol. 8796). Springer, Cham, 197–212. doi:10.1007/978-3319-11964-9_13 [2] Antoine Amarilli, Timothy van Bremen, Octave Gaspard, and Kuldeep S. Meel. 2025. Approximating Queries on Probabilistic Graphs. Logical Methods in Computer Science 21, 4 (2025), 30:1–30:31. doi:10.46298/LMCS-21(4:30)2025 [3] Renzo Angles, Carlos Buil Aranda, Aidan Hogan, Carlos Rojas, and Domagoj Vrgoč. 2022. WDBench: A Wikidata Graph Query Benchmark. In The Semantic Web – ISWC 2022 (LNCS, Vol. 13489). Springer, Cham, 714–731. doi:10.1007/9783-031-19433-7_41 [4] Renzo Angles and Claudio Gutierrez. 2016. The Multiset Semantics of SPARQL Patterns. In The Semantic Web – ISWC 2016 (LNCS, Vol. 9981). Springer, Cham, 20–36. doi:10.1007/978-3-319-46523-4_2 [5] Zubaria Asma, Daniel Hernández, Luis Galárraga, Giorgos Flouris, Irini Fundulaki, and Katja Hose. 2024. NPCS: Native Provenance Computation for SPARQL. In Proceedings of the ACM Web Conference 2024 (WWW). ACM, New York, NY, USA, 2085–2093. doi:10.1145/3589334.3645557 [6] Zubaria Asma, Daniel Hernández, Luis Galárraga, Giorgos Flouris, Irini Fundulaki, and Katja Hose. 2026. Native Provenance Computation for Federated and Non-Federated SPARQL Queries. Transactions on Graph Data and Knowledge (TGDK) 4, 1 (2026), 4:1–4:43. doi:10.4230/TGDK.4.1.4 [7] Guillaume Bagan, Angela Bonifati, Radu Ciucanu, George H. L. Fletcher, Aurélien Lemay, and Nicky Advokaat. 2017. gMark: Schema-Driven Generation of Graphs and Queries. IEEE Transactions on Knowledge and Data Engineering 29, 4 (2017), 856–869. doi:10.1109/TKDE.2016.2633993 [8] Mihir Bellare and Phillip Rogaway. 1993. Random Oracles Are Practical: A Paradigm for Designing Efficient Protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security (CCS). ACM, New York, NY, USA, 62–73. doi:10.1145/168588.168596 [9] Dan Brickley and R. V. Guha. 2014. RDF Schema 1.1. W3C Recommendation. https://www.w3.org/TR/rdf-schema/. [10] Andrew Carlson, Justin Betteridge, Richard C. Wang, Estevam R. Hruschka, and Tom M. Mitchell. 2010. Coupled Semi-Supervised Learning for Information Extraction. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM). ACM, New York, NY, USA, 101–110. doi:10.1145/ 1718487.1718501 [11] Jeremy J. Carroll, Christian Bizer, Pat Hayes, and Patrick Stickler. 2005. Named Graphs, Provenance and Trust. In Proceedings of the 14th International Conference on World Wide Web (WWW). ACM, New York, NY, USA, 613–622. doi:10.1145/ 1060745.1060835 [12] İsmail İlkan Ceylan, Adnan Darwiche, and Guy Van den Broeck. 2021. OpenWorld Probabilistic Databases: Semantics, Algorithms, Complexity. Artificial Intelligence 295 (2021), 103474. doi:10.1016/j.artint.2021.103474 [13] Xuelu Chen, Muhao Chen, Weijia Shi, Yizhou Sun, and Carlo Zaniolo. 2019. Embedding Uncertain Knowledge Graphs. Proceedings of the AAAI Conference on Artificial Intelligence 33, 1 (2019), 3363–3370. doi:10.1609/aaai.v33i01.33013363 [14] Richard Cyganiak, David Wood, and Markus Lanthaler. 2014. RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation. https://www.w3.org/TR/rdf11concepts/. [15] Nilesh N. Dalvi and Dan Suciu. 2012. The Dichotomy of Probabilistic Inference for Unions of Conjunctive Queries. Journal of the ACM 59, 6 (2012), 30:1–30:87. doi:10.1145/2395116.2395119 [16] Carlos Viegas Damásio, Anastasia Analyti, and Grigoris Antoniou. 2012. Provenance for SPARQL Queries. In The Semantic Web – ISWC 2012 (LNCS, Vol. 7649). Springer, Berlin, Heidelberg, 625–640. doi:10.1007/978-3-642-351761_39 [17] Adnan Darwiche and Pierre Marquis. 2002. A Knowledge Compilation Map. Journal of Artificial Intelligence Research 17 (2002), 229–264. doi:10.1613/jair.989 [18] Rina Dechter. 1999. Bucket Elimination: A Unifying Framework for Reasoning. Artificial Intelligence 113, 1–2 (1999), 41–85. doi:10.1016/S0004-3702(99)00059-4 [19] Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen. 2014. Circuits for Datalog Provenance. In Proceedings of the 17th International Conference on Database Theory (ICDT). OpenProceedings.org, Konstanz, Germany, 201–212. doi:10.5441/002/icdt.2014.22

[20] Renata Dividino, Sergej Sizov, Steffen Staab, and Bernhard Schueler. 2009. Querying for Provenance, Trust, Uncertainty and Other Meta Knowledge in RDF. Journal of Web Semantics 7, 3 (2009), 204–219. doi:10.1016/j.websem.2009.07.004 [21] Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. 2014. Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). ACM, New York, NY, USA, 601–610. doi:10.1145/2623330.2623623 [22] Oren Etzioni, Michael Cafarella, Doug Downey, Stanley Kok, Ana-Maria Popescu, Tal Shaked, Stephen Soderland, Daniel S. Weld, and Alexander Yates. 2004. WebScale Information Extraction in KnowItAll (Preliminary Results). In Proceedings of the 13th International Conference on World Wide Web (WWW). ACM, New York, NY, USA, 100–110. doi:10.1145/988672.988687 [23] Austen Z. Fan, Paraschos Koutris, and Sudeepa Roy. 2025. Circuits and Formulas for Datalog over Semirings. Proceedings of the ACM on Management of Data 3, 2 (2025), 93:1–93:22. doi:10.1145/3725230 [24] Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. 2015. Inference and Learning in Probabilistic Logic Programs Using Weighted Boolean Formulas. Theory and Practice of Logic Programming 15, 3 (2015), 358–401. doi:10.1017/ S1471068414000076 [25] Jean-Christophe Filliâtre and Sylvain Conchon. 2006. Type-Safe Modular HashConsing. In Proceedings of the 2006 Workshop on ML. ACM, New York, NY, USA, 12–19. doi:10.1145/1159876.1159880 [26] Robert Fink, Jiewen Huang, and Dan Olteanu. 2013. Anytime Approximation in Probabilistic Databases. The VLDB Journal 22, 6 (2013), 823–848. doi:10.1007/ s00778-013-0310-5 [27] Robert Fink and Dan Olteanu. 2016. Dichotomies for Queries with Negation in Probabilistic Databases. ACM Transactions on Database Systems 41, 1 (2016), 4:1–4:47. doi:10.1145/2877203 [28] Koumudi Ganepola, Maxime Jakubowski, and Katja Hose. 2026. Computing WhyProvenance for Property Graph Queries. Proceedings of the VLDB Endowment 19, 11 (2026), 3552–3564. doi:10.14778/3836663.3836708 [29] Wolfgang Gatterbauer and Dan Suciu. 2017. Dissociation and Propagation for Approximate Lifted Inference with Standard Relational Database Management Systems. The VLDB Journal 26, 1 (2017), 5–30. doi:10.1007/s00778-016-0434-5 [30] Garima Gaur, Abhishek Dang, Arnab Bhattacharya, and Srikanta Bedathur. 2021. Computing and Maintaining Provenance of Query Result Probabilities in Uncertain Knowledge Graphs. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management (CIKM). ACM, New York, NY, USA, 545–554. doi:10.1145/3459637.3482330 [31] Floris Geerts and Antonella Poggi. 2010. On Database Query Languages for K-relations. Journal of Applied Logic 8, 2 (2010), 173–185. doi:10.1016/j.jal.2009. 09.001 [32] Floris Geerts, Thomas Unger, Grigoris Karvounarakis, Irini Fundulaki, and Vassilis Christophides. 2016. Algebraic Structures for Capturing the Provenance of SPARQL Queries. Journal of the ACM 63, 1 (2016), 7:1–7:63. doi:10.1145/2810037 [33] Todd J. Green, Gregory Karvounarakis, and Val Tannen. 2007. Provenance Semirings. In Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). ACM, New York, NY, USA, 31–40. doi:10.1145/1265530.1265535 [34] Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. https://www.w3.org/TR/sparql11-query/. [35] Olaf Hartig, Pierre-Antoine Champin, Gregg Kellogg, and Andy Seaborne. 2021. RDF-star and SPARQL-star. W3C Final Community Group Report. https: //www.w3.org/2021/12/rdf-star.html [36] Daniel Hernández, Luis Galárraga, and Katja Hose. 2021. Computing HowProvenance for SPARQL Queries via Query Rewriting. Proceedings of the VLDB Endowment 14, 13 (2021), 3389–3401. doi:10.14778/3484224.3484235 [37] Hai Huang and Chengfei Liu. 2009. Query Evaluation on Probabilistic RDF Databases. In Web Information Systems Engineering – WISE 2009 (LNCS, Vol. 5802). Springer, Berlin, Heidelberg, 307–320. doi:10.1007/978-3-642-04409-0_32 [38] Gregg Kellogg, Olaf Hartig, Pierre-Antoine Champin, and Andy Seaborne. 2026. RDF 1.2 Concepts and Abstract Data Model. W3C Candidate Recommendation Snapshot. https://www.w3.org/TR/rdf12-concepts/. [39] Sanjeev Khanna, Sudeepa Roy, and Val Tannen. 2011. Queries with Difference on Probabilistic Databases. Proceedings of the VLDB Endowment 4, 11 (2011), 1051–1062. doi:10.14778/3402707.3402741 [40] Roman Kontchakov and Egor V. Kostylev. 2016. On Expressibility of NonMonotone Operators in SPARQL. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR). AAAI Press, Palo Alto, CA, USA, 369–378. [41] Jean-Marie Lagniez and Pierre Marquis. 2017. An Improved Decision-DNNF Compiler. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI). International Joint Conferences on Artificial Intelligence Organization, California, 667–673. doi:10.24963/ijcai.2017/93

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

[42] Xiang Lian and Lei Chen. 2011. Efficient Query Answering in Probabilistic RDF Graphs. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (SIGMOD). ACM, New York, NY, USA, 157–168. doi:10. 1145/1989323.1989341 [43] Stanislav Malyshev, Markus Krötzsch, Larry González, Julius Gonsior, and Adrian Bielefeldt. 2018. Getting the Most Out of Wikidata: Semantic Technology Usage in Wikipedia’s Knowledge Graph. In The Semantic Web – ISWC 2018 (LNCS, Vol. 11137). Springer, Cham, 376–394. doi:10.1007/978-3-030-00668-6_23 [44] Ontotext. 2024. GraphDB. https://graphdb.ontotext.com/. Version 10.7.6. [45] Thomas Pellissier Tanon. 2026. Oxigraph 0.5.9. doi:10.5281/zenodo.7408022 [46] Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. 2009. Semantics and Complexity of SPARQL. ACM Transactions on Database Systems 34, 3 (2009), 16:1–16:45. doi:10.1145/1567274.1567278 [47] Yann Ramusat, Silviu Maniu, and Pierre Senellart. 2021. ProvenanceBased Algorithms for Rich Queries over Graph Databases. In Proceedings of the 24th International Conference on Extending Database Technology (EDBT). OpenProceedings.org, Konstanz, Germany, 73–84. doi:10.5441/002/edbt.2021.08 [48] Christopher Ré, Nilesh Dalvi, and Dan Suciu. 2007. Efficient Top-k Query Evaluation on Probabilistic Data. In Proceedings of the 23rd International Conference on Data Engineering (ICDE). IEEE, Piscataway, NJ, USA, 886–895. doi:10.1109/ICDE.2007.367934 [49] Tian Sang, Paul Beame, and Henry Kautz. 2005. Performing Bayesian Inference by Weighted Model Counting. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI). AAAI Press, Menlo Park, CA, USA, 475–481. [50] Aryak Sen, Silviu Maniu, and Pierre Senellart. 2026. ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data. In Proceedings of the 42nd International Conference on Data Engineering (ICDE). IEEE, Piscataway, NJ, USA, 1252–1265. doi:10.1109/ICDE65706.2026.00098 [51] Pierre Senellart et al. 2026. ProvSQL: Semiring Provenance and Probability Management for PostgreSQL, Versions 1.7.0 to 1.12.0. doi:10.5281/zenodo. 19512786 [52] Pierre Senellart, Louis Jachiet, Silviu Maniu, and Yann Ramusat. 2018. ProvSQL: Provenance and Probability Management in PostgreSQL. Proceedings of the VLDB Endowment 11, 12 (2018), 2034–2037. doi:10.14778/3229863.3236253 [53] Fabio Somenzi. 2015. CUDD: CU Decision Diagram Package Release 3.0.0. University of Colorado at Boulder. [54] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. 2011. Probabilistic Databases. Morgan & Claypool, San Rafael, CA, USA. doi:10.2200/ S00362ED1V01Y201105DTM016 [55] Nicholas P. Tatonetti, Patrick P. Ye, Roxana Daneshjou, and Russ B. Altman. 2012. Data-Driven Prediction of Drug Effects and Interactions. Science Translational Medicine 4, 125 (2012), 125ra31. doi:10.1126/scitranslmed.3003377 [56] The Apache Software Foundation. 2025. Apache Jena Fuseki. https://jena.apache. org/documentation/fuseki2/. Version 5.4.0. [57] The Eclipse Foundation. 2026. Eclipse RDF4J. https://rdf4j.org/. Versions 4.2.1 and 5.3.2. [58] Transaction Processing Performance Council. 2022. TPC-H: A Decision Support Benchmark (Standard Specification). https://www.tpc.org/tpch/. Revision 3.0.1. [59] G. S. Tseitin. 1983. On the Complexity of Derivation in Propositional Calculus. In Automation of Reasoning: 2. Classical Papers on Computational Logic 1967–1970, Jörg H. Siekmann and Graham Wrightson (Eds.). Springer, Berlin, Heidelberg, 466–483. doi:10.1007/978-3-642-81955-1_28 [60] Octavian Udrea, V. S. Subrahmanian, and Zoran Majkić. 2006. Probabilistic RDF. In Proceedings of the IEEE International Conference on Information Reuse and Integration (IRI). IEEE, Piscataway, NJ, USA, 172–177. doi:10.1109/IRI.2006.252408 [61] Leslie G. Valiant. 1979. The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing 8, 3 (1979), 410–421. doi:10.1137/0208032 [62] Denny Vrandečić and Markus Krötzsch. 2014. Wikidata: A Free Collaborative Knowledgebase. Communications of the ACM 57, 10 (2014), 78–85. doi:10.1145/ 2629489 [63] Marcin Wylot, Philippe Cudré-Mauroux, and Paul Groth. 2014. TripleProv: Efficient Processing of Lineage Queries in a Native RDF Store. In Proceedings of the 23rd International Conference on World Wide Web (WWW). ACM, New York, NY, USA, 455–466. doi:10.1145/2566486.2568014

⊥ otherwise. For a mapping 𝜇 with dom(𝜇) ⊆ 𝑌 , the root of 𝜇 in the flat plan denotes 𝑚 Ü Û
Φflat (𝜇) = 𝐹 𝑗 𝜌 | var(tp 𝑗 ) . (8) 𝜌:𝑉𝑄 →adom(𝐺 ) 𝑗=1 𝜌 |𝑌 =𝜇

Let F𝑖 be the factors after eliminating 𝑧 1, . . . , 𝑧𝑖 . For a binding 𝜌 of the remaining variables, let Ü Û
𝐼𝑖 (𝜌) = 𝑓 (𝜌 ∪ 𝜅)| scope(𝑓 ) . (9) 𝜅:{𝑧 1 ,...,𝑧𝑖 }→adom(𝐺 ) 𝑓 ∈ F0

We prove that the conjunction of the factors in F𝑖 at 𝜌 equals 𝐼𝑖 (𝜌). For 𝑖 = 0, Equation (9) contains the unique empty assignment and equals the original factor conjunction. Assume the claim for 𝑖 − 1, let 𝑧 = 𝑧𝑖 , and let 𝜌𝑎 = 𝜌 ∪ {𝑧 ↦→ 𝑎} for 𝑎 ∈ adom(𝐺). The scopes of the factors outside A𝑧 do not contain 𝑧. The claim for 𝑖 − 1 and distributivity therefore give Û  Ü Û     𝐼𝑖 (𝜌) = 𝑓 (𝜌 | ) ∧ 𝑓 (𝜌 | ) 𝑎 scope( 𝑓 ) scope(𝑓 )    𝑓 ∉A𝑧 𝑎∈adom(𝐺 )  𝑓 ∈ A𝑧  Û = 𝐻𝑧 (𝜌 |𝑈𝑧 ) ∧ 𝑓 (𝜌 | scope( 𝑓 ) ). 𝑓 ∉A𝑧

The second equality holds because the terms of the values 𝑎 ∉ 𝐴𝑧 (𝜌 |𝑈𝑧 ) are ⊥, and the disjunction of the other terms is the function of the gate 𝐻𝑧 (𝜌 |𝑈𝑧 ) of Definition 4.4, or ⊥ when 𝐴𝑧 (𝜌 |𝑈𝑧 ) is empty. The result is the conjunction after replacing A𝑧 by 𝐻𝑧 . At 𝑖 = 𝑘, restriction to 𝜇 yields Equation (8), so the roots of 𝜇 in both plans denote the same Boolean function. □

A.2

Transitive closures

𝑒 form an acyclic circuit and Proof of Theorem 4.6. The gates 𝑏𝑢𝑣 satisfy the equivalence of Section 4.4 (Appendix G). For an 𝑒-walk 𝜋 = (𝑣 0, . . . , 𝑣 ℓ ) in 𝐸𝑠 , we write 𝜋 : 𝑣 0 { 𝑣 ℓ and |𝜋 | = ℓ, and let

𝜓 (𝜋) =

[[𝑏 𝑒𝑣 𝑗 −1 𝑣 𝑗 ]].

𝑗=1

We prove by induction on 𝑖 ≥ 1 that Ü [[𝑟𝑖 (𝑣)]] = 𝜓 (𝜋).

(10)

𝜋 :𝑠 {𝑣 |𝜋 |=𝑖

For 𝑖 = 1, Equation (4) is the disjunction over all one-edge 𝑒-walks from 𝑠 to 𝑣. Assume Equation (10) for 𝑖. Equation (5) gives Ü
𝑒 [[𝑟𝑖+1 (𝑣)]] = [[𝑟𝑖 (𝑢)]] ∧ [[𝑏𝑢𝑣 ]] (𝑢,𝑣) ∈𝐸𝑠

=

A Proofs A.1 Factored basic graph patterns

Ü

Ü

𝑒 𝜓 (𝜋 ′ ) ∧ [[𝑏𝑢𝑣 ]]

(𝑢,𝑣) ∈𝐸𝑠 𝜋 ′ :𝑠 {𝑢 |𝜋 ′ |=𝑖

= Proof of Lemma 4.5. Let 𝑉𝑄 be the variables of 𝑄, let adom(𝐺) contain the terms that occur in 𝐺, and let (𝑧 1, . . . , 𝑧𝑘 ) be the elimination order. We identify a factor with the map that sends every mapping of the scope to the Boolean function of the gate of the factor at the mapping, and to ⊥ where the factor has no gate. The base factor 𝐹 𝑗 thus maps 𝜌 to 𝑥 𝜌 (tp 𝑗 ) when 𝜌 (tp 𝑗 ) ∈ 𝐺 and to

ℓ Û

Ü

𝜓 (𝜋).

𝜋 :𝑠 {𝑣 |𝜋 |=𝑖+1

Appending (𝑢, 𝑣) to every walk of length 𝑖 ending at 𝑢 gives exactly the walks of length 𝑖 + 1 ending at 𝑣. If 𝑣 ≠ 𝑠, a shortest positive 𝑒-walk from 𝑠 to 𝑣 contains no repeated node and has length at most 𝑛 − 1, because removing the

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

segment between equal nodes yields a shorter walk. If 𝑣 = 𝑠, the same deletion argument makes a shortest positive closed walk a simple cycle of length at most 𝑛. The construction runs 𝜆 ≤ 𝑛 levels, and Equation (6) gives Ü [[𝑅(𝑣)]] = 𝜓 (𝜋). 𝜋 :𝑠 {𝑣 1≤ |𝜋 | ≤𝜆

If the construction stopped because level 𝜆 + 1 is empty, no walk exceeds 𝜆, since every longer walk has a prefix of length 𝜆 + 1. Otherwise 𝜆 = 𝑛. The closure gate 𝑅(𝑣) is therefore true in 𝑊 whenever (𝑠, 𝑣) ∈ Rel𝑒 + (𝑊 ), because a shortest such walk has length at most 𝜆. Conversely, every satisfied term denotes an 𝑒walk in 𝑊 , so for every 𝑊 ⊆ 𝐺 val𝑊 ( [[𝑅(𝑣)]]) = ⊤ ⇐⇒ (𝑠, 𝑣) ∈ Rel𝑒 + (𝑊 ).

(11)

𝐶 . For ⋄ = +, 𝑔 (𝑠, 𝑣) = 𝑅(𝑣), and 𝐶 returns 𝜇 on𝑊 exactly Let 𝜇 = 𝜇𝑠,𝑣 𝐶

when (𝑠, 𝑣) ∈ Rel𝑒 + (𝑊 ). For ⋄ = ∗ and 𝑣 ≠ 𝑠, 𝑔𝐶 (𝑠, 𝑣) = 𝑅(𝑣) as well, and the same equivalence holds because a walk from 𝑠 to 𝑣 ≠ 𝑠 has positive length. For ⋄ = ∗ and 𝑣 = 𝑠, 𝑔𝐶 (𝑠, 𝑠) is the zero-length gate of 𝑠. For a constant source, the zero-length gate is 𝑔⊤ , and 𝐶 returns 𝜇 on every𝑊 . For a variable source, the zero-length gate is 𝑜𝑠 , which is true in𝑊 exactly when 𝑠 is the subject or object of a triple of𝑊 . The atom 𝐶 returns 𝜇 on 𝑊 under the same condition, because the first 𝑒-step of a closed walk at 𝑠 uses a triple of𝑊 whose subject or object is 𝑠. In every case, val𝑊 ([[𝑔𝐶 (𝑠, 𝑣)]]) = ⊤ exactly when 𝐶 returns 𝜇 on 𝑊 , which holds exactly when val𝑊 (BProv𝐶 (𝜇)) = ⊤ by the definition of BProv𝐶 (·) in Section 2. The two Boolean functions therefore agree under every valuation of 𝑋 . Each of the at most 𝑛 levels has at most |𝑉𝑠 | sum gates and |𝐸𝑠 | product gates, so the levels have 𝑂 (𝑛(𝑛 + |𝐸𝑠 |)) gates. One further sum gate per target forms 𝑅(𝑣). Level 𝑖 + 1 references only the gates 𝑒 and level-𝑖 gates, so the level order is topological. 𝑏𝑢𝑣 □

A.3

Correctness of the plans

Proof of Lemma 4.8. Under the assumption, two gates have the same IRI exactly when they have the same name, and we use three facts. (1) Two product gates have the same IRI if and only if their lists of children are equal up to order, because the name (T, sort(𝑐 1, . . . , 𝑐𝑛 )) is the same for two lists of children exactly when the lists are equal up to order. (2) Two sum gates, or two difference gates, have the same IRI if and only if they have the same letter, the same mapping and subpatterns equal up to the identities of Definition 4.1. The name (𝐿, 𝜃 (𝑃), 𝜏 (𝑎 1 ), . . . , 𝜏 (𝑎𝑘 )) lists the values 𝑎 𝑗 of the variables in scope at 𝑃 under the mapping, with 𝑎 𝑗 = unbound for an unbound variable, 𝜃 (𝑃) determines 𝑃 up to these identities, which preserve Boolean provenance, and 𝜏 is injective. (3) The IRI of a gate depends only on the row, because a key expression applies only functions whose values SPARQL 1.1 fixes on IRIs and literals (Appendix E), and 𝐺 reif contains no blank nodes. For a pattern 𝑃 and a mapping 𝜇, let 𝑣¯𝑃 be the tuple of the variables in scope at 𝑃 in lexicographic order, as in Definition 4.2, let Cand𝑃 (𝜇) be the gates bound by the rows of rw(𝑃, 𝑔𝑃 ) that restrict to 𝜇 on 𝑣¯𝑃 , and let Ü Ü Φ𝑃 (𝜇) = [[𝑔]], ∅ = ⊥. (12) 𝑔∈Cand𝑃 (𝜇 )

We then prove Φ𝑃 (𝜇) = BProv𝑃 (𝜇) by structural induction on 𝑃, for every subpattern 𝑃 that is not a closure atom with a variable source and for every mapping 𝜇. The base cases are triple patterns and closure atoms. For a compound pattern, the induction hypothesis is the claim for each of its direct subpatterns and every mapping. For a closure atom we prove the claim at the mappings whose source lies in 𝑆𝐶 , and the join and difference cases use the source-bound condition to apply it. Triple pattern. For a matching triple 𝑡, Cand𝑃 (𝜇) = {𝑥𝑡 } and Φ𝑃 (𝜇) = 𝑥𝑡 = BProv𝑃 (𝜇). For every other mapping, both sides are ⊥. Closure atom. Let 𝑃 = 𝐶 = (𝛼, 𝑒 ⋄ , ?𝑦). Every row of 𝐶 restricts 𝐶 with 𝑠 ∈ 𝑆 and a returned target 𝑣, and on 𝑣¯𝐶 to a mapping 𝜇𝑠,𝑣 𝐶 all rows for one pair (𝑠, 𝑣) bind the gate 𝑔𝐶 (𝑠, 𝑣) of Section 4.4. For 𝐶 ) = [[𝑔 (𝑠, 𝑣)]] = BProv (𝜇𝐶 ). If 𝑠 ∈ 𝑆𝐶 , Theorem 4.6 gives Φ𝐶 (𝜇𝑠,𝑣 𝐶 𝐶 𝑠,𝑣 the construction does not return 𝑣, then (𝑠, 𝑣) ∉ Rel𝑒 + (𝑊 ) for every 𝐶 ) = ⊥ and both sides are ⊥. Thus 𝑊 ⊆ 𝐺, so BProv𝐶 (𝜇𝑠,𝑣 Φ𝐶 (𝜇) = BProv𝐶 (𝜇)

for every 𝜇 whose source lies in 𝑆𝐶 . (13)

For a constant source, 𝑆𝐶 = {𝛼 }, so Equation (13) holds for every 𝜇. Filter. Let 𝑃 = Filter𝜑 (𝑃 ′ ). If 𝜇 satisfies 𝜑, then Cand𝑃 (𝜇) = Cand𝑃 ′ (𝜇) and the induction hypothesis gives Φ𝑃 (𝜇) = BProv𝑃 ′ (𝜇) = BProv𝑃 (𝜇). If 𝜇 does not satisfy 𝜑, item (5) keeps filter(𝜑) in the rewritten pattern, so Cand𝑃 (𝜇) = ∅ and Φ𝑃 (𝜇) = ⊥, and BProv𝑃 (𝜇) = ⊥ by the filter case of Section 2. Join. Let 𝑃 = Join(𝑃 1, . . . , 𝑃𝑛 ). The gates of Cand𝑃 (𝜇) are the product gates of the compatible decompositions 𝜇 = 𝜇 1 ∪· · ·∪𝜇𝑛 and choices 𝑔𝑖 ∈ Cand𝑃𝑖 (𝜇𝑖 ). Fix a compatible decomposition 𝜇 = 𝜇 1 ∪ Ó · · ·∪𝜇𝑛 and a world 𝑊 ⊆ 𝐺. We show that val𝑊 satisfies 𝑖 Φ𝑃𝑖 (𝜇𝑖 ) Ó exactly when val𝑊 satisfies 𝑖 BProv𝑃𝑖 (𝜇𝑖 ). For an operand that is not a closure atom with a variable source, the induction hypothesis gives Φ𝑃𝑖 (𝜇𝑖 ) = BProv𝑃𝑖 (𝜇𝑖 ). Let 𝑃𝑖 = 𝐶 be a closure atom with a variable source. If val𝑊 satisfies every Φ𝑃 𝑗 (𝜇 𝑗 ), then 𝐶 has a row at 𝜇𝑖 , so the source of 𝜇𝑖 lies in 𝑆𝐶 and Equation (13) applies. If val𝑊 satisfies every BProv𝑃 𝑗 (𝜇 𝑗 ), induction on 𝑗 shows that val𝑊 satisfies Φ𝑃 𝑗 (𝜇 𝑗 ) for every 𝑗 < 𝑖. Every such 𝑃 𝑗 then has a row at 𝜇 𝑗 , Ð so 𝜌 = 𝑗 <𝑖 𝜇 𝑗 belongs to I𝐶 . The source-bound condition makes 𝜌 bind the source, and compatibility gives 𝜌 (𝛼) = 𝜇𝑖 (𝛼). The source of 𝜇𝑖 therefore lies in 𝑆𝐶 , and Equation (13) applies. Distributivity over the choices of the gates 𝑔𝑖 and the equivalence just shown give 𝑛 𝑛 Ü Û Ü Û Φ𝑃 (𝜇) = Φ𝑃𝑖 (𝜇𝑖 ) = BProv𝑃𝑖 (𝜇𝑖 ) = BProv𝑃 (𝜇), 𝜇=∪𝑖 𝜇𝑖 𝑖=1

𝜇=∪𝑖 𝜇𝑖 𝑖=1

with both disjunctions over the compatible decompositions of 𝜇. Union. Let 𝑃 = Union(𝑃1, . . . , 𝑃𝑛 ). By fact (2), all rows for 𝜇 Ð bind the same gate 𝑔𝑃 , with child set 𝑖 Cand𝑃𝑖 (𝜇). Thus, Φ𝑃 (𝜇) = Ô Ô [[𝑔𝑃 ]] = 𝑖 Φ𝑃𝑖 (𝜇) = 𝑖 BProv𝑃𝑖 (𝜇) = BProv𝑃 (𝜇). If every child set is empty, Cand𝑃 (𝜇) = ∅ and both sides are ⊥. Projection. Let 𝑃 = Proj𝑌 (𝑃 ′ ). For a mapping 𝜇 with dom(𝜇) ⊆ Ð 𝑌 , the child set of 𝑔𝑃 is 𝜇 ′ :𝜇 ′ |𝑌 =𝜇 Cand𝑃 ′ (𝜇 ′ ). Hence, Φ𝑃 (𝜇) = Ô Ô ′ ′ 𝜇 ′ |𝑌 =𝜇 Φ𝑃 ′ (𝜇 ) = 𝜇 ′ |𝑌 =𝜇 BProv𝑃 ′ (𝜇 ) = BProv𝑃 (𝜇). Difference. Let 𝑃 = Diff(𝑃 1, 𝑃2 ) and let 𝑔𝑃 , 𝑠𝑃 be the gates of Definition 4.2. For every 𝜇 with Cand𝑃1 (𝜇) ≠ ∅, pos(𝑔𝑃 ) = Ð Cand𝑃1 (𝜇), ch(𝑠𝑃 ) = 𝜈∼𝜇 Cand𝑃2 (𝜈) and neg(𝑔𝑃 ) = 𝑠𝑃 . In the subtrahend query, the group of 𝑃 1 binds 𝑠𝑃 before the join with 𝑃2 . The name 𝑠𝑃 therefore depends on the mapping of 𝑃1 alone, also when 𝑃2 binds a variable that the mapping of 𝑃1 leaves

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

unbound. If Cand𝑃1 (𝜇) = ∅, then Φ𝑃 (𝜇) = ⊥ and BProv𝑃 (𝜇) implies BProv𝑃1 (𝜇) = Φ𝑃1 (𝜇) = ⊥. Otherwise 𝜇 belongs to I𝑃2 when 𝑃2 is a closure atom with a variable source. If 𝜇 leaves the source unbound, the source-bound condition and Equation (1) give BProv𝑃1 (𝜇) = ⊥, and both sides are ⊥. Otherwise every 𝜈 ∼ 𝜇 with a source takes the source 𝜇 (𝛼). The source-bound condition places 𝜇 (𝛼) in 𝑆𝑃2 , so Equation (13) gives Φ𝑃2 (𝜈) = BProv𝑃2 (𝜈) for every 𝜈 ∼ 𝜇. For any other 𝑃2 , the induction hypothesis gives the same equation. Therefore, Ü Ü © ª ©Ü ª Φ𝑃 (𝜇) = ­ [[𝑔]] ® ∧ ¬ ­ [[𝑔′ ]] ® ′ «𝑔∈Cand𝑃1 (𝜇 ) ¬ «𝜈∼𝜇 𝑔 ∈Cand𝑃2 (𝜈 ) ¬ Ü = BProv𝑃1 (𝜇) ∧ ¬ BProv𝑃2 (𝜈) = BProv𝑃 (𝜇). 𝜈∼𝜇

An Opt(𝑃1, 𝑃2 ) without a filter is Union(Join(𝑃 1, 𝑃2 ), Diff(𝑃1, 𝑃2 )) (Section 2), so the cases above cover it. A minus follows from the reduction to Diff below. By fact (2), Cand𝑃 (𝜇) = {𝑔𝑃 } for a union, projection or difference 𝑃, so 𝑔𝑃 denotes Φ𝑃 (𝜇) = BProv𝑃 (𝜇), and for 𝑃 = Diff(𝑃1, 𝑃2 ) by Ô the difference case, 𝑠𝑃 denotes 𝜈∼𝜇 BProv𝑃2 (𝜈). □ Proof of Theorem 4.9. Lemma 4.8 proves Equation (7) for the root 𝑔𝑄 of every mapping 𝜇, so the plan is sound. If Cand𝑄 (𝜇) = ∅, the plan produces no root for 𝜇, and Equation (12) gives Φ𝑄 (𝜇) = ⊥, which equals BProv𝑄 (𝜇) by the induction in the proof of Lemma 4.8. By Equation (1), 𝜇 is then not an answer, so the plan is complete. The circuit is acyclic by Section 4.5 and the proof of Theorem 4.6, because subpatterns that share a gate have the same height when filters are not counted. Every answer 𝜇 also has a root in the factored plan, because every factor is defined at the restriction of a match that extends 𝜇. Conversely, by Equation (9), the remaining factors are all defined at 𝜇 only when a match extends 𝜇, so Lemma 4.5 applies to every root of the factored plan. □ Coverage beyond the grammar. W3C Minus(𝑃1, 𝑃2 ) removes a mapping of 𝑃1 exactly when a compatible mapping of 𝑃2 shares a variable with it [34]. The following facts reduce Minus(𝑃1, 𝑃2 ) to Diff for all patterns 𝑃1 and 𝑃2 once their unions are moved to the top, and each fact follows from the definitions of the operators. The operator Minus distributes over a union in its first operand, and Minus(𝑃 1, Union(𝑃2, 𝑃3 )) = Minus(Minus(𝑃1, 𝑃2 ), 𝑃3 ). All mappings of a union-free pattern bind the same set of variables. For union-free 𝑃1 and 𝑃 2 , Minus(𝑃1, 𝑃2 ) is 𝑃 1 if the mappings of 𝑃1 and the mappings of 𝑃2 bind disjoint sets of variables, and Diff(𝑃 1, 𝑃2 ) otherwise. Before it moves any union, SPARQLcirc applies two further facts. The pattern Minus(𝑃 1, 𝑃2 ) is Diff(𝑃 1, 𝑃2 ) when, on every graph, every mapping of 𝑃 1 and every mapping of 𝑃2 bind a common variable, and 𝑃1 when every mapping of 𝑃1 and every mapping of 𝑃2 bind disjoint sets of variables. A filter Filter𝜑 (𝑃) mentions only variables that every mapping of 𝑃 binds, so 𝑃1 optional {𝑃2 filter 𝜑 } equals Opt(𝑃 1, Filter𝜑 (𝑃 2 )) [34]. A path pattern (𝛼, 𝑒 ⋄ , 𝑐) with a constant target 𝑐 equals the closure atom (𝑐, ('^'𝑒) ⋄ , 𝛼) when 𝛼 is a variable, because W3C evaluates a constant target as the constant source of the inverse path [34], and Proj∅ (FiltersameTerm(?𝑦,𝑐 ) ((𝛼, 𝑒 ⋄ , ?𝑦))) for a fresh variable ?𝑦 when 𝛼 is a constant.

B

Gate Names, Blank Nodes and Identifiers

The hash expression ℎ of Definition 4.1 applies SHA256 to the encoded arguments of the name and forms the gate IRI from urn:g: and the first 128 bits of the digest, and 𝜏ˆ encodes the kind of a value with the digests of its lexical form, datatype and lower-cased language tag (Appendix E). SPARQL 1.1 only recommends lowercase digits for SHA256 [34], so every digest passes through LCASE, and every engine names a gate identically. Since SPARQL 1.1 cannot sort the values of a row, the plan sorts the digests of the children of a product gate with compare-exchange steps, each a pair of IF expressions. The digests have fixed widths, so distinct names have distinct encodings whenever the hashed parts have distinct digests. The proofs assume that distinct names have distinct IRIs. A leaf keeps the identifier of the triple as its IRI, and every identifier of 𝐺 reif lies outside the namespace urn:g: of the other gates. Two distinct names of a circuit with 𝑁 gates receive the same IRI only when the 128-bit prefixes of the digests of two distinct encodings agree or two distinct hashed strings have equal digests. Computing one name hashes fewer than 264 strings, so in the random-oracle model [8] the probability is below 𝑁 2 /2128 < 3 · 10−21 for 𝑁 = 109 . Skolem IRIs. A key expression applies STR to every bound term, STR raises an error on a blank node, and a bind expression that raises an error leaves its variable unbound [34], so a key over a blank node drops its gate. The reified graph 𝐺 reif therefore uses fresh Skolem IRIs from a namespace that 𝐺 and 𝑄 do not use. The filter conditions of S use the built-ins STR, LANG, DATATYPE, isIRI, isLiteral, isBlank, isNumeric, sameTerm, langMatches, REGEX, IN, STRDT, CONCAT, CONTAINS and YEAR [34]. In the filter conditions of 𝑄, the rewriting replaces isBlank, isIRI, STR and STRDT by expressions that return on a Skolem IRI what SPARQL returns on a blank node, and the key expressions keep the SPARQL 1.1 built-ins. The other built-ins compare terms or treat an IRI and a blank node alike. A filter therefore keeps a mapping on 𝐺 reif exactly when the filter keeps the corresponding mapping on 𝐺. Identifier-level annotations. Let 𝐽 be the identifiers in 𝐺 reif , let 𝐽𝑡 ⊆ 𝐽 be the nonempty set of identifiers of 𝑡 ∈ 𝐺 and let the 𝑦𝑖 for 𝑖 ∈ 𝐽 be independent Boolean variables with the probabilities Ô Pr(𝑦𝑖 ) of the identifiers. The substitution 𝜎 maps 𝑥𝑡 to 𝑖 ∈ 𝐽𝑡 𝑦𝑖 . For an identifier world 𝜔 ⊆ 𝐽 , let 𝑊𝜔 = {𝑡 ∈ 𝐺 | 𝐽𝑡 ∩ 𝜔 ≠ ∅}, and let val𝜔 make 𝑦𝑖 true exactly when 𝑖 ∈ 𝜔. Since substitution preserves conjunction, disjunction and negation, every Boolean function 𝑓 over 𝑋 satisfies val𝜔 (𝜎 (𝑓 )) = val𝑊𝜔 (𝑓 ). (14) The rows of a matching triple 𝑡 bind the leaves 𝑦𝑖 for 𝑖 ∈ 𝐽𝑡 , whose disjunction is 𝜎 (𝑥𝑡 ), and the inductions in the proofs of Theorem 4.6 and Lemma 4.8 carry over under 𝜎, so the root of 𝜇 denotes 𝜎 (BProv𝑄 (𝜇)). By Equations (14) and (1), the root is true at 𝜔 exactly when 𝜇 ∈ supp([[𝑄]]𝑊𝜔 ), so its weighted model count is the marginal probability of 𝜇 over the worlds 𝑊𝜔 .

C

Tests and the Reimplementation of NPCS

Tests compare the probabilities of SPARQLcirc with an enumeration of the possible worlds on query shapes that cover S. For the comparison with NPCS, we reimplemented the rewriting rules of NPCS. The published NPCS rewriter is a compiled JAR that

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

returns no provenance or provenance without triples for queries with optional, union, distinct or filter and evaluates minus as optional. On the 138 basic graph pattern queries of the WatDiv workload of NPCS, our reimplementation returns the same rewritten queries as the JAR up to variable names and operand order.

D Proofs in Detail D.1 Factored basic graph patterns Appendix A.1 proves Lemma 4.5 for the base factors of Definition 4.4. When a triple pattern of 𝑄 has a constant subject or object, the factored plan computes all base factors with one query that matches the whole basic graph pattern. Every base factor is therefore defined only at restrictions of these matches. The restriction of the base factors drops a mapping only when no match of the basic graph pattern extends the mapping. Every total binding 𝜌 that extends a dropped mapping then has 𝜌 (tp𝑙 ) ∉ 𝐺 for some 𝑙, and therefore 𝐹𝑙 (𝜌 | var(tp𝑙 ) ) = ⊥ and the conjunction in Equation (8) is ⊥ at 𝜌. The dropped mappings contribute only ⊥ to Equation (8), so the restriction leaves the equation unchanged. For the bound of Section 4.3, the induced width gives |𝑈𝑧 | ≤ 𝑤 for every eliminated 𝑧. Each factor 𝐻𝑧 is defined at most at |adom(𝐺)| 𝑤 mappings, while its product gates range over at most |adom(𝐺)| 𝑤+1 assignments to 𝑈𝑧 ∪ {𝑧}. Since |adom(𝐺)| ≤ 3|𝐺 | and there are 𝑂 (𝑚) base factors and elimination steps, the elimination steps create 𝑂 (𝑚(3|𝐺 |) 𝑤+1 ) gates, which is 𝑂 (𝑚|𝐺 | 𝑤+1 ) for fixed 𝑤. The roots add one product gate and one sum gate per answer.

D.2

Gate names in the proof of Lemma 4.8

The proof of Lemma 4.8 in Appendix A uses three facts about the names, which we prove here: (1) two product gates have the same IRI if and only if their lists of children are equal up to order, (2) two sum gates, or two difference gates, have the same IRI if and only if they have the same letter, the same mapping and subpatterns equal up to the identities of Definition 4.1, and (3) the IRI of a gate depends only on the values that the row binds. Under the assumption, two gates have the same IRI exactly when they have the same name. (1) The name of a product gate is (T, sort(𝑐 1, . . . , 𝑐𝑛 )) for the IRIs 𝑐 1, . . . , 𝑐𝑛 of its children. Two product gates with the same IRI have the same name by the assumption, so their lists of children are equal up to order. Conversely, two such lists have the same hashes in ascending order, and the IRI depends only on these hashes. (2) The name of a sum gate is (𝐿, 𝜃 (𝑃), 𝜏 (𝑎 1 ), . . . , 𝜏 (𝑎𝑘 )) for its letter 𝐿, its subpattern 𝑃 and the values 𝑎 𝑗 of the variables ?𝑥 1 < · · · <?𝑥𝑘 in scope at 𝑃 under its mapping 𝜇, with 𝑎 𝑗 = unbound when 𝜇 leaves ?𝑥 𝑗 unbound. Since 𝜃 (𝑃) determines 𝑃 up to the identities of Definition 4.1, which preserve Boolean provenance, and 𝜏 is injective, two names are equal exactly when the letters, the mappings and the subpatterns up to these identities are equal. Difference gates have the letter M and the same argument. (3) A key expression applies only the functions of Section E to the values of a row, SPARQL 1.1 fixes their values on IRIs and literals, and 𝐺 reif contains no blank nodes. The IRI of a gate therefore depends only on the values that the row binds.

E

Gate Names, Collisions and Identifiers in Detail

The hash expression ℎ of Definition 4.1 is ℎ(T, 𝑑 1, . . . , 𝑑𝑛 ) = CONCAT("urn:g:t:", 𝛿 128 (CONCAT("T|", 𝑑 1, "|", . . . , "|", 𝑑𝑛 ))), ℎ(𝐿, 𝜃, 𝑎 1, . . . , 𝑎𝑘 ) = CONCAT("urn:g:", LCASE(𝐿),":", 𝛿 128 (CONCAT(𝐿,"@", 𝛿 (𝜃 ), 𝜂 1, . . . , 𝜂𝑘 ))), where 𝐿 is one of the letters U, P, A, S and M, 𝛿 (·) is LCASE(SHA256(·)) and 𝛿 128 (·) is SUBSTR(𝛿 (·), 1, 32) for a string expression, and 𝜂 𝑗 is 𝛿 (CONCAT("𝑥 𝑗 =", 𝑎 𝑗 )) for the name 𝑥 𝑗 of ?𝑥 𝑗 . The children enter ℎ(T, . . .) as their digests 𝛿 (STR(?𝑐𝑖 )) in ascending order, and 𝜏ˆ (?𝑥) encodes 𝜏 of the value of ?𝑥: IF(!BOUND(?x), "u", IF(isIRI(?x), CONCAT("i", 𝛿 (STR(?x))), IF(isBlank(?x), CONCAT("b", 𝛿 (STR(?x))), IF(isLiteral(?x), CONCAT("l", 𝛿 (STR(?x)), 𝛿 (STR(DATATYPE(?x))), 𝛿 (LCASE(LANG(?x)))), CONCAT("t", 𝛿 (STR(?x))))))). The letter t marks a quoted triple of SPARQL-star [35]. On 𝐺 reif , every value is an IRI, a literal or a quoted triple, so the branch for blank nodes is never taken. SPARQL 1.1 only recommends lowercase digits for SHA256 [34], and 𝛿 therefore applies LCASE, so every engine names a gate identically. SPARQL 1.1 offers no function that sorts the values of a row, and the plan sorts the digests of the children of a product gate with compare-exchange steps of two IF expressions each. The digests have fixed widths, so names whose hashed parts have distinct digests have distinct encodings. The proofs assume that distinct names have distinct IRIs. A leaf keeps the identifier of the triple as its IRI, and every identifier of 𝐺 reif lies outside the namespace urn:g: of the other gates. For a circuit with 𝑁 gates, let 𝑀 be the number of distinct strings that the plan hashes to compute the names. Two distinct names receive the same IRI only when the digests of two distinct encodings agree in the first 128 bits or two of the 𝑀 strings have equal digests. In the random-oracle model [8], the probability of either event is at most 𝑁 (𝑁 − 1)/2129 + 𝑀 (𝑀 − 1)/2257 . Computing one name hashes fewer than 264 strings, so 𝑀 < 264 𝑁 and the probability is below 𝑁 2 /2128 . For 𝑁 = 109 gates, 𝑁 2 /2128 < 3 · 10−21 . Identifier-level annotations. Let 𝐽 be the identifiers in 𝐺 reif , let 𝐽𝑡 ⊆ 𝐽 be the nonempty set of identifiers of 𝑡 ∈ 𝐺, and let 𝑦𝑖 be a Boolean variable with the probability Pr(𝑦𝑖 ) of the identifier 𝑖 for every 𝑖 ∈ 𝐽 . The variables 𝑦𝑖 are independent. In Section 2, the sets 𝐽𝑡 are disjoint singletons. Multiple Wikidata statements give several identifiers for one triple, whereas the RDF triples of a TPC-H row Ô share its identifier. The substitution 𝜎 maps 𝑥𝑡 to 𝑖 ∈ 𝐽𝑡 𝑦𝑖 . For an identifier world 𝜔 ⊆ 𝐽 , let 𝑊𝜔 = {𝑡 ∈ 𝐺 | 𝐽𝑡 ∩ 𝜔 ≠ ∅}, and let the valuation val𝜔 make 𝑦𝑖 true exactly when 𝑖 ∈ 𝜔. Since substitution preserves conjunction, disjunction and negation, every Boolean function 𝑓 over 𝑋 satisfies val𝜔 (𝜎 (𝑓 )) = val𝑊𝜔 (𝑓 ).

(15)

For a matching triple 𝑡, the encoded rows bind the leaves {𝑦𝑖 | 𝑖 ∈ 𝐽𝑡 }, whose disjunction is 𝜎 (𝑥𝑡 ), and the inductions in the proofs of Theorem 4.6 and Lemma 4.8 carry over to the functions under 𝜎. The

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

root of 𝜇 therefore denotes 𝜎 (BProv𝑄 (𝜇)). By Equations (15) and (1), the root is true at 𝜔 exactly when 𝜇 ∈ supp([[𝑄]]𝑊𝜔 ). The weighted Î Î model count of the root is the sum of 𝑖 ∈𝜔 Pr(𝑦𝑖 ) 𝑖 ∈ 𝐽 \𝜔 (1 − Pr(𝑦𝑖 )) over the sets 𝜔 ⊆ 𝐽 at which the root is true, that is, the marginal probability of 𝜇 over the worlds 𝑊𝜔 . Shared identifiers correlate the RDF triples of a row, but the 𝑦𝑖 stay independent.

F

⇐⇒ (𝑢, 𝑣) ∈ Rel𝑝 (𝑊 ).

'^'𝑒 1 val𝑊 ([[𝑏𝑢𝑣 ]]) = ⊤ ⇐⇒ val𝑊 ([[𝑏 𝑒𝑣𝑢1 ]]) = ⊤

𝑡𝑖 = (Aspirin, interactsWith, D𝑖 ), 𝑢𝑖 = (D𝑖 , interactsWith, Metformin), 𝑣 𝑗 = (Metformin, interactsWith, E 𝑗 ).

⇐⇒ (𝑣, 𝑢) ∈ Rel𝑒1 (𝑊 ) ⇐⇒ (𝑢, 𝑣) ∈ Rel'^'𝑒1 (𝑊 ).

The names 𝑡𝑖 , 𝑢𝑖 and 𝑣 𝑗 also denote the leaves of their triples. Over 𝐺 hub , the running query returns E1 , E2 and E3 , and every answer E 𝑗 has the three derivations (𝑡𝑖 , 𝑢𝑖 , 𝑣 𝑗 ). The flat plan of Definition 4.2 creates one product gate per derivation, so the circuit in Figure 7(a) has nine product gates with three edges each below three roots. The factored plan of Definition 4.4 eliminates ?𝑥 first, and 𝐻𝑥 maps Metformin to ℎ𝑥 = ⊕(⊗(𝑡 1, 𝑢 1 ), ⊗(𝑡 2, 𝑢 2 ), ⊗(𝑡 3, 𝑢 3 )). Eliminating ?𝑦 then yields the factor 𝐻 𝑦 that maps E 𝑗 to ⊕(⊗(ℎ𝑥 , 𝑣 𝑗 )), so the three answers share ℎ𝑥 in Figure 7(b). For 𝑘 drugs between Aspirin and Metformin and 𝑙 drugs after Metformin, the flat circuit has 𝑘𝑙 + 𝑙 gates other than leaves and 4𝑘𝑙 edges. After the removal of non-root sum gates with one child, the factored circuit has 𝑘 + 2𝑙 + 1 gates and 3(𝑘 +𝑙) edges. For 𝑘 = 𝑙 = 3, the flat circuit has 12 gates and 36 edges, and the factored circuit 10 gates and 18 edges. SPARQLcirc emits these circuits on 𝐺 hub .

Alternative. Let 𝑒 = 𝑒 1 '|' 𝑒 2 . Since [[𝑔⊥ ]] = ⊥, omitting 𝑔⊥ does not change the disjunction. The two induction hypotheses yield 𝑒 1 '|'𝑒 2 𝑒1 val𝑊 ([[𝑏𝑢𝑣 ]]) = ⊤ ⇐⇒ val𝑊 ([[𝑏𝑢𝑣 ]]) = ⊤ 𝑒2 ∨ val𝑊 ([[𝑏𝑢𝑣 ]]) = ⊤

⇐⇒ (𝑢, 𝑣) ∈ Rel𝑒1 (𝑊 ) ∨ (𝑢, 𝑣) ∈ Rel𝑒2 (𝑊 ) ⇐⇒ (𝑢, 𝑣) ∈ Rel𝑒1 '|'𝑒2 (𝑊 ). Sequence. Let 𝑒 = 𝑒 1 '/' 𝑒 2 . Equation (16), the semantics of Section 2 and the induction hypotheses give 𝑒 1 '/'𝑒 2 𝑒1 val𝑊 ([[𝑏𝑢𝑣 ]]) = ⊤ ⇐⇒ ∃𝑤 ∈ 𝐷𝐺 : val𝑊 ([[𝑏𝑢𝑤 ]]) = ⊤ 2 ∧ val𝑊 ([[𝑏 𝑒𝑤𝑣 ]]) = ⊤

⇐⇒ ∃𝑤 ∈ 𝐷𝐺 : (𝑢, 𝑤) ∈ Rel𝑒1 (𝑊 ) ∧ (𝑤, 𝑣) ∈ Rel𝑒2 (𝑊 ) ⇐⇒ (𝑢, 𝑣) ∈ Rel𝑒1 '/'𝑒2 (𝑊 ).

Transitive Closures in Detail

Let 𝐷𝐺 contain the subjects and objects occurring in 𝐺. For every 𝑒 by closure-free expression 𝑒 and 𝑢, 𝑣 ∈ 𝐷𝐺 , we construct a gate 𝑏𝑢𝑣 recursion on 𝑒. A construction with no child uses 𝑔⊥ . For an IRI 𝑝,
𝑝 𝑏𝑢𝑣 = ⊕ {𝑥𝑡 | 𝑡 = (𝑢, 𝑝, 𝑣) ∈ 𝐺 } . Inverse and alternative use
𝑒 1 '|'𝑒 2 𝑒1 𝑒2 '^'𝑒 𝑏𝑢𝑣 = 𝑏 𝑒𝑣𝑢 and 𝑏𝑢𝑣 = ⊕ {𝑏𝑢𝑣 , 𝑏𝑢𝑣 } \ {𝑔⊥ } . For sequence, let  
𝑤 ∈ 𝐷 , 𝑏 𝑒 1 ≠ 𝑔⊥ , 𝑒 1 '/'𝑒 2 𝑒1 2 𝑏𝑢𝑣 = ⊕ ⊗ {𝑏𝑢𝑤 , 𝑏 𝑒𝑤𝑣 } 𝑏 𝑒2 ≠ 𝐺𝑔 𝑢𝑤 . ⊥ 𝑤𝑣

𝑡 =(𝑢,𝑝,𝑣) ∈𝐺

⇐⇒ (𝑢, 𝑝, 𝑣) ∈ 𝑊

The empty child set yields ⊥ on both sides. Inverse. Let 𝑒 = '^'𝑒 1 . By construction and induction,

The Factored Plan on a Hub

For 𝑖, 𝑗 ∈ {1, 2, 3}, let 𝐺 hub contain the triples

G

IRI. Let 𝑒 = 𝑝. The semantics of Section 2 gives Ü 𝑝 val𝑊 ([[𝑏𝑢𝑣 ]]) = ⊤ ⇐⇒ val𝑊 (𝑥𝑡 ) = ⊤

(16)

Gate keys contain the syntax node of 𝑒 and the node pair. Inverse reuses the gate 𝑏 𝑒𝑣𝑢 , so the gate keys mention only IRI, sequence and alternative nodes. These equations define the global closurefree circuit 𝐶𝑒 . The equations index a gate by every node pair, so Lemma G.1 counts the gates of 𝐶𝑒 over the whole graph. A plan materializes only the gates other than 𝑔⊥ that a root reaches. Lemma G.1. For every closure-free 𝑒, 𝑢, 𝑣 ∈ 𝐷𝐺 and world 𝑊 ⊆ 𝐺, 𝑒 val𝑊 ( [[𝑏𝑢𝑣 ]]) = ⊤ ⇐⇒ (𝑢, 𝑣) ∈ Rel𝑒 (𝑊 ).

The circuit 𝐶𝑒 is acyclic and has 𝑂 (|𝑒 | |𝐷𝐺 | 3 ) gates. Proof of Lemma G.1. We use structural induction on 𝑒. The base case is an IRI 𝑝, and the induction hypothesis is the claim for the direct subexpressions of 𝑒 at all 𝑢, 𝑣 ∈ 𝐷𝐺 and all 𝑊 ⊆ 𝐺.

If no midpoint satisfies the first line, the outer disjunction is empty and both sides are false. The cases above exhaust the grammar. Let 𝑑 = |𝐷𝐺 |. Each IRI or alternative syntax node creates 𝑂 (𝑑 2 ) gates. Each sequence node creates at most one sum gate per node pair and one product gate per node triple (𝑢, 𝑤, 𝑣), so the count per sequence node is 𝑂 (𝑑 3 ). The syntax tree has 𝑂 (|𝑒 |) nodes, so 𝐶𝑒 has 𝑂 (|𝑒 |𝑑 3 ) gates. Every edge leads to a leaf, to a gate of a proper subexpression or from the sum gate of a sequence to one of its product gates. The children of a product gate of a sequence are gates of the two subexpressions. Ordering the gates by expression depth and placing the product gates of a sequence below its sum gates therefore gives a topological order. □ 𝑒 ≠ 𝑔 . The set 𝑉 Let 𝐸𝑒 contain the pairs (𝑢, 𝑣) ∈ 𝐷𝐺2 with 𝑏𝑢𝑣 ⊥ 𝑠 of Section 4.4 contains 𝑠 and the nodes that 𝐸𝑒 reaches from 𝑠, and 𝐸𝑠 = 𝐸𝑒 ∩ (𝑉𝑠 × 𝑉𝑠 ). Only part of 𝐶𝑒 is ever needed. The levels of 𝑒 for (𝑢, 𝑣) ∈ 𝐸 alone, and expanding one such Section 4.4 use 𝑏𝑢𝑣 𝑠 ′ 𝑒 gate involves 𝑏𝑢𝑤 only for a subexpression 𝑒 ′ of 𝑒 and a midpoint 𝑤 that a prefix of 𝑒 reaches from 𝑢. SPARQLcirc therefore emits these gates only on the matches of 𝑒 that start in 𝑉𝑠 . Choosing one part at every alternative node turns 𝑒 into finitely many sequences, and for each sequence one construct query matches it from the nodes of 𝑉𝑠 and emits the gates of the syntax nodes that the sequence passes 𝑝 through. For 𝑒 = 𝑝, these are the 𝑂 (|𝐸𝑠 |) gates 𝑏𝑢𝑣 with (𝑢, 𝑣) ∈ 𝐸𝑠 . Lemma G.1 and the count of level gates in the proof of Theorem 4.6 give the global total 𝑂 (|𝑒 | |𝐷𝐺 | 3 + 𝑛(𝑛 + |𝐸𝑠 |)). For 𝑒 = 𝑝, the total is 𝑂 (𝑛(𝑛 + |𝐸𝑠 |)).

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

⊗

⊗

E1

E2

E3

E1

E2

E3

⊕

⊕

⊕

⊕

⊕

⊕

⊗

⊗

⊗

𝑣1

𝑣2

𝑣3

⊗

⊗

⊗

⊗

⊗

⊗

⊗ ⊕

ℎ𝑥 ⊗ 𝑡1

𝑢1

𝑢2

𝑡2

𝑡3

𝑡1 𝑣1

𝑣2

⊗

⊗

𝑢3 𝑢1

𝑡2

𝑢2

𝑡3

𝑢3

𝑣3

(a) flat plan: 12 gates, 36 edges

(b) factored plan: 10 gates, 18 edges

Figure 7: Circuits of the running query over 𝐺 hub . The gray edges in (a) lead to the leaves 𝑣 𝑗 , and the three answers in (b) share the orange sum gate ℎ𝑥 .

SPARQLcirc first collects 𝑉𝑠 with select queries that each follow 𝑒 one 𝑒-step from the nodes found so far, and then emits the gates 𝑏𝑢𝑣 with 𝑢 ∈ 𝑉𝑠 together with level 1. SPARQLcirc keeps one row per gate of level 𝑖 with the source and the target of the gate, and issues construct queries for the product and sum gates of level 𝑖 + 1. Every level gate records the level with c:rlvl, the digest of 𝑒 ⋄ with c:rpath, the source with c:rfrom and the target with c:rto. SPARQLcirc derives the rows from the level, the source and the target. Gate keys contain 𝑒 ⋄ , 𝑠, 𝑖 and the target, so every edge points to a lower level and the two closures of one expression build separate circuits. The key of the closure gate 𝑅(𝑣) contains 𝑒 ⋄ , 𝑠 𝑒 and the zero-length gate carry and 𝑣 alone. The base gates 𝑏𝑢𝑣 distinguished levels of their own, so no round composes the zerolength gate. A last construct query emits the closure gates 𝑅(𝑣) together with the roots or the rows of the closure atom, which take the zero-length gate for the pair (𝑠, 𝑠) when ⋄ = ∗. For a closure that forms the whole query, the level queries receive the rows of level 𝑖 in a values clause and only read the endpoint. When the rows exceed the size of one request, SPARQLcirc splits them over several queries and gives each query the base rows that start at the targets of its rows. The merged results equal those of one query. For a closure atom inside a larger pattern, SPARQLcirc inserts the rows into the private namespace under two predicates, and the level queries read the rows from the endpoint. The names of the two predicates contain the run, the digest of 𝑒 ⋄ , the source and the level, and therefore keep the rows of different runs, closure atoms, sources and levels apart. The digest also separates 𝑒 + from 𝑒 ∗ , so only the star construction reads the zero-length row that it inserts. A source variable from an enclosing pattern invokes the same construction for each source binding, and the query that emits 𝑜𝑠 matches the triples whose subject or object is the source. RDF4J parses a closure atom whose source is its target variable, (?𝑥, 𝑒 ⋄ , ?𝑥), as the atom (?𝑥, 𝑒 ⋄ , ?𝑡) with a fresh variable ?𝑡 under the filter sameTerm(?𝑥, ?𝑡). SPARQLcirc passes the source binding through this filter and keeps the column of ?𝑡 in the relation, so the filter keeps the pairs (𝑠, 𝑠). The Bellman–Ford circuit of Fan et al. [23] carries 𝑟𝑖 (𝑣) into level 𝑖 + 1, so one level accumulates every length. In the endpoint, the

carried gates republish a pair at every later level as a sum gate with one input. The level is also part of a key, so the products 𝑒 }) and ⊗({𝑟 𝑒 ⊗({𝑟𝑖 (𝑢), 𝑏𝑢𝑣 𝑖+1 (𝑢), 𝑏𝑢𝑣 }) have different children and are distinct gates. Both products cover the walks of length at most 𝑖 + 1 that end with the step (𝑢, 𝑣). Exact-length levels hold each walk at one level and avoid both costs. The construction stops at the first empty level or after 𝑛 levels (Section 4.4). The bound 𝑛 and the emptiness of a level depend only on 𝑄 and 𝐺, so SPARQLcirc stops at the same 𝜆 and emits the same gates on every engine.

H

Implementation Details

Gate names. SPARQLcirc computes 𝛿 (𝜃 (𝑃)) once for every subpattern 𝑃, and the tag of the outer projection serializes the parsed query. The query fixes the number 𝑛 of children of a product gate, and the plan sorts their digests with the 𝑛(𝑛 − 1)/2 compare-exchange steps of a bubble-sort network. Each step is the pair IF(?a <= ?b, ?a, ?b) and IF(?a <= ?b, ?b, ?a). Roots. The prefix c: stands for urn:circuit:. The query that emits a root 𝑟 also emits the triple 𝑟 c:answerRoot vs with a literal vs that lists the projected variables. For every projected variable ?𝑦 that the mapping of 𝑟 binds to a value 𝑣, the query also emits the triple 𝑟 c:bind:hx 𝑣. The suffix hx is the hexadecimal encoding of the UTF-8 bytes of the name of ?𝑦, and vs consists of vars: followed by the comma-separated suffixes of all projected variables. The plan (3) writes z in place of its encoding 7a. SPARQLcirc reads the mapping of every root from these triples. Skolem IRIs. A key over a blank node drops its gate (Appendix B) because a template omits every triple with an unbound variable. The label of a blank node is scoped to one query result [34], so two queries can return different labels for one blank node. In the filter conditions of 𝑄, the expressions that replace isBlank, isIRI, STR and STRDT test whether an IRI is a Skolem IRI. On a Skolem IRI, isBlank then returns true and isIRI false, and STR and STRDT raise the error that SPARQL raises for a blank node. Every Skolem IRI in an answer is mapped back to its blank node. The implemented plan. SPARQLcirc builds the queries of Definition 4.2 with two changes. The query of the operator above

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

a join emits the product gates of the join, which has no query of its own. The query contains the where clause of the join, and its template emits the product gate of every row of the join with the edges to the children of the gate. Every product gate that a root reaches is therefore in the circuit. The pattern rw(𝑃, 𝑔𝑃 ) of a union 𝑃 ends with the bind of 𝑔𝑃 . On RDF4J 4.2.1 and 5.3.2 [57], we observed that a join of two groups is evaluated as a hash join on the shared variables when one group contains a bind. The hash join drops every row that leaves a shared variable unbound. SPARQL makes the row compatible with every row that agrees on the bound variables of the row. Over the triples :s :p0 :a, :s :p0 :b, :s :p1 :c and :s :p2 :d, the pattern { {?x :p0 ?v2} { {?x :p1 ?v1 . ?x :p2 ?v2} UNION {?x :p1 ?v1} BIND("R" AS ?g) } } returns 0 rows on both versions, and the correct result has 2 rows. Before applying Definition 4.2, SPARQLcirc therefore rewrites a join or a difference whose operand has a union with a branch that leaves unbound a variable of the other operand. Join and the left operand of a difference distribute over union, and Diff(𝑃 1, Union(𝑃2, 𝑃3 )) = Diff(Diff(𝑃 1, 𝑃2 ), 𝑃3 ). The rewritten query therefore has the answers and the Boolean provenance of the original query. For the RDF-star annotation, standard reification and named graphs, SPARQLcirc matches a triple pattern together with its encoding. The matches remain those of Definition 4.2, because 𝐺 reif contains the triples of 𝐺 with Skolem IRIs in place of blank nodes. SPARQLcirc also adds distinct to the subquery of a projection. The keyword removes duplicate solutions and leaves the rows and the circuit unchanged. Factored basic graph patterns. Every row of a factor is an RDF node in the private namespace that stores the mapping and the gate of the row. The sum gates of a factor carry the prefix urn:g:s: and hash a tag together with the bindings of the scope. The tag of a base factor combines a digest of the basic graph pattern with the index of its triple pattern, and the tag of any other factor combines the digest with the eliminated variable and the step. The subtrahend sum gates of Definition 4.1 carry the same prefix, and only their hashed strings begin with S@. A base factor maps a row to the sum gate over the identifiers of its triple. One insert makes the rows of a factor available to the next query. At every step, SPARQLcirc eliminates a variable 𝑧 with the smallest |𝑈𝑧 | and breaks ties by the name of the variable. The factored plan multiplies the factors of A𝑧 two at a time. Pairwise multiplication changes the nesting of the product gates and preserves their Boolean functions and the bound of Section 4.3. SPARQLcirc uses the flat plan in three cases. In the first case, the basic graph pattern has at most one triple pattern, so every derivation consists of at most one triple. The other two cases concern a basic graph pattern whose subjects and objects are variables, and every base factor then contains every match of its triple pattern in 𝐺. In the second case, the query projects every variable, so every answer has one derivation. In the third case, a triple pattern has a variable predicate, and its base factor contains every triple of 𝐺. Compilation. Before compilation, SPARQLcirc replaces every sum gate that has one child and is not a root by its child. For d4,

SPARQLcirc compiles the Tseitin encoding [59] of the circuit below the root, a CNF with one auxiliary variable per gate. Weight 1 on both literals of each auxiliary variable keeps the WMC [24, 49].

I

Builder Independence

Definition 4.1 derives every gate name from the operator, the pattern tag and either the bindings of the row or the IRIs of the children, all of which 𝑄 and 𝐺 reif determine. Every engine that follows the SPARQL 1.1 semantics and evaluates the plan over 𝐺 reif therefore returns the same circuit. For a subpattern 𝑃, let 𝛾 wit (𝑃) be the select queries obtained from each construct query of Definition 4.2 by replacing its template with the projection of 𝑣¯𝑃 and the child gate variables of that case. A union therefore has one such query per branch and a difference two, and 𝑣¯𝑃 is 𝑣¯𝑃1 for a difference. The witness query of 𝑞𝑃− projects 𝑠𝑃 , which the group of 𝑃1 binds before the join with 𝑃2 , in place of 𝑣¯𝑃1 , because a variable unbound in the row of 𝑃1 can take a value of 𝑃2 . We call their results the witness relations of 𝑃. Applying the templates of Definition 4.2 to the witness relations of every subpattern of 𝑄 yields the circuit of the plan 𝛾 (𝑄) with the same gate names, kinds and child sets. The plan and the witness relations give the key expressions the same arguments: the pattern tag and the binding tuple for ⊕- and ⊖-gates, and the child gates for ⊗-gates. A witness relation returns the binding tuple verbatim, the gate 𝑠𝑃 of a subtrahend query, and the child gates as its gate columns. In both cases, the children of one name are those of the rows that bind the name. Emitting the gates inside the engine and building them from the witness relations differ in cost. Let 𝑅 be the number of rows that a plan enumerates, 𝑁 the number of distinct gates and 𝐸 the number of edges of its circuit. Emission inside the engine materializes Θ(𝑁 + 𝐸) triples, because set semantics merges a gate the moment it is emitted a second time. A witness relation instead returns Θ(𝑚𝑅) terms for 𝑚 patterns. The two coincide only when 𝑁 + 𝐸 is Θ(𝑚𝑅). The flat plan of a basic graph pattern gives every row a product gate with at most 𝑚 children and one edge from the root, so 𝐸 ≤ (𝑚+1)𝑅, and 𝑁 +𝐸 is Θ(𝑚𝑅) when distinct rows match distinct sets of triples. The factored plan makes 𝐸 small even when the flat plan enumerates many rows, and the gain holds only while its intermediate factors stay in the endpoint that evaluates the joins.

J

Additional Experiments

This section gives the results of Section 5 for all engines and the results that Section 5 leaves out. On WatDiv, the endpoint and the remaining steps each have 600 s with 10.9 million triples and 3000 s with 109 million triples. On gMark, the endpoint has 5000 s. On Wikidata, a run has 600 s from the rewriting of the query to the probabilities. On TPC-H, a run has 3000 s from the rewriting of the query to the probabilities.

J.1

WatDiv

NPCS reports an overhead of 20 to 30% over the original queries on GraphDB with a cold cache [5]. Our runs follow a warm-up run, the plain query runs on 𝐺 and NPCS on 𝐺 reif , and with 10.9 million triples on GraphDB, NPCS takes 1.9 times as long as the reified query, which takes 8.7 times as long as the plain query (Section 5.1).

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

Table 2: End-to-end time (s) on WatDiv (RDF-star). GraphDB Triples

Fuseki

Oxigraph

10.9M

109M

10.9M

109M

10.9M

109M

0.46 0.87 1.34

0.80 1.11 2.20

0.49 0.82 1.15

0.87 1.43 3.29

0.69 1.09 1.15

11.89 12.88 1.53

NPCS Flat plan Factored plan

Table 2 gives the end-to-end time over the queries that NPCS and both plans complete. At the endpoint, the flat plan costs 2.5 to 2.6 times NPCS on GraphDB and the factored plan 4.3 to 5.1 times. Fuseki and Oxigraph follow GraphDB, except on Oxigraph with 109 million triples. There, the reified query already takes 9.1 times as long as the plain query. The factored plan builds every factor in a separate query and takes 0.2 times as long as NPCS at the endpoint on the 19 templates of basic graph patterns that it completes. End to end, the factored plan returns all probabilities in 1.53 s against 11.89 s for NPCS. The encoding changes the times by factors that depend on the engine. Standard reification stores four statements per triple instead of two and matches a triple with its identifier by three triple patterns instead of one. Over the queries that all three encodings complete, standard reification is slower than RDF-star for every engine, method and size, by median factors from 1.02 to 3.94. Relative to RDF-star, named graphs take 0.74 to 0.93 times as long on Oxigraph for NPCS and the flat plan, 0.87 to 1.15 times on GraphDB and 1.06 to 1.74 times on Fuseki. Figure 8 repeats Figure 5 with 109 million triples.

endpoint time (s)

Base

Reification

NPCS

linear

star

SPARQLcirc (flat)

SPARQLcirc (factored)

102

100

10−2 snowflake complex

optional

minus

Figure 8: Endpoint time per WatDiv class (109M triples). Figures 9 to 14 give the endpoint time of every template, where Base is the plain query and Reification the reified query. The two property-path templates P+ and P* run only the plain query and the plan of Section 4.4.

J.2

gMark

At 𝑘 = 6, GraphDB runs with a heap of 128 GiB instead of 48 GiB, and SPARQLcirc with 96 GiB instead of 64 GiB. Outside the endpoint, NPCS keeps about 0.1 GiB, since it only stores the response, whereas the factored plan reaches 2 to 25 GiB while it builds the circuit.

J.3

Wikidata

The graph holds the statements of the full dump of 29 September 2026 without qualifiers and references in 8.87 billion triples.

At the endpoint, NPCS completes on GraphDB 42 queries with one triple pattern, 32 with several and 13 with optional, the flat plan 42, 30 and 15, and the factored plan 41, 25 and 14. On Oxigraph, NPCS completes 82 queries, the flat plan 77 and the factored plan 71, and the flat plan completes 5 of the queries with optional against 10 for NPCS. At the median, the flat plan takes 2.5 times as long as NPCS on GraphDB and 1.7 times on Oxigraph (Figure 15), and the factored plan 2.8 and 2.2 times. Figure 15 gives the endpoint time of every query, which ends before NPCS parses and merges its provenance expressions. NPCS is therefore faster at the endpoint on almost every query, and the flat plan overtakes it only end to end on queries with many derivations (Table 1). End to end with CUDD, the flat plan returns all probabilities for 87 queries on GraphDB and 77 on Oxigraph, and NPCS for 82 and 80. If NPCS compiles the expression of every answer separately instead of merging them, it completes 66 and 64 queries, and the flat plan is faster on 49 of the 62 queries that both complete on GraphDB, by 2.7 times at the median. With d4, compilation and weighted model counting take 54 to 68% of the end-to-end time of the flat plan, against about a fifth with CUDD (Figure 16), and the flat plan and NPCS take about the same time end to end. On GraphDB, the flat plan is more than ten times faster than NPCS on seven queries with optional, with 2.1 s against 67 s at the median, although five of them have fewer than 500 derivations. On Oxigraph, the flat plan is at most twice as fast with optional and exceeds the budget on four of these queries that NPCS completes.

J.4

TPC-H

TPC-H [58] at nine scale factors from 0.01 to 1 becomes 1.2 to 123 million triples under the mapping of SPARQLprov [36], in which the IRI of a row identifies its triples (Section E). ProvSQL 1.11.0-dev [52] in PostgreSQL 18.4 runs on a relational copy. The time of SPARQLcirc grows about linearly with the size of TPC-H, as does that of ProvSQL. The flat plan completes every scale factor on six of the twelve templates on GraphDB and on seven on Oxigraph, and ProvSQL on eleven. On these templates, the time of the flat plan grows with the scale factor at a median exponent of 0.78 on GraphDB and 0.95 on Oxigraph, against 0.93 and 0.90 for ProvSQL. ProvSQL is faster in absolute terms, by 20 times at the median for the flat plan on GraphDB, because the direct mapping turns every attribute of a row into a triple, so a template joins more triple patterns than ProvSQL joins tables. Figure 17 gives the end-to-end time on every template. On GraphDB, ProvSQL is faster than the flat plan on every template, by 5.7 to 288 times at the median of a template, and the factored plan takes 121 times as long as ProvSQL at the median.

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

Figure 9: Endpoint time per WatDiv template with 10.9 million triples and RDF-star annotations.

Figure 10: Endpoint time per WatDiv template with 10.9 million triples and standard reification.

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

Figure 11: Endpoint time per WatDiv template with 10.9 million triples and named graphs.

Figure 12: Endpoint time per WatDiv template with 109 million triples and RDF-star annotations.

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

Figure 13: Endpoint time per WatDiv template with 109 million triples and standard reification.

Figure 14: Endpoint time per WatDiv template with 109 million triples and named graphs.

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

Figure 15: Endpoint time of every Wikidata query against its number of derivations, on GraphDB (top) and Oxigraph (bottom).

Figure 16: Share of the stages in the end-to-end time of SPARQLcirc on Wikidata, on GraphDB (top) and Oxigraph (bottom).

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, and Steffen Staab

Figure 17: Exact PQE end to end on TPC-H, one panel per template. A line stops short where the budget was exhausted.

SPARQLcirc : Probabilistic Query Evaluation with Provenance Circuits

K

Notation Table 3: Notation. Symbol

Meaning

I, B, L, V, T S 𝐺 𝑡 , tp, 𝑃 , 𝑄 𝑊 , 𝑥𝑡 𝜇, 𝜈 , ∼ [[𝑃 ]]𝐺 , supp 𝑌 𝐶 𝜇𝑠,𝑣 val𝑊 𝑋 BProv𝑃 (𝜇 ) Pr(𝑥𝑡 ) , Pr(𝜇 ) , WMC

IRIs, blank nodes, literals, variables, RDF terms SPARQL fragment (Section 2) RDF graph underlying the probabilistic model triple, triple pattern, pattern, query possible world 𝑊 ⊆ 𝐺 , variable of 𝑡 ∈ 𝐺 solution mappings and compatibility multiset evaluation and its support projected variables of a query mapping of closure atom 𝐶 for 𝑠 and 𝑣 valuation that makes 𝑥𝑡 true exactly when 𝑡 ∈ 𝑊 variables {𝑥𝑡 | 𝑡 ∈ 𝐺 } Boolean provenance of 𝜇 for pattern 𝑃 probability of 𝑡 , marginal probability of 𝜇 , weighted model count reified graph that the endpoint stores sum, product and difference gates children, minuends and subtrahend of a gate root of the mapping 𝜇 Boolean function of gate 𝑔 (Section 2) childless gates for ⊥ and ⊤ term encoding, serialization of 𝑃 scope and projection tuples in lexicographic order lower-cased SHA-256 digest, its first 128 bits key expressions, their parts and the letter of a sum or difference gate (Definition 4.1) plan of construct queries and gate variable of 𝑃 queries of 𝑃 (Definition 4.2) reification of tp with identifier variable ?𝑡 rewritten pattern of 𝑃 that binds 𝑔𝑃 gates bound by the rows of rw (𝑃, 𝑔𝑃 ) for 𝜇 , disjunction of their functions subtrahend gate of a difference 𝑃 number of triple patterns, variables of 𝑄 outside 𝑌 , base factor of tp 𝑗 factors whose scopes contain 𝑧 , the factor that replaces them values of 𝑧 at which every factor of A𝑧 is defined, terms of 𝐺 scope of 𝐻𝑧 , induced width input relation and sources of a closure atom 𝐶 𝐶 gate of 𝜇𝑠,𝑣 closure-free expression, closure ( ⋄ ∈ {+, ∗} ), source, target subjects and objects of 𝐺 , closure-free circuit of 𝑒 (Section G) relation of 𝑒 on 𝐺 and its transitive closure zero-length pairs of a closure 𝑒 ∗ (Section 2) closure atom with source 𝛼 and target variable ?𝑦 gate that is true in 𝑊 exactly when (𝑢, 𝑣) ∈ Rel𝑒 (𝑊 ) nodes and 𝑒 -steps reachable from 𝑠 , 𝑛 = |𝑉𝑠 | gate for length-𝑖 walks, closure gate of 𝑣 , last level zero-length gate: sum of the leaves of the triples with subject or object 𝑠 identifiers, identifiers of 𝑡 , variable of identifier 𝑖 (Appendix B) Ô substitution of 𝑥𝑡 by 𝑖 ∈ 𝐽𝑡 𝑦𝑖 , world of the identifiers 𝜔

𝐺 reif ⊕, ⊗, ⊖ ch, pos, neg root(𝜇 ) [[𝑔]] 𝑔⊥ , 𝑔⊤ 𝜏 , 𝜃 (𝑃 ) 𝑣¯𝑃 , 𝑌¯ 𝛿 , 𝛿 128 KEY_∗, ℎ , sort, 𝜏ˆ, 𝐿 𝛾 (𝑃 ) , 𝑔𝑃 𝑞𝑃 , 𝑞𝑃,𝑖 , 𝑞𝑃− , 𝑞𝑃+ reif (tp, ?𝑡 ) rw (𝑃, 𝑔𝑃 ) Cand𝑃 (𝜇 ) , Φ𝑃 (𝜇 ) 𝑠𝑃 𝑚, 𝑍 , 𝐹 𝑗 A𝑧 , 𝐻𝑧 𝐴𝑧 (𝜈 ) , adom(𝐺 ) 𝑈𝑧 , 𝑤 I𝐶 , 𝑆𝐶 𝑔𝐶 (𝑠, 𝑣) 𝑒, 𝑒 ⋄ , 𝑠, 𝑣 𝐷𝐺 , 𝐶𝑒 Rel𝑒 (𝐺 ) , Rel𝑒 + (𝐺 ) Δ 𝐶 = (𝛼, 𝑒 ⋄ , ?𝑦) 𝑒 𝑏𝑢𝑣 𝑉𝑠 , 𝐸𝑠 , 𝑛 𝑟𝑖 (𝑣) , 𝑅 (𝑣) , 𝜆 𝑜𝑠 𝐽 , 𝐽𝑡 , 𝑦𝑖 𝜎 , 𝑊𝜔

Related documents

• SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits#1535682
• PyKEEN-NSX: A Modular Framework for Static, Dynamic and Schema-Aware Negative Sampling in PyKEEN#818708
• PyKEEN-NSX: A Modular Framework for Static, Dynamic and Schema-Aware Negative Sampling in PyKEEN#808716
• AlchemQ: Proof-Carrying Quantum Circuit Optimization with Per-Result Equivalence Certificates#1013761
• Data Provenance Aggregation and Structural Descriptors for Query-Template Identification#1386677