Uncertain databases have evolved as an active area of database research, surveyed, for example, in [10].The possible worlds semantics [1] is commonly used to deal with uncertain data. Several representation systems for uncertain databases have been proposed to provide efficient storage and query facilities for a potentially big number of possible worlds, see, e.g., [14,4,8]. Antova et al. introduced U-relations [2], which guarantee polynomial data complexity for queries of positive relational algebra (RA, for short). U-relations have been implemented and are available in the MayBMS system [6].
As in the case of certain databases, we clearly also want to update uncertain databases and pose queries of unrestricted RA. In [3], an API for uncertain databases, which also covers updates, is presented. The paper mentions that, for updates, decompression of the succinct representation of the possible worlds may be necessary. However, it leaves open the details and also the question if decompression could at least partly be avoided by some extension of the representation system. While the evaluation of positive RA queries on uncertain databases has been studied extensively, there has been little work beyond positive RA, like queries with having clauses [7] and queries with one level of anti-join (not-exists [13]). Fink et al. [5] describe an approach for unrestricted RA queries, but in a formalism that does not exhibit polynomial time data complexity for computing possible answers.
The goal of this work is to start the investigation of the update problem of U-relations and to tackle the problem of evaluating queries with anti-joins over this formalism. To this end, we will first define the anti-join operator for U-relations and show how to use it to model updates. It will turn out that the decompression of the succinct representation of possible worlds may indeed be a performance problem. We will therefore introduce an extension of the Urelation representation system and show that our new formalism may lead to an exponential decrease in the representation of an updated uncertain database. Our main contributions will be as follows.
Formal definition. We first present a formal definition of the anti-join operator on U-relations such that the result is again a U-relation. Using the anti-join, we then define the semantics of the update operator on U-relations.
New representations. Non-monotonous operators and updates can seriously compromise the space efficiency of U-relations. To address this problem, we introduce two generalizations of U-relations: (i) U i -relations, which additionally allow inequalities in the descriptors of possible worlds; and (ii) U int -relations, which allow intervals to specify ranges of the variables in descriptors of possible worlds. We prove that by using U i -relations or U int -relations, the required storage and the complexity of query answering can drop exponentially. Complexity of optimization of world sets. We point out the intractability of a basic optimization problem for U-relations, U i -relations, and U int -relations.
Propositional Logic of Finite Domains. The formalism of U-relations uses the logic known in the literature as propositional logic of finite domains, PLFD [12]. It is an extension of propositional logic, in which each variable x is associated with a fixed set of constants called the domain of x, denoted dom(x). The atomic formulas in PLFD have the form x = v, where x is a variable and v ∈ dom(x) is a value from the domain of x. A PLFD interpretation (•) i assigns to each variable a value from its domain: (x = v) i = iff x i = v. The interpretations of complex formulas using the usual Boolean connectives ∧, ∨, →, ¬ are defined as usual. Possible worlds and U-relations. In the possible worlds semantics, an uncertain database can have multiple possible states called possible worlds. In the sequel, we will write P w to denote the state of the relation P in the possible world w. Two ideas are crucial for U-relations: (i) possible worlds are described by conjunctions of PLFD atoms, and (ii) vertical decomposition of relations may allow one to exponentially reduce the size of the representation of the possible worlds.
Given an uncertain database B with a relational schema S, one can find a set of PLFD variables W with accordingly chosen domains, so that each total valuation (•) i assigning a value to every variable in W corresponds to exactly one possible world in B. U-relations split each relation R = (T , A) ∈ S with key T in one or more vertical partitions U 1 , . . . , U m with the schema (D, T , A i ), i = 1 . . . m where A i is a subset of the attributes in A, and D stores the world-set descriptors, or ws-descriptors, for short. In the original definition of the formalism of U-relations [2], the world-set descriptors in D are simply conjunctions of PLFD atoms. Since possible worlds of B are associated with total valuations for variables in W , each world-set descriptor φ defines a set of possible worlds: namely, the worlds associated with the valuations that turn φ to . The relation R can be recombined from the partitions U 1 , . . . , U m by joining the tuples with consistent ws-descriptors over T . The semantics of the usual positive relational operators is a straightforward extension of the semantics of queries over a vertically partitioned database schema, projecting ws-descriptors along with the primary key columns: see [2] for a complete specification. The main difference is in the binary operators like cartesian product and join: they only allow combining tuples whose ws-descriptors are not contradictory. Importantly, unary
where the condition of anti-join and join operators is A1 = A2. operators do not alter ws-descriptors, whereas positive binary operators take a conjunction of the ws-descriptors of the relations passed as operands. Thus, positive relational operators on U-relations can be efficiently implemented. Notation of Relational Operators. We use the extended form of the projection operator π which supports computed attributes: e.g., π A1+A2 as A (U ) is a unary relation whose attribute A is the sum of the attributes A 1 and A 2 in U . The anti-join operator ("where not exists") is denoted by the symbol . The operator A1 G f (A2) (U ) applies the aggregate function f to the set of attributes A 2 of U , whereby the tuples of U are grouped by the values of attributes A 1 .
As pointed out in the previous section, U-relations allow for a natural implementation of positive relational operators. However, the non-monotonic operators over U-relations have not yet been considered. One such operator especially well-suited for U-relations, which must contain tuple ids, is the anti-join.
Definition 1. The anti-join R P is the uncertain relation defined, for each possible world w, by the expression R w \ (R w >< P w ).
U contains all possible t 1 -tuples of U that do not match any possible t 2,3tuples. This corresponds to the (U 1 U 2 ) branch in Fig. 1. Such a tuple is x = 2, t 1 , b . Additionally, for t 1 -tuples that have matches in t 2 or t 3 , the transformation of ws-descriptors using negate is needed. Such tuple is x = 1, t 1 , a . The call negate(σ T =t1 (U ), A) first aggregates ws-descriptors of tuples that satisfy the condition A = a using ∨ and then passes the relation y = 1 ∨ y = 3, a to neg dnf clause. The latter function negates the aggregate ws-descriptor and transforms it to the DNF: provided that dom(y) = {1, 2, 3}, the resulting DNF has a single clause y = 2. Thus, the result of negate(σ
The join (σ T =t1 (U ) A negate(σ T =t1 (U ), A)) followed by merging ws-descriptors with ∧ thus gives x = 1 ∧ y = 2, t 1 , a . Since (x = 1 ∧ y = 2) |= ⊥ holds, the result of the anti-join query
Important on its own right, the anti-join operator allows implementing updates of U-relations. Consider a general form GU of the update operator:
Such update queries are supported by all major RDBMS's. GU updates an attribute A k of a relation R = (A 1 , . . . , A k , . . . , A n ) and allows to join R with some query Q serving as a source for the new value Expr of A k . It is essential that the update be unambiguous, i.e. if a tuple in R has more than one join partner in Q then Expr must return the same value for all join partners. The update GU can be expressed as a query Q GU , which is a union of two queries, in which the former selects the updated tuples and the latter selects the unchanged ones:
It is not difficult to show that no positive relational expression can express Q GU .
As follows from the definition in Fig. 1 and from Example 1, the performance of anti-join on U-relations depends crucially on the function negate. In compliance with the definition of U-relations [2], this function produces ws-descriptors being conjunctions of PLFD atoms. In the presence of non-monotonic queries or updates such restricted form of ws-descriptors may prevent U-relations from delivering on the promise of representing possible worlds succinctly.
Example 2. Consider a schema R = (T, A 1 , . . . , A n ), where T is the key attribute, split into n U-relations U i = (D, T, A i ). Let B be an uncertain instance of relation R, and let the tuple t in R have possible values constructed by picking an arbitrary value from some fixed set of constants V for each attribute t.A i . Using the vertical partitioning in U-relations, the |V | n possible values of t can be represented by total n • |V | tuples in the U-relations U i , . . . , U n . E.g., for n = 3 and V = {a, b, c}, the following tuples in the U-relations are needed.
Now, consider the result of the relational expression B {R(t, a, a, a)}. The entries with T = t in the U-relations should represent the remaining 26 possible values of t: V ×V ×V \{a, a, a}. After recombining R from U 1,2,3 and subtracting We address this issue by allowing more expressive ws-descriptors.
• Iws-descriptors allow for inequalities along with equalities to be present in the conjunctive formulas. Thereby the PLFD formula
, where dom(x) = {v 1 , . . . , v m }, which explains the source of increased space-efficiency of the new representation. The resulting formalism is called U i -relations .
• Intws-descriptors replace equalities and inequalities with intervals of values which the given variable can take. An intws-descriptor is a set of triples (v, lo, hi) that consist of a variable v with a lower bound lo and an upper bound hi, such that lo ≤ hi, lo, hi ∈ dom(v) and such that each v occurs at most once in the set. It is assumed that the domain of v is 0 . . . n, for some integer n. The respective modification of U-relations is called U int -relations. For instance, for v i ∈ {0, n}, we can represent the formula x = v i by two triples (x, 0, v i − 1) and (x,
Theorem 2. There exist ws-descriptors whose negation represented as sets of iws-resp. intws-descriptors is exponentially more succinct than if represented as sets of ws-descriptors. For instance, using U i -relations the result of the anti-join B {R(t, a, a, a)} from Example 2 can be expressed by exactly the same number of tuples as in B:
Extending ws-descriptors preserves the favorable properties of U-relations:
Theorem 3. Positive relational algebra queries can be evaluated on U i -resp. U int -relational databases in polynomial time data complexity.
Proof (Sketch). Evaluating positive RA operators on extended U-relations only differs from evaluating these operators on U-relations of [2] in the consistency test of the binary operators: the tuples in two relations are only combined if the respective ws-descriptors are mutually consistent. That is, if the conjunction of two ws-descriptors is satisfiable. The satisfiability test is feasible in polynomial time in all three cases of U-relations, U i -relations and U int -relations. Therefore, the claim of the theorem follows from the result in [2] claiming that the problem of evaluating positive RA operators on U-relations has polynomial data complexity.
The performance of queries updates depends on the choice of the concrete expression representing the set of possible worlds. Below, we show that optimizing sets of ws-descriptors is intractable even without the extensions proposed above. Obviously, this intractability result also holds for U i -relations and U intrelations.
Proposition 1. Let S be a set of ws-descriptors occurring in a given U-relation U . Let ω(S) denote a set of all valuations which turn at least one ws-descriptor in S to . It is Σ P 2 -complete to decide whether a ws-descriptor S exists, such that |S | < |S| and ω(S) = ω(S ).
Proof (Sketch). We show hardness by a reduction from the DNF minimization problem Min-DNF(φ, k) [9] defined as follows:
Given a propositional formula φ in DNF and an integer k, is there a DNF formula equivalent to φ that contains k or fewer occurrences of literals?
This problem has been shown to be Σ P 2 -complete by Umans [11]. We encode an instance of Min-DNF(φ, k) as a problem in the claim of the theorem. Thereby each propositional variable x in φ gives rise to a fresh PLFD variable ẋ with domain {1, 2}, and each conjunctive clause in φ is encoded into a ws-descriptor by replacing the positive propositional literal x with the PLFD atom ẋ = 1 and each negative literal x with the PLFD atom ẋ = 2.
For membership, consider the following algorithm: guess a set of ws-descriptors S and check in polynomial time whether it contains at most k equalities (PLFD atoms). With a coNP oracle we check that there does not exist a valuation w such that w ∈ ω(S) and w / ∈ ω(S ) or vice versa. The check itself is feasible in polynomial time.
In this paper we have introduced two features of U-relations missing so far: the non-monotonous operator of anti-join and updates. Moreover, we have shown how the formalism of U-relations can be extended in order to improve the performance of these operations. We have also implemented our extensions on top of the open-source MayBMS system [6] and experimentally verified their efficiency. For example, Fig. 2 shows the impact of extended U-relations from Section 4 on the performance of both select and update queries, for various limits of possible values which uncertain tuple attributes can take.
To deal with the high worst-case complexity of optimizing U-relations, we have incorporated some easy heuristics that often lead to better representations (which are not guaranteed to be optimal, though). Our experiments show the effectiveness of these heuristics. A systematic investigation of such methods and further experiments with extending U-relations, enabling efficient support of updates and non-monotonic operators, remains a subject of future research.
Acknowledgements. This work has been supported by the Austrian Science Fund (FWF): P25207-N23.