arXiv:2604.06520v1 [cs.DB] 7 Apr 2026
Database Querying under Missing Values Governed by Missingness Mechanisms Leopoldo Bertossi1, Farouk Toumani2 and Maxime Buron2 1 Carleton University, Ottawa, Canada & IMFD, Chile. 2 LIMOS, CNRS, UCA, France.
Abstract
sibility of those approaches.
We address the problems of giving a semantics to- and doing query answering (QA) on a relational database (RDB) that has missing values (MVs). The causes for the latter are governed by a Missingness Mechanism that is modelled as a Bayesian Network, which represents a Missingness Graph (MG) and involves the DB attributes. Our approach considerable departs from the treatment of RDBs with NULL (values). The MG together with the observed DB allow to build a block-independent probabilistic DB, on which basis we propose two QA techniques that jointly capture probabilistic uncertainty and statistical plausibility of the implicit imputation of MVs. We obtain complexity results that characterize the computational fea-
1
Introduction
It is common to find missing values (MVs) in a relational database (DB) D⋆ , that is, values for some attributes that are not reported. We will use na, for “not available”, to indicate that the true value of a variable in that place is absent. No other semantics is assigned to na. We consider the observed DB D⋆ as obtained from an independent sample from an outside reality.1 We assume that D⋆ is an incomplete representation of the “true”, possibly unknown and underlying DB D that represents the external reality. All of D’s at1
This kind of observed DBs, including independence and MVs, are common with census-related data [Gelman et al.,2007].
Xm
Yo Bo
tributes have non-na values that we may not see. m Z
Example 1. Relation R⋆ in Table 1 beo longs to an observed DB D⋆ . We W will use global tuple identifiers (tids): τ1 , etc. Some (true) values are missing, as indicated with na. Following notation and conventions in [Mohan et al.,2021], attribute B o is fully observable, i.e. it never shows na, whereas an attributes A⋆ , C ⋆ may have MVs. R⋆ has the observed schema R⋆ (A⋆ , B o , C ⋆ ). A⋆ a1 a2 na a4 na na
Bo 0 1 0 0 1 1
Yo
Zm*
IZ
IC
Cm
Ao
C*
Figure 1: Missingness Graph. Example 2. (Ex. 1 cont.) For simplicity, assume now that attribute A is fully observed and denoted with Ao . The MG in Figure 1 shows Ao as independent from the other attributes. IC is an indicator variable for C m that takes the value 1 when the value for C m is missing, and 0, otherwise. The MG tells us that whether C ⋆ takes the value na or not, depends on variable C m and B o , for the latter, via IC . ■
Table 1: Relation with Missing Values. R⋆ τ1 τ2 τ3 τ4 τ5 τ6
Zm
C⋆ c1 na c3 c4 c5 na
In general, we start with an observed DB, D⋆ , possibly with MVs, and a MG, M, that models the occurrence of MVs. Observed values are assumed to be certain, but MVs are uncertain. We also assume D⋆ is compatible with the joint distribution induced by the MG.2 We will extract na-free and stochastically reliable information from D⋆ by using the combination of D⋆ and M to create (virtually or physically) a Block-Independent Probabilistic DB (BID) [Suciu et al.,2011]. This BID, in its turn, gives rise to a collection W of possible worlds, each of them an na-free DB instance for the underlying schema, with an associated global probability. W represents the uncertainty due to the occurrence of MVs. Each possible world in it becomes
The underlying DB D has the underlying schema R(Am , B o , C m ), where the superscript “m” indicates that the attribute may have MVs. We do not observe Am directly, but via A⋆ . When the latter does not show an na, it shows the real value of Am . ■ The main question that underlies our work is the following: How can we query the “underlying” DB D in a meaningful way “through” the observed DB D⋆ ? This quest looks hopeless unless we have some additional information. Actually, we will assume we know about the causes for the occurrence of MVs by means of a Bayesian Network (BN) [Pearl,2009] that stochastically models, as a Missingness Graph (MG), the Missingness Mechanisms (MMs) at play 2 Learning a MG and checking an instance against [Little et al.,2019]. Those MMs describe un- a MG are orthogonal problems to ours, and matter der what stochastic conditions MVs may ap- of ongoing separate research. pear. 2
a possible materialization -without MVs- of the partially observed underlying DB D. Our approach can be seen as a generalization of traditional imputation techniques [Gelman et al.,2007], where instead of a single “clean” instance, a class of probabilistically-weighted clean instances is considered. This makes for a more principled and uncertainty-aware data semantics and query answering (QA). Our way of dealing with MVs can be understood as a form of collective imputation by means of probability distributions over possible values; distributions that are related to each other through an underlying joint distribution determined by a MG. Those “cell-level” distributions can be seen as footprints of that joint distribution. Query answering (QA) can be done on the BID, which has a clear semantics [Suciu et al.,2011]. Without neglecting this direct approach, we propose an alternative semantics that builds on the BID, but takes into account the statistical compliance of possible worlds with the distribution induced by the MG. We start by collecting in different classes those possible worlds that are essentially the same, the matching worlds. QA on matching worlds returns the same answer. After that, we introduce a measure of compliance for classes of matching worlds. We identify those classes that are maximally compliant, and do QA on top of them. More specifically, in this work we make the following contributions: 1. We define the semantics of a DB with MVs in relation to a MG representing the missingness mechanisms at play. This is
done through a BID associated to the observed DB and the MG, giving rise to classes of matching possible worlds. Classes are used to define QA. 2. We propose two data and QA semantics: The Most-Probable Classes (MPC), and the Most-Compliant Classes (MCC). The latter has a statistical component in that compliance is measured as the distance between a world’s empirical distribution and that induced by the MG. 3. We investigate the computational complexity of the QA-semantics. For a broad and common family of notions of compliance, one can compute a most-compliant class in polynomial time in the size of the observed DB, on which QA can be done. Furthermore, although there may be exponentially many classes, enumerating all the most-compliant classes and query answers on them can be done with polynomial-time delay. We obtain several hardness results for the MCCsemantics. Still, its has better computational properties than the MPC-semantics. This paper is structured as follows. Section 2 provides background. Section 3 introduces MMs and MGs. Section 4 introduces the BIDs associated to an observed DB. Section 5 introduces classes of matching worlds and class-based QA. Section 6 introduces the notion of compliance. In Section 7, we investigate algorithmic and complexity aspects of class computation and QA. Section 8 discusses related work; and Section 9 summarizes our contributions and outlines directions of future work. The Appendix provides additional material and proofs of results. 3
2
Background and Preliminaries
is a collection W of possible worlds that are the subinstances W of D. Each PW ∈ W has a probability p(W ), such that W ∈W p(W ) = 1 [Suciu et al.,2011]. Dp becomes a discrete probability space ⟨W, p⟩, with p probability distribution on W. The probability of tuple τPbeing in D (as seen through Dp ) is P (τ ) := A numeric query Q on τ ∈W ∈W p(W ). D becomes a random variable on W; with Bernoulli distribution if it is a BQ, in which case, the probability P of Q (being true) is P (Q) := P (Q = 1) := W ∈W: W |=Q p(W ).
Relational Databases. A relational schema, usually denoted with S, is a finite set of logical predicates, usually denoted with R, with fixed arities. Variables, a.k.a. attributes or features, are associated to the predicate positions. A relational DB, usually denoted with D, is a collection of relations which are finite extensions for the predicates. Their elements are called tuples; and their values come from fixed and finite domains. dom(X) denotes the domain of an attribute X. For several attributes, X̄, dom(X̄) denotes the cartesian product of the individual domains. We use dom for the union of the domains. The string na, indicating a missing value, does not belong to any of these domains. dom⋆ denotes dom ∪ {na}. Unless otherwise stated, DB relations may have duplicates, i.e. repeated tuples, which we tell apart by means of global tuple identifiers (tids) that appear in a first attribute of tuples, acting as a surrogate key, as shown in Example 1. We denote tids with τ, τ1 , . . .. We will frequently denote and refer to tuples by their tids. We concentrate on conjunctive queries (CQs), i.e. “project-join-select” queries, and aggregations over CQs. Queries may have constants from dom, and then, different from na. The set of answers to a query Q from a DB D is denoted with Q[D]. Boolean queries (BQ) have 0 or 1 answers.
Table 2: A BID.
R τ11 τ12 τ21 τ22 τ23
A a1 a2 a3 a4 a5
B b1 b2 b3 b4 b5
C c1 c2 c3 c4 c5
P p11 p21 p12 p22 p32
In our work we are interested in blockindependent PDBs (BIDs) [Suciu et al.,2011]. Tuples have probabilities, and tuples of a same relation are separated in mutually independent blocks of mutually exclusive tuples. Tuples in a block are stochastically independent from tuples in other blocks. Table 2 shows a BID R with two blocks. In a possible world W ∈ W, the corresponding relation RW is built from relation R, by choosing from each block Bj exactly one tuple τji . The probability associated to RW is defined by: p(RW ) := Πpij . Any other kind of subrelation has probability 0. The probability of a world W is the product of the probabilities of its relations. A most probable database (MPDB) is a possible world with the highest probability. Within a block, the sum, Probabilistic Databases. Given a rela- p, of the tuples’ probabilities is not greater tional DB, D, a PDB, Dp associated to D than 1. In case none of the tuples is chosen 4
from the block, the block contributes with the factor (1 − p) to the relation’s probability. A tuple-independent PDB (TID) is a particular kind of BID, where each block has a single tuple with a probability that can be less than 1.
3
The MG in Figure 2(b) shows a case of MAR (missing at random): C ⋆ stochastically depends on C m and IC ; while the latter depends on B o . As expected, C ⋆ depends directly on its real, underlying version, C m , and its own indicator variable. The BN m also has the distributions: P (C ), P (B o ), P (IC |B o ), P (C ⋆ |C m , IC ). Furthermore, due to the Markov condition, absolute and conditional independences hold: B o ⊥ ⊥ C m , IC ⊥ ⊥ m ⋆ o C ⊥ B )|I . C , (C ⊥ Finally, the MG in Figure 2(c) shows a case of MNCAR (missing not completely at random); actually of self-censorship: IC depends on C m . For example, C m could be Salary m , that -with hight probability- is not reported when it is very high. When ISalary takes value 1, Salary ⋆ takes value na. Otherwise, Salary ⋆ takes the real value of Salary m . The BN has absolute and conditional distributions: P (C m ), P (I|C m ), P (C ⋆ |C m , IC ). ■
Missingness and Observed DBs
A Missingness Mechanism (MM) specifies how the occurrence of MVs in a variable depends on the values that other (or the same) variables take. There are some MMs that commonly found in practice [Little et al.,2019]. Following [Mohan et al.,2021], MMs are represented by Missingness Graphs (MGs), i.e. Bayesian Networks whose directed edges capture causal or stochastic-dependence directions. Accordingly, MGs become directed acyclic In a MG, each variable X ⋆ is a sink, and graphs subject to the usual Markov Conm X X dition: Given its parents, a variable is in- has exactly two parents: X and I . I o dependent from its non-descendant variables mightZ depend on variables of the forms Ym and I , for other variables of the form Z . [Darwiche,2010, Pearl,2009]. Variables of the form B o are sources. In a Example 3. The MG in Figure 2(a) cor- MG M the probability distributions at its responds to the MCAR case (missing com- nodes determine a joint distribution P M over pletely at random) in that variable IC does all variables. In particular, a tuple τ for the not depend on any other variable, and has underlying schema S has a marginal probaabsolute probabilities of taking values 0 or 1. bility P M (τ ). Furthermore, MGs satisfy the Bo following conditions, where, c, c′ ∈ dom(X m ) are arbitrary, but different: Cm IC IC IC Cm Cm C*
C*
(a)
(b)
C*
P
(c)
M
P
Figure 2: Three Missingness Graphs.
P M (X ⋆ = na | IX = 1, X m = c, . . .) ⋆
(X = na, . . . | I
M
⋆
′
X
M
⋆
X
(X = c , . . . | I P
5
X
(X = c | I
= 0, X
m
= 0, X
m
= 0, X
m
=
1,(1)
= c, . . .)
=
0,(2)
= c, . . .)
=
0,(3)
= c, . . .)
=
1,(4)
but queries will be posed in the language of the underlying schema S (see Section 5). ■ P M (X ⋆ = na, . . . | IX = 1, X m = c, . . .) = We will assume that in an observed inP M (. . . | IX = 1, X m = c, . .(5) .), stance D⋆ all the tuples are stochastically inP M (X ⋆ = c, . . . | IX = 0, X m = c, . . .) = dependent from each other, as obtained from P M (. . . | IX = 0, X m = c, . .(6) .). an independent sample of the real world. In Example 4. (Ex. 2 cont.) Con- particular, D⋆ may have duplicate tuples. sider the observed DB R⋆ in Table 3(a) Furthermore, we will assume that an obfor the observed schema S ⋆ . MVs in it served DB D⋆ is compliant with the given are governed by the MG M in Example MG M. In particular, D⋆ satisfies both the 2. On the basis of the local distribu- (in)dependencies represented by the MG and tions P (Ao ), P (C ⋆ |C m , IC ), P (I|B o ), P (B o ), its induced distributions. and the Markov condition, M induces the A possible underlying DB, such as W in the factorized joint distribution: previous example, may also introduce dupliP M (Ao , B o , C ⋆ , IC , C m ) = P M (C ⋆ | C m , IC ) × P M (I C | B o ) cates, when na’s are replaced by domain val×P M (C m ) × P M (B o ) × P M (Ao ). (7) ues. Table 3: (a) Observed (b) Underlying (c) Expanded DBs. 4 BIDs for Missing R⋆ τ1 τ2 τ3 τ4 τ5 τ6
Ao a1 a2 a3 a4 a5 a6
Bo 0 1 0 0 1 1 Rex τ1 τ2 τ3 τ4 τ5 τ6
C⋆ c1 na c3 c4 c5 na Ao a1 a2 a3 a4 a5 a6
Ao a1 a2 a3 a4 a5 a6
W τ1 τ2 τ3 τ4 τ5 τ6 Bo 0 1 0 0 1 1
C⋆ c1 na c3 c4 c5 na
IC 0 1 0 0 0 1
Bo 0 1 0 0 1 1
Cm c1 c5 c3 c4 c5 c2
Values We can see observed DB D⋆ , together with a MG M, as a single representation for a set, W(D⋆ ), of possible worlds, namely, of nafree databases, W , for the underlying schema S. For this, we start by replacing values from dom for each occurrence of an na in D⋆ . Then, each tuple with MVs in D⋆ gives rise to a “block” of “potentially observed” tuples, without na, each of them with a probability. We obtain a BID, Dp (D⋆ , M). The following example shows this; in particular, how we assign probabilities to the tuples in a block. The general construction can be found in Definition 6 in the Appendix.
Cm c1 c5 c3 c4 c5 c2
Table 3(b) shows W as a possible na-free underlying instance for the underlying schema S, where the true values c5 and c2 (underlined) for C m where not all observed, giving rise to R⋆ . The “expanded” relation Rex in Table 3(c), for an expanded schema S ex , shows a possible sample from the outside reality represented by M, with values for all variables in it. R⋆ and R can Example 5. (Ex. 4 cont.) Assume be seen as footprints of Rex . A “user” has dom(C) = {c1 , . . . , c5 }, Table 3(a) gives rise access only to the observed instance R⋆ , to the relation in Table 4(a). The first tuple, 6
fully observed, gives rise to a certain block via tids. In Example 1, duplicates are generwith one tuple, with probability 1. ated from τ2 and τ6 by replacing na by c3 in the former, and by a2 and c3 in the latter. Table 4: (a) Blocks of tuples, (b) A BID. Example 6. (Ex. 5 cont.) It is easy to R Ao Bo Cm Rp Ao Bo Cm pBID τ1 a1 0 c1 τ1 a1 0 c1 1 check that, starting from (8), the probabiliτ21 a2 1 c1 τ21 a2 1 c1 p1 2 τ22 a2 1 c2 τ22 a2 1 c2 p2 ties pi2 of the tuples τ2i , i = 1, . . . , 5, in block 2 B(τ2 ) τ23 a2 1 c3 τ23 a2 1 c3 p3 2 B(τ2 ) in Table 4(b) are as follows: τ24 a2 1 c4 τ24 a2 1 c4 p4 2 5 τ2 ···
a2 ···
1 ···
c5 ···
τ25 ···
a2 ···
1 ···
p5 2 ···
c5 ···
pBID (τ2i ) =
Tuple τ2 in R⋆ gives rise to a block, B(τ2 ), of five tuples, τ21 , . . . , τ25 , with probabilities p12 := pBID (τ21 ), . . . , p52 := pBID (τ25 ); etc. In this way, we obtain a BID as in Figure 3(b). In block B(τ2 ), the probability of tuple τ21 is defined on the basis of (or conditioned to) the observed values in the same tuple (similarly for the other tuples):
=
P M (Ao = a2 , B o = 1, C m = ci , IC = 1) P M (Ao = a2 , B o = 1, IC = 1) P M (C m = ci ).
■
Each possible world W of the BID becomes one version of the observed DB D⋆ obtained via multiple imputation [Gelman et al.,2007]. Since each possible world W of the BID is an instance for the underlying schema S, a query pBID (τ21 ) := P M (C m = c1 | Ao = a2 , B o = 1, C ⋆ = na). Q posed to the BID will be expressed in lan(8) guage of the underlying schema, using only By choosing one tuple per block, the BID in attributes of the forms Ao and Am . Then, by Table 4(b) gives rise to a set W(R⋆ ) of possi- definition, posing a query Q to the observed ble worlds, W , among them, those in Table 5, database D⋆ means querying the associated where the underlined values are obtained by BID Dp (D⋆ , M). replacing na by domain values. Their proba- It is easy to see that the number of possible bilities are: P W (R1 ) = 1 × p12 × 1 × 1 × 1 × p56 , worlds for Dp (D⋆ , M) can be exponential in and P W (R2 ) = 1×p22 ×1×1×1×p36 , resp. ■ the size of D⋆ . Furthermore, the QA problem is bound to be hard in data complexity, Table 5: Two Possible Worlds. because the problem of computing the probaR1 Ao Bo Cm R2 Ao Bo Cm τ1 a1 0 c1 τ1 a1 0 c1 bility of BQ on a TID [Suciu et al.,2011] can τ21 a2 1 c1 τ22 a2 1 c2 be reduced in polynomial-time in the data to τ3 a3 0 c3 τ3 a3 0 c3 τ4 a4 0 c4 τ4 a4 0 c4 QA under an observed DB with its MG. τ5 a5 1 c5 τ5 a5 1 c5 5 3 τ6
a6
1
c5
τ6
a6
1
c3
Theorem 1. Conjunctive query answering on observed databases with missing values via the generated BIDs is #P -hard. ■ Instead of going deeper into the investigation of general QA on the resulting BIDs, we will propose, starting in Section 5, an alternative
⋆
A possible world associated to D is an instance W for schema S, with relations RW that contain, for each τ ∈ R⋆ , only one τ ′ ∈ B(τ ), and nothing more. Possible worlds may contain duplicates which we tell apart 7
QA semantics. The presence of duplicates Example 7. (Ex. 6 cont.) Consider the will be particularly important. MG in Example 2, the observed DB in Table 6(a), and dom(C m ) = {0, 1, 2}. As1 M m M m sume: P (C = 0) = 2 , P (C = 1) = 5 Class-Based Data P M (C m = 2) = 41 , that, by Example 6, is all we need to build the BID in Table 6(b). Semantics Table 6(c) shows the most-probable possible Our data QA semantics, that builds upon the world, W1 in Table 7. It has duplicates. classic one for BIDs, leverages the stochastic Table 7 shows all possible worlds. We use v and statistical origins of the observed DB D⋆ . the notation W for possible worlds where m We adopt a two-dimensional perspective: (a) v is a vector of values from C ’s domain Each possible world is associated with a prob- of length n, the number of (non-singleton) ability that reflects its stochastic uncertainty. blocks in the BID. Here, n = 3. World [0,0,0] is obtained by choosing 0 for the This is what we have so far. (b) The second W MVs for C m in each of the three blocks of dimension is of a statistical nature: A no[1,2,0] is obtained by tion of compliance quantifies how well a pos- the BID. Similarly, W sible world aligns with the joint distribution choosing 1 for block 1; 2 for block 2; and induced by the MG. This second dimension 0 for block 3. The last column of Table 7 W is developed in detail in Section 6. In this shows the probability P (W ) of each world ■ section, we prepare the ground and bring up W . some relevant issues by means of our running Table 7: Possible Worlds with Probabilities. example. World W1 W2 W3 W4 ... W20 W21 W22 ... W26 W27
Table 6: (a) Obs. D⋆ , (b) BID Dp , (c) MPD w/prob. ( 12 )3 .
τ1 τ2 τ3 τ4 τ5 τ6 τ7 τ8
Ao a a a a a a a a
Bo 0 0 1 1 1 1 1 1
τ1 τ2
C⋆ 0 0 na 0 na 1 na 2
B(τ3 ) τ4 B(τ5 ) τ6 B(τ7 ) τ8 τ1 τ2 τ31 τ4 τ51 τ6 τ71 τ8
Ao a a a a a a a a
Bo 0 0 1 1 1 1 1 1
Ao a a a a a a a a a a a a a a
Bo 0 0 1 1 1 1 1 1 1 1 1 1 1 1
Cm 0 0 0 1 2 0 0 1 2 1 0 1 2 2
pBID 1 1 1/2 1/4 1/4 1 1/2 1/4 1/4 1 1/2 1/4 1/4 1
Notation W [000] W [001] W [002] W [010] ... W [201] W [202] W [210] ... W [221] W [222]
PW (W) (1/2)3 = 0.125 (1/2)2 × 1/4 = 0.06 (1/2)2 × 1/4 = 0.06 (1/2)2 × 1/4 = 0.06 ... (1/4)2 × 1/2 = 0.03 (1/4)2 × 1/2 = 0.03 (1/4)2 × 1/2 = 0.03 ... (1/4)3 = 0.015 (1/4)3 = 0.015
Our running example shows that some possible worlds coincide as multisets except for the tuples’s tids. This is the case of W [002] and W [020] . We can also obtain the same answer to a query from different possible worlds (see Example 8). Given the accidental coincidence of worlds due to the implicit imputation process, we
Cm 0 0 0 0 0 1 0 2
8
Classes C1 C2 C3
will group together possible worlds into classes of worlds, each class containing the worlds that coincide as multisets modulo the tids. Clearly, worlds in a same class return the same answer to a query.
C4 C5 C6 C7 C8 C9 C10
Definition 1. (a) Possible worlds ′ ⋆ W, W ∈ W(D , M) obtained from a BID. are said to be matching iff they become the same multiset instance when stripped from tids. (b) A class of possible worlds, C, is a maximal subset (under set-inclusion) of W where all worlds in it are matching with each other. C(D⋆ , M) denotes the collection of all classes. (c) The P probability W C of a class C is: P (C) := W ∈C P (W ). (d) C is a most probable class (MP-class) if P C (C) takes a maximum value in C(D⋆ , M). MP (C(D⋆ , M)) denotes the collection of MP-classes. (e) Given a query Q (in the in the language of schema S), and a class C ∈ C(D⋆ , M), the answer to Q from C is Q[C] := Q[W ], with arbitrary W ∈ C, and its probability is P C (C). ■
Worlds W [002] , W [020] , W [200] W [011] , W [101] , W [110] W [012] , W [021] , W [102] , W [120] , W [201] , W [210] W [111] W [001] , W [010] , W [100] W [022] , W [202] , W [220] W [112] , W [121] , W [211] W [000] W [122] , W [212] , W [221] W [222]
P C (C) 0.188 0.094 0.188
sum(C m )[C] 5 5 6
0.016 0.188 0.094 0.047 0.125 0.047 0.0164
6 4 7 7 3 8 9
Remark 1. (canonical representation of classes) Given the BID Dp (D⋆ , M), with a set of n blocks B = {B1 , . . . , Bn } (including singletons), a class C of worlds is determined by the multiplicities of the tuples they contain. Let T = ⟨t1 , . . . , tm ⟩, called the support of the BID, be the vector of distinct tuples appearing in the BID (without considering the tids). So, T has a fixed enumeration of tuples. (We will still use the notation t ∈ T and |T |.) Let nj denote the multiplicity of tuple tj across the blocks in B, i.e. its number of occurrences in the BID. Accordingly, a class C is uniquely determined by a vectorPof positive integers k = ⟨k1 , . . . , km ⟩, with j∈[1,m] kj = n, where each kj ≤ nj is the number of occurrences of tj in C. This class is denoted with Ck . We denote with adm(k) the fact that k is admissible, that is, there is a class Ck for Dp (D⋆ , M). When searching for such a k, i.e. searching for a class with good properties, we have to check admissibility. ■
Example 8. (Ex. 7 cont.) Table 8 shows the different classes obtained from the worlds in Table 7; and their probabilities. With the aggregate query Q : sum(C m ) over the partially observed attribute C m , we obtain the answers in Table 8. The probability of an answer is the sum of the probabilities of the classes that return it. Answer sum = 5 is the most probable answer, with probability 0.28125. ■ Example 9. (ex. 7 cont.) Consider the BID in Table 6(b). Here, n = 8 and Table 8: Classes and Answers (bag seman- T = ⟨(a, 0, 0), (a, 1, 0), (a, 1, 1), (a, 1, 2)⟩, in tics). this order, with m = 4. For t3 = (a, 1, 1), 9
n3 = 4. Class C2 contains W [011] = {(a, 0, 0), (a, 1, 0), (a, 0, 0), (a, 1, 0), (a, 1, 1), (a, 1, 1), (a, 1, 2), (a, 1, 1)}, and its matching worlds (see Table 8). C2 is characterized by the vector k = ⟨2, 2, 3, 1⟩, and denoted C⟨2,2,3,1⟩ . ■ Now, we can consider a set C pref ⊆ C of preferred classes, those with a desired property. For example, we already have the mostprobable classes. In Section 6, we will consider most-compliant classes. QA can be defined in general, on an arbitrary set of preferred classes. Definition 2. (Preferred QA-Semantics) Given C pref ⊆ C(D⋆ , M) and a relational query Q: The set of all preferred answers is: Ans(Q, C pref ) := {⟨Q[C], P C (C)⟩ | C ∈ C pref }. ■ Several computational problems arise in relation to this general formulation of QA, and the notion of preferred class. Some problems will be presented in Section 7, where we will concentrate mostly on class-related computational problems, leaving QA aside, which is easier than computing classes with certain properties.
6
Possible-World Compliance
We can go beyond the purely probabilistic dimension by introducing a new and natural dimension for data and QA semantics: world compliance, which we develop in this section. It quantifies how well a possible world con-
forms to the joint distribution induced by the MG. Actually, in the rest of this paper, we will concentrate on world and class compliance, leaving aside, due to the lack of space, the development of the probabilistic dimension for an extended version of this work. Some possible worlds (or classes thereof) may be more compliant than others w.r.t. the underlying MG M, with compliance as a measure statistical fidelity. It can be cast as a distance between the data distribution of a world W (and of those in its class) and the distribution induced by M. In our running example, some of the worlds that contribute to the most probable answer, sum = 5, such as W [110] and W [101] , may not be the most compliant. In order to define compliance, we start with the empirical distribution of a world (which is the same for all the worlds in its class). It is based on the multiset nature of worlds. Definition 3. Given a BID Dp (D⋆ , M), and its support T (see Remark 1), the E empirical distribution, PW , of a possible ⋆ world W ∈ W(D , M) as a multiset is, E (t) := mult W(t)/||W ||, with for t ∈ T : PW mult W(t) the multiplicity of t in W , and ||W || is the bag-cardinality of W , i.e. counting duplicates. ■ Notice that the support T does not have duplicates. A tuple in it that does not belong to a particular W has empirical probability 0 in that world. The empirical distribution will be compared with P M , the distribution induced by the MG M, as a marginal for the underlying schema S. The comparison is made considering only tuples in T .
10
Example 10. (ex. 9 cont.) Consider world W [002] in Table 9 belonging to class C1 in Table 8; and its associated duplicate-free world, denoted with W [002] ↓, with its and empirical distribution. The two other worlds in C1 share the same empirical distribution.
Distance-Based Compliance. If we have an abstract measure of distance, d(·, ·), between an empirical distribution and the joint distribution P M , we can define compliance.
Definition 4. (a) The compliance de⋆ gree of C ∈ C(D , M) is: dc (C, M) := E M Table 9: A World’s Associated Distributions. d(PW , P ), with any W ∈ C. (b) C is a most-compliant class (an MC-class) w.r.t. [002] o o m d if dc (C, M) takes a minimum value in W A B C τ1 a 0 0 C(D⋆ , M). Cdmc denotes the collection of τ2 a 0 0 MC-classes relative to d. ■ B(τ3 ) a 1 0 τ4 B(τ5 ) τ6 B(τ7 ) τ8
W [002]↓ t1 t2 t3 t4
a a a a a
Ao B o C m a 0 0 a 1 0 a 1 1 a 1 2
1 1 1 1 1
0 0 1 2 2
E PW [002] 1/4 3/8 1/8 1/4
The distance in (a) is well defined since all worlds in a class of matching worlds have the same empirical distribution. Several distances between probability distributions offer themselves to define the compliance degree, among them the KullbackLeibler Divergence (KLD) [Wasserman,2010]:
PM 0.225 0.225 0.1125 0.1125
E E dKL(PW , P M ) := DivKL (PW ∥ P M ) :=
X t∈T
E PW (t) ln
E (t) PW , M P (t)
(9)
Let us assume, consistently with Example 7, that dom(C m ) = {0, 1, 2}, dom(Ao ) = {a, b}, dom(B o ) = {0, 1}, dom(C ⋆ ) = {0, 1, 2, na}, and also: P M (C m = 0) =
so as the Euclidean Distance, dEU [Hastie et al.,2017]. For a class C, KLD(C) denotes the KL-distance in common to all worlds in C to P M . Any two matching M m M m M o 1/2, P (C = 1) = P (C = 2) = 1/4, P (B = worlds, W, W ′ , become equally compliant. 0) = P M (B o = 1) = 1/2, P M (Ao = a) = However, they may have different global 0.9, P M (Ao = b) = 0.1. As noted in Example probabilities, pW (W ) and pW (W ′ ). 7, with these probabilities we can compute the induced probabilities (using equations Example 11. (ex. 10 cont.) With (9), (1)- (6), (7)): For x ∈ {a, b}, y ∈ {0, 1}, z ∈ we can compute the KL-distance for each {0, 1, 2}: P M (Ao = x, B o = y, C m = z) = class. Table 10 shows the distances of the P P M (Ao = x, B o = y, C m = z, IC = u, C ⋆ = different classes to the induced distribution. u∈{0,1},v∈{0,1,2,na} The most-compliant classes (MC-classes) are v) = P M (C m = z)×P M (B o = y)×P M (Ao = x). We C1 , C5 , C8 . The most probable classes are obtain the last column, P M , in Table 9, also C1 , C3 , C5 . ■ shared with the other worlds in class C1 . ■ 11
Consistently with Definition 4(b), we denote 7 Computing Classes mc ⋆ mc ⋆ with CKL (D , M) and CEU (D , M) the set of and QA MC-classes with respect to the KL- and Euclidean distances, resp. Table 10: Classes and Compliance (bag se- With a general notion of class-based query mantics). answering (QA), and the most-compliant and Classes C Worlds P C (C) KLD(C) the most-probable collections of classes, we C1 W [002] , W [020] , W [200] 0.188 0.431 can turn to computational problems that natC2 W [011] , W [101] , W [110] 0.094 0.518 [012] [021] [102] urally arise and to their computational comC3 W ,W ,W , 0.188 0.452 W [120] , W [201] , W [210] plexities. C4 W [111] 0.016 0.711 We will concentrate only on most-compliantC5 W [001] , W [010] , W [100] 0.188 0.431 C6 W [022] , W [202] , W [220] 0.094 0.711 related computational problems. They will C7 W [112] , W [121] , W [211] 0.047 0.929 be formulated and addressed using the class C8 W [000] 0.125 0.431 representation in Remark 1; in particular, C9 W [122] , W [212] , W [221] 0.047 0.972 C10 W [222] 0.016 1.111 we consider classes Ck , and a representative world therein, Wk , that can also be seen as Goodness-of-Fit Compliance. An alter- encoding the degree of compliance of its class. notion of convex-separability native take on possible-world compliance is The based on hypothesis testing. Given W ∈ W [Ahuja et al.,1993] associated to distances as a sample, we test the hypothesis, H0 , that will become critical. Intuitively, such disit fits the induced distribution P M . We use tances d(·, ·) can be computed by aggregating independent contributions associated with the χ2 -statistic: m E M 2 X individual tuples, so that the total distance (PW (a¯i ) − P (āi )) , (m = |T |) χ2 (W ) := M P (āi ) decomposes as a sum P of per-tuple convex i=1 m 2 M which, under H0 , has approximately a χm−1 - terms: d(Ck , M) = (tj ) , j=1 dj kj , P distribution [Wasserman,2010]. It can be where each dj is a convex function capseen as a distance, actually a measure of the turing the local cost of the assignment E relative square deviation of PW from P M . made to tuple tj . The family of convex In order to compare worlds, we can use a com- separable functions encompasses many pliance order based on the p-values for the classical measures of discrepancy, including test: pV(W ) := PH0 (χ2 ≥ χ2 (W )), that f -divergences [Ali et al.,1966] such as the is the probability (under H0 ) that χ2 -as a KL-divergence, the Hellinger distance , the random variable- is at least as contradictory total variation distance, and the χ2 -statistic, to H0 as the value of χ2 (W ). It is defined as well as Lp -norms [Royden,1988], for V V by: W1 <M In 1 ≤ p < ∞, such as the L1 Manhattan pv W2 iff p (W1 ) < p (W2 ). mc this way, we have the family Cpv of most- distance and the L2 - Euclidean distance. compliant classes based on the p-value of the The following definition formalizes computaχ2 -test. tional problems of interest related to MCC. 12
Definition 5. (MC-related problems) Assume Dp (D⋆ , M) is a BID. We define the following computational problems: 1. MCC (MC-Class): Compute an ⋆ admissible class-vector k ∈ Nm that minimizes the compliance-distance (or maximizes compliance): C k⋆ ∈ c P argmink∈Nm , m d (Ck , M). j=1 kj =n
2. #MCC (Counting MC-Classes): Count the number of MC-classes, i.e. all classvectors k⋆ , such that Ck⋆ minimizes 3. MCC-Enum (Enumerating MC-Classes): Effectively enumerate all class-vectors k⋆ , such that Ck⋆ minimizes d c (Ck , M). ■ Theorem 2 provides computational complexities of MCC-related problems (see [Papadimitriou,1994]).
a single MC-class can be achieved in polynomial time for a wide class of distance functions. Moreover, the (possibly exponentially many) MC-classes can be effectively enumerated with polynomial delay. However, counting the number of MC-classes turns out to be #P -complete. These results are obtained through a reduction from MCC to computing a “minimum-cost flow” in bipartite graphs and some related problems. Note that, due to the convex-separability of the KL-divergence, eucledian distance and the χ2 -statistic, Theorem 2 holds in mc mc mc . ■ and Cpv , CEU particular for CKL
8
Related Work
Incomplete DBs, in particular in relation to MVs have been investigated for a long time, under different representations and semantics [Imielinski et al.,1984, Reiter,1986, Greco et al.,2012]. None of those approaches is directly our line of work. Since the inception of relational DBs, null values, in the form of the SQL constant NULL, have been used to represent MVs. Its use has been contentious and a subject of several papers. A recent body of investigation has shed light on the semantic and algorithmic issues related to the use of NULL. See [Toussaint et al.,2022] for an interesting discussion and references. For a simple and practical reconstruction of the use of NULL MCC is about computing one good class. in SQL that is based on query-rewriting Once we have it, QA on it is straightfor- see [Bertossi et al.,2017]. More recently, ward. Theorem 2 tells us that computing [Console et al.,2022] have considered numer-
Theorem 2. (MC-related problems) Assume Dp (D⋆ , M) is a BID with n blocks and a support T with m distinct tuples. For a convex-separable distance d, we have: 1. MCC is in FP, the class of functional problems computable in deterministic polynomial time. 2. #MCC is #P-complete, i.e. it belongs and is hard for the class of counting solutions of NP decision problems. 3. MCC-Enum is in DelayP, the class of enumeration problems where the time delay between the output of any two consecutive solutions is polynomial in the input size. ■
13
ical queries in the presence of null values. See also [Gheerbrant et al.,2023] for recent results along this line of work. However, following this common approach, i.e, replacing MVs in D⋆ by NULL, and using any SQL-based DB management system for QA, we would be assigning a very particular “semantics” to data with MVs; one that is embedded in the way SQL DBs operates with NULL. In our work, we do not refer to- or handle null values or NULL as in SQL DBs. In PDBs, a query semantics defines how answers are interpreted and computed under uncertainty. The possible worlds semantics determines probability distributions over those worlds and over query answers, by evaluating the query on each world [Suciu et al.,2011]. Alternatively, the confidence or marginal semantics focuses on marginal probabilities of individual tuples appearing in results, simplifying computations by ignoring correlations [Dalvi et al.,2004, Soliman et al.,2007, 26]. Extensions such as the top-k and the expected score semantics rank or score tuples based on probabilities or utilities [Soliman et al.,2007, Das Sarma et al.,2006, Ré et al.,2007]. One can also decide to use the most probable database to evaluate the query [Van den Broeck et al.,2015]. For aggregate queries, similar semantics apply: the possible worlds semantics yields a distribution over aggregate values [Dalvi et al.,2004]. There is a large body of research on dealing with MVs, mostly in Statistics [Allison,2002, Gelman et al.,2007]. A common technique is imputation, which amounts to filling in for them using other values in the do-
main. MMs were proposed in that context [Little et al.,2019]. Imputation methods and statistical estimates in the presence of MV come in different forms, and may depend on MMs [Little et al.,2019, Gelman et al.,2007]. Our work is not about these forms of “classic imputation”, but, instead and in general terms, we do something like an implicit causality-informed probabilistic imputation that gives rise to several possible “imputed” instances with attached probabilities. MMs represented as causal networks [Pearl,2009] have been introduced and investigated by Mohan and Pearl [Mohan,2017, Mohan et al.,2021]. We build upon them. In [De Sa et al.,2019], the authors take a probabilistic and general approach to data quality, which may in principle involve different dimensions of quality, including incompleteness. MVs, as those we deal with, are not specifically addressed. Various methodologies have been proposed to assess the compatibility of a dataset with a Bayesian network, such as model-fit measures, e.g. maximum-likelihood [Bischop,2006, Allison,1993, Wasserman,2010], informationtheoretic measures [MacKay,2003], and representation of stochastic dependencies via generalized multi-valued dependencies [Wong et al.,1994].
9
Conclusions
In this work, we have provided a principled semantics to a DB with MVs. Their occurrences as assumed to be governed by a
14
quantitative Bayesian-Network, that represents missingness mechanisms. The data semantics relies on the construction of a BID that induces a space of possible worlds with associated probabilities. Possible worlds are multiset-DBs without MVs. To support QA, possible worlds are classified in classes. We introduced and investigated two collections of classes: the Most Compliant Classes, the MCC-semantics, which prioritizes classes that best align with the underlying MG; and the Most Probable Classes, the MPC-semantics, which selects classes according to their aggregate probability mass. They reflect the complementary dimensions of statistical plausibility and probabilistic likelihood. We presented complexity results for QA under MCC semantics. Notably, we showed that, assuming access to an oracle for evaluating queries over complete databases, QA under the MCC semantics on a single class is tractable in polynomial time. Although enumerating the answers under all MC-classes is computationally intractable, it can still be performed with polynomial delay. As part of our ongoing work, not reported here, we have investigated the complexity of the MPC-semantics. With the aim of identifying classes of observed DBs for which efficient query evaluation is tractable, we have uncovered a natural class of them for which the MCC- and the MPC-semantics coincide, and QA becomes tractable. About future research, we plan to investigate hybrid query semantics that jointly consider compliance and probability, allowing for a more expressive and flexible notion of QA.
We are also interested in exploring how our class-based semantics could inform or be integrated with advanced imputation strategies, especially in statistical or machine learning pipelines. We are also interested in the verification and enforcement of compliance of an observed DB D⋆ with the underlying the MG. Techniques as those reported in [Salimi et al.,2019, Salimi et al.,2024] could be useful. Finally, implementing these techniques and conducting experimental evaluations on real-world datasets will be essential for assessing their practical applicability and performance. Acknowledgements: Leopoldo Bertossi has been financially supported by the “Millennium Institute for Research on Data” (IMFD, Chile), and NSERC-DG 2023-04650. Part of this work was done while he was visiting the “Laboratory of Informatics, Modelling and Optimization of the Systems” (LIMOS), at U. Clermont-Ferrand, France. He appreciates their support and hospitality. XXX References [Ahuja et al.,1993] Ahuja, R. K., Magnanti, T. L. and Orlin, J.B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. [Ali et al.,1966] Ali, S. M. and Silvey, S. D. A General Class of Coefficients of Divergence of one Distribution from Another. Journal of the Royal Statistical Society, Series B, 1996, 28(1):131–142.
15
[Allison,1993] Allison, P. D. Maximum Likelihood Estimation. Quantitative Applications in the Social Sciences, 96. Sage Publications, 1993. [Allison,2002] Allison, P. D. Missing Data. Quantitative Applications in the Social Sciences, 136. Sage Publications, 2002.
A Formal Framework for Probabilistic Unclean Databases. Proc. ICDT 2019, pp. 6:1-6:18. [Dinic,1970] Dinic, E. A. Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation. Soviet Mathematics Doklady, 1970, 11:1277– 1280.
[Bertossi et al.,2017] Bertossi, L. and Bravo, L. Consistency and Trust in Peer [Gelman et al.,2007] Gelman, A. and Hill, J. Data Exchange Systems. Theory and Data Analysis Using Regression and MulPractice of Logic Programming, 2017, tilevel/Hierarchical Models. Cambridge 17(2):148-204. Univ. Press, 2007.
[Bischop,2006] Bishop, C. M. Pattern RecogA., nition and Machine Learning. Springer, [Gheerbrant et al.,2023] Gheerbrant, Libkin, L., Rogova, A. and Sirangelo, C. 2006. Querying Incomplete Data: Complexity [Console et al.,2022] Console, M, Libkin, L. and Tractability via Datalog and Firstand Peterfreund, L. Querying IncomOrder Rewritings. Theory and Practice plete Numerical Data: Between Cerof Logic Programming. Published online tain and Possible Answers. 2022, CoRR on 28 November 2023. abs/2210.15395. [Greco et al.,2012] Greco, S., Molinaro, C. [Dalvi et al.,2004] Dalvi, N. and Suciu, D. and Spezzano, F. Incomplete Data Efficient Query Evaluation on Probabilisand Data Dependencies in Relational tic Databases. In Proc VLDB 2004. Databases. Synthesis Lectures in Data Management, Morgan & Claypool Pubs., [Das Sarma et al.,2006] Das Sarma, A., Ben2012. jelloun, O., Halevy, A. and Widom, J. Working Models for Uncertain Data. Proc [Hastie et al.,2017] Hastie, T., Tibshirani, R. ICDE 2006. and Friedman, J. The Elements of Statistical Learning. 2nd Ed., Springer, 2017. [Darwiche,2010] Darwiche, A. Bayesian Networks. Communications of the ACM, [Imielinski et al.,1984] Imielinski, T. and 2010, 53(12):80-90. Lipski Jr., W. Incomplete Information [De Sa et al.,2019] De Sa, C., Ilyas, I., in Relational Databases. Journal of the Kimelfeld, B., Re, C. and Rekatsinas, T. ACM, 1984, 31(4):761-791. 16
[Little et al.,2019] Little, R. J. and Ru- [26] Ré, C., Dalvi, N. and Naughton, J. F. bin, D. B. Statistical Analysis with MissTrio: A System for Integrated Manageing Data. John Wiley & Sons, 3rd Ed., ment of Data, Accuracy, and Lineage. 2019. Proc. CIDR, 2005, pp. 262–276. [MacKay,2003] MacKay, D. J. Informa- [Reiter,1986] Reiter, R. A Sound and Sometimes Complete Query Evaluation Algotion Theory, Inference, and Learning Alrithm for Relational Databases with Null gorithms. Cambridge University Press, Values. J. of the ACM, 1986, 33(2):3492003. 370. [Minoux,1986] Minoux, M.. Solving Integer Minimum Cost Flows with Separable [Royden,1988] Royden, H. L. Real Analysis, 3rd ed. Macmillan, New York, 1988. Convex Cost Objective Polynomially. In: Gallo, G., Sandi, C. (eds) ‘Netflow at [Salimi et al.,2019] Salimi, B., Rodriguez, L., Pisa’. Mathematical Programming StudHowe, B. and Suciu, D. Interventional ies, Springer 1986, vol 26. Fairness: Causal Database Repair for Algorithmic Fairness. Proc. SIGMOD, [Mohan,2017] Mohan, K. Graphical Mod2019, pp. 793–810. els for Inference with Missing Data. PhD Thesis, UCLA, 2017. https:// [Salimi et al.,2024] Salimi, B., Milani, M., escholarship.org/uc/item/6mk2b174 Pirhadi, A., Cloninger, A. and Moslemi, M. H. OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport. Proc. SIGMOD, 2024.
[Mohan et al.,2021] Mohan, K. and Pearl, J. Graphical Models for Processing Missing Data. Journal of the American Statistical Association, 2021, 116(534):1023–1037. [Papadimitriou,1994] Papadimitriou, C. Computational Complexity, AddisonWesley, Reading, MA, 1994.
[Senellart et al.,2018] Senellart, P., Jachiet, L., Maniu, S. and Ramusat, Y. ProvSQL: Provenance and Probability Management in PostgreSQL. Proc VLDB, 2018.
[Pearl,2009] Pearl, J. Causality: Models, Reasoning and Inference. Cambridge [Soliman et al.,2007] Soliman, M., Ilyas, I Univ. Press, 2nd edition, 2009. and Chang, K. Top-k Query Processing in Uncertain Databases. In Proc. ICDE [Ré et al.,2007] Ré, C., Dalvi, N. and Su2007. ciu, D. Efficient Top-k Query Evaluation on Probabilistic Data. Proc. ICDE, 2007, [Suciu et al.,2011] Suciu, D., Olteanu, D., pp. 886-895. Ré, C. and Koch, C. Probabilistic 17
Databases. Synthesis Lectures on Data (a) The block associated to τ is the set of Management, Morgan & Claypool Pubs., tuples for schema R(Āo , Ām ): 2011. ⋆ ⋆ B(τ ) := { τ ′ | τ ′ [Āo , Ā′ ] = τ [Āo , Ā′ ], and, for each ⋆ A ∈ (Ā⋆ ∖ Ā′ ), τ ′ [A] ∈ dom(Am )(10) }. [Toussaint et al.,2022] Toussaint, E., Guagliardo, P., Libkin, L. and Se′ ′ queda, J. Troubles with Nulls, Views (b) For τ ∈ B(τ ), its probability p(τ ) is the from the Users. Proc. VLDB Endow., conditional probability: 2022, 15(11):2613-2625. ⋆ pBID(τ ′ ) := P M (τ ′ [Ā⋆ ∖ Ā′ ] | τ ). (11) [Van den Broeck et al.,2015] Van den Broeck, G. and Suciu, D. Query Processing on Probabilistic Data: A Survey. Foundations and Trends in Databases, 2015, 7(3-4):197–341. NOW Publishers. [Wasserman,2010] Wasserman, L. Statistics. Springer, 2010.
All of
[Wong et al.,1994] Wong, S. K. M. and Wang, Z. W. On Axiomatization of Probabilistic Conditional Independence. Proc. Conf. Uncertainty in Artificial Intelligence, 1994, pp. 591–597.
The probability of the tuple in a singleton block is 1. (c) Dp(D⋆ , M) denotes the BID whose relations Rp contain the blocks B(τ ) for τ ∈ R⋆ , and each tuple τ ′ ∈ Rp has probability pBID (τ ′ ). (d) A possible world associated to D⋆ is an instance W for the underlying schema S, with relations RW that contain, for each τ ∈ R⋆ , only one τ ′ ∈ B(τ ), and nothing more. W(D⋆ ) denotes the set of possible worlds. ■
Proof of Theorem 1.
A
Theorem 1 follows from Proposition 1 and the #P -hardness of BCQ evaluation on TIDs [Suciu et al.,2011].
Appendix
Definition 6. Consider an MG M and an observed instance D⋆ for schema S ⋆ , and R⋆ a relation in D⋆ with schema R(Āo , Ā⋆ ), where Āo , Ā⋆ are lists of fully observed and possibly taking na attributes, resp. Let τ be a tuple ⋆ in R⋆ , and τ [Āo , Ā′ ] its restriction to those ⋆ attributes without an na, with Ā′ ⊆ Ā⋆ .
Proposition 1. For a fixed underlying schema S and BCQ Q, there is an observed schema S ⋆ , a qualitative MG M, and a BCQ Q′ , such that: For every TID D for S, an observed DB D⋆ for the observed schema S ⋆ and a distribution on M can be built in PTIME in |D|, such that
18
Q[D] = Q′ [Dp (D⋆ , M)].
■ attributes for R⋆ ).
Proposition 1 above shows that arbitrary TIDs can be recovered as special cases of the kind of BIDs arising from our data semantics. In fact, we establish a more general statement, in Proposition 2: Any BID can be obtained from a corresponding observed D⋆ and an MG M. Before going into this result, we show an example that illustrates Proposition 1. R τ1 τ2
A a a′
B b b′
P p1 p2
S A τ3 a τ4 b τ5 b′ S ⋆ Ao τ3 a τ4 b τ5 b′
P p3 p4 p5 M2⋆ na na na
Table 11: (a) Initial TID. observed DB.
R⋆ τ1 τ2
Ao a a′
Bo b b′
We need to define appropriate distributions in the MG, in such a way that we obtain column P in Figure 3(b). For example, for the first probability in that column, it should be: p1 = p(τ11 ) := P (M1m = 1|A = a, B = b, M1⋆ = na). Ao
Bo IM1
M1m
M1⋆ na na
M 1* Rp τ11 τ12 τ21 τ22
A a a a′ a′
B b b b′ b′
M1 1 0 1 0
P p1 (1 − p1 ) p2 (1 − p2 )
Figure 3: (a) Missingness graph. (b) Associated sulting BID.
(b) Re-
For this MG, the probabilities are calculated as in Example 6, obtaining, for example, for the tuples in the first block of Rp : Example 12. Consider schema S = {R(A, B), S(B)} for a the TID in Table 11(a). The schema for the associated observed DB with MVs is S ⋆ = {R(Ao , B o , M1⋆ ), S(B o , M2⋆ )}. Attributes ⋆ ⋆ M1 , M2 may exhbit MVs, and dom(M1m ) = dom(M2m ) = {0, 1}. Table 11(a) shows the initial TID that we want to represent as a BID, which we will obtain by first creating the observed instance in Table 11(b). We concentrate on table R. In order to obtain the BID, which should be the one in Figure 3(b), we use, for R⋆ , the MG in Figure 3(a) (showing only the
p(τ11 )
=
P M (M1m = 1|A = a, B = b) × P M (A = a, B = b),
p(τ21 )
=
P M (M1m = 0|A = a, B = b) × P M (A = a, B = b).
Accordingly, we define the probabilities in the MG in such a way that p(τ11 ) = p1 , p(τ21 ) = (1 − p1 ), etc. Now, consider the query posed to the original TID: Q : ∃x∃y(R(x, y) ∧ S(y)). In order to pose the query to the BID, rewrite it into: Q′ : ∃x∃y(R(x, y, 1) ∧ S(y, 1)), and we answer it via the BID. ■ Now, towards Proposition 2, we first introduce a notion of equivalence between BIDs
19
that ensures their sets of possible worlds, such that, for every world W ∈ W and every along with the associated probabilities, co- tuple τ ∈ D: incide. (a) τ ∈ W if and only if g(τ ) ∈ h(W ); Definition 7. (Equivalence of BIDs) Let D ■ and D′ be two BID instances over the same (b) p(W ) = p h(W ) . ′ schema, and let B and B denote their respective sets of blocks. We say that D and D′ are Hence, if D ≡ D′ , then the two instances equivalent, denoted D ≡ D′ , if there exist biare indistinguishable with respect to query jections answering, as every query returns exactly the ′ ′ same answers (with the same probabilities) f :B→B and g:D→D on both. such that, for every block B ∈ B: Using the notion of equivalence, we show that for every BID instance, there exist an ob(a) g restricts to a bijection from B onto served instance and an MG whose associated f (B); BID is equivalent to the original one. (b) for every tuple τ ∈ B, we have τ ↓= Proposition 2. For any BID instance g(τ )↓; D over a schema S, there are an (ob(c) for every tuple τ ∈ B, served) instance D⋆ for a schema S ⋆ and an MG M, such that, for the BID Dp dePB (τ ) = Pf (B) g(τ ) , termined by D⋆ and M, it holds: D ≡ Dp . ■ where PB (τ ) denotes the probability of Proof: Let D be a BID instance over a τ in block B. schema S consisting of n blocks B1 , . . . , Bn , where each bloc Bi contains a set of tuples When we wish to make the witnessing f,g bijections explicit, we write D ≡ D′ . ■ ti1 , . . . , t1mi . W.l.o.g., we assume that the schema S consists of a single attribute T that As a direct consequence of Definition 7, encodes each tuple. Formally, let S = {T}, tij ∈ Bi , we define tij [T] = equivalence of BID instances preserves their and for every j “t ”. Let p denote the probability of tuple ij i possible-world semantics. tj in block Bi . By the definition of a BID, we ′ Corollary 1. Let D and D be two BID have: f,g
instances such that D ≡ D′ , and let W and W ′ be their respective sets of possible worlds. Then there exists a bijection h : W → W′
mi X pji = 1 for each i ∈ {1, . . . , n} j=1
Figure 4 shows the BID D. 20
ure 5, contains one row JBj i for each tuple tj in block Bi . Each row is defined as follows:
bloc id tuple id T P B1 τ11 t11 p11 ... ... ... m1 τ1 t1m1 p1m1 ... ... ... 1 Bn τn tn1 p1n ... ... ... τnmn tnmn pnmn
JBj i [T m ] = tj , JBj i [Am l ] = in(tj , Bl ),
( 0 if tj ∈ Bl , where in(tj , Bl ) = 1 otherwise, ( 1 if tj ∈ Bl , JBj i [A∗l ] = na otherwise, ( 0 if tj ∈ Bl , JBj i [I Al ] = 1 otherwise.
Figure 4: A arbitrary BID B
To construct the proof, we start with a BID D over a schema S = {T} and, in polynomial time, build an incomplete database D∗ , an MG M, and a join distribution P M . From this construction, we derive a BID instance Dp ≡ D. The database D∗ is defined over the schema {T ∗ , A∗1 , . . . , A∗n }. The attribute T has domain dom(T ) = {t1 , . . . , tn }, while each attribute Ai (for i ∈ {1, . . . , n}) has domain dom(Ai ) = [0, 1]. Each attribute Ai encodes the block Bi . For example, a tuple t in Dp with t[T ] = “t” and t[A1 ] = t[A3 ] = 1 encodes the fact that the tuple t belongs to blocks B1 and B3 . The database D∗ contains n tuples τBi , each corresponding to a block Bi in the BID. Each tuple τBi has value 1 for the attribute Ai and the value na for all the other attributes; that is, τBi [Ai ] = 1 and τBi [T] = τBi [Aj ] = na, ∀j ̸= i. See Figure 7 for an illustration of D∗ . The MG M, shown in Figure 8, encodes the dependency structure between attributes in the incomplete database. Specifically, M specifies that the value of the attribute T depends on the values of the attributes A∗i . The join distribution P M , illustrated in Fig-
The probability associated with each row is pji j Pr(JBi ) = . n
These probabilities are normalized, ensuring that |Bi | n X X P M (JBj i ) = 1. i=1 j=1
The BID instance Dp , derived from (D∗ , M, P M ) is illustrated in Figure 6. It contains a block f (τBi ) for each incomplete tuple τBi in D∗ . Each block f (τBi ) consists of tuples τBj i , which correspond to the possible completions of τBi , derived from tuples tj encoded in Dp .
21
f (τBn )
τBn ... τBn1
t1 ... tn
A1,1 ... A1,n
... ... ...
1 ... 1
pn ... pnn
Bi
l
j JB [A∗l ] = i
Figure 6: The derived BID Dp
The proba
tuple id Tm Am 1 1 JB1 t1 in(t1 , B1 ) ... ... ... n JB1 tn in(tn , B1 ) ... ... ... n JBn tn in(tn , Bn )
bloc_id T∗ A∗1 . . . A∗n τB1 na 1 na na ... ... ... ... ... ∗ n IA1 τ.B. n. A∗nna IAna Tna IT1 Prob
... Am A∗1 n p11 . . . in(t1 , Bn ) 1 0 . . . na 1 na 1 ∗n Figure 7: The incomplete database D ... ... ... ... ... ... ... ... ... ... pn 1 . . . in(tn , Bn ) 1 0 . . . na 1 na 1 n ... ... ... ... ... ... ... ... ... ... pn n . . . in(tn , Bndatabase. ) na Specifically, 1 . . . 1M specifies 0 nathat1the value n of the
These pro
attribute T depends on the values of the attributes A∗i .
Figure 5: The join distribution P M
Am 1
I A1
The BID lustrated i incomplet tuples τBj i τBi , deriv P M (τBj i ) Dp is com
IT
A∗1
bloc id tuple id T A1 f (τB1 ) t1 1 τB1 1 ... ... ... n τB1 tn 1 ... 1 ... ... f (τBn ) τB1 n t1 A1,1 ... ... ... τBn1 tn A1,n
Am 2
I A2
. . . An P . . . An,1 p11 ... ... ... . . . An,n pn1 ... ... ... ... 1 p1n ... ... ... ... 1 pnn
.. .
Tm
T∗
A∗2 .. .
.. .
P M (τBj
Am n
I An A∗n
Figure MGMM Figure8:8: The The MG
Figure 6: The derived BID Dp
The probability P M (τBj i ) assigned to a tuple The jjoin distribution P M , illustratedp in Figure 5, contains τ i in block Bi of the BID D is computed as j one Brow JB for each tuple tj in block Bi . Each row is i follows: defined as follows: P bloc id τB1 ... τBn
∗
A∗1
T na 1 ... ... na na
A∗n
... na na ... ... na 1
n ^ j M m m nd (τBi ) = toP the 42T Conference = tj Submitted onA Uncertainty inl ), Artificial Intelligence l ∈ (tj , B l=1 ∗
M
T = na,
A∗i = 1, I Ai = 0, ^ A∗l = na,
Figure 7: The incomplete database D∗
l̸=i
^ l̸=i
22
From the
I Al = 1
(12)
From the MG M, T m depends only on A∗l , Hence, we conclude that D ≡ Dp . for l ∈ [1, n]. Hence, we can simplify the conditional probability to: P M (τBj i ) = P M (T m = tj | A∗i = 1, =
P
M
^
A∗l = na)
l̸=i
V
■
Proof of Theorem 2. The results in Theorem 2 are obtained
(T = tj , A∗i = 1, l̸=i A∗l = na)through a reduction of the MCC-problem V to a particular case of “minimum cost flow P M (A∗i = 1, l̸=i A∗l = na) problem” in bipartite graphs. The key insight
pji n = P n l pi n l=1
m
pji = P = pji n pli l=1
(13) The following lemma establishes that the transformation from a BID instance B to the derived instance Dp via the intermediate construction (D∗ , M, P M ) preserves the probabilistic semantics over the original schema S. Lemma 1. Let D be an arbitrary BID over a schema S = {T}. Let D∗ , M, and the join distribution P M be constructed from D as described above. Then, we have Dp ≡ B, where Dp is the BID derived from D∗ , M, and P M . Proof: Let Bi , with i ∈ {1, . . . , n}, denote the blocks in the BID D. By construction, the mapping f which assigns each block Bi in B to the block f (τBi ) in Dp is bijective. Additionally, there is a one-to-one correspondence between the tuples in each block Bi and those in the corresponding block B(τBi ), such that: τij ∈ Bi with τij [T] = ”tj ” and p(τij ) = pji ⇔
is that finding a most-compliant class corresponds to solving an min cost flow problem where blocks are matched to tuple multiplicities, while minimizing the distance objective. We formalize the reduction of MCC problem to a minimum cost flow problem. The reduction constructs a flow network whose feasible integral flows are in one-to-one correspondence with the BID possible worlds, and the cost of a flow equals the compliance distance of the corresponding class-vector. MCC-Problem Setup. Let D⋆ be an observed instance, M its associated MG and P M the induced join distribution. An instance of the MCC problem is given by: • A set of blocks B = {B1 , . . . , Bn } of the corresponding BID Dp . • A set of tuples T = {t1 , . . . , tm }. • For each block Bi and tuple tj , a probability pi (tj ) ∈ [0, 1].
The goal is to compute an admissible class⋆ vector k⋆ = (k1⋆ , . . . , km ) ∈ Nm that minimizes
τBj i ∈ B(τbi ) with τBj i [T] = ”tj ” and p(τBj i ) = pi j . 23
Ck⋆ ∈ argmin dc (Ck , M) , m
k∈N Pm j=1 kj =n
Flow Network Construction. From an MCC instance we construct a directed graph GDp = (V, E) with source s and sink t as follows.
flow conservation at all intermediate nodes (L ∪ R). For the source arcs, the lower bound forces fs,ui = 1 for every i; thus each block node sends exactly one unit of flow into the network. By flow conservation, that unit must travel along a middle arc to some tuple Nodes. node vj (with pi (tj ) > 0) and then to the sink via the corresponding sink arc. Consequently, V = {s} ∪ L ∪ R ∪ {t}, the flow values on the sink arcs determine a where vector • L = {ui | Bi ∈ B} is a set of block k(f ) = fv1 ,t , fv2 ,t , . . . , fvm ,t ∈ Nm , nodes in one-to-one correspondence with P which satisfies m the blocks. j=1 fvj ,t = n because each block contributes exactly one unit to the total • R = {vj | tj ∈ T } is a set of tuple outflow from s. nodes in one-to-one correspondence with the tuples. Cost. The cost of a flow f is defined solely in terms of the vector k(f ): Arcs. The edge set E = ES ∪ ELR ∪ ET consists of three layers:
Cost(f ) = dc Ck(f ) , M .
1. Source arcs: For each ui ∈ L, add an We now establish the formal correspondence arc (s, ui ) with lower bound ℓs,ui = 1 and between feasible integral flows in GDp and admissible class-vectors, and prove that an opcapacity cs,ui = 1. timal flow yields an optimal solution to the 2. Middle arcs: For each block Bi and MCC problem. tuple tj such that pi (tj ) > 0, add an arc Lemma 2. For every feasible integral flow (ui , vj ) with capacity cui ,vj = 1. f in GDp , the vector P k(f ) is an admissible 3. Sink arcs: For each vj ∈ R, add an class-vector (i.e., j kj = n and kj counts arc (vj , t) with capacity cvj ,t = degin (vj ), the number of blocks assigned to tuple tj ). where degin (vj ) denotes the number of Conversely, for every admissible class-vector incoming arcs to vj (i.e., the number of k, there exists a feasible integral flow f such blocks that can select tj ). that k(f ) = k. Proof: The forward direction follows from Flow. A feasible integral flow f assigns to the construction: each block ui sends one unit each arc a ∈ E a nonnegative integer fa sat- to some tuple vj , and the sink arc capacities isfying the lower bounds and capacities, and ensure that no tuple receives more than its 24
degree, which is automatically satisfied because each incoming edge to vj can carry at most one unit. Hence k(f ) is a vector of nonnegative integers summing Pto n. Conversely, given k with j kj = n, we need to assign each block to a tuple so that exactly kj blocks are assigned to tj . This is a feasible assignment if and only if for every tuple tj , the number of blocks that can select tj (i.e., deg(vj )) is at least kj . Since k arises from a valid assignment in the original MCC instance, this condition holds. Construct a flow by sending one unit from s to each ui , then from ui to the tuple node corresponding to its assigned tj , and finally from that tuple node to t. By construction all capacities and lower bounds are satisfied, yielding a feasible integral flow with k(f ) = k.
Complexity Analysis. We now analyze the computational complexity of solving the MCC problem via the minimum cost flow reduction. The complexity depends critically on the structure of the distance function dc . When dc is separable convex, it induces a separable convex cost on the sink arcs of the flow formulation. This places the problem within the class of minimum cost flow problems with separable convex costs, which can be solved in polynomial time [Minoux,1986].
Lemma 3. Let dc (·, M) be a convexseparable distance. For an MCC instance with n blocks and m tuples, an optimal admissible class-vector k⋆ can be computed polynomial time Proof: By construction, the network GDp has N = O(n + m + nm) edges and all capacities are integral and polynomially bounded Theorem 3. An optimal solution to the in the input size. Specifically: MCC instance is obtained by solving the minimum cost flow problem on GDp with objec• Source arcs: n edges with unit capacity. tive Cost(f ) = dc (Ck(f ) , M). Specifically, if f ⋆ minimizes Cost(f ) over all feasible integral • Middle arcs: at most n × m edges (only flows, then k(f ⋆ ) is an optimal class-vector where pi (tj ) > 0) with unit capacity. for the MCC instance. Proof: The lemma establishes a correspon• Sink arcs: m edges with capacity dence between feasible integral flows and addeg(vj ) ≤ n. missible class-vectors (the mapping is surjective, and two different flows can yield the The objective is to minimize a separable consame k only if multiple assignments give the vex cost function of the flow on the sink same counts, which does not affect the cost arcs. This is precisely a minimum-cost flow because it depends only on k). The cost of a problem with an edge-separable convex cost flow is exactly the compliance distance of the function [Minoux,1986]. The algorithm of corresponding class-vector. Therefore mini- [Minoux,1986] solves such problems for intemizing over flows is equivalent to minimizing gral flows on directed graphs in polynomial over class-vectors. time. 25
Proof: #MCC is #P-Complete. We prove that #MCC is #P-complete via the following two lemmas. Lemma 4 addresses membership in #P, and Lemma 5 establishes hardness. Lemma 4. Verifying whether a class Ck is an optimal solution to the MCC problem can be done in polynomial time. Consequently, the problem of counting the number of distinct optimal MCC classes, denoted #MCC, belongs to the complexity class #P. Proof: We establish polynomial-time verification through two independent checks, each reducible to classical network flow problems. Step 1: Admissibility. Given a candidate vector k = (k1 , . . . , km ) ∈ Nm with P m j=1 kj = n, we must determine whether there exists a feasible assignment of the n blocks to tuples such that exactly kj blocks are assigned to tuple tj . This is equivalent to checking whether the constructed flow network GDp admits a feasible integral flow f with fvj ,t = kj for all j. To test this, construct a modified network Gk from GDp by setting the capacity of each sink arc (vj , t) to kj (all other capacities remain as in GDp : unit capacities on source arcs and middle arcs). A feasible integral flow of value n in Gk exists iff k is admissible, because such a flow saturates all source arcs (each block sends one unit) and exactly meets the prescribed outflows at the sink. The network Gk has O(n + m) nodes and O(nm) edges. Computing its maximum flow value can be done in polynomial time using, e.g., Dinic’s algorithm [Dinic,1970], which
√ runs in O( n, |E|) for unit-capacity bipartite networks. Hence admissibility is decidable in polynomial time. Step 2: Optimality. Let dmin denote the minimum compliance distance for the given MCC instance. By Lemma 3, an optimal class-vector can be computed in polynomial time (specifically, O((nm)1+o(1) log m log C)), so dmin can be obtained efficiently. Once dmin is known, verifying whether Ck is optimal reduces to computing its compliance distance dc (Ck , M) and checking whether dc (Ck , M) = dmin . The compliance distance depends only on k and the fixed instance parameters, and is assumed computable in polynomial time (as is typical for distance functions in such settings). Thus optimality can be checked in polynomial time. Since both steps run in polynomial time, the decision problem “Is k an optimal MCC class?” belongs to the class P and therefore #MCC is in #P. Lemma 5. #MCC is #P-hard. Proof: We prove hardness by a polynomialtime reduction from the problem of counting perfect matchings in 3-regular bipartite graphs, which is known to be #P-complete. Let G = (U ∪ V, E) be a 3-regular bipartite graph with |U | = |V | = n. We construct a p BID DG and a join distribution PGM as follows.
26
• Tuples. For each edge (ui , vj ) ∈ E, create a distinct tuple ti,j . Let T = {ti,j : (ui , vj ) ∈ E} be the set of all tuples. Since G is 3-regular, |U | = |V | = n
and each vertex has degree 3, we have We consider a convex separable distance |T | = 3n. function of the form
m X • Primary blocks (type B). For each d(Ck , M) = d kj , P M (tj ) , vertex ui ∈ U , define a block bi that conj=1 tains the tuples corresponding to its incident edges. Specifically, if ui is adjacent where kj denotes the number of occurrences to vj1 , vj2 , vj3 in G, then of tuple tj in the multiset Ck (i.e., in the class). We define d kj , P M (tj ) to be any bi = {ti,j1 , ti,j2 , ti,j3 }. convex function satisfying In each such block, the probability disd kj , P M (tj ) = 0 if kj ∈ {0, 1}, tribution is uniform: every tuple ti,j ∈ bi d kj , P M (tj ) > 0 if kj ≥ 2. is assigned probability pi (ti,j ) = 13 .
• Supplementary blocks (type S). For each vertex vj ∈ V , list its incident tuples in a fixed order, say ti1 ,j , ti2 ,j , ti3 ,j where (ui1 , vj ), (ui2 , vj ), (ui3 , vj ) ∈ E. Add two supplementary blocks sj,1 and sj,2 . The block sj,1 contains the two consecutive tuples ti1 ,j and ti2 ,j , and the block sj,2 contains the two consecutive tuples ti2 ,j and ti3 ,j . In each supplementary block, the probability distribution is uniform: every tuple in the block has probability 21 . Consequently, each tuple ti,j belongs to exactly one primary block bi and to either one or two supplementary blocks: specifically, ti1 ,j belongs only to sj,1 ; ti2 ,j belongs to both sj,1 and sj,2 ; and ti3 ,j belongs only to sj,2 .
For instance, we can define ( 0, if k ≤ 1, d(k, p) = k − 1, if k ≥ 2,
which is convex in k (its discrete second differences are nonnegative) and independent of p (as p is uniform in our construction). In our setting, the join distribution PGM is uniform over all tuples, so the contribution of each tuple depends only on its occurrence count. Consequently, a class Ck with k = (k1 , . . . , k3n ) such that every kj ≤ 1—call such a class a 0/1 class—has zero cost and is therefore optimal whenever it is realizable. The structure of the supplementary blocks imposes a crucial constraint on 0/1 classes: for each vertex vj ∈ V , among its three in• Join distribution. The join distribu- cident tuples ti1 ,j , ti2 ,j , ti3 ,j , at most one can tion PGM is uniform over all tuples, i.e., be selected by a primary block. Indeed, if 1 two of these tuples were selected by primary for every t ∈ T . PGM (t) = 3n blocks, then at least one supplementary block This construction is clearly computable in would be forced to select a tuple already used, polynomial time in the size of G. creating an occurrence count of kj ≥ 2 and 27
thus positive cost. Moreover, if exactly one of these tuples is selected by a primary block, the supplementary blocks sj,1 and sj,2 have a unique valid assignment using the remaining two tuples, each exactly once. Conversely, if no tuple among the three is selected by a primary block, the supplementary blocks cannot both select distinct tuples without violating the 0/1 condition. Hence, in any realizable 0/1 class, for each vj exactly one of its three incident tuples is selected by a primary block, and the other two are assigned to the supplementary blocks in the unique forced manner. This property establishes a bijection between the set of 0/1 classes and the set of perfect matchings of the original 3-regular bipartite graph G. Specifically, each primary block bi (corresponding to ui ∈ U ) selects exactly one tuple, corresponding to an edge incident to ui . The condition that each vj has exactly one of its incident tuples selected by a primary block ensures that the selected edges form a matching that covers all vertices in V ; since |U | = |V | = n and each ui selects exactly one edge, this matching is perfect. Thus every perfect matching gives rise to a unique 0/1 class, and conversely every 0/1 class yields a perfect matching. A crucial observation is that, by the structure of the construction and the definition of the distance function, either all minimum-cost classes are 0/1 classes, or none of them are. This follows from the fact that the cost of any class is determined solely by the occurrence counts: if a 0/1 class exists, it attains cost zero, which is the global minimum, and any class with a tuple occurring more than once incurs a positive cost and therefore cannot be
an MCC. Conversely, if no 0/1 class exists, then every realizable class has at least one tuple with kj ≥ 2, yielding positive cost, and all such classes have the same minimum cost (by uniformity of the construction). Hence the number of minimum-cost classes (MCCs) p of (DG , PGM ) equals either the number of perfect matchings in G (when perfect matchings exist) or some constant independent of the graph’s matching structure (when no perfect matching exists). Since counting perfect matchings in 3-regular bipartite graphs is #P-complete, we conclude that #MCC is #P-hard. Proof: MCC-Enum is in DelayP. We outline a naive polynomial-delay algorithm for enumerating all the MCCs. The algorithm explores the vector space of MCCs in lexicographic order using a recursive depthfirst search. The search space can be represented as a rooted tree: • The root is labeled by the empty vector ∅. • The first level consists of nodes labeled 1, 2, . . . , m. • In general, the children of a node labeled by h are nodes labeled h0, h1, . . . , hn. Note that, at a level l, only correct vectors are generated: P namely those satisfying the constraint: lj=1 hj ≤ n.
A node at depth l encodes the vector v = (k1 , . . . , kl ) corresponding to the set of classes whose characteristic vectors begin with the
28
prefix (k1 , . . . , kl ). In particular, the leaves of the tree correspond bijectively to complete MCC vectors, i.e., to the classes themselves. The enumeration algorithm generates every MCC exactly once. Thus, the crux of ensuring polynomial delay lies in testing, at each step, whether an intermediate node is valid, i.e., whether it can lead to at least one MCC, before exploring its children. We now detail this validity check. First, compute the global minimum cost cmin of an optimal flow f GDp by solving a min cost flow in GDp (in polynomial time). An intermediate node h = (k1 , . . . , kl ) corresponds to the partial assignment where tuple tj (1 ≤ j ≤ l) is used exactly kj times. /h We then construct a new graph GDp from GDp by assigning to each arc (vj , t), for 1 ≤ j ≤ l, a lower bound and capacity given by ℓvj ,t = cvj ,t = kj . This enforces that each vj , for 1 ≤ j ≤ l, must be matched to exactly kj block nodes in L, thereby preserving only matchings consistent with h. A node h /h is valid if and only if GDp admits a minimal /h cost flow GDp equal to cmin . /h
Both the construction of GDp and the computation of the optimal cost can be performed in polynomial time. Overall, the enumeration visits at most O(mn) nodes between two consecutive MCCs.
29