<p><strong>Background</strong>: In the context of Datalog, <a href="https://dl.acm.org/doi/10.1145/1265530.1265535" rel="nofollow noreferrer">Green et. al (2007)</a> introduce the notion of the <em>Datalog provenance semiring</em>, a generalization of why-provenance as well as bag and probabilistic database semantics in which each EDB tuple is tagged with a symbolic value and combined via the operations of a commutative semiring. They call this form of provenance &quot;how-provenance&quot; because it shows <em>how</em> each EDB contributes to a derived fact.</p>
<p>Sometimes, though, the &quot;how-provenance&quot; of a derived fact is defined as its <em>set of derivation trees</em>, for example by <a href="https://dl.acm.org/doi/10.14778/2824032.2824039" rel="nofollow noreferrer">Deutch et. al (2015)</a>.</p>
<p>When the number of derivation trees is finite, the semiring provenance of a derived fact is the sum over all its derivation trees of the product of the tags of the leaves of the tree.</p>
<p><strong>Question:</strong> Is it possible to go in the other direction—that is, to recover the set of derivation trees from the semiring provenance? And does the answer change if there are a finite or infinite number of derivation trees?</p>
<p>To do so, I think you would need to modify the Datalog program so that each relation is tagged with an EDB that represents an identifier for that rule. But even then, the commutativity of the provenance semiring seems to make it difficult to reconstruct proof trees because you lose the order of derivations and leaves.</p>

CC BY-SA 4.0
2023-12-02T08:59:25.583Z
What is the precise input, just an element of the semiring? With the derived fact? With the entire program? If you give yourself too much input you'll be able to just compute the derivation trees.
Andrej Bauer
CC BY-SA 4.0
2023-12-02T17:29:14.940Z
Ah, that's a really good point, thanks @AndrejBauer! The one I had in mind was just an element of the semiring (symmetric to the case where we can compute the semiring provenance from only the set of derivation trees), but I'm interested in any case where the semiring provenance could help compute the set of derivation trees more efficiently than simply throwing the provenance away and computing the derivation trees from scratch.
Justin Lubin
CC BY-SA 4.0
2023-12-07T22:16:42.150Z
@JustinLubin: when the set of derivation trees is infinite, how is it represented as input? Also, even when it is finite, I'm not sure how to formally specify the problem. Probably you could just ignore the input and naively recompute all the derivation trees. Is your question whether, for a Datalog query Q, the complexity of the problem "Given a database D and the how-provenance of Q on D, compute all derivations trees of Q on D" could be higher than "Given a database D, compute all derivation trees of Q on D"? But the set of derivation trees would be large, so this can mess up the complexity
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-12-15T23:05:23.287Z
@a3nm Ahh, the set of derivation trees being so large that it messes up the complexity is a really good point. I hadn't considered that, but that makes perfect sense. I think that means that what I'd be looking for is something along the lines of enumerating derivation trees given an enumeration of the semiring provenance (which would also handle the infinite case). But that's a fuzzy notion I don't know how to formalize :) I think my underlying question is whether the two definitions of how-provenance are, in some sense, "equivalent" to each other (which I know is also a fuzzy one). Thanks!
Justin Lubin
CC BY-SA 4.0
2023-12-17T04:21:58.263Z
@JustinLubin: Yes, I think the problem should be better formalized: how is the semiring provenance enumerated? Also, does the question depend on the semiring?
Antoine Amarilli 'a3nm'
<lo.logic><db.databases>
Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?
Justin Lubin
# Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?

(Asked by: username_0 on 2023-12-01)

**Background**: In the context of Datalog, [Green et. al (2007)](https://dl.acm.org/doi/10.1145/1265530.1265535) introduce the notion of the *Datalog provenance semiring*, a generalization of why-provenance as well as bag and probabilistic database semantics in which each EDB tuple is tagged with a symbolic value and combined via the operations of a commutative semiring. They call this form of provenance "how-provenance" because it shows *how* each EDB contributes to a derived fact.

Sometimes, though, the "how-provenance" of a derived fact is defined as its *set of derivation trees*, for example by [Deutch et. al (2015)](https://dl.acm.org/doi/10.14778/2824032.2824039).

When the number of derivation trees is finite, the semiring provenance of a derived fact is the sum over all its derivation trees of the product of the tags of the leaves of the tree.

**Question:** Is it possible to go in the other direction—that is, to recover the set of derivation trees from the semiring provenance? And does the answer change if there are a finite or infinite number of derivation trees?

To do so, I think you would need to modify the Datalog program so that each relation is tagged with an EDB that represents an identifier for that rule. But even then, the commutativity of the provenance semiring seems to make it difficult to reconstruct proof trees because you lose the order of derivations and leaves.

**Tags:** lo.logic, db.databases
> **Comments:**
> **username_1**: What is the precise input, just an element of the semiring? With the derived fact? With the entire program? If you give yourself too much input you'll be able to just compute the derivation trees.  
> **username_0**: Ah, that's a really good point, thanks @AndrejBauer! The one I had in mind was just an element of the semiring (symmetric to the case where we can compute the semiring provenance from only the set of derivation trees), but I'm interested in any case where the semiring provenance could help compute the set of derivation trees more efficiently than simply throwing the provenance away and computing the derivation trees from scratch.  
> **username_2**: @JustinLubin: when the set of derivation trees is infinite, how is it represented as input? Also, even when it is finite, I'm not sure how to formally specify the problem. Probably you could just ignore the input and naively recompute all the derivation trees. Is your question whether, for a Datalog query Q, the complexity of the problem "Given a database D and the how-provenance of Q on D, compute all derivations trees of Q on D" could be higher than "Given a database D, compute all derivation trees of Q on D"? But the set of derivation trees would be large, so this can mess up the complexity  
> **username_0**: @a3nm Ahh, the set of derivation trees being so large that it messes up the complexity is a really good point. I hadn't considered that, but that makes perfect sense. I think that means that what I'd be looking for is something along the lines of enumerating derivation trees given an enumeration of the semiring provenance (which would also handle the infinite case). But that's a fuzzy notion I don't know how to formalize :) I think my underlying question is whether the two definitions of how-provenance are, in some sense, "equivalent" to each other (which I know is also a fuzzy one). Thanks!  
> **username_2**: @JustinLubin: Yes, I think the problem should be better formalized: how is the semiring provenance enumerated? Also, does the question depend on the semiring?  

---

## 0 answers

