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 e cient 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 rst de ne 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 de nition. We rst present a formal de nition of the anti-join operator on U-relations such that the result is again a U-relation. Using the anti-join, we then de ne the semantics of the update operator on U-relations. New representations. Non-monotonous operators and updates can seriously compromise the space e ciency of U-relations. To address this problem, we introduce two generalizations of U-relations: (i) Ui-relations, which additionally allow inequalities in the descriptors of possible worlds; and (ii) Uint-relations, which allow intervals to specify ranges of the variables in descriptors of possible worlds. We prove that by using Ui-relations or Uint-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, Ui-relations, and Uint-relations. 2
Propositional Logic of Finite Domains. The formalism of U-relations uses
the logic known in the literature as propositional logic of nite domains, PLFD
[
Given an uncertain database B with a relational schema S, one can nd 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) 2 S with
key T in one or more vertical partitions U1; : : : ; Um with the schema (D; T ; Ai),
i = 1 : : : m where Ai is a subset of the attributes in A, and D stores the world-set
descriptors, or ws-descriptors, for short. In the original de nition of the
formalism of U-relations [
AGW D
D;A(U ) : JQ1 . Q2K :=
D1^D2 as D;T1;A1 U1 no negate(U2; A2)
D 6j=? where the condition of anti-join . and join no operators is A1 = A2: [ (U1 . U2); 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 e ciently implemented. Notation of Relational Operators. We use the extended form of the projection operator which supports computed attributes: e.g., A1+A2 as A0 (U ) is a unary relation whose attribute A0 is the sum of the attributes A1 and A2 in U . The anti-join operator (\where not exists") is denoted by the symbol .. The operator A1 Gf(A2)(U ) applies the aggregate function f to the set of attributes A2 of U , whereby the tuples of U are grouped by the values of attributes A1. 3
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. De nition 1. The anti-join R . P is the uncertain relation de ned, for each possible world w, by the expression Rw n (Rw >< P w).
Theorem 1. The translation in Fig. 1 satis es De nition 1.
Example 1. Consider the U-relation U = (D; T; A) consisting of the following tuples: hx = 1; t1; ai; hx = 2; t1; bi; hy = 1; t2; ai; hy = 2; t2; ci; hy = 3; t3; ai. The result U. of the relational expression T =t1 (U ) .A T 6=t1 (U ) is found as follows. U. contains all possible t1-tuples of U that do not match any possible t2;3tuples. This corresponds to the (U1 . U2) branch in Fig. 1. Such a tuple is hx = 2; t1; bi. Additionally, for t1-tuples that have matches in t2 or t3, the transformation of ws-descriptors using negate is needed. Such tuple is hx = 1; t1; ai. The call negate( T 6=t1 (U ); A) rst aggregates ws-descriptors of tuples that satisfy the condition A = a using _ and then passes the relation hy = 1 _ y = 3; ai to neg dnf clause. The latter function negates the aggregate ws-descriptor and transforms it to the DNF: provided that dom(y) = f1; 2; 3g, the resulting DNF has a single clause y = 2. Thus, the result of negate( T 6=t1 (U ); A) is fhy = 2; aig. The join ( T =t1 (U ) onA negate( T 6=t1 (U ); A)) followed by merging ws-descriptors with ^ thus gives hx = 1 ^ y = 2; t1; ai. Since (x = 1 ^ y = 2) 6j= ? holds, the result of the anti-join query U. is fhx = 1 ^ y = 2; t1; ai; hx = 1; t1; aig.
Important on its own right, the anti-join operator allows implementing updates of U-relations. Consider a general form GU of the update operator:
GU : update R set Ak = Q:Expr from Q on R Such update queries are supported by all major RDBMS's. GU updates an attribute Ak of a relation R = (A1; : : : ; Ak; : : : ; An) and allows to join R with some query Q serving as a source for the new value Expr of Ak. 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 QGU, which is a union of two queries, in which the former selects the updated tuples and the latter selects the unchanged ones: QGU :
A1;:::Ak 1;Expr;Ak+1;:::;An (R on Q) [ (R . Q) It is not di cult to show that no positive relational expression can express QGU. 4 4.1
Ws-descriptors with inequalities and intervals
As follows from the de nition 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 de nition of U-relations [
Now, consider the result of the relational expression B . fR(t; a; a; a)g. The entries with T = t in the U-relations should represent the remaining 26 possible values of t: V V V nfa; a; ag. After recombining R from U1;2;3 and subtracting fhx = 1 ^ y = 1 ^ z = 1; t; a; a; aig according to the de nition of ., U1 contains tuples hx = 1 ^ y = 2 ^ z = 1; t; ai; hx = 1 ^ y = 3 ^ z = 1; t; ai; hx = 1 ^ y = 1 ^ z = 2; t; ai; hx = 1 ^ y = 1 ^ z = 3; t; ai; hx = 2; t; bi; hx = 3; t; ci. U2 and U3 need to be updated accordingly. That is, 6 tuples with T = t per U-relation are now needed to represent the result of anti-join operator, instead of the 3 tuples per U-relation in B. One can show that for R with n attributes split into n U-relations, additional m (jV jn jV j) entries in each U-relation are needed to represent the deletion of one possible world with m tuples from B. 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 x 6= vi is a shorthand for (x = v1) _ : : : _ (x = vi 1) _ (x = vi+1) _ : : : _ (x = vm), where dom(x) = fv1; : : : ; vmg, which explains the source of increased space-e ciency of the new representation. The resulting formalism is called Ui-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 2 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 modi cation of U-relations is called Uint-relations. For instance, for vi 62 f0; ng, we can represent the formula x 6= vi by two triples (x; 0; vi 1) and (x; vi + 1; n). 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 Ui-relations the result of the anti-join B . fR(t; a; a; a)g from Example 2 can be expressed by exactly the same number of tuples as in B: U1 : hx = 1 ^ y 6= 1; t; ai; hx = 2; t; bi; hx = 3; t; ci, U2 : hy = 1 ^ x 6= 1 ^ z 6= 1; t; ai; hy = 2; t; bi; hy = 3; t; ci;
U3 : hz = 1 ^ x 6= 1 ^ y 6= 1; t; ai; hz = 2; t; bi; hz = 3; t; ci.
Extending ws-descriptors preserves the favorable properties of U-relations: Theorem 3. Positive relational algebra queries can be evaluated on U i- resp. Uint-relational databases in polynomial time data complexity.
Proof (Sketch). Evaluating positive RA operators on extended U-relations only
di ers from evaluating these operators on U-relations of [
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 2P -complete to decide whether a ws-descriptor S0 exists, such that jS0j < jSj and !(S) = !(S0).
Proof (Sketch). We show hardness by a reduction from the DNF minimization
problem Min-DNF( ; k) [
For membership, consider the following algorithm: guess a set of ws-descriptors S0 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 2 !(S) and w 2= !(S0) or vice versa. The check itself is feasible in polynomial time. 5
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 [
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 e ectiveness of these heuristics. A systematic investigation of such methods and further experiments with extending U-relations, enabling e cient 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.