Daniel Deutch
email: danielde@post.tau.ac.il

Nave Frost
email: navefrost@mail.tau.ac.il

Benny Kimelfeld
email: bennyk@cs.technion.ac.il

Mikaël Monet
email: mikael.monet@inria.fr

Computing the Shapley Value of Facts in Query Answering

The Shapley value is a game-theoretic notion for wealth distribution that is nowadays extensively used to explain complex data-intensive computation, for instance, in network analysis or machine learning. Recent theoretical works show that query evaluation over relational databases fits well in this explanation paradigm. Yet, these works fall short of providing practical solutions to the computational challenge inherent to the Shapley computation. We present in this paper two practically effective solutions for computing Shapley values in query answering. We start by establishing a tight theoretical connection to the extensively studied problem of query evaluation over probabilistic databases, which allows us to obtain a polynomial-time algorithm for the class of queries for which probability computation is tractable. We then propose a first practical solution for computing Shapley values that adopts tools from probabilistic query evaluation. In particular, we capture the dependence of query answers on input database facts using Boolean expressions (data provenance), and then transform it, via Knowledge Compilation, into a particular circuit form for which we devise an algorithm for computing the Shapley values. Our second practical solution is a faster yet inexact approach that transforms the provenance to a Conjunctive Normal Form and uses a heuristic to compute the Shapley values. Our experiments on TPC-H and IMDB demonstrate the practical effectiveness of our solutions.

INTRODUCTION

