Representation, Provenance, and Explanations in Database Theory and Logic

In this talk, I will present our recent work that develops a framework for synthetic data generation that is both differentially-private and fair, where fairness is modeled by an adaptation of the causal definition for justifiable fairness.

SHAP scores are expressions designed to capture the contribution of a feature to the output of a machine learning model. They are grounded in the well-studied game-theoretical notion of Shapley values. In this discussion, I will elucidate the meaning of these SHAP scores expressions and explain how they are obtained from first principles. Subsequently, I will delve into the examination of the problem of computing SHAP scores over machine learning models. I will provide insights into when and why this problem becomes computationally intractable. Additionally, I will identify a large and practically relevant class of models for which the problem can be solved in polynomial time. Finally, I will show that even for slight extensions of this class, the computation of SHAP scores is not only intractable but also does not admit a Fully Polynomial Randomized Approximation Scheme (FPRAS).

The talk is based on the cited ICALP’23 paper. It will be about factorized databases for multi-way join queries, or, in other words, succinct representations of all homomorphisms between two structures A and B. The main result is a characterisation of (bounded-arity) structures A where this is efficiently doable. In the talk I will mainly focus on lower bounds for factorized representations.

The presentation is about recent research on the Shap Scores in Explainable Machine Learning. More specifically, on the basis of the tractability result for Shap [1] for open-box classifiers defined by a class of Boolean circuits (actually, d-DBCs), we show how Shap can be computed much more efficiently than through the sheer use of the classifier’s input/output relation when a Binary Neural Network classifier is, first, represented by means of a compact CNF formula, which is, next, (knowledge) compiled into an SDD, followed by a transformation into a d-DBC [2].

Querying trees via Tree automata presents a lot of interest because several important questions can be executed with a guaranteed efficient time. Over the last decades, different approaches have been presented to solve major query answering questions such as enumeration, probabilistic evaluation… In this survey, we review a particular approach which can be adapted to all these questions: a knowledge compilation approach. We present the different results that can be resolved by this approach and also its limits.

In this talk, we will review two algorithms to construct tractable circuits from a conjunctive query and a database whose size can be bounded using fractional hypertree width. The first one is a classical bottom up dynamic programming on a join tree of the conjunctive query, which can be seen as a generalization of Yannakakis approach. The second one is based on a top-down approach akin to exhaustive DPLL, an algorithm originally devised for solving #SAT. We will show that both algorithms construct very similar circuits on conjunctive queries but that DPLL can be applied to a more general setting without changing much of its structure.

What is a minimal set of tuples to delete from a database in order to eliminate all query answers? This problem is called “the resilience of a query” and is one of the key algorithmic problems underlying various forms of reverse data management, such as view maintenance, deletion propagation and causal responsibility. A long-open question is determining the conjunctive queries (CQs) for which resilience can be solved in PTIME.

We shed new light on this problem by proposing a unified Integer Linear Programming (ILP) formulation. It is unified in that it can solve both previously studied restrictions (e.g., self-join-free CQs under set semantics that allow a PTIME solution) and new cases (all CQs under set or bag semantics). It is also unified in that all queries and all database instances are treated with the same approach, yet the algorithm is guaranteed to terminate in PTIME for all known PTIME cases. In particular, we prove that for all known easy cases, the optimal solution to our ILP is identical to a simpler Linear Programming (LP) relaxation, which implies that standard ILP solvers return the optimal solution to the original ILP in PTIME.

In broader terms, we believe that using one single algorithm that can solve all queries (easy and hard) and then proving that it terminates in PTIME for the subset of PTIME queries will become a conventional and unified approach for attacking several other open problems in reverse data management.

Graph explainability is a critical aspect in understanding and interpreting complex relationships within graph-structured data. The need for transparent and interpretable models has led to the exploration of various methodologies, with a focus on providing insights into the contribution of individual nodes or edges in a graph. Shapley values, inspired by cooperative game theory, offer a principled approach to attribute values to each node, reflecting their marginal contributions to different coalitions. Myerson value further refines this concept by considering the externalities of a coalition, providing a more comprehensive understanding of node importance. In the context of graph explainability, Hamiache and Navarro score introduces a novel perspective by evaluating the relevance of nodes based on the information flow and connectivity patterns, offering a nuanced interpretation of their impact on the overall graph structure. Together, these approaches contribute to the development of explainable graph models, enabling stakeholders to gain deeper insights into the dynamics and significance of individual elements within complex graph data.

In this talk I will introduce to the audience lessons learned from my work and other group’s work on building systems for capturing and managing provenance and explanations. For instance, an underappreciated concept in developing such systems is that provenance creates a separate information flow in the system that does not conform to the standard way of how data flows through the operators of a query.