Explaining query answers has been the objective of extensive research in recent years [START_REF] Deutch | Explaining natural language query results[END_REF][START_REF] Todd | The semiring framework for database provenance[END_REF][START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Roy | Explaining query answers with explanation-ready databases[END_REF][START_REF] Salimi | Quantifying causal effects on query answering in databases[END_REF]. A prominent approach is to devise an explanation based on the facts that were used for deriving the answers; these facts are often termed provenance or lineage of the query answer. For illustration, consider a query asking whether there exists a route from the USA to France with at most one connection over a database of airports and flights. The answer is Boolean, and upon receiving a positive answer one may seek explanations of why it is so. The basis for such explanations would include all details of qualifying routes that are used in the derivation of the answer. Unfortunately, the number of relevant routes might be huge (specifically, quadratic in the database size). Moreover, it is conceivable that different facts differ considerably in their importance to the answer at hand; for instance, some flights may be crucial to enabling the USA-France connection, while others may be easily replaced by alternatives.

To address these issues, there have been several proposals for principled ways of quantifying the contribution of input facts to query answers [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Meliou | The complexity of causality and responsibility for query answers and non-answers[END_REF][START_REF] Meliou | Causality and explanations in databases[END_REF][START_REF] Salimi | Quantifying causal effects on query answering in databases[END_REF]. We focus here on the recent approach of Livshits et al. [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF] that applies to this setting the notion of Shapley values [START_REF] Lloyd | A value for n-person games[END_REF]-a game-theoretic function for distributing the wealth of a team in a cooperative game. This function has strong theoretical justifications [START_REF] Roth | The Shapley Value: Essays in Honor of Lloyd S. Shapley[END_REF], and indeed, it has been applied across various fields such as economics, law, environmental science, and network analysis. It has also been used for explanations in data-centric paradigms such as knowledge representation [START_REF] Hunter | On the measure of conflicts: Shapley inconsistency values[END_REF][START_REF] Yun | Inconsistency Measures for Repair Semantics in OBDA[END_REF] and machine learning [START_REF] Scott M Lundberg | From local explanations to global understanding with explainable AI for trees[END_REF][START_REF] Scott | A unified approach to interpreting model predictions[END_REF]. In the context of relational databases, given a query 𝑞( x), a database 𝐷, an input fact 𝑓 ∈ 𝐷 and a tuple t of same arity as x, the Shapley value of 𝑓 in 𝐷 for query 𝑞( x) and tuple t intuitively represents the contribution of 𝑓 to the presence (or absence) of t in the query result.

Livshits et al. [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Reshef | The impact of negation on the complexity of the Shapley value in conjunctive queries[END_REF] initiated the study of the computational complexity of calculating Shapley values in query answering. They showed mainly lower bounds on the complexity of the problem, with the exception of the sub-class of self-join free SPJ queries called hierarchical, where they gave a polynomial-time algorithm. The results are more positive if imprecision is allowed, as they showed that the problem admits a tractable approximation scheme (FPRAS, to be precise) via Monte Carlo sampling. The state of affairs is that the class of known tractable cases (namely the hierarchical conjunctive queries) is highly restricted, and the approximation algorithms with theoretical guarantees are impractical in the sense that they require a large number of executions of the query over database subsets (the samples). Hence, the theoretical analysis of Livshits et al. [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Reshef | The impact of negation on the complexity of the Shapley value in conjunctive queries[END_REF] does not provide sufficient evidence of practical feasibility for adopting the Shapley value as a measure of responsibility in query answering. Moreover, the results of Livshits et al. [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF] imply that, for self-join free SPJ queries the class of tractable queries for computing Shapley values coincides with the class of tractable queries in probabilistic tuple-independent databases [START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF]. Yet, no direct connection has been made between these two problems and, theoretically speaking, it has been left unknown whether algorithms for probabilistic databases can be used for Shapley computation.

Recently, Van den Broeck et al. [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF] and Arenas et al. [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF][START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF] investigated the computational complexity of the SHAP-score [START_REF] Scott | A unified approach to interpreting model predictions[END_REF], a notion used in machine learning for explaining the predictions of a model. While both are based on the general notion of Shapley value, the SHAP-score for machine learning and Shapley values for databases are different. In the latter case, the players are the tuples of the database and the game function that is used is simply the value of the query on a subset of the database, while in the former case, the players are the features of the model and the game function is a conditional expectation of the model's output (see Section 6.2 for a more formal definition of the SHAP-score). Remarkably, Van den Broeck et al. [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF] have shown that computing the SHAP-score is equivalent (in terms of polynomial-time reductions) to the problem of computing the expected value of the model. One of our contributions is to show that the techniques developed by [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF][START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF][START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF] can be adapted to the context of Shapley values for databases. For instance, by adapting to our context the proof of Van den Broeck et al. [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF] that computing the SHAP-score reduces to computing the expected value of the model, we resolve the aforementioned open question affirmatively: we prove that Shapley computation can be efficiently (polynomial-time) reduced to probabilistic query answering. Importantly, this applies not only to the restricted class of SPJ queries without self-joins, but to every database query. Hence, extending theory to practice, one can compute the Shapley values using a query engine for probabilistic databases.

In turn, a common approach that was shown to be practically effective for probabilistic databases is based on Knowledge Compilation [START_REF] Darwiche | A knowledge compilation map[END_REF][START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF]. In a nutshell, the idea is to first compute the Boolean provenance of a given output tuple in the sense of Imielinski and Lipski [START_REF] Imielinski | Incomplete Information in Relational Databases[END_REF], and then to "compile" the provenance into a particular circuit form that is more favorable for probability computation. Specifically, the target class of this compilation is that of deterministic and decomposable circuits (d-D). In our case, rather than going through probabilistic databases, we devise a more efficient approach that computes the Shapley values directly from the d-D circuit. This is similar to how Arenas at al. [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF][START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF] directly prove that the SHAP-score can be computed efficiently over such circuits, without using the more general results of [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF]. By adapting the proof of [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF][START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF], we show how, given a d-D circuit representing the provenance of an output tuple, we can efficiently compute the Shapley value of every input fact. While the aforementioned properties of the circuit are not guaranteed in general (beyond the class of hierarchical queries), we empirically show the applicability and usefulness of the approach even for non-hierarchical queries.

Our experimental results (see below) indicate that our exact computation algorithm is fast in most cases, but is too costly in others. For the latter cases, we propose a heuristic approach to retrieve the relative order of the facts by their Shapley values, without actually computing these values. Indeed, determining the most influential facts is in many cases already highly useful, even if their precise contribution remains unknown. The solution that we propose to this end is termed CNF Proxy; it is based on a transformation of the provenance to Conjunctive Normal Form (CNF) and using it to compute proxy values intuitively based on (1) the number of clauses in which a variable occur and (2) its alternatives in each clause. These are two aspects that are correlated with Shapley values. The proxy values may be very different from the real Shapley values, and yet, when we order facts according to their proxy values we may intuitively get an ordering that is similar to the order via Shapley. Our experiments validate that this intuition indeed holds for examined benchmarks.

We have experimented with multiple queries from the two standard benchmarks TPC-H and IMDB. Our main findings are as follows. In most cases (98.67% of the IMDB output tuples and 83.83% for TPC-H), our exact computation algorithm terminates in 2.5 seconds or less, given the provenance expression. In the vast majority of remaining cases the execution is very costly, typically running out of memory already in the Knowledge Compilation step. By contrast, our inexact solution CNF Proxy is extremely fast even for these hard cases -it typically terminates in a few milliseconds with the worst observed case (an outlier) being 4 seconds. In fact, it is faster by several orders of magnitude than sampling-based approximation techniques (the Monte Carlo sampling proposed in [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF] as well as a popular sampling-based solution for Shapley values in Machine Learning (Kernel SHAP [START_REF] Scott | A unified approach to interpreting model predictions[END_REF]). To measure quality, we use CNF Proxy to rank the input tuples, and compared the obtained ranked lists to ranking by actual Shapley values (in cases where exact computation has succeeded), using the standard measures of nDCG and Precision@k. Our solution outperforms the competitors in terms of quality as well.

We then propose a simple hybrid approach: execute the exact algorithm until it either terminates or a timeout elapses. If we have reached the timeout, resort to executing CNF Proxy and rank the facts based on the obtained values. We show experiments with different timeout values, justifying our choice of 2.5 seconds.

Hence, our contributions are both of a theoretical and practical nature and can be summarized as follows.

• By adapting the proof technique of [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF], we establish a fundamental result about the complexity of computing Shapley values over relational queries: Shapley values can be computed in polynomial time-in data complexity-whenever the query can be evaluated in polynomial time over tupleindependent probabilistic databases (Proposition 3.1). This holds for every query. • By adapting the proof technique of [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF][START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF], we devise a novel algorithm for computing Shapley values for query evaluation via compilation to a deterministic and decomposable circuit (Proposition 4.4). We show that this algorithm is practical and has the theoretical guarantee of running in polynomial time in the size of the circuit. • We present a novel heuristic, CNF Proxy, that is fast yet inexact, and is practically effective if we are interested in ranking input facts by their contribution rather than computing exact Shapley values (Section 5). • We describe a thorough experimental study of our algorithms over realistic data and show their efficiency (Section 6).

Related work.

Existing models for explaining database query results may roughly be divided in two categories: (1) models that are geared for tracking/presenting provenance of output tuples, e.g., the set of all input facts participating in their computation [START_REF] Cui | Tracing the lineage of view data in a warehousing environment[END_REF], possibly alongside a description of the ways they were used, in different granularity levels (e.g., [START_REF] Buneman | Curated databases[END_REF][START_REF] Buneman | Why and where: A characterization of data provenance[END_REF][START_REF] Todd J Green | Provenance semirings[END_REF]); (2) models that quantify contributions of input facts [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Meliou | The complexity of causality and responsibility for query answers and non-answers[END_REF][START_REF] Meliou | Causality and explanations in databases[END_REF][START_REF] Salimi | Quantifying causal effects on query answering in databases[END_REF], which is the approach that we follow here. Works in the latter context often have connections with the influential line of work on probabilistic databases [START_REF] Suciu | Probabilistic Databases[END_REF], and we show that this is the case for Shapley computation as well.

As already mentioned, an important point of comparison is the work of Van den Broeck et al. [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF] and that of Arenas et al. [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF][START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF] on the SHAP-score. While we show that the proof techniques developed in this area can be adapted to the context of relational databases, we point out that the two sets of results obtained (for SHAP-score and for Shapley values for databases) seem incomparable, as we do not see a way of proving results for Shapley value for query answering using the results on the SHAP-score, or vice-versa. In fact, this adaptation only works up to a certain point. For instance, the efficiency axiom of the Shapley value immediately implies that computing the expected value of a model can be reduced in polynomial time to computing the SHAP-score of its features; in contrast, this axiom does not seem to yield any clear such implication in our context (see our Open Problem 1 and the discussion around it).

Paper organization. We formalize the notion of Shapley values for query answering in Section 2. In Section 3 we present the theoretical connection to probabilistic databases and its implications. Our exact computation algorithm is presented in Section 4 and our heuristic in Section 5. Experimental results are presented in Section 6 and we conclude in Section 7.

THE SHAPLEY VALUE OF FACTS

We define here the main notion and illustrate it with an example.

Relational databases and queries. Let Σ = {𝑅 1 , . . . , 𝑅 𝑛 } be a signature, consisting of relation names 𝑅 𝑖 each with its associated arity ar(𝑅 𝑖 ) ∈ N, and Const be a set of constants. A fact over (Σ, Const) is simply a term of the form 𝑅(𝑎 1 , . . . , 𝑎 ar(𝑅) ), for 𝑅 ∈ Σ and 𝑎 𝑖 ∈ Const. A (Σ, Const)-database 𝐷, or simply a database 𝐷, is a finite set of facts over (Σ, Const). We assume familiarity with the most common classes of query languages and refer the reader to [START_REF] Abiteboul | Foundations of Databases[END_REF] for the basic definitions. In particular, we recall the equivalence between relational algebra and relational calculus [START_REF] Abiteboul | Foundations of Databases[END_REF], and the fact that Select-Project-Join-Union (SPJU) queries are equivalent to unions of conjunctive queries (UCQs). Depending of the context and for consistency with relevant past publications, we will use terminology of either relational calculus or relational algebra. What we call a Boolean query is a query 𝑞 that takes as input a database 𝐷 and outputs 𝑞(𝐷) ∈ {0, 1}. If 𝑞( x) is a query with free variables x and t is a tuple of constants of same length as x, we denote by 𝑞[ x/ t] the Boolean query defined by: 𝑞[ x/ t] (𝐷) = 1 if and only if t is in the output of 𝑞( x) on 𝐷.

Shapley values of facts. Following [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Reshef | The impact of negation on the complexity of the Shapley value in conjunctive queries[END_REF], we use the notion of Shapley values [START_REF] Lloyd | A value for n-person games[END_REF] to attribute a contribution to facts of an input database. In this context, the database 𝐷 is traditionally partitioned into two sets of facts: a set 𝐷 x of so-called exogenous facts, and a set 𝐷 n of endogenous facts. The idea is that exogenous facts are considered as given, while endogenous facts are those to which we would like to attribute contributions. Let 𝑞 be a Boolean query and 𝑓 ∈ 𝐷 n be an endogenous fact. The Shapley value of 𝑓 in 𝐷 for query 𝑞, denoted Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑓 ), is defined as

Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑓 ) def = (1)
∑ 𝐸 ⊆𝐷 n \{𝑓 } |𝐸|!(|𝐷 n | -|𝐸| -1)! |𝐷 n |! 𝑞(𝐷 x ∪ 𝐸 ∪ {𝑓 }) -𝑞(𝐷 x ∪ 𝐸) .
Notice that here, |𝐸|!(|𝐷 n | -|𝐸| -1)! is the number of permutations of 𝐷 n with all endogenous facts in 𝐸 appearing first, then 𝑓 , and finally, all the other endogenous facts. Intuitively then, the value Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑓 ) represents the contribution of 𝑓 to the query's output: the higher this value is, the more 𝑓 helps in satisfying 𝑞.

For non-Boolean queries 𝑞( x), we are interested in the Shapley value of the fact 𝑓 for every individual tuple t in the output [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF]. The extension to non-Boolean 𝑞( x) is then straightforward: the Shapley value of the fact 𝑓 for the answer t to 𝑞( x) is the value Shapley(𝑞[ x/ t], 𝐷 n , 𝐷 x , 𝑓 ). Therefore, the computational challenge reduces to that of the Boolean query 𝑞 [ x/ t]. Hence, in the theoretical analysis we focus on Boolean queries, and we go back to considering non-Boolean queries when we study the implementation aspects (starting in Section 4.2).

Example 2.1. Consider the database 𝐷 and the Boolean query 𝑞 from Figures 1a and1c. All facts in table Flights are endogenous, while facts in Airports are exogenous. To alleviate the notation we write, e.g., 𝑎 1 for Flights(JFK, CDG). The query 𝑞 checks if there are routes from "USA" to "FR" with one or less connecting flights. Let us compute the Shapley value of all endogenous facts. First, we notice that fact 𝑎 8 is not part of any valid route, so Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑎 8 ) = 0 by Equation [START_REF] Abiteboul | Foundations of Databases[END_REF]. Next, let us focus on 𝑎 1 . Since 𝑎 1 is a valid route on its own, adding it to any subset of (endogenous) facts 𝐸 such that 𝐸 does not contain a valid route results in 𝑞(𝐷 x ∪ 𝐸 ∪ {𝑎 1 }) -𝑞(𝐷 x ∪ 𝐸) = 1 (for all other subsets the difference will be 0). The relevant subsets are the empty set, all singletons {𝑎 𝑖 } for 2 ≤ 𝑖 ≤ 8 (7 singletons), all the pairs of tuples from 𝑎 2 , . . . , 𝑎 8 excluding the pairs {𝑎 2 , 𝑎 4 }, {𝑎 2 , 𝑎 5 }, {𝑎 3 , 𝑎 4 }, {𝑎 3 , 𝑎 5 }, and {𝑎 6 , 𝑎 7 } (so 7 2 -5 = 16 pairs), the quadruples {𝑎 2 , 𝑎

Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑎 1 ) = 1 • 0! • 7! 8! + 7 • 1! • 6! 8! + 16 • 2!5! 8! + 14 • 3!4! 8! + 4 • 4!3! 8! = 43

REDUCTION TO PROBABILISTIC DATABASES

In this section we investigate the complexity of computing Shapley values. As explained in the previous section, the non-Boolean setting of the problem may be reduced to that of Boolean queries, so we will study the following problem for a given Boolean query 𝑞.

PROBLEM: Shapley(𝑞)

INPUT: A database 𝐷 = 𝐷 x ∪ 𝐷 n and an endogenous fact 𝑓 ∈ 𝐷 n . OUTPUT: The value Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑓 ).

Note that for the sake of complexity analysis, the query 𝑞 is assumed to be fixed, so that each query gives rise to a different computational problem; we are then considering what is called the data complexity [START_REF] Vardi | The complexity of relational query languages[END_REF]. This assumption is motivated by the fact that in practice, the queries are much smaller than the databases.

The complexity of this problem has been studied in [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Reshef | The impact of negation on the complexity of the Shapley value in conjunctive queries[END_REF], where in particular a dichotomy has been obtained for self-join-free Boolean conjunctive queries (sjfbcqs). There, the authors show that, for every sjfbcq 𝑞, either 𝑞 is hierarchical (we will not need to define this notion here) and Shapley(𝑞) can be solved in polynomial time, or 𝑞 is not hierarchical and then Shapley(𝑞) is intractable (specifically, FP Routes from "USA" to "FR" with one or less connecting flights

𝑞 1 = ∃𝑥, 𝑦 : Airports(𝑥, "USA") ∧ Airports(𝑦, "FR") ∧ Flights(𝑥, 𝑦) 𝑞 2 = ∃𝑥, 𝑦, 𝑧 : Airports(𝑥, "USA") ∧ Airports(𝑧, "FR") ∧ Flights(𝑥, 𝑦) ∧ Flights(𝑦, 𝑧) 𝑞 = 𝑞 1 ∨ 𝑞 2 (c) 𝑞 is a Boolean union of conjunctive queries (UCQ) (𝑎 1 ∧ 𝑏 1 ∧ 𝑏 8 ) 𝑞 1 provenance ∨ (𝑎 2 ∧ 𝑎 4 ∧ 𝑏 2 ∧ 𝑏 8 ) ∨ (𝑎 2 ∧ 𝑎 5 ∧ 𝑏 2 ∧ 𝑏 7 ) ∨ (𝑎 3 ∧ 𝑎 4 ∧ 𝑏 3 ∧ 𝑏 8 ) ∨ (𝑎 3 ∧ 𝑎 5 ∧ 𝑏 3 ∧ 𝑏 7 ) ∨ (𝑎 6 ∧ 𝑎 7 ∧ 𝑏 5 ∧ 𝑏 7 ) 𝑞 2 provenance (d)
The lineage Lin(𝑞, 𝐷) as a formula in Disjunctive Normal Form (DNF) Figure 1: The database, query 𝑞 and its lineage used for our running example is obtained-being hierarchical-is exactly the same as in the context of probabilistic query evaluation (PQE); see, e.g., [START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF][START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF]. In fact, the main result of this section is that this is not a coincidence: we prove that, for every Boolean query 𝑞 (not just for sjfbcqs), if PQE is tractable for 𝑞 then so is the problem Shapley(𝑞). Since PQE has been intensively studied already, our result allows us to vastly extend the tractable cases identified in [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF][START_REF] Reshef | The impact of negation on the complexity of the Shapley value in conjunctive queries[END_REF]. We now proceed with the definitions and proof of this result, and explain its consequences.

Probabilistic query evaluation.

A tuple-independent (TID) database is a pair consisting of a database 𝐷 and a function 𝜋 mapping each fact 𝑓 ∈ 𝐷 to a probability value 𝜋 (𝑓 ) ∈ [0, 1]. The TID (𝐷, 𝜋) defines a probability distribution Pr 𝜋 on 𝐷 ′ ⊆ 𝐷, where

Pr 𝜋 (𝐷 ′ ) def = 𝑓 ∈𝐷 ′ 𝜋 (𝑓 ) × 𝑓 ∈𝐷\𝐷 ′ (1 -𝜋 (𝑓 ))
. Given a Boolean query 𝑞, the probability that 𝑞 is satisfied by (𝐷, 𝜋) is Pr(𝑞, (𝐷, 𝜋))

def = 𝐷 ′ ⊆𝐷 s.t. 𝑞 (𝐷 ′ )=1 Pr 𝜋 (𝐷 ′ ).
The probabilistic query evaluation problem for 𝑞, PQE(𝑞) for short, is then defined as follows.

PROBLEM: PQE(𝑞)

INPUT: A tuple-independent database (𝐷, 𝜋). OUTPUT: The value Pr(𝑞, (𝐷, 𝜋)).

For two computational problems 𝐴 and 𝐵, we write 𝐴 ≤ p T 𝐵 to assert the existence of a polynomial-time Turing reduction from 𝐴 to 𝐵. We are ready to state the main result of this section. This result implies that for any query 𝑞 for which PQE(𝑞) is tractable then so is Shapley(𝑞). Dalvi and Suciu [START_REF] Dalvi | The dichotomy of probabilistic inference for unions of conjunctive queries[END_REF] showed a dichotomy for unions of conjunctive queries: for every such query 𝑞, either PQE(𝑞) is solvable in polynomial time, in which case 𝑞 is called safe1 , or PQE(𝑞) is FP #P -hard (and 𝑞 is called unsafe). Therefore, we obtain as a direct corollary of Proposition 3.1 that Shapley(𝑞) can be solved in polynomial time for all safe queries. Corollary 3.2. If 𝑞 is a safe UCQ then Shapley(𝑞) can be solved in polynomial time.

In particular, this corollary generalizes the tractability result obtained in [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF], to account for CQs with self-joins and even unions of such queries. We now prove Proposition 3. Then, by grouping by size the terms 𝐸 from Equation 1 we obtain

Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑓 ) = |𝐷 n |-1 ∑ 𝑘=0 𝑘!(|𝐷 n | -𝑘 -1) |𝐷 n | (2) #Slices(𝑞, 𝐷 x ∪ {𝑓 }, 𝐷 n \ {𝑓 }, 𝑘) -#Slices(𝑞, 𝐷 x , 𝐷 n \ {𝑓 }, 𝑘) .
All arithmetical terms (such as 𝑘! or |𝐷 n |!) can be computed in polynomial time. Therefore, to prove that Shapley(𝑞) ≤ p T PQE(𝑞), it is enough to show that, given an oracle to the problem PQE(𝑞), we can compute in polynomial time the quantities #Slices(𝑞, 𝐷 x , 𝐷 n , 𝑘), for some arbitrary 𝐷 = 𝐷 x ∪ 𝐷 n and 𝑘 ∈ {0, . . . , |𝐷 n |}. This is what we do next.

The proof is similar to that of [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF]Theorem 2] in the context of SHAP-score for machine learning (but, as explained in the Introduction, the two results seem to be incomparable).

We wish to compute #Slices(𝑞, 𝐷 x , 𝐷 n , 𝑘), for some database 𝐷 = 𝐷 x ∪𝐷 n and integer 𝑘 ∈ {0, . . . |𝐷 n |}. Let 𝑛 = |𝐷 n | be the number of endogenous facts of 𝐷. For 𝑧 ∈ Q, we define a TID database (𝐷 𝑧 , 𝜋 𝑧 ) as follows: 𝐷 𝑧 contains all the facts of 𝐷, and for an exogenous fact 𝑓 of 𝐷 we define 𝜋 𝑧 (𝑓 ) def = 1 while for an endogenous fact 𝑓 of 𝐷 we define 𝜋 𝑧 (𝑓 ) def = 𝑧 1+𝑧 . It is then routine to show that the following relation holds:

(1 + 𝑧) 𝑛 Pr(𝑞, (𝐷 𝑧 , 𝜋 𝑧 )) = 𝑛 ∑ 𝑖=0 𝑧 𝑖 #Slices(𝑞, 𝐷 x , 𝐷 n , 𝑖).
This suffices to conclude the proof. Indeed, we now call an oracle to PQE(𝑞) on 𝑛 + 1 databases 𝐷 𝑧 0 , . . . , 𝐷 𝑧 𝑛 for 𝑛 + 1 arbitrary distinct values 𝑧 0 , . . . , 𝑧 𝑛 , forming a system of linear equations as given by the relation above. Since the corresponding matrix is a Vandermonde with distinct coefficients, it is invertible, so we can compute in polynomial time the value #Slices(𝑞, 𝐷 x , 𝐷 n , 𝑘). □

A intriguing natural question is whether the converse of Proposition 3.1 is true, that is, whether we also have PQE(𝑞) ≤ p T Shapley(𝑞). This is true when 𝑞 is a self-join-free conjunctive query: indeed, by the results of [START_REF] Livshits | The Shapley value of tuples in query answering[END_REF], either 𝑞 is hierarchical and then both PQE(𝑞) and Shapley(𝑞) can be solved in polynomial time (hence PQE(𝑞) ≤ p T Shapley(𝑞)), or 𝑞 is not hierarchical and then Shapley(𝑞) is FP #Phard (which, together with the fact that PQE(𝑞) ∈ FP #P , implies PQE(𝑞) ≤ p T Shapley(𝑞)). However, to the best of our knowledge, the existence of such a reduction in the general case is unknown.

Open problem 1. Do we have PQE(𝑞) ≤ p T Shapley(𝑞) for every Boolean query 𝑞?

Interestingly, we note that this direction is trivial in the setting of SHAP-scores. Indeed, this is directly implied by the efficiency axiom of the Shapley value; see, e.g., [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF]Lemma 4.2] or [START_REF] Van Den Broeck | On the tractability of shap explanations[END_REF]Equation 5]. In our case, this axiom only gives us the following equality:

∑ 𝑓 ∈𝐷 n Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑓 ) = 𝑞(𝐷 n ∪ 𝐷 x ) -𝑞(𝐷 x ),
which does not seem to help in showing PQE(𝑞) ≤ p T Shapley(𝑞).

EXACT COMPUTATION THROUGH KNOWLEDGE COMPILATION

Motivated by the connection to PQE that we have seen in Section 3, we now investigate whether an approach using knowledge compilation can be used for computing Shapley values. Indeed, a common method to compute the probability that a probabilistic database (𝐷, 𝜋) satisfies a Boolean query 𝑞 is to first compute the lineage of 𝑞 on 𝐷 in a formalism from knowledge compilation, and then to use the good properties of said formalism to compute Pr(𝑞, (𝐷, 𝜋)) in linear time [START_REF] Jha | Knowledge compilation meets database theory: compiling queries to decision diagrams[END_REF][START_REF] Monet | Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases[END_REF][START_REF] Suciu | Probabilistic Databases[END_REF]. Recently, Arenas and others [START_REF] Arenas | On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results[END_REF][START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF] showed that this approach is also viable for the notion of SHAP-score used in machine learning, by proving that SHAPscores can be computed in polynomial time when the models are given as circuits from knowledge compilation. By reusing some of these techniques, we can show that this method can also be used in our setting for computing Shapley values of database facts. Again, to the best of our knowledge, the two results are incomparable, i.e., we are not aware of a reduction in either direction between the two problems. We start by formally defining the notions of lineage and the relevant circuit classes from knowledge compilation. Boolean functions and query lineages. Let 𝑋 be a finite set of variables. An assignment 𝜈 of 𝑋 is a subset 𝜈 ⊆ 𝑋 of 𝑋 . We denote by 2 𝑋 the set of all assignments of 𝑋 . A Boolean function 𝜑 over 𝑋 is a function 𝜑 : 2 𝑋 → {0, 1}. An assignment 𝜈 ⊆ 𝑋 is satisfying if 𝜑 (𝜈) = 1. We denote by SAT(𝜑) ⊆ 2 𝑋 the set of all satisfying assignments of 𝜑, and by #SAT(𝜑) the size of this set. For 𝑘 ∈ N, we define SAT 𝑘 (𝜑)

∧ ∧ ¬ ¬ ¬ 𝑎 3 𝑎 5 𝑎 1 ¬ ¬ ∧ ∧ 𝑎 7 ∧ 𝑎 6 𝑎 4 𝑎 2 ∨ ∨ ¬ ¬ ¬
def = SAT(𝜑) ∩ {𝜈 ⊆ 𝑋 | |𝜈 | = 𝑘 }, that
is, the set of satisfying assignments of 𝜑 of Hamming weight 𝑘, and let #SAT 𝑘 (𝜑) be the size of this set.

Let 𝑞 be a Boolean query and 𝐷 be a database. The lineage Lin(𝑞, 𝐷) is the (unique) Boolean function whose variables are the facts of 𝐷, and that maps each sub-database 𝐷 ′ ⊆ 𝐷 to 𝑞(𝐷 ′ ). This definition extends straightforwardly to queries with free variables as follows: if 𝑞( x) is a query with free variables x and t is a tuple of constants of the appropriate size, then Lin(𝑞[ x/ t]), 𝐷) is the lineage for the tuple t.

Example 4.1. Consider again the database 𝐷 and the Boolean query 𝑞 from Figures 1a and1c. In Figure 1d, the lineage Lin(𝑞, 𝐷) is represented as a formula in disjunctive normal form (DNF).

For our purposes, we will use a refinement of this lineage that accounts for the nature of exogenous tuples; specifically, these tuples should be considered as always being part of the database. Let 𝐷 = 𝐷 n ∪ 𝐷 x be a database with endogenous tuples 𝐷 n and exogenous tuples 𝐷 x , and let 𝑞 be a Boolean query. Then the endogenous lineage ELin(𝑞, 𝐷 x , 𝐷 n ) is the (unique) Boolean function whose variables are 𝐷 n and that maps every set 𝐸 of endogenous facts to 𝑞(𝐷 x ∪ 𝐸). In other words, ELin(𝑞, 𝐷 x , 𝐷 n ) can be obtained from Lin(𝑞, 𝐷) by fixing all variables in 𝐷 x to the value 1. Again, we extend this definition to queries with free variables by using the function ELin(𝑞[ x/ t], 𝐷 x , 𝐷 n ).

Example 4.2. Continuing the previous example, the endogenous lineage ELin(𝑞, 𝐷 n , 𝐷 x ) can be represented as a DNF by

𝑎 1 ∨ (𝑎 2 ∧ 𝑎 4 ) ∨ (𝑎 2 ∧ 𝑎 5 ) ∨ (𝑎 3 ∧ 𝑎 4 ) ∨ (𝑎 3 ∧ 𝑎 5 ) ∨ (𝑎 6 ∧ 𝑎 7 ) .
In the last two examples, lineages were represented with Boolean formulas in DNF. Since a lineage is a Boolean function, it can be represented with any formalism that allows to represent Boolean functions. We next review some classes of circuits from the field of knowledge compilation that will be relevant for our work.

Knowledge compilation classes.

Let 𝐶 be a Boolean circuit, featuring ∧, ∨, ¬, and variable gates, with the usual semantics. 2 The output gate, for instance, is a deterministic ∨-gate: indeed, its left child requires 𝑎 1 to be 1, whereas its right child requires 𝑎 1 to be 0. The right child of the output gate is a decomposable ∧-gate: indeed, for its left child 𝑔 1 we have Vars(𝑔 1 ) = {𝑎 1 }, whereas for its right child 𝑔 2 we have Vars(𝑔 2 ) = {𝑎 2 , 𝑎 3 , 𝑎 4 , 𝑎 5 , 𝑎 6 , 𝑎 7 }, and these are indeed disjoint. The reader can easily check that all other ∨gates are deterministic, and that all other ∧-gates are decomposable.

Algorithm

The main result of this section is then the following. Proof of Proposition 4.4. Let 𝐶 be a deterministic and decomposable circuit representing ELin(𝑞, 𝐷 n , 𝐷 x ), and let 𝑓 ∈ 𝐷 n . First, we complete the circuit 𝐶 so that all variables of 𝐷 n appear in 𝐶. Indeed, it could be the case that Vars(𝐶) ⊊ 𝐷 n : this happens for instance with the deterministic and decomposable circuit in Figure 2, where the endogenous fact 𝑎 8 does not appear in the circuit. To do this, we conjunct 𝐶 with the conjunction 𝑓 ′ ∈𝐷 n \Vars(𝐶) (𝑓 ′ ∨ ¬𝑓 ′ ). Note that this does not change the semantics of the circuit (as this conjunction always evaluates to 1) and that the resulting circuit is still deterministic and decomposable. Now, let 𝐶 1 (resp., 𝐶 2 ) be the Boolean circuit obtained from 𝐶 by replacing all variable gates corresponding to the fact 𝑓 by a constant 1-gate (resp., by a constant 0-gate). Observe then that the variables of 𝐶 1 and 𝐶 2 are exactly 𝐷 n \ {𝑓 }, and moreover that 𝐶 1 and 𝐶 2 are still deterministic and decomposable. By definition of the endogenous lineage, we can rewrite Equation (2) into the following. 2 We allow unbounded-fanin ∧and ∨-gates, and also allow constant 1-gates and constant 0-gates as, respectively, ∧-gates with no input and ∨-gates with no inputs.

Shapley(𝑞, 𝐷

n , 𝐷 x , 𝑓 ) = |𝐷 n |-1 ∑ 𝑘=0 𝑘!(|𝐷 n | -𝑘 -1) |𝐷 n | (3)
#SAT 𝑘 (𝐶 1 ) -#SAT 𝑘 (𝐶 2 ) .

Proposition 4.4 will thus directly follow from the next lemma. First of all, we preprocess 𝐶 so that the fanin of every ∨and ∧-gate is exactly 0 or 2; this can simply be done by rewriting every ∧-gate of fanin 𝑚 > 2 with 𝑚 -1 ∧gates of fanin 2 (same for ∨-gates), and adding a constant gate of the appropriate type to every ∨and ∧-gate of fan-in 1. We then compute, for every gate 𝑔 of 𝐶, the set of variables Vars(𝑔) upon which the value of 𝑔 depends. For a gate 𝑔 of 𝐶, let us denote by 𝜑 𝑔 the Boolean function over the variables Vars(𝑔) that is represented by this gate. For a gate 𝑔 and an integer ℓ ∈ {0, . . . , |Vars(𝑔)|}, we define 𝛼 ℓ 𝑔 def = #SAT ℓ (𝜑 𝑔 ), i.e. the number of assignments of size ℓ to Vars(𝑔) that satisfy 𝜑 𝑔 . We will show how to compute all the values 𝛼 ℓ 𝑔 for every gate 𝑔 of 𝐶 and ℓ ∈ {0, . . . , |Vars(𝑔)|} in polynomial time. This will conclude the proof since, for the output gate 𝑔 output of 𝐶, we have that 𝛼 𝑘 𝑔 output = #SAT 𝑘 (𝑓 ). We will need the following notation: for two disjoint sets of variables 𝑋 1 , 𝑋 2 and two subsets 𝑆 1 ⊆ 2 𝑋 1 , 𝑆 2 ⊆ 2 𝑋 2 of assignments to 𝑋 1 and 𝑋 2 , we denote by

𝑆 1 ⊗ 𝑆 2 ⊆ 2 𝑋 1 ∪𝑋 2 the set of assignments of 𝑋 1 ∪ 𝑋 2 defined by 𝑆 1 ⊗ 𝑆 2 def = {𝜈 1 ∪ 𝜈 2 | 𝜈 1 ∈ 𝑆 2 ,
SAT(𝜑 𝑔 ) = (SAT(𝜑 𝑔 1 ) ⊗ 2 𝑆 1 ) ∪ (SAT(𝜑 𝑔 2 ) ⊗ 2 𝑆 2 )
with the union being disjoint. By intersecting with the assignments of Vars(𝑔) of size ℓ, we obtain:

SAT ℓ (𝜑 𝑔 ) = (SAT(𝜑 𝑔 1 ) ⊗ 2 𝑆 1 ) ∩ {𝜈 ⊆ Vars(𝑔) | |𝜈 | = ℓ } ∪ (SAT(𝜑 𝑔 2 ) ⊗ 2 𝑆 2 ) ∩ {𝜈 ⊆ Vars(𝑔) | |𝜈 | = ℓ }
with again the middle union being disjoint, therefore:

#SAT ℓ (𝜑 𝑔 ) =|(SAT(𝜑 𝑔 1 ) ⊗ 2 𝑆 1 ) ∩ {𝜈 ⊆ Vars(𝑔) | |𝜈 | = ℓ }| + |(SAT(𝜑 𝑔 2 ) ⊗ 2 𝑆 2 ) ∩ {𝜈 ⊆ Vars(𝑔) | |𝜈 | = ℓ }|
∑ 𝑖 = max(0, ℓ-|𝑆 1 |) 𝛼 𝑖 𝑔 1 × |𝑆 1 | ℓ -𝑖 .
Decomposable ∧-gate. If 𝑔 is a decomposable ∧-gate with no input then 𝜑 𝑔 is the Boolean function on variables Vars(𝑔) = ∅ that is always true, hence 𝛼 0 𝑔 = 1. Otherwise, let 𝑔 1 and 𝑔 2 be the two input gates of 𝑔. Since 𝑔 is decomposable we have Vars(𝑔) = Vars(𝑔 1 ) ∪ Vars(𝑔 2 ) with the union being disjoint. But then we have:

SAT(𝜑 𝑔 ) = SAT(𝜑 𝑔 1 ) ⊗ SAT(𝜑 𝑔 2 )
We now intersect with the set of assignments of Vars(𝑔) of size 𝑙 to obtain

𝛼 ℓ 𝑔 = #SAT ℓ (𝜑 𝑔 ) = min(ℓ, |Vars(𝑔 1 ) |) ∑ 𝑖 = max(0, ℓ-|Vars(𝑔 2 ) |) 𝛼 𝑖 𝑔 1 × 𝛼 ℓ-𝑖 𝑔 2
This concludes the proof of the lemma, as well as the proof of Proposition 4.

This function computes values 𝛼 ℓ

𝑔 by bottom-up induction on 𝐶 just as in the proof of Lemma 4.5, by using the appropriate equations depending on the type of each gate. Then, Lines 1-5 in the algorithm simply follow the part of the proof that starts at the beginning of this section until Lemma 4.5. For instance, the returned value on Line 5 corresponds to Equation [START_REF] Arenas | The tractability of SHAP-score-based explanations over deterministic and decomposable Boolean circuits[END_REF]. A quick inspection of Algorithm 1 reveals that, if one ignores the complexity of performing arithmetic operations (i.e., considering that additions and multiplications take constant time), the running time is 𝑂 (|𝐶 | • |𝐷 n | 2 ). If one wishes to compute the Shapley value of every endogenous fact (as will be done in the experiments), then the overall complexity is 𝑂 (|𝐶 | • |𝐷 n |3 ). Last, we point out that, in the case of non-Boolean queries, this cost is incurred for each potential output tuple that one wants to analyze.

Implementation Architecture

In this section, we present our architecture for implementing the knowledge compilation approach over realistic datasets. The relevant parts, for now, are the middle and top part of Figure 3, which we next explain. Given a database 𝐷 = 𝐷 x ∪ 𝐷 n , a query 𝑞( x), a tuple t of the same arity as x, and an endogenous fact 𝑓 ∈ 𝐷 n , we want to compute Shapley(𝑞[ x/ t], 𝐷 x , 𝐷 n , 𝑓 ). We use two existing tools to help us with this task: ProvSQL [START_REF] Senellart | Provsql: Provenance and probability management in postgresql[END_REF] and the knowledge compiler c2d [START_REF] Darwiche | New advances in compiling CNF to decomposable negation normal form[END_REF]. ProvSQL is a tool integrated into PostgreSQL that can perform provenance (lineage) computation in various semirings. For our purposes, a knowledge compiler is a tool that takes as input a Boolean function in CNF and outputs an equivalent Boolean function into another formalism. The target formalism that we will use is the so-called "d-DNNF". A d-DNNF is simply a deterministic and decomposable Boolean circuit such that negation gates are only applied to variables (NNF stands for negation normal form). 4In our case, we use ProvSQL as follows: we feed it the database 𝐷, query 𝑞( x) and tuple t, and ProvSQL computes Lin(𝑞 [ x/ t], 𝐷) as a Boolean circuit, called 𝐶 in Figure 3. We note here that for SPJU queries, 𝐶 can be computed in polynomial-time data complexity. We then set to 1 all the exogenous facts to obtain a Boolean circuit 𝐶 ′ for ELin(𝑞[ x/ t], 𝐷 x , 𝐷 n ). Then, ideally, we would like to use the knowledge compiler to transform 𝐶 ′ into an equivalent d-DNNF, in order to be able to apply Algorithm 1. Unfortunately, every knowledge compiler that we are aware of takes as input Boolean formulas in conjunctive normal form (CNF), and not arbitrary Boolean circuits. To circumvent it, we use the Tseytin transformation [START_REF] Grigori S Tseitin | On the complexity of derivation in propositional calculus[END_REF] to transform the circuit 𝐶 ′ into a CNF 𝜑 def = Tseytin(𝐶 ′ ), whose size is linear in that of 𝐶 ′ . This CNF 𝜑 has the following properties: (1) its variables are the variables of 𝐶 ′ plus a set 𝑍 of additional variables; (2) for every valuation 𝜈 ⊆ Vars(𝐶 ′ ) that satisfies 𝐶 ′ , there exists exactly one valuation 𝜈 ′ ⊆ 𝑍 such that 𝜑 (𝜈 ∪ 𝜈 ′ ) = 1; and (3) for every valuation 𝜈 ⊆ Vars(𝐶 ′ ) that does not satisfy 𝐶 ′ , there is no valuation 𝜈 ′ ⊆ 𝑍 such that 𝜑 (𝜈 ∪ 𝜈 ′ ) = 1. We then feed 𝜑 to the knowledge compiler, which produces a d-DNNF 𝐶 ′′ equivalent to 𝜑 (the variables of 𝐶 ′′ are again Vars(𝐶 ′ ) ∪ 𝑍 ). We note here that there is no theoretical guarantee that this step is efficient; indeed, the task of transforming a CNF into an equivalent d-D circuit is FP #P -hard in general; see Section 6 for an experimental analysis of its tractability in practice. Next, we need to eliminate the additional variables 𝑍 in order to be able to apply Algorithm 1. To this end, we use the following Lemma. Lemma 4.6. Given as input a d-DNNF 𝐶 ′′ that is equivalent to Tseytin(𝐶 ′ ) for a Boolean circuit 𝐶 ′ , we can compute in time 𝑂 (|𝐶 ′′ |) a d-DNNF 𝐶 ′′′ that is equivalent to 𝐶 ′ (in particular, the variables of 𝐶 ′′′ are the same as the variables of 𝐶 ′ ; in our case, they consist only of endogenous facts).

Proof sketch. Let 𝑍 be the additional variables coming from the Tseytin transformation. First, we remove all the gates of 𝐶 ′′ that are not satisfiable, and then we remove all the gates that are not connected to the output gate. Now, let 𝐶 ′′′ be the circuit that is obtained from this intermediate circuit by replacing every literal 𝑧 or ¬𝑧 for 𝑧 ∈ 𝑍 by a constant 1-gate. We return 𝐶 ′′′ . The proof that this algorithm is correct uses the properties (1-3) of the Tseytin transformation, and is omitted due to lack of space. □

Using this lemma, we obtain a d-DNNF 𝐶 ′′′ for the endogenous lineage ELin(𝑞[ x/ t], 𝐷 x , 𝐷 n ), to which we can finally apply Algorithm 1 to obtain the value Shapley(𝑞[ x/ t], 𝐷 x , 𝐷 n , 𝑓 ).

INEXACT COMPUTATION

As we will show in the experimental section, the exact computation algorithm that we have proposed performs well in most cases but is too costly in others. In the latter cases, we may wish to resort to methods that do not necessarily compute exact Shapley values, if their results still typically suffice to determine the order of facts according to their Shapley contribution. In this section we propose CNF Proxy, a heuristic solution that is very efficient, and we will experimentally show that the ranking of facts based on CNF Proxy tends to match the ranking based on the exact Shapley values.

At a high level, CNF Proxy is based on the observation that having a high Shapley score is correlated (albeit in a complex manner) with (1) appearing many times in the provenance and (2) having few "alternatives," that is, facts that could compensate for the absence of the given fact. The first factor (number of occurrences) may be directly read from the CNF obtained by applying the Tseytin transformation to the provenance circuit (𝐶 ′ in Figure 3). It is also easy to read from the CNF partial information about the second factor (number of alternatives), namely the number of alternatives in each clause (ignoring intricate dependencies between clauses). Next, we present the details of CNF Proxy.

We will start with an auxiliary definition, denoting the Shapley value of a general function ℎ : 2 𝑋 → R and a variable 𝑥 ∈ 𝑋 as

Shapley(ℎ, 𝑥) def = ∑ 𝑆 ⊆𝑋 \{𝑥 } |𝑆 |!(|𝑋 | -|𝑆 | -1)! |𝑋 |! ℎ(𝑆 ∪ {𝑥 }) -ℎ(𝑆) .
Naturally, if ℎ = ELin(𝑞, 𝐷 n , 𝐷 x ), i.e., the endogenous lineage, and 𝑥 is a fact in 𝐷 n , then Shapley(ℎ, 𝑥) = Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑥). 𝑛 𝜓 𝑖 (𝜈). Intuitively, a fact that appears in many clauses of the CNF 𝜑 will occur in many summands of 𝜑, and when we compute Shapley values with respect to 𝜑, the number of alternatives in each clause will be reflected in decreased value of the respective summands.