The talk will describe recent results on the fine-grained complexity of database queries that involve joins, grouping, aggregation, and ordering. For some common aggregate functions (e.g., min, max, count, sum), such a query can be phrased as an ordinary conjunctive query over a database annotated with a suitable commutative semiring. I will discuss the ability to evaluate such queries by constructing, in quasilinear time in the database size (i.e., roughly the time it takes to read the database), a data structure that provides logarithmic-time direct access to the answers, ordered by a desired lexicographic order. This task is nontrivial since the number of answers might be larger than quasilinear in the database size, so, the data structure needs to provide a representation that is compact, easy to construct, and fast to access. The results provide classifications of queries, orderings, and semirings by the feasibility of such complexity guarantees.

We consider two situations where we wish to quantify the responsibility of individual database tuples to the outcome. The first is query answering, where we wish to provide an explanation as to why we obtained a specific answer. The second is database inconsistency, where the goal is to identify the most problematic tuples. Some tuples may contribute more than others to the outcome, which can be a bit in the case of a Boolean query, a tuple or a number for conjunctive and aggregate queries, respectively, or a number indicating how inconsistent the database is (i.e., an inconsistency measure). To quantify the contribution of tuples, we use the well-known Shapley value that was introduced in cooperative game theory in the 1950s and has found applications in a plethora of domains. We investigate the applicability of the Shapley value in the two settings, as well as the computational aspects of its calculation in terms of complexity, algorithms, and approximation.

Consider the non-stratified, recursive query Q: win(X) :- move(X,Y), not win(Y).
Its 2-valued reading states that a position x in a two-player game is won if there exists a move to a position y that is lost (not won). If the move graph contains cycles, drawn positions may occur (neither player can force a win). It is well known that the 3-valued well-founded semantics can be used to solve games: win(x) is true, false, and undefined, respectively, iff x is won, lost, or drawn.
The query Q has been used in logic programming (e.g., to illustrate the well-founded semantics [3], in database theory (e.g., to show that stratified Datalog is strictly less expressive than the class of Fixpoint queries [2], and in formal argumentation (as a meta-interpreter for abstract argumentation frameworks).
Solved game graphs can be said to “explain themselves” (or contain their own provenance “for free”): The provenance of a won, lost, or drawn position is easily obtained via an RPQ-definable subgraph of the solved (labeled) game graph in which positions and moves have an associated value (won, lost, or drawn for positions, and winning, delaying, drawing, or blundering for moves, respectively). Since Q is a syntactic variant of Dung’s meta-interpreter for abstract argument frameworks AF [4], the provenance structure available in solved game graphs can be used to explain and justify the grounded (i.e., well-founded) extensions of AF. Another application of game provenance are query evaluation games: The n-ary version of Q can be understood as a normal form for Fixpoint, i.e., all Fixpoint queries can be rewritten into a game normal form, even when restricted to draw-free games [5]. For the subclass of FO queries (First-Order queries expressed in Datalog syntax), this normal form has been used to derive an elegant and powerful provenance representation that unifies how-provenance and why-not provenance [6].

It has been known essentially since the introduction of conjunctive queries that self-joins have an impact on the evaluation of join queries. While in settings like answering Boolean queries and counting their complexity implications are completely understood, the situation is far less clear for other query answering tasks. In this talk, I will present some recent progress for enumeration (Carmeli and Segoufin 2023) and direct access (Bringmann, Carmeli, and Mengel 2023) showing that, even though these settings are often conceptually very close, self-joins behave very differently for them.

Dalvi and Suciu established a dichotomy for probabilistic query evaluation (PQE) over tuple-independent databases, for unions of conjunctive queries (UCQs): for each UCQ, the problem is either solvable in PTIME, or is #P-hard. The UCQs for which the problem is in PTIME are called *safe*. Dalvi and Suciu’s algorithm on such a safe query relies essentially on the following three probabilistic rules: Independence, Negation, and Inclusion-Exclusion. In parallel, another method to obtain PTIME algorithms for PQE is through *knowledge compilation*: one first compiles the provenance of a query Q on a TID D as a Boolean circuit or diagram from the field of knowledge compilation (e.g., OBDDs, FBDDs, d-DNNFs, etc), and then uses this circuit to compute the probability. At a high-level, this type of algorithm makes use of the following three probabilistic rules: Independence, Negation, and *Disjoint union* (instead of inclusion-exclusion). This naturally leads to the following question, called the intensional-extensional problem: letting Q be a safe UCQ, can the tractability of PQE(Q) be captured with the knowledge compilation approach?

In this talk I will talk about this problem, present a technique that allowed to handle a specific class of UCQs, and discuss our ongoing work on the problem. In particular, I will present a neat combinatorial conjecture, that we named the “non-cancelling intersections” conjecture, that talks only about sets and the so-called Möbius function (i.e., no databases, no queries, no complexity). This talk is based on ongoing work with Antoine Amarilli, Louis Jachiet, and Dan Suciu.

While the definition of semiring provenance is uncontroversial for unions of conjunctive queries, the picture is less clear for Datalog. Indeed, the original definition might include infinite computations and is not consistent with other proposals for Datalog semantics over annotated data. In this work, we propose and investigate several provenance semantics, based on different approaches for defining classical Datalog semantics. We study the relationship between these semantics, and introduce properties that allow us to analyze and compare them.

Datalog is a successful query language that extends relational calculus by recursion, has an elegant declarative semantics as well as a simple operational semantics, and admits several powerful optimizations such as semi-naive evaluation and magic set rewriting. However, datalog also has its limitations since it only supports monotone queries over sets. This means, for instance, that aggregates (which are crucial in many data analytics tasks but are not monotone under set inclusion) are not supported in pure datalog.

In a seminal paper by Green, Karvounarakis, and Tannen [1], K-relations were introduced as a generalization of standard relations. In a K-relation, tuples are mapped to some semiring K. We can then consider standard relations as K-relations over the Boolean semiring, bags of tuples as K-relations over the natural numbers, sparse tensors as K-relations over the reals, etc. Also provenance information at various levels of detail can be captured by an appropriate choice of the semiring K.

In this talk, I have presented our recent work [2, 3] on the query language datalogo, which is based on the concept of K-relations and generalizes datalog to (pre-)semirings. In particular, I have shown how it can capture various computations involving aggregates as well as provenance information. Moreover, I have briefly mentioned convergence properties of datalogo and some optimization techniques.

I will present a survey of MSO enumeration problems over words based on the model of annotated automata, a model for encoding MSO queries with output. In the first half, I will present the basic MSO enumeration problem and the representations needed for efficient enumeration. In the second half, I will go through extensions of this MSO enumeration problem, with the required extensions on the representations. Toward the end, I will present some open problems.

I will give an overview of different types of explanations for aggregate query answers answering user questions like why a value is high/low or higher/lower than another value. I will discuss explanations by intervention, counterbalance, augmented provenance, causal explanations, and actionable explanations. Explanations by Shapley Value will be covered in other talks.

In this talk, I aim to discuss the significant challenge of learning machine learning models that satisfy invariant properties under conditional independence constraints. The importance of this problem will be illustrated through various real-world examples, emphasizing its relevance and urgency. Subsequently, I will analyze existing approaches and their shortcomings, especially in situations where data is compromised by quality issues such as selection bias. To overcome these obstacles, I will introduce a framework inspired by techniques for querying incomplete data in data management. This framework is tailored to effectively handle the specific challenges posed by incomplete datasets. Additionally, I will demonstrate its application in the context of algorithmic fairness.

Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, along with other similar power indices such as Banzhaf values. In this work we adapt these Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in polynomial time, thus obtaining the same tractability landscape. We investigate the specific tractable case where Boolean functions are represented as deterministic decomposable circuits, designing a polynomial-time algorithm for this setting. We present applications to probabilistic databases through database provenance, and an effective implementation of this algorithm within the ProvSQL system, which experimentally validates its feasibility over a standard benchmark.

In this talk, I will introduce a framework for quantifying the importance of the choices of parameter values to the result of a query over a database. In our framework, the importance of a parameter is its SHAP score and we make the case for the rationale of using this score by showing that we arrive at this score in two different, apparently opposing, approaches to quantifying the contribution of a parameter. We then point out that this framework yields an interesting complexity-theoretic landscape.

We study the problem of quantifying the contribution of each Boolean variable to the satisfying assignments of a Boolean function, based on the Shapley value. This problem was introduced by Livshits et al. in order to quantify the contribution of an input tuple to the output of a query. We prove polynomial-time equivalence between computing Shapley values and model counting, for classes of Boolean functions that are closed under substitutions of variables with disjunctions of fresh variables. This result settles an open problem raised by Deutch et at, which sought to connect the Shapley value computation to probabilistic query evaluation.

We consider the complexity of answering Quantile Join Queries, which ask for the answer at a specified relative position (e.g., 50% for the median) under some ordering over the answers to an ordinary Join Query (JQ). Compared to the task of direct access, this task is easier since only one access is required. The goal is to avoid materializing the set of all join answers, and to achieve quasilinear time in the size of the database, regardless of the total number of answers. The tractability of such a query does not only depend on the join structure, but also on the desired order. We show an algorithm that covers all known tractable cases by iteratively using a “trimming” subroutine which removes query answers that are higher or lower (according to the ranking function) than a certain answer determined as the “pivot”. Trimming essentially adds inequality predicates to our initial query and an efficient representation of these inequalities implies efficient Quantile Join Query answering for a large class of ranking functions.