Example 5.1. Consider the CNF formula 𝜑 = (𝑥 1 ∨ 𝑥 2 ) ∧ (𝑥 1 ∨ 𝑥 3 ∨ 𝑥 4 ). The Shapley values of 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 are 7 12 , 3 12 , 1 12 , 1 12 respectively. Note that 𝑥 1 has the highest influence, which intuitively may be attributed to its appearance in two clauses whereas each other variable appears only in a single clause. The variable 𝑥 2 has more influence than 𝑥 3 and 𝑥 4 , intuitively since it has less alternatives. These comparative features are preserved in 𝜑 = (𝑥 1 ∨ 𝑥 2 ) + (𝑥 1 ∨ 𝑥 3 ∨ 𝑥 4 ), and indeed the Shapley values of 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 with respect to 𝜑 are 5 6 , 1 2 , 1 3 , 1 3 respectively. Observe that although the values assigned to the variables are very different from their actual Shapley values, their order remains intact in this case.

Due to the linearity of Shapley values, their computation with respect to 𝜑 is much more efficient, as implied by the following lemma (whose proof we omit for space reasons): Lemma 5.

Φ(𝜓 𝑖 , 𝑥) =              1 (𝑎 𝑖 +𝑏 𝑖 ) •( 𝑎 𝑖 +𝑏 𝑖 -1 𝑏 𝑖 ) if 𝑥 appears in 𝜓 𝑖 in positive form; -1 (𝑎 𝑖 +𝑏 𝑖 ) •( 𝑎 𝑖 +𝑏 𝑖 -1 𝑎 𝑖
)

if 𝑥 appears in 𝜓 𝑖 in negative form;

0 otherwise.
Algorithm 2 then describes the operation of CNF Proxy, computing Shapley values of 𝜑 according to Lemma 5.2. The input to the algorithm is a CNF formula 𝜑 and the set of endogenous facts 𝐷 n . In Line 1, CNF Proxy counts the number 𝑛 of clauses of 𝜑, and in Line 2 it initializes the contribution of every variable of 𝜑 to zero. Then, it iterates over the clauses (Line 3). For each clause, it counts the number 𝑚 of literals, and identifies the set of positive and negative literals, 𝑝𝑜𝑠 and 𝑛𝑒𝑔 respectively (Lines 4-7). In Lines 9 and 12 we add (resp., subtract) quantities for each variable in a positive (resp., negative) literal according to Lemma 5.2 (note that 𝑚 corresponds to 𝑎 𝑖 + 𝑏 𝑖 as denoted in the lemma). Finally, in Line 15 the algorithm returns the contribution value of each fact 𝑥 ∈ 𝐷 n based on Shapley( 𝜑, 𝑥). Observe that CNF Proxy runs in linear time in the size of 𝜑 (which itself, being the Tseytin transformation of the provenance circuit 𝐶 ′ from Figure 3, is linear in 𝐶 ′ ).

Example 5.3. Recall the queries 𝑞 1 , 𝑞 2 , 𝑞 and their lineages depicted in Figure 1. Using endogenous lineages, we have:

• ELin(𝑞 1 , 𝐷 n , 𝐷 x ) = 𝑎 1 • ELin(𝑞 2 , 𝐷 n , 𝐷 x ) = (𝑎 2 ∧ 𝑎 4 ) ∨ (𝑎 2 ∧ 𝑎 5 ) ∨ (𝑎 3 ∧ 𝑎 4 ) ∨ (𝑎 3 ∧ 𝑎 5 ) ∨ (𝑎 6 ∧ 𝑎 7 ) • ELin(𝑞, 𝐷 n , 𝐷 x ) =𝑎 1 ∨ (𝑎 2 ∧ 𝑎 4 ) ∨ (𝑎 2 ∧ 𝑎 5 ) ∨ (𝑎 3 ∧ 𝑎 4 ) ∨ (𝑎 3 ∧ 𝑎 5 ) ∨ (𝑎 6 ∧ 𝑎 7 )
The lineage of 𝑞 1 is a CNF with a single variable, thus the contribution of 𝑎 1 to 𝑞 1 as computed by Algorithm 2 is 1, which is indeed equal to Shapley(𝑞 1 , 𝐷 n , 𝐷 x , 𝑎 1 ). Applying the Tseytin transformation to the lineage of 𝑞 2 introduces 6 new variables ({𝑧 𝑖 } 6 𝑖=1 ) and results in the following equisatisfiable CNF:

(𝑧 1 ) ∧ (𝑧 1 ∨ 𝑧 2 ) ∧ (𝑧 1 ∨ 𝑧 3 ) ∧ (𝑧 1 ∨ 𝑧 4 ) ∧ (𝑧 1 ∨ 𝑧 5 ) ∧ (𝑧 1 ∨ 𝑧 6 ) ∧ (𝑧 1 ∨ 𝑧 2 ∨ 𝑧 3 ∨ 𝑧 4 ∨ 𝑧 5 ∨ 𝑧 6 ) ∧ (𝑧 2 ∨ 𝑎 2 ) ∧ (𝑧 2 ∨ 𝑎 4 ) ∧ (𝑧 2 ∨ 𝑎 2 ∨ 𝑎 4 ) ∧ (𝑧 3 ∨ 𝑎 2 ) ∧ (𝑧 3 ∨ 𝑎 5 ) ∧ (𝑧 3 ∨ 𝑎 2 ∨ 𝑎 5 ) ∧ (𝑧 4 ∨ 𝑎 3 ) ∧ (𝑧 4 ∨ 𝑎 4 ) ∧ (𝑧 4 ∨ 𝑎 3 ∨ 𝑎 4 ) ∧ (𝑧 5 ∨ 𝑎 3 ) ∧ (𝑥 5 ∨ 𝑎 5 ) ∧ (𝑧 5 ∨ 𝑎 3 ∨ 𝑎 5 ) ∧ (𝑧 6 ∨ 𝑎 6 ) ∧ (𝑧 6 ∨ 𝑎 7 ) ∧ (𝑧 6 ∨ 𝑎 6 ∨ 𝑎 7 )
Algorithm 2 iterates over the above clauses, and computes the contribution of the endogenous facts 𝐷 n over the proxy function. Note that the facts 𝐷 n appear in clauses of two forms. The first form is 𝑧 𝑗 ∨ 𝑎 𝑖 ; appearance in this type of clause adds

1 22•2•( 1 1 ) = 1 44 to the contribution of 𝑎 𝑖 . The second form is 𝑧 𝑗 ∨ 𝑎 𝑖 ∨ 𝑎 ℎ , which adds -1 22•3•( 2 1 ) = -1
132 . Note that each of 𝑎 2 , 𝑎 3 , 𝑎 4 , 𝑎 5 has two appearances in clauses of the first form, and one appearance in clauses of the second form. Thus, according to Algorithm 2 the contribution of 𝑎 2 , 𝑎 3 , 𝑎 4 , 𝑎 5 is 5 132 ≈ 0.038. In contrast, 𝑎 6 and 𝑎 7 each have a single appearance in a clause of the first form and a single appearance in a clause of the second form, thus their contribution is 1 66 ≈ 0.015. We note that the values calculated by Algorithm 2 are very different from the actual Shapley values, as

Shapley(𝑞 2 , 𝐷 n , 𝐷 x , 𝑎 𝑖 ) = 11 60 ≈ 0.183 for 𝑎 𝑖 ∈ {𝑎 2 , 𝑎 3 , 𝑎 4 , 𝑎 5 } and Shapley(𝑞 2 , 𝐷 n , 𝐷 x , 𝑎 𝑖 ) = 2
15 ≈ 0.133 for 𝑎 𝑖 ∈ {𝑎 6 , 𝑎 7 }. However, the facts 𝑎 2 , 𝑎 3 , 𝑎 4 , 𝑎 5 , are correctly determined to be more influential than 𝑎 6 and 𝑎 7 .

Our experimental evaluation indicates that in most cases, the ordering of facts according to the values assigned to them by Algorithm 2 agrees with the order obtained by using the actual Shapley values. There is however no theoretical guarantee that this will always be the case, as shown by the following example.

Example 5.4. Applying the Tseytin transformation over the lineage of 𝑞 will result in a CNF similar to that obtained for 𝑞 2 , with a new variable (𝑧 7 ) and the new clauses (𝑧 1 ∨ 𝑧 7 ) ∧ (𝑧 7 ∨ 𝑎 1 ) ∧ (𝑧 7 ∨ 𝑎 1 ). In addition, the disjunct ∨𝑧 7 will be added to the clause (𝑧 1 ∨ 𝑧 2 ∨ 𝑧 3 ∨ 𝑧 4 ∨ 𝑧 5 ∨ 𝑧 6 ). Similarly to the case of 𝑞 2 , the contributions of 𝑎 2 , 𝑎 3 , 𝑎 4 , and 𝑎 5 are correctly determined to be larger than those of 𝑎 6 and 𝑎 7 . As for 𝑎 1 , its contribution according to Algorithm 2 is 0 while in fact it is the most influential fact.

EXPERIMENTS

Our system is implemented in Python 3.6 and using the PostgreSQL 11.10 database engine, and the experiments were performed on a Linux Debian 14.04 machine with 1TB of RAM and an Intel(R) Xeon(R) Gold 6252 CPU @ 2.10GHz processor. ProvSQL [START_REF] Senellart | Provsql: Provenance and probability management in postgresql[END_REF] was used to capture the provenance. For knowledge compilation we have used the c2d compiler [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF][START_REF] Darwiche | New advances in compiling CNF to decomposable negation normal form[END_REF]. The source code of our implementation is available in [START_REF] Deutch | Shapley for database facts source code[END_REF].

Since no standard benchmark for our problem exists, we have created such a benchmark of 40 queries over the TPC-H (1.4GB) and IMDB (1.2GB) databases.The TPC-H queries are based on the ones in [START_REF]Transaction Processing Performance Council (TPC)[END_REF], where we have only removed nested queries (which ProvSQL does not handle) and aggregation operations (for which provenance is not Boolean). The queries for the IMDB database are based on the join queries in [START_REF] Leis | How good are query optimizers, really?[END_REF], where for each query we have added a (last) projection operation over one of the join attributes to make provenance more complex and thus more challenging for our algorithms. The resulting queries are quite complex: in particular, only 4 out of the 40 are hierarchical. See [START_REF] Deutch | Shapley for database facts source code[END_REF] for details of the obtained queries.

Exact computation

We have evaluated our solution for exact Shapley computation, presented in Section 4.2, on each of the 40 queries. In total, we have obtained 95,803 output tuples along with their provenance expressions (computed with ProvSQL). We have then transformed each provenance expression into a d-DNNF structure using the c2d [START_REF] Darwiche | On the tractable counting of theory models and its application to truth maintenance and belief revision[END_REF][START_REF] Darwiche | New advances in compiling CNF to decomposable negation normal form[END_REF] knowledge compiler. In this experiment, for both the knowledge compilation (KC) and Shapley evaluation steps we have set a timeout of one hour (in fact, as we show below, a much shorter timeout of 2.5 seconds typically suffices). In case the compilation completed successfully within this timeframe, we have computed the Shapley values using Algorithm 1. Table 1 presents the execution times of our solution for 16 representative queries; next we will overview different aspects of the results.

Success rate. We report here the rate of successful executions. The IMDB queries resulted in 95,636 output tuples; the KC step completed successfully for 95,599 out of them, where all 37 failures were the result of insufficient memory. For each of the IMDB output tuples that were successfully compiled into a d-DNNF, we have executed Algorithm 1; only a single execution failed in this step (due to a timeout of one hour). Overall, the exact computation of Shapley values was successful for 95,598 out of the 95,636 IMDB output tuples (i.e., 99.96% success rate). The TPC-H queries resulted in 167 output tuples; the KC step has completed successfully for 141 out of them, again all 26 failures were the result of insufficient memory. For all TPC-H outputs that compiled successfully Algorithm 1 was successful, yielding an overall 84.43% success rate.

Execution time. For each of the 40 queries, we have measured the execution time of each step of the computation. First, we have measured (in the column "Execution time") the execution time in PostgreSQL, which includes provenance generation for every output tuple using ProvSQL. Then, for each tuple t in the output of the query, we have measured the KC execution time and the execution time of Algorithm 1 to compute the contribution of all input facts with respect to the output tuple t. For the latter two algorithms, the execution times varied significantly for the different output tuples, and thus we report the execution times for different percentiles (mean, p25, p50, p75 and p99). Observe that the computation is typically efficient; outliers include q11d for which the execution time of Algorithm 1 was over 96 seconds in average. In contrast, Figure 5b depicts 4 query outputs for which the exact computation failed to complete over the full TPC-H database. We observe that the algorithm does succeed in these cases if we execute the queries over subsets of the input database, though its execution time may still be high: e.g., if we take a "slice" of the lineitem table consisting of 480,097 facts, then computation of the contribution of all input facts w.r.t. "Q9 ALGERIA" takes 556sec.

Inexact computation

As observed above, computing exact Shapley values using our solution for a given output tuple is typically fast, but may be costly or even fail in some cases. In this section we evaluate inexact computation alternatives.

Algorithms. We compare three algorithms: CNF Proxy (Section 5) and two existing baselines: Monte Carlo, and Kernel SHAP.

Monte Carlo. This is a well-known sampling algorithm [START_REF] Mann | Values for large games, IV: Evaluating the Electoral College by Monte Carlo Techniques[END_REF] for approximating Shapley values in general. To employ the Monte Carlo algorithm in our setting, we feed it a provenance expression ℎ containing 𝑛 distinct input facts, and a budget of 𝑟 • 𝑛 samples, for some 𝑟 ∈ Z + . The Shapley value of each fact 𝑓 is approximated by sampling 𝑟 permutations (𝜋 1 , . . . , 𝜋 𝑟 ) of the input facts, and then outputting 1 𝑟 • 𝑟 𝑖=1 ℎ(𝑆 𝜋 𝑖 ,<𝑓 ∪ {𝑓 })ℎ(𝑆 𝜋 𝑖 ,<𝑓 ) , where 𝑆 𝜋 𝑖 ,<𝑓 is the coalition of all facts preceding 𝑓 in the permutation 𝜋 𝑖 .

Kernel SHAP. Lundberg and Lee [START_REF] Scott | A unified approach to interpreting model predictions[END_REF] have defined the notion of SHAP values in the context of ML explainability. Given a function ℎ : R 𝑑 → R (the model whose decisions we want to explain), a probability distribution D on R 𝑑 (the inputs), and an input vector ē ∈ R 𝑑 , SHAP values were defined to measure the contribution of ē's features to the outcome ℎ( ē). To overcome the issue that ℎ does not operate over subsets of features, the notion of SHAP-score has been defined as follows

SHAP(ℎ, ē, 𝑥) def = ∑ 𝑆 ⊆𝑋 \{𝑥 } |𝑆 |!(|𝑋 | -|𝑆 | -1)! |𝑋 |! (ℎ ē (𝑆 ∪{𝑥 })-ℎ ē (𝑆)),
where 𝑋 is the set of 𝑑 features, 𝑥 is a specific feature whose contribution we wish to assess, and ℎ ē : 2 𝑋 → R is defined by

ℎ ē (𝑆) def = E z∼D [ℎ( z) | ē𝑆 = z𝑆 ],
where ē𝑆 and z𝑆 denote the vectors ē and z restricted to the features in 𝑆.

In [START_REF] Scott | A unified approach to interpreting model predictions[END_REF] the authors have proposed a method for approximating SHAP values, called Kernel SHAP. Kernel SHAP assumes feature independence and estimates the probability by multiplying the marginal distributions 𝑖∉𝑆 Pr(𝑧 𝑖 ). The marginal probabilities Pr(𝑧 𝑖 ) in turn are estimated from a background data 𝑇 . To approximate SHAP values, Kernel SHAP then samples 𝑚 coalitions 𝑆 1 , . . . , 𝑆 𝑚 of features, and trains a linear model 𝑔 : 2 𝑋 → R by minimizing the weighted loss 𝑚 𝑖=1 𝑤 𝑖 • (𝑔(𝑆 𝑖 ) -ĥ ē (𝑆 𝑖 )) 2 , where 𝑤 𝑖 is proportional to the size of 𝑆 𝑖 and ĥ ē is the estimation of ℎ ē using the feature independence assumption. The coefficient associated with a feature 𝑥 in the trained model 𝑔 is the approximated SHAP value of 𝑥.

We adapt Kernel SHAP to our setting and use it to approximate the Shapley values of facts, as follows. The features are the input facts of the database, we set ℎ to be the Boolean function representing the (endogenous) provenance; the vector of interest, ē, has the value 1 for all facts, and the background data 𝑇 contains a single example with value 0 in all its entries. Note that for such ē and 𝑇 , Kernel SHAP estimates ℎ ē (𝑆) as the result of applying ℎ to a vector with ones in 𝑆 features and zeros in the remaining entries.

The input of both Monte Carlo and Kernel SHAP includes a budget of 𝑚 samples; for provenance expressions containing 𝑛 distinct facts we have experimented with 𝑚 ∈ {10𝑛, 20𝑛, 30𝑛, 40𝑛, 50𝑛}.

Accuracy metrics To evaluate the performance of the above methods we have used various metrics, specified below. All metrics were computed with respect to the ground truth values obtained by the knowledge compilation approach, and thus these experiments are confined to the cases where the exact computation succeeded.

• nDCG is the normalized discounted cumulative gain score [START_REF] Wang | A theoretical analysis of NDCG ranking measures[END_REF], used to compare the ordering based on the inexact solution to the ordering based on the ground truth. • Precision@k is the number of facts that appears in the top-𝑘 of both the inexact and exact solutions, divided by 𝑘. This was evaluated for 𝑘 ∈ {1, 3, 5, 10}. • L1 and L2 are the mean absolute error and squared error, respectively, of the results of an inexact computation method with respect to the ground truth (i.e. how different the results are from the actual Shapley values).

Execution time. Figure 6a depicts the execution time of the above methods as a function of the sampling budget. The execution times of Monte Carlo and Kernel SHAP are rather similar, while the CNF Proxy method (which does not rely on sampling) is substantially faster, with a median of 0.72 milliseconds and a mean of 2.06 milliseconds for a single query output. Figures 7a and7b depict the distribution and worst-case running times of the three methods (for Monte Carlo and Kernel SHAP we used a budget of 20 samples per fact) as function of the number of distinct facts in the provenance expressions. CNF Proxy is substantially faster than its competitors: in most cases CNF Proxy completes in few milliseconds and 4 seconds in the worst case, whereas Monte Carlo and Kernel SHAP median execution time for circuits with 101-200 distinct input facts are 59 and 62 seconds respectively and may take up to 1,539 seconds.

Recall our analysis of the execution time of the exact solution in Section 6.1. The computation of Shapley values (KC plus Algorithm 1) takes 27,600 seconds if performed for all output tuples of query q8d in the IMDB dataset; for comparison, the CNF Proxy method has (inexactly, see quality analysis below) computed the Shapley value of the proxy functions for all query outputs within 95 seconds, which is 0.3% of the exact computation time. Surprisingly, the execution time of the exact computation was comparable to Monte Carlo and Kernel SHAP, and even faster for large sampling budgets; For example, Kernel SHAP with 𝑚 = 10𝑛 (where 𝑛 is the number of distinct facts in the provenance) has completed computation for all output tuples of the query q8d in 16,447 seconds, which is 59% of the exact computation time. For 𝑚 = 50𝑛, Kernel SHAP required 58,161 seconds for completion of this computation, which is 210% of the exact computation time. This means that using such a sampling budget for Kernel SHAP is impractical in this setting, and we will use it to obtain upper bounds on Kernel SHAP's quality. Quality analysis. Figures 6b and6c depict the ranking quality of the above methods as a function of the sampling budget. The rankings were compared for output tuples where the exact computation succeeded, so we have the ground truth. Recall that CNF Proxy does not rely on sampling, and so it remains constant throughout the different budgets. Naturally, as the sampling budget grows, Monte Carlo and Kernel SHAP quality improves. Most notable is Monte Carlo improvement in terms of nDCG (Figure 6b), where its median (resp., mean) nDCG with budget of 10 samples per fact is 0.9669 (resp., 0.9435), while with budget of 50 samples per fact it is 1.0 (resp., 0.9923). Comparison between the two sampling methods (Monte Carlo and Kernel SHAP) reveals that Kernel SHAP is superior w.r.t all metrics, across the entire budgets range. In terms of nDCG, all methods achieve rather high scores, but CNF Proxy performs best. Indeed, the median (resp., mean) nDCG of CNF Proxy is 1.0 (resp., 0.9989), while Kernel SHAP requires 50 samples per fact to get a median (resp., mean) nDCG of 1.0 (resp., 0.9986); as previously noted such budget leads to slower execution than that of the exact computation. It is worth mentioning that also when looking at nDCG@k for 𝑘 ∈ {1, 3, 5, 10}, CNF Proxy performs better than Monte Carlo and Kernel SHAP, even when allowing a budget of 50 samples per fact. In terms of identifying the top influential facts (i.e., Precision@k), CNF Proxy also outperforms the other methods. For example, CNF Proxy's median (resp., mean) Precision@10 are 1.0 (resp., 0.9688), while Kernel SHAP reaches 1.0 (resp., 0.9611) with 50 samples per fact. Similarly, CNF Proxy outperforms Monte Carlo and Kernel SHAP in terms of Precision@k for 𝑘 ∈ {1, 3, 5}.

Finally, Table 2 zooms in on the results when fixing the budgets of Monte Carlo and Kernel SHAP to 50 samples per fact, which is the highest budget tested (already for this budget, computation of Monte Carlo and Kernel SHAP is slower than for the exact algorithm). Note that CNF Proxy is much faster then the other methods, while still being superior in terms of ranking (nDCG and Precision@k). As explained above, ranking of facts is indeed the use case we recommend for CNF Proxy. Unsurprisingly, Kernel SHAP achieves better distance from the exact Shapley values (L1 and L2), at the cost of being slower by several orders of magnitude.

Dependency on the provenance size. Figure 7 depicts the performance of Monte Carlo, Kernel SHAP, and CNF Proxy as a function of the number of facts in the provenance expression. The results are aggregated over all output tuples of all queries. Figure 7c presents the quality of facts ranking (nDCG) as a function of the number of distinct provenance facts. CNF Proxy performs the best, and its quality remains steady regardless of the number of facts in the provenance expression. For example, with 1-10 facts the CNF Proxy median (resp., mean) nDCG is 1.0 (resp., 0.9999), and with 201-400 facts it is 0.9977 (resp., 0.9924). Kernel SHAP has a minor deterioration, where it drops from median (resp., mean) nDCG of 1.0 (resp., 0.9998) with 1-10 facts to 0.9906 (resp., 0.9888) with 201-400 facts. Figure 7d zooms in on the aggregated results over the worst case expressions of all output tuples for all queries, and shows that even the worst case CNF Proxy is superior to the alternatives, and that the error in terms of nDCG is small (0.92 in the worst case evaluated). Figure 7e depicts the dependency of Precision@10 on the number of provenance facts. Both Monte Carlo and Kernel SHAP suffer from a massive drop of median (resp., mean) Precision@10, down to 0.4 (resp., 0.476) and 0.6 (resp., 0.6253) respectively with 201-400 facts, while CNF Proxy remains at 0.8 (resp., 0.8293) median and mean Precision@10. A similar trend is observed for Precision@5, whereas for Precision@3 and Precision@1 the drop is less significant. Here again, Figure 7f zooms in on the worst case and again shows the superiority of CNF Proxy.

Hybrid computation

Recall that in Section 6.1 we have measured the success rate of the exact computation: for IMDB the success rate was 99.96% and for TPC-H the success rate was 84.43%. We saw in Section 6.2 that the inexact method CNF Proxy is very efficient and that the ranking of tuples based on CNF Proxy is typically close to the ranking obtained based on the real Shapley values.

In this section we consider a hybrid approach that works as follows. First, we start by running the exact computation, that is, the knowledge compilation step and Algorithm 1. If the exact computation completes successfully within less than 𝑡 seconds (where 𝑡 is configurable) we return its result. Otherwise, we terminate the exact computation and execute the inexact method CNF Proxy, returning only a ranking of input tuples rather than their Shapley values. Figure 8a depicts the success rate of the exact computation given different timeouts. Note that given a timeout of 2.5 seconds, the exact computation succeed for 98.67% of the IMDB output tuples, and 83.83% for TPCH-H. Increasing the timeout has a rather minor impact on the success rate: having a 15 seconds timeout increases the success rate for IMDB to 99.52%, while the success rate for TPC-H remains unchanged. Recall that having a timeout of one hour results in success rates of 99.96% and 84.43% for IMDB and TPC-H respectively. Figure 8b depicts the mean execution time of the hybrid approach as a function of the chosen timeout 𝑡. Observe that given a timeout of 2.5 seconds the mean hybrid execution time is 0.31 seconds and 0.67 seconds for IMDB and TPC-H respectively. The mean execution time of the hybrid approach grows very moderately w.r.t. the timeout for IMDB (since most cases do not reach the timeout); it grows faster for TPC-H, where the difficult cases for which timeout is reached have a more significant effect on the overall mean execution time.

Main conclusions. Our experimental results indicate that for most output tuples (98.67% for IMDB and 83.83% for TPC-H) exact computation of Shapley values terminates within 2.5 seconds. When it does not, we propose an alternative of ranking facts according to CNF Proxy values, which typically only takes several milliseconds (up to 4 seconds for an outlier case). Experimental evidence shows that the ranking obtained via CNF Proxy is both much faster to compute and more accurate (in terms of nDCG and Precision@k, measured in cases where exact computation does succeed, and so we have the ground truth) than the alternative of only using sampling to approximate the actual Shapley values.

CONCLUSION

We have proposed in this paper a first practical framework for computing the contributions of database facts in query answering, quantified through Shapley values. The framework includes an exact algorithm that computes the contribution of input facts, and a faster algorithm that is practically effective in ranking contributions of input facts, while producing inexact Shapley values. Our practical implementation is currently designed for SPJU queries (that is, to the class of queries supported by ProvSQL). In addition to these practical contributions, we have also established a theoretical connection between the problem of computing Shapley values and that of probabilistic query evaluation, by showing that, for every query, the former can be reduced in polynomial time to the latter.

We leave it open to determine whether there is also a reduction in the other direction (Open Problem 1). Other interesting directions would be to study further constructs such as aggregates and negation, or to extend the framework to bag semantics. Concerning bag semantics we observe that, by differentiating each copy of a same tuple in a bag database (for instance, adding an identifier attribute), our framework can be used as-is. Nevertheless, it would be interesting to see how one could adapt the definitions in order to consider fact multiplicities in a more elaborate way.

Proposition 3 . 1 .

 31 For every Boolean query 𝑞, we have that Shapley(𝑞) ≤ p T PQE(𝑞).

1 .

 1 Proof of Proposition 3.1. For a Boolean query 𝑞, database 𝐷 = 𝐷 x ∪ 𝐷 n , and integer 𝑘 ∈ {0, . . . , |𝐷 n |}, define #Slices(𝑞, 𝐷 x , 𝐷 n , 𝑘) def = |{𝐸 ⊆ 𝐷 n | |𝐸| = 𝑘 and 𝑞(𝐷 x ∪ 𝐸) = 1}|.

Figure 2 :

 2 Figure 2: Deterministic and decomposable circuit for ELin(𝑞, 𝐷 x , 𝐷 n ) from the running example.

Proposition 4 . 4 .

 44 Given as input a deterministic and decomposable circuit 𝐶 representing ELin(𝑞, 𝐷 n , 𝐷 x ) for a database 𝐷 = 𝐷 x ∪ 𝐷 n and Boolean query 𝑞, and an endogenous fact 𝑓 ∈ 𝐷 n , we can compute in polynomial time (in |𝐶 |) the value Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑓 ).Next, we prove Proposition 4.4 and present the algorithm, and then explain in Section 4.2 the architecture of the implementation.

Lemma 4 . 5 .

 45 Given as input a deterministic and decomposable Boolean circuit 𝐶 and an integer 𝑘 ∈ {0, . . . , |Vars(𝐶)|}, we can compute in polynomial time the quantity #SAT 𝑘 (𝐶). Proof. Our proof is similar to that of [3, Section 3.2]. Let 𝑋 def = Vars(𝐶) and 𝑛 def = |𝑋 |.

  We now explain how to compute the first term, that is, |(SAT(𝜑 𝑔 1 ) ⊗ 2 𝑆 1 ) ∩ {𝜈 ⊆ Vars(𝑔) | |𝜈 | = ℓ }|; the second term is similar. This is equal3 to min(ℓ, |Vars(𝑔 1 ) |)

  4. □ Algorithm. Algorithm 1 depicts the solution underlying Proposition 4.4. The subroutine ComputeAll#SAT 𝑘 takes as input a d-D circuit 𝐶 and outputs all the values #SAT 0 (𝐶), . . . , #SAT |Vars(𝐶) | (𝐶).

Algorithm 2 : 4 L 5 𝑚 ← |L|; 6 𝑝𝑜𝑠 7 𝑛𝑒𝑔 8 for ℓ ∈ 𝑝𝑜𝑠 ∩ 𝐷 n do 9 𝑣

 2456789 CNF ProxyInput : CNF 𝜑 and a set of endogenous facts 𝐷 n . Output : The value Shapley( 𝜑, 𝑥) for each 𝑥 ∈ 𝐷 n .1 𝑛 ← |𝜑.𝑐𝑙𝑎𝑢𝑠𝑒𝑠 ()|; 2 𝑣 ← 0 |𝐷 n | ;// As an array3 for 𝜓 ∈ 𝜑.𝑐𝑙𝑎𝑢𝑠𝑒𝑠 () do ← 𝜓 .𝑙𝑖𝑡𝑒𝑟𝑎𝑙𝑠 (); ← {ℓ ∈ L | ℓ is positive}; ← {ℓ ∈ L | ℓ is negative}; [ℓ.𝑣𝑎𝑟 ()] ← 𝑣 [ℓ.𝑣𝑎𝑟 (𝑛𝑒𝑔 ∩ 𝐷 n do 12 𝑣 [ℓ.𝑣𝑎𝑟 ()] ← 𝑣 [ℓ.𝑣𝑎𝑟 ()] -Now, note that for a CNF formula 𝜑 = 𝑛 𝑖=1 𝜓 𝑖 (where each 𝜓 𝑖 is a disjunction of literals) and an assignment 𝜈 it holds that 𝜑 (𝜈) = 𝑛 𝑖=1 𝜓 𝑖 (𝜈). Instead of calculating the Shapley values of a CNF formula 𝜑 (which may be a hard problem), CNF Proxy computes Shapley values with respect to a proxy function, denoted 𝜑. The proxy function of 𝜑 is defined as the sum (instead of the product) of the clauses of 𝜑, i.e., 𝜑 (𝜈)

Figure 3 :

 3 Figure 3: Our implementation architecture.

Figure 4

 4 depicts the running time of the KC step and of the computation of Shapley values from the d-DNNF as a function of different features of the provenance, such as the number of facts appearing in the provenance, the number of clauses in its CNF representation, and the number of gates in its d-DNNF representation. Scalability. To evaluate the scalability of Algorithm 1 we have further looked at different scales of the TPC-H database.

  Figure

5

 5

Figure 4 :

 4 Figure 4: Running times of knowledge compilation and computation of Shapley values from the d-DNNF as function of the number of distinct facts, CNF clauses, and d-DNNF size

Figure 5a depicts 4

 4 representative query outputs, for which the running time takes a few milliseconds, e.g., for "Q3 23426" (result 23426 of query 𝑄3) and the full TPC-H dataset, the computation of Shapley values for all relevant input facts complete in 4.3ms.

  (a) Representative outputs (b) "Difficult" outputs

Figure 5 :

 5 Figure 5: Alg. 1 running time for various TPC-H query outputs as function of table lineitem size

Figure 6 :

 6 Figure 6: Comparing various metrics for inexact methods as a function of the sampling budget; CNF Proxy does not rely on sampling, thus remains constant for all budgets.

  (a) Running time distribution (b) Worst case running time (c) nDCG Distribution (d) Worst case nDCG (e) Precision@10 distribution (f) Worst case Precision@10

Figure 7 :

 7 Figure 7: Comparing inexact methods as a function the number of distinct facts in the provenance (𝑛). Sampling methods (Kernel SHAP and Monte Carlo) presented with sampling budget of 𝑚 = 20𝑛; different budgets led to similar trends.

  (a) Exact computation success rate as function of the computation timeout (b) Mean execution time of the hybrid approach as a function of the computation timeout

Figure 8 :

 8 Figure 8: Hybrid approach performance

  3 , 𝑎 6 , 𝑎 8 }, {𝑎 2 , 𝑎 3 , 𝑎 7 , 𝑎 8 }, {𝑎 4 , 𝑎 5 , 𝑎 6 , 𝑎 8 }, and {𝑎 4 , 𝑎 5 , 𝑎 7 , 𝑎 8 }, and overall 14 triplets (left to the reader). Summing it all up results in

  𝐷 n , 𝐷 x , 𝑎 𝑖 ) = 23 210 ≈ 0.1095, and that for 𝑎 𝑖 ∈ {𝑎 6 , 𝑎 7 } we have Shapley(𝑞, 𝐷 n , 𝐷 x , 𝑎 𝑖 ) = 8 105 ≈ 0.0762.

			≈ 0.4095.
			105
	Similarly one can compute the Shapley value of the remaining facts,
	and find that for 𝑎 𝑖	∈	{𝑎 2 , 𝑎 3 , 𝑎 4 , 𝑎 5 } it holds that
	Shapley(𝑞,

  #P -hard). It turns out that the tractability criterion that

							𝑎 6
						LAX	MUC
	Flights (endo)		Airports (exo)				𝑎
									7
	Src	Dest		Name Country
	𝑎 1 𝑎 2 EWR JFK	CDG LHR	𝑏 1 𝑏 2 EWR JFK	USA USA	BOS	3 𝑎	𝑎 8	𝑎 5	ORY
	𝑎 3 BOS	LHR	𝑏 3	BOS	USA		LHR
	𝑎 4 LHR	CDG	𝑏 4	LAX	USA		𝑎 2
	𝑎 5 LHR	ORY	𝑏 5	LHR	EN	EWR			𝑎 4
	𝑎 6 LAX	MUC	𝑏 6 MUC	GR
	𝑎 7 MUC	ORY	𝑏 7	ORY	FR		𝑎 1
						JFK				CDG
	𝑎 8 LHR	MUC	𝑏 8	CDG	FR
						(b) Flights in graph view. Dark
	(a) Database of flights and airports		and light gray depict "USA"
						and "FR" airports respectively

  For a gate 𝑔 of 𝐶, we denote by Vars(𝑔) the set of variables that have a directed path to 𝑔. An ∧-gate 𝑔 of 𝐶 is decomposable if for every two input gates 𝑔 1 ≠ 𝑔 2 of 𝑔 we have Vars(𝑔 1 ) ∩ Vars(𝑔 2 ) = ∅. We call 𝐶 decomposable if all ∧-gates are. An ∨-gate 𝑔 of 𝐶 is deterministic if the Boolean functions captured by each pair of distinct input gates of 𝑔 are pairwise disjoint; i.e., no assignment satisfies both. We call 𝐶 deterministic if all ∨-gates in it are. A deterministic and decomposable (d-D [26]) Boolean circuit is a Boolean circuit that is both deterministic and decomposable. If 𝐶 is a Boolean circuit we write Vars(𝐶) to denote the set of variables that appear in it. Example 4.3. Recall ELin(𝑞, 𝐷 n , 𝐷 x ) from Example (4.2) represented as a DNF. Figure 2 depicts a d-D circuit for ELin(𝑞, 𝐷 n , 𝐷 x ).

=

  𝜈 2 ∈ 𝑆 2 }. We next show how to compute the values 𝛼 ℓ 𝑔 by bottom-up induction on 𝐶. Variable gate. If 𝑔 is a variable gate corresponding to some variable 𝑦, then Vars(𝑔) = {𝑦}. Then, 𝛼 0 𝑔 is 0 and 𝛼 1 𝑔 is 1. ¬-gate. If 𝑔 is a ¬-gate with input gate 𝑔 ′ , then 𝛼 ℓ 𝑔 = Deterministic ∨-gate. If 𝑔 is a deterministic ∨-gate with no input then 𝜑 𝑔 is the Boolean function on variables Vars(𝑔) = ∅ that is always false, hence 𝛼 0 𝑔 = 0. Otherwise 𝑔 has exactly two input gates; let us denote them 𝑔 1 and 𝑔 2 . Observe that Vars(𝑔) = Vars(𝑔 1 ) ∪ Vars(𝑔 2 ) by definition. De-Vars(𝑔 2 ) \Vars(𝑔 1 ) and similarly 𝑆 2 def = Vars(𝑔 1 ) \ Vars(𝑔 2 ). Since 𝑔 is deterministic, we have:

		|Vars(𝑔) | 𝑙	-
	𝛼 ℓ
	𝑔 fine 𝑆 1	def

′ for every ℓ ∈ {0, . . . , |Vars(𝑔)|}.

Algorithm 1 :

 1 Shapley values from deterministic and decomposable Boolean circuits Input : Deterministic and decomposable Boolean circuit 𝐶 with output gate 𝑔 output representing ELin(𝑞, 𝐷 x , 𝐷 n ) and an endogenous fact 𝑓 ∈ 𝐷 n . Output : The value Shapley(𝑞, 𝐷 x , 𝐷 n , 𝑓 ). Complete 𝐶 so that Vars(𝑔 output ) = 𝐷 n ; 2 Compute 𝐶 1 = 𝐶 [𝑓 → 1] and 𝐶 2 = 𝐶 [𝑓 → 0]; // Partial evaluations of 𝐶 by setting 𝑓 to 1 and to 0 ∈ {0, . . . , |Vars(𝑔)|} by bottom-up induction on 𝐶 using the inductive relations from the proof of Lemma 4.5;

	3 Γ = ComputeAll#SAT 𝑘 (𝐶 1 );	// As an array
	4 Δ = ComputeAll#SAT 𝑘 (𝐶 2 );	// As an array
			|𝐷 n |-1
	5 return	∑
	10	return [𝛼 0 𝑔 output , . . . , 𝛼	|Vars(𝐶) | 𝑔 output	];

1 𝑘=0 𝑘! (|𝐷 n | -𝑘 -1)! |𝐷 n |! • (Γ [𝑘] -Δ[𝑘]); 6 Def ComputeAll#SAT 𝑘 (C):

7

Preprocess 𝐶 so that each ∨-gate and ∧-gate has fan-in exactly 0 or 2; 8 Compute the set Vars(𝑔) for every gate 𝑔 in 𝐶; 9 Compute values 𝛼 ℓ 𝑔 for every gate 𝑔 in 𝐶 and ℓ

  2. Let ℎ = 𝑛 𝑖=1 1 𝑛 𝜓 𝑖 , where each 𝜓 𝑖 is a Boolean function representing a disjunction of literals. Without loss of generality let us assume that for each 𝜓 𝑖 there is no variable that appears in more than one literal of 𝜓 𝑖 . Denote by 𝑎 𝑖 and 𝑏 𝑖 the number of positive and negative literals in 𝜓 𝑖 respectively. Then, for every variable 𝑥, it holds Shapley(𝑞[ x/t], 𝐷 x , 𝐷 n , 𝑓 ) The Shapley value Algorithm 1 d-DNNF 𝐶 ′′′ for ELin(𝑞[ x/t], 𝐷 x , 𝐷 n )

				Lemma 4.6	d-DNNF 𝐶 ′′ (w/ extra vars)
			(w/o extra vars)			equivalent to 𝜑
						Knowledge
							compiler
	Database 𝐷 = 𝐷 x ∪ 𝐷 n		Partial eval: set			Tseytin
	Query 𝑞( x) Fact 𝑓 ∈ 𝐷 n Answer t ProvSQL	for Lin(𝑞[ x/t], 𝐷) Boolean circuit 𝐶	exo vars to 1	ELin(𝑞[ x/t], 𝐷 x , 𝐷 n ) Bool. circuit 𝐶 ′ for	transform	CNF formula 𝜑 (w/ extra vars) Proxy
							formula
	Input		The value Shapley( 𝜑, 𝑓 )	Algorithm 2	𝜑 (w/ extra vars)
			(heuristics)

Table 1 :

 1 Statistics on the exact computation of Shapley values for 16 representative queries

			#Joined	#Filter	Execution	#Output	Success	KC execution times [sec]			Alg. 1 execution times [sec]
	Dataset Query
			tables	conditions	time [sec]	tuples	rate	Mean p25 p50 p75	p99	Mean	p25	p50	p75	p99
		3	3	5	20980.71	100	100%	0.06	0.04 0.07 0.08	0.13	0.00	0.00	0.00	0.00	0.01
		5	6	9	48.67	5	0%	-	-	-	-	-	-	-	-	-	-
	TPC-H	7 10 11	6 4 6	8 6 7	30.57 4.72 0.13	4 10 10	0% 100% 100%	-0.14 0.09	-0.13 0.13 0.14 --0.08 0.08 0.08	-0.19 0.13	-0.01 0.01	-0.01 0.00	-0.01 0.00	-0.01 0.01	-0.01 0.03
		16	3	5	1.25	10	100%	0.26	0.13 0.18 0.33	0.57	0.18	0.01	0.03	0.29	0.88
		18	4	3	37.31	10	100%	0.13	0.08 0.08 0.18	0.23	0.01	0.00	0.01	0.01	0.03
		19	2	21	2.04	1	100%	1.20	1.20 1.20 1.20	1.20	156.06 156.06 156.06 156.06	156.06
		1a	5	10	0.25	35	100%	0.17	0.08 0.08 0.13	2.10	5.92	0.01	0.01	0.01	206.72
		6b	5	8	2.61	1	100%	0.44	0.44 0.44 0.44	0.44	0.08	0.08	0.08	0.08	0.08
		7c	8	21	77.33	2415	99%	0.82	0.18 0.28 0.63	9.44	24.28	0.02	0.05	0.39	787.12
	IMDB	8d 11a	7 8	10 18	145.10 3.20	44517 10	99.9% 100%	0.26 0.75	0.13 0.18 0.29 0.18 0.48 1.14	1.09 2.15	0.36 23.34	0.01 0.01	0.02 0.13	0.05 1.27	2.28 151.99
		11d	8	16	56.99	210	98.1%	0.99	0.19 0.32 0.78	5.97	96.19	0.02	0.06	0.48	1650.72
		13c	9	19	2.44	14	100%	0.22	0.13 0.18 0.28	0.53	0.02	0.01	0.01	0.01	0.06
		15d	9	18	24.25	207	97.6%	1.89	0.24 0.48 1.28 10.01	70.05	0.06	0.30	3.52	1821.13
		16a	8	15	5.56	173	100%	0.18	0.13 0.14 0.20	0.53	0.02	0.01	0.01	0.02	0.12

Table 2 :

 2 Median (resp., mean) performance. Monte Carlo and Kernel SHAP use 50 • #facts samples

		Monte Carlo Kernel SHAP	CNF Proxy
	Execution time 0.079 (1.875)	0.127 (1.978) 7e-4 (0.002)
	L1	0.439 (0.448) 0.110 (0.109) 0.317 (0.315)
	L2	0.03 (0.034)	0.001 (0.002) 0.010 (0.014)
	nDCG	1.0 (0.992)	1.0 (0.998)	1.0 (0.999)
	Precision@5	1.0 (0.955)	1.0 (0.961)	1.0 (0.989)
	Precision@10	1.0 (0.953)	1.0 (0.961)	1.0 (0.968)

This notion of safety is distinct from the "usual" notion of query safety[START_REF] Abiteboul | Foundations of Databases[END_REF] that ensures domain independence.

This comes from the fact that, for disjoint 𝑋 1 , 𝑋 2 and assignments 𝜈 1 of 𝑋 1 and 𝜈 2 of 𝑋 2 we have |𝜈 1 ∪ 𝜈 2 | = |𝜈 1 | + |𝜈 2 |, and Vars(𝜑 𝑔 1 ) and 𝑆 1 are disjoint.

This additional NNF restriction is not important here, but, as far as we know, no knowledge compiler has the more general "deterministic and decomposable circuits" (without NNF) as a target. It is currently unknown whether d-DNNFs and deterministic and decomposable circuits are exponentially separated or not[START_REF] Darwiche | A knowledge compilation map[END_REF] Table 7].

ACKNOWLEDGMENTS

This research has been partially funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 804302). The work of Benny Kimelfeld was supported by the Israel Science Foundation (ISF), Grant 768/19, and the German Research Foundation (DFG) Project 412400621 (DIP program).