{'fraction_non_alphanumeric': 0.03662628810776077, 'fraction_numerical': 0.009781289416692448, 'mean_word_length': 4.475632004169924, 'pattern_counts': {'":': 1, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fast and Simple Relational Processing of Uncertain Data

This paper introduces U-relations, a succinct and purely relational representation system for uncertain databases. U-relations support attribute-level uncertainty using vertical partitioning. If we consider positive relational algebra extended by an operation for computing possible answers, a query on the logical level can be translated into, and evaluated as, a single relational algebra query on the U-relation representation. The translation scheme essentially preserves the size of the query in terms of number of operations and, in particular, number of joins. Standard techniques employed in off-the-shelf relational database management systems are effective for optimizing and processing queries on U-relations. In our experiments we show that query evaluation on U-relations scales to large amounts of data with high degrees of uncertainty.


Introduction
Several recent works [10,9,8,2,14,4,6] aim at developing scalable representation systems and query processing techniques for large collections of uncertain data as they arise in data cleaning, Web data management, and scientific databases. Most of them are based on a possible worlds semantics, and for all of them such a semantics can be conveniently defined.
Four desiderata for representation systems for incomplete information appear important. 1. Expressiveness. The representation should be closed under the application of (relational algebra) queries and data cleaning algorithms (which remove some possible worlds). That is, the results of such operations to the represented data should be again representable within the formalism. 2. Succinctness. It should be possible to represent large sets of alternative worlds using fairly little space.

Efficient query evaluation.
A trade-off is required between the succinctness of a representation formalism and the complexity of evaluating interesting queries. This tradeoff follows from established theoretical results [1,11,6].
However, while the formalisms in the literature tend to differ in succinctness, several have polynomial-time data complexity for (decision) problems such as tuple possibility under positive (but not full) relational algebra. This includes vtables [12,11], uncertainty-lineage databases (ULDBs) [8], and world-set decompositions (WSDs) [6]. 4. Ease of use for developers and researchers in the sense that the representation system can be easily put on top of a relational DBMS. This in particular includes that queries on the logical schema level can be translated down to, ideally, relational algebra queries on the representation relations and that this translation is simple and easy to implement. This goal is motivated by the availability and maturity of existing relational database technology.
An important aspect of a representation system is whether it represents uncertainty at the attribute-level or the tuple-level. Attribute-level representation refers to the succinct representation of relations in which two or more fields of the same tuple can independently take alternative values (see also [6]). Attribute-level representation of uncertainty (as supported by c-tables [12] and WSDs) offers finer granularity of independence than tuple-level approaches such as [8,10,2]. This is useful in applications like data cleaning in which the values of several fields of a single tuple can be independently uncertain. For instance, the U.S. Census Bureau maintains relations with dozens of columns (> 50), most of which may require cleaning [4].

U-relations.
In this paper, we develop and study U-relations, a representation system that we introduce with the following example. Example 1.1. Let us assume that an aerial photograph of a battlefield shows four vehicles at distinct positions 1 to 4. The resolution of the image does not allow for the identification of vehicle types, but we can draw certain conclusions from earlier reconnaissance and a calculation of the maximum distance each vehicle may have covered since. Say we know that vehicle 1 is (a) a friendly tank. Vehicles 2 and 3 are (b) a friendly transport and (c) an enemy tank, but we do not know which one is which. Nothing is known about  vehicle 4. Figure 1a shows a schematic drawing of how this scenario can arise. Only 1 is in the range of (a); 2 and 3 are in the ranges of (b) and (c); and position 4 is near the border of the photograph but outside the ranges of (a), (b), and (c), so this vehicle must have newly moved onto the map.
We want to model this by an uncertain database of schema R(Id, Coord, Type, Faction), representing the ids (1)(2)(3)(4), coordinate positions, types, and factions of the vehicles on the map. Let us assume there are only two vehicle types (tank or transport) and two factions (friend or enemy). Then there are eight possible worlds. We obtain one by taking three choices -answering the following questions: Has the friendly transport (b) now become vehicle 2 (x → 1) or 3 (x → 2)? Is vehicle 4 a tank (y → 1) or a transport (y → 2)? Is vehicle 4 friendly (z → 1) or an enemy (z → 2)? Thus the uncertainty can be naturally modelled using three variables x, y, z that each can independently take one of two values.
We model this scenario by the U-relational database shown in Figure 1b. We use vertical partitioning (cf. e.g. [7,15]) to achieve attribute-level representation. R is represented using four U-relations, one for each column of R. The U-relation for the coordinate positions (which are all certain) is not shown since we do not want to use it subsequently, but of course, conceptually, coordinate positions are an important feature of the example and have to be part of the schema. In addition there is a relation W which defines the possible values the three variables can take.
We can compute a vertical decomposition of one world given by a valuation θ of the variables x, y, z by (*) removing all the tuples from the U-relations whose D columns contain assignments that are inconsistent with θ (For example, if θ = {x → 1, y → 1, z → 1} then we remove the third and fifth tuples of U 1 and the fifth tuples of U 2 and U 3 .) and then (*) projecting the D columns away. Of course we can resolve the vertical partitioning by joining the decomposed relations on the tuple id columns T R . U-relations have the following properties: • Expressiveness: U-relations are complete for finite sets of possible worlds, that is, they allow for the representation of any finite world-set. • Succinctness: U-relations represent uncertainty on the attribute level. Even though they allow for more efficient query evaluation, U-relations are, as we show, exponentially more succinct than ULDBs and WSDs. That is, there are (relevant) world-sets that necessarily take exponentially more space to represent by ULDBs or WSDs than by U-relations. • Leveraging RDBMS technology: U-relations allow for a large class of queries (positive relational algebra extended by the operation "possible") to be processed using relational algebra only, and thus efficiently in the size of the data. Our approach is the first so far to achieve this for the above-named query language. Indeed, this not only settles that there is a succinct and complete attribute-level representation for which the so-called tuple Q-possibility problem for positive relational algebra is in polynomial time (previously open [6]) but puts a rich body of research results and technology at our disposal for building uncertain database systems.
This makes U-relations the most efficient and scalable approach to managing uncertain databases to date. • Parsimonious translation: The translation from relational algebra expressions on the logical schema level to query plans on the physical representations replaces a selection by a selection, a projection by a projection, a join by a join (however, with a more intricate join condition), and a "possible" operation by a projection. We have observed that state-of-the-art RDBMS do well at finding efficient query plans for such physical-level queries.

Ease of use:
A main strength of U-relations is their simplicity and low "cost of ownership": • The representation system is purely relational and in close analogy with relational representation schemes for vertically decomposed data. Apart from the column store relations that represent the actual data, there is only a single auxiliary relation W (which we need for computing certain answers, but not for possible answers). • Query evaluation can be fully expressed in relational algebra. The translation is quite simple and can even be done by hand, at least for moderately-sized queries. • The query plans obtained by our translation scheme are usually handled well by the query optimizers of off-theshelf relational DBMS, so the implementation of special operators and optimizer extensions is not strictly needed for acceptable performance.
Thus U-relations are not only suited as a representation system for dedicated uncertain database implementations such as MayBMS [4], but are also relevant to "casual users" of representation systems for uncertain data, such as researchers in data cleaning and data integration who want to store and query uncertain data without great effort.
Apart from those implicitly mentioned above, we make the following further contributions in this paper.
• We study algebraic query optimization and present equivalences that hold on vertically decomposed representations. We address query optimization using them in the context of managing uncertainty with U-relations. • We present an algorithm for normalizing a U-relational representation obtained from a query. Normalized Urelational databases yield a conceptually simple algorithm for computing the certain answers of queries. In particular, certain answer tuples on normalized tuplelevel representations can be computed using relational algebra only, which is not true in general for previous representation systems. • We provide experimental evidence for the efficiency and relevance of our approach.
The structure of the paper is as follows. Section 2 establishes U-relations formally. Section 3 presents our reduction from queries on the logical level to relational algebra on the level of U-relations and addresses algebraic query evaluation. Section 4 presents the normalization algorithm. Section 5 discusses the relationship between Urelations, WSDs and ULDBs and argues that U-relations combine the advantages of the other two formalisms without sharing their drawbacks. In Section 6, we report on our experiments with U-relations. We conclude with Section 7.

U-relational databases
We define world-sets in close analogy to the case of ctables [12]. Consider a finite set of variables over finite domains. A possible world is represented by a total valuation (or assignment) f :Var → Rng of variables to constants in their domains, and the world-set is represented by the finite set of all total valuations 1 . We represent relationally the variable set and the associated domains by a world-  Figure 1 defines three variables x, y, z, whose common domain is {1, 2}. The number of worlds defined by W is 2 · 2 · 2 = 8.
Given a world-table W, a world-set descriptor over W, or ws-descriptor for short, is a valuation d such that its graph is a subset of W. If d is a total valuation, then it represents one world. In our examples, to represent the entire world-set we use an empty ws-descriptor, as a shortcut for a singleton wsdescriptor with a new variable with a singleton domain.
We are now ready to define databases of U-relations.
A ws-descriptor {c 1 → l 1 , . . . , c k → l k } is relationally encoded in π Di,j (U i, j ) of arity n ≥ k as a tuple (c 1 → l 1 , . . . , c k → l k , c k+1 → l k+1 , . . . , c n → l n ), where each c i → l i is a c j → l j for any j and all i with 1 ≤ j ≤ k < i ≤ n.
Although we speak of vertical partitioning, we do not require the value columns of U i, j to disjointly partition the columns of R i . Indeed, overlap may be useful to speed up query evaluation, see e.g. [15].
We next define the semantics of a U-relational database. To obtain a possible world we first choose a total valuation f over W. We then process the U-relations tuple by tuple.
If the function f extends 2 the ws-descriptor d of a tuple of the form (d, t, a) from a U-relation of schema (D, T , A), we insert in that world the values a into the A-fields of the tuple with identifier t. In general this may leave some tuples partial in the end (i.e., the values for some fields have not been provided.) These tuples are removed from the world.
We require, for a U-relational database (U 1 , . . . , U n , W) to be considered valid, that the representation does not provide several contradictory values for a tuple field in the same world. Formally, we require, for all 1 ≤ i, j ≤ n, and tuples t 1 ∈ U i [D i , T i , A i ] and t 2 ∈ U j [D j , T j , A j ] such that U i and U j are vertical partitions of the same relation, that if there is a world that extends both t 1 .D i and t 2 .D j , then for Then U 1 and U 2 cannot form part of a valid U-relational database because there would be a world with c 1 → 1, c 2 → 2 in which the tuple from U 1 requires field t 1 .B to take value b while the tuple from U 2 requires the same field to take value b'.
A salient property of U-relational databases is that they form a complete representation system for finite world-sets.

Query Processing
The semantics of a query Q on a world-set is to evaluate Q in each world. For complete representation systems like U-relational databases, there is an equivalent, more efficient approach [12]: Translate Q into a queryQ such that the evaluation ofQ on a U-relational encoding of the world-set produces the U-relational encoding of the answer to Q.
Queries on vertical decompositions. U-relations rely essentially on vertical decomposition for succinct (attributelevel) representation of uncertainty. To evaluate a query, we first need to reconstruct relations from vertical decompositions by (1) joining two partitions on the common tuple id attributes and (2) discarding the combinations that yield inconsistent ws-descriptors. We call this operation merge and give its precise definition in Figure 4, where the two above conditions are defined by α and ψ, respectively. The query σ Faction= ′ Enemy ′ ∧Type= ′ Tank ′ (R) lists the enemy tanks on the map. To answer this query, we need to merge the necessary partitions of R and obtain a new query with merge(π Faction (R), π Type (R)) in the place of R.
Our query evaluation approach can take full advantage of query evaluation and optimization techniques on vertical partitions. First, it does not require to reconstruct the entire relations involved in the query, but rather only the necessary vertical partitions. Second, necessary partitions can be flexibly merged in during query evaluation. Thus early and late tuple materialization [15] carry over naturally to our framework. For this, our merge operator allows to merge two partitions not only if they are given in their original form, but also if they have been modified by queries.
The first advantage only holds for so-called reduced Urelational databases, which do not have tuples that cannot be completed in any world. That is, each tuple of a reduced U-relation can always be completed to an actual tuple in a world. The advantage becomes evident even for a simple projection query. Consider a reduced database containing a U-relation U defining the A attribute of R. To evaluate π A (R) we do not need to merge in all U-relations defining the attributes of R and later project on A. Instead, the answer is simply U. In the following, we assume that the input database is always reduced. As we will discuss next, our query evaluation technique always produces reduced Urelations for reduced input U-relational databases.

Example 3.2.
Consider the following non-reduced database of two U-relations: In each U-relation the second tuple cannot find a partner in the other U-relation with which a complete tuple (with both where sch(R) = A, sch(S ) = B attributes A and B) can be formed. If these second tuples are removed, the database is reduced.
We can always reduce a U-relational database as follows: We filter each U-relation using semijoins with each of the other U-relations representing data of the same relation R i . The semijoin conditions are the α and ψ-conditions.

Proposition 3.3. Given a schema Σ, there is a relational algebra query that reduces a U-relational database over Σ.
Algebraic equivalences. Figure 2 gives algebraic equivalences of relational algebra expressions with merge operator on vertical decompositions: Merging is the reverse of vertical partitioning, it is commutative and associative, it commutes with selections, joins, and projections.
Standard heuristics known from classical query optimization for relational algebra apply here as well. Intuitively, we usually push down projections and selections and merge in U-relations as late as possible. An interesting new case is the decision on join ordering among an explicit join from the input query and a join due to merging: If the merge is executed before the explicit join, it may reduce the size of an input relation to join. We have seen in our experiments that the standard selectivity-based cost measures employed by relational database management systems do a good job, as long as the queries remain reasonably small. Example 3.4. Consider a U-relational database U that represents a set of possible worlds over two TPC-H relations Ord and Cust (short for Order and Customer, respectively) [16]. U has one U-relation for each attribute of the two relations, of which we only list DATE and CUSTKEY for Ord, and NAME and CUSTKEY for Cust. The following query finds all dates of orders placed by Al after 2003: Query plan P3. P1 first reconstructs Ord from its two partitions then applies the selection and the join with Cust. In P2 and P3 the merge operator is pushed up in the plans, first immediately above the selection (P2), and then above the join operator (P3). Among the three plans, P1 is clearly the least efficient.
However, without statistics about the data, one cannot tell which of P2 and P3 should be preferred. If DATE>2003 is very selective, then merging immediately thereafter as in P2 will lead to filtering of tuples from π CUSTKEY (Ord) and thus fewer tuples will be processed by the join. Is this not the case, then first merging only increases the number and size of the tuples that have to be processed by the join. Also, in P3 all value attributes except of DATE are projected away after the join as they are not needed for the final result.
Queries on U-relations. Figure 4 gives the function [[·]] that translates positive relational algebra queries with poss and merge operators into relational algebra queries on Urelational databases. The poss operator applied on a U-relation U closes the possible worlds semantics by computing the set of tuples possible in U. It thus translates to a simple projection on the value attributes of U. The result of a projection is a U-relation whose value attributes are those from the projection list (thus the input ws-descriptors and tuple ids are preserved). Selections apply conditions on the value attributes.
The merge operator that reconstructs a relation from its vertical partitions was already explained. Similarly to the merge, the join uses the ψ-condition to discard tuple combinations with inconsistent ws-descriptors. Figure 4 gives the translation in case U 1 and U 2 do not contain partitions of the same relation. For the case of self-joins we require aliases for the copies of the relation involved in it such that they do not have common tuple id attributes.
The union of U 1 and U 2 like the ones from Figure 4 is sketched next. We assume that A 1 = A 2 , T 1 ∩ T 2 = ∅, and the tuples of different relations have different ids. To bring U 1 and U 2 to the same schema, we first ensure wsdescriptors of the same size by pumping in the smaller wsdescriptors already contained variable assignments, and add new (empty) columns T 2 to U 1 and T 1 to U 2 . We then perform the standard union.
From our translation [[·]] it immediately follows that Theorem 3.5. Positive relational algebra queries extended with the possible operator can be evaluated on U-relational databases using relational algebra only.
Example 3.6. Recall the U-relational database of Figure 1 storing information about moving vehicles. Consider a query asking for ids of enemy tanks: After merging the necessary partitions of relation R and translating it into positive relational algebra, we obtain where the conditions ψ 1 , ψ 2 , α 1 , and α 2 follow the translation given in Figure 4. The three vertical partitions are joined on the tuple id attributes (α 1 and α 2 ) and the combinations with conflicting mappings in the ws-descriptors are discarded (ψ 1 and ψ 2 ). Before and after translation, the query is subject to optimizations as discussed earlier. (In this case, a good query plan would first apply the selections on the partitions, then project away the irrelevant value attributes Type and Faction, and then merge the partitions).
The above U-relation U 4 encodes the query answer.
Example 3.7. We continue Example 3.6 and ask whether it is possible that the enemy has two tanks on the map, and if so, which vehicles are those. For this, we compute the pairs of enemy tanks as a self-join of S : (S s 1 ) ⊲⊳ s 1 .Id s 2 .Id (S s 2 ). This query is in turn equivalent to a self-join of U 4 .
The answer is encoded by the above U-relation U 5 . Note that the combinations of the first two tuples of U 4 are not in U 5 , because they have inconsistent ws-descriptors and are filtered out using the ψ-condition (vehicle c cannot be at the same time at two different positions). To obtain the possible pairs of vehicle ids, we apply the poss operator on U 5 . This is expressed as the projection on the value attributes of U 5 .
Our translation yields relational algebra queries, whose evaluation always produces tuple-level U-relations, i.e., Urelations without vertical decompositions, by joining and merging vertical partitions of relations. Following the definition of the merge operator, if the input U-relations are reduced, then the result of merging vertical partitions is also reduced. We thus have that

Normalization of U-relations
U-relations do not forbid large ws-descriptors. The ability to extend the size of ws-descriptors is what yields efficient query evaluation on U-relations. However, large wsdescriptors cause an inherent processing overhead. Also, after query evaluation or dependency chasing on a Urelational database, it may happen that tuple fields, which used to be dependent on each other, become independent. In such a case, it is desirable to optimize the world-set representation [6]. We next discuss one approach to normalize U-relational databases by reducing large ws-descriptors to ws-descriptors of size one. Normalization is an expensive operation per se, but it is not unrealistic to assume that uncertain data is initially in normal form [4,6] and can subsequently be maintained in this form. variable, whose domain becomes the product of the domains of the variables from that class. Figure 5 shows a U-relational database and its normalization.

Theorem 4.2. Given a reduced U-relational database, Algorithm 1 computes a normalized reduced U-relational database that represents the same world-set.
Computing certain answers. Given a set of possible worlds, we call a tuple certain iff it occurs in each of the worlds. It is known that the tuple certainty problem is coNP-hard for a number of representation systems, ranging from attribute-level ones like WSDs to tuple-level ones like ULDBs [6]. In case of tuple-level normalized U-relations, however, we can efficiently compute the certain tuples using relational algebra.

Succinctness and Efficiency
This section compares U-relational databases with WSDs [4,6] and ULDBs [8] using two yardsticks: succinctness, i.e., how compactly can they represent world-sets, and efficiency of query evaluation. WSDs vs. U-Relations. WSDs are essentially normalized U-relational databases where each variable c i of a Urelation corresponds to a WSD component relation C i and each domain value l i of c i corresponds to a tuple of C i . Figure 5(c) shows a WSD equivalent to a normalized Urelational database. The normalization may lead to an exponential blow-up in the database size and accounts for Urelations with arbitrarily large ws-descriptors being more compact than U-relations with singleton ws-descriptors and thus than WSDs.

Example 5.1. Consider a relation over schema R[AB]
where each field value can be 0 or 1, and t i .A and the tuple fields t (i+1) mod n .B depend on each other (1 ≤ i ≤ n). The encodings as WSD and as a set of two U-relations are given in Figure 6. Positive relational queries have polynomial data complexity for U-relations (Section 3) and exponential data complexity for WSDs [6]. This can be explained in close   analogy to the difference in succinctness and by the fact that query evaluation creates new dependencies [10]: Urelations can efficiently store the new dependencies by enlarging ws-descriptors, whereas WSDs correspond to Urelations with normalized ws-descriptors, hence the exponential blowup.

Example 5.3.
Consider the WSD and U-relations of Example 5.1 and the selection with join condition σ A=B (R). The answer is represented by the WSD and U-relation respectively shown in Figure 7. The U-relation U 3 has 2 · n tuples, whereas the WSD c 1 × · · · × c n has 2 n tuples, each representing a possible combination of the values of the existing fields (a tuple t i does not occur in worlds where t i .A or t i .B have values ⊥). Note that by normalizing U 3 we would also obtain one variable with 2 n domain values, as for the WSD. The answer to poss(σ A=B (R)) is efficiently computed as π A,B (U 3 ) in the case of U-relations. In the WSD case, it is computed as n ∪ i (π t i .A,t i .B (c 1 × · · · × c n )).
Finally, the query translations employed by the evaluation algorithms in the WSD and U-relational cases are different. Whereas for WSDs all operators are translated to sequences of relational queries and in the case of projection and join even to fixpoint programs [4], the translation remains strictly in relational algebra for U-relations.

ULDBs vs. U-Relations.
A ULDB relation is a set of x-tuples, where each x-tuple represents a set of alternatives. One world is defined by choosing precisely one alternative of each x-tuple. A world may contain none of the alternatives of an x-tuple, if this x-tuple is marked as optional (or maybe) using the ?-symbol. Dependencies between alternatives of different x-tuples are enforced using lineage: An alternative i of an x-tuple s occurs in the same worlds with an alternative j of another x-tuple t if the lineage of (s, i) points either to (t, j), or to another alternative that transitively points to (t, j). The lineage of an alternative can also point to an external symbol (t, j), if there is no alternative (t, j) in the database [8]. To construct an ULDB equivalent to the U-relational database of Figure 1, we have to enumerate all possible value combinations for the attributes of R. This enumeration is not necessary for U-relations because of vertical partitioning and the independence of (most) tuple fields.

Lemma 5.5. ULDBs [8] can be translated linearly into Urelational databases.
Proof. We sketch the proof for a single ULDB relation R; it can be extended trivially to the case of several relations.
For every x-tuple t in R we create a new variable c t , and for each alternative j of t we create a new domain value w (t, j) of c t . For every alternative in R with value a, id (t, j) and lineage λ(t, j) = n (t, j) i (t i , j i ) we create a tuple in U R with value a, tuple id t and ws-descriptor (n = n (t, j) ) w (t, j) ), (c t 1 , w (t 1 , j 1 ) ), . . . , (c t n , w (t n , j n ) )].
In case n (t, j) is smaller than n (s,l) of an alternative l of an xtuple s, then we pad the above ws-descriptor with n (s,l) −n (t, j) pairs (c t , w (t, j) ). There are U-relations, however, whose ULDB encodings are necessarily exponential in the arity of the logical relation. This is the case of, e.g., or-set relations [13], attribute-level representations that can be linearly encoded as U-relations but exponentially as ULDBs.
Theorem 5.6. U-relational databases are exponentially more succinct than ULDBs.
Both ULDBs and U-relations have polynomial data complexity for positive relational queries. Differently from ULDBs, evaluating queries on U-relations is possible using relational algebra only. The main difference between their evaluation algorithms concerns erroneous tuples, i.e., tuples that do not appear in any world. In contrast to Urelations, erroneous tuples may appear in the answers to queries on ULDBs (see [8] for an example). The removal of such tuples is called data minimization, an expensive operation that involves the computation of the transitive closure of lineage [8]. Such tuples occur with ULDBs because the lineage of an alternative in the answer only points to the lineage of alternatives from the input relations, even though these input alternatives may not occur in the same world. This cannot happen with U-relations because each query operation ensures that only valid tuples are in the query answer by (1) using the ψ-condition in the join and merge operations and by (2) carrying all dependencies in the wsdescriptors -and not only to tuples of the input relation.
To sum up, U-relations have the advantages of WSDs (attribute-level representation) and ULDBs (polynomial evaluation of positive relational algebra queries), while forming an exponentially more succinct representation system than both aforementioned approaches.

Experiments
Prototype Implementation. We implemented the query translator of Figure 4 and also extended the C implementation of the TPC-H population generator version 2.6 build 1 [16] to generate attribute and tuple-level U-relations and ULDBs. The code is available on the MayBMS project page (http://www.infosys.uni-sb.de/projects/maybms). Setup. The experiments were performed on a 3GHZ/1GB Pentium running Linux 2.6.13 and PostgreSQL 8.2.3. Generation of uncertain data. Our data generator creates eight tables: part, partsupp, supplier, customer, lineitem, orders, nation, region. The field values are sensitive to the attribute types and are randomly generated or randomly chosen from the dictionary explained in the TPC-H benchmark specification. The following parameters were used to tune the generation: scale (s), uncertainty ratio (x), correlation ratio (z), and maximum alternatives per field (m). The (dbgen standard) parameter s is used to control the size of each world; x controls the percentage of (uncertain) fields with several possible values, and m controls how many possible values can be assigned to a field. The parameter z defines a Zipf distribution for the variables with different dependent field counts 3  This assumption fits naturally to data cleaning scenarios. Previous work [4] shows that chasing dependencies on WSDs enforces correlations between field values and removes combinations that violate the dependencies. We considered here that after correlating two variables with arbitrary DFCs, 100(1 − p) percent of the combinations violate constraints and thus are dropped. The uncertain fields are assigned randomly to variables. This can lead to correlations between fields belonging to different tuples or even to different relations. This fits to scenarios where constraints are enforced across tuples or relations. We do not assume any kind of independence of our initial data as done in several other approaches [10,8].
Our data generator works as follows. While generating tuples for the eight tables, we use the uncertainty ratio to decide at each tuple field if it is uncertain or not. We collect in a field pool the coordinates (i.e., relation, tuple id, attribute) of the uncertain tuple fields and when the original TPC-H generator finishes its job or the field pool is full, we shuffle the uncertain tuple fields, compute the correlation ratio for variables with different DFC, and incrementally assign tuple fields to variables. Then, we compute the domain size of each variable, and the number of different values for each of variable's fields. The field values are then generated using the data distribution and dictionary for that field type, as specified by the original TPC-H generator. Because there can be too many field coordinates to keep in memory at a time, we use in our experiments a window of 10 million fields to be processed in bulk 4 ; after a window is processed, the memory is released, and a new window is filled in and processed. The window size influences the number and dependent field count of the variables. For the experiments, we fixed p to 0.25, m to 8, and varied the remaining parameters as follows: s ranges over An important property of our generator is that any world in a U-relational database shares the properties of the oneworld database generated by the original dbgen: The sizes of relations are the same and the join selectivities are approximately equal. We checked this by randomly choosing one world of the U-relational database and comparing the selectivities of joins on the keys of the TPC-H relations for different scale factors and uncertainty ratios. Queries. We used the three queries from Figure 8. Query Q 1 is a join of three relations of large sizes. Query Q 2 is a select-project query on the relation lineitem (the largest in our settings). Query Q 3 is a fairly complex query that involves joins between six relations. All queries use the operator 'possible' to retrieve the set of matches across all worlds. Note that these queries are modified versions of Q 3 , Q 6 , and Q 7 of TPC-H where all aggregations are dropped (dealing with aggregation is subject to future work). Figure 11 shows that our queries are moderately selective and their answer sizes increase with uncertainty x and marginally with correlation z. For scale 1, the answer sizes range from tens of thousands to tens of millions of tuples. There is only one setting (z = 0.25 and x = 0.1) where one of our queries, Q 3 , has an empty answer. Before the execution, the queries were optimized using our U-relation-aware optimizations. Figure 10 shows Q 1 after optimizations. Characteristics of U-relations. Following Figure 9, the U-relational databases are exponentially more succinct than databases representing all worlds individually: while the number of worlds increases exponentially (when varying the uncertainty ratio x), the database size increases only linearly. The case of x = 0 corresponds to one world generated using the original dbgen. Interestingly, to represent 10 8·10 6 worlds, the U-relational database needs about 6.7 times the size of one world.
An increase of the scaling factor leads to an exponential increase in the number of worlds and only to a linear increase in the size of the U-relational database. The maximum domain size of a variable is indirectly influenced by s: When s increases, there are more uncertain fields and thus more likely to obtain variables with more dependent fields. By our construction, the domain size of variables with higher DFC can be much larger than the maximum domain size of variables with DFC=1 (which is m = 8). This is because a variable with DFC=k has a fraction (p = 0.25) of the product of the domain values of k variables taken together. As shown in Figure 9, our settings have variables with domain sizes of up to 3392. Although we only report here on experiments with scale factors up to 1, further experiments confirmed that similar characteristics are obtained for larger scales, too. An increase of the correlation parameter leads to a moderate relative increase in the database size. When compared to one-world databases, the sizes of U-relational databases have increase factors that vary from 6.2 (for z = 0.1) to 8.2 (for z = 0.5). Query Evaluation on U-relations. We run four times our set of three queries on the 45 different datasets reported in Figure 9. For each query and correlation ratio, Figure 12 has a log-log scale diagram showing the median evaluation (including storage) time in seconds as a function of the scale and uncertainty parameters . The different lines in each of the diagrams correspond to different uncertainty ratios. Figure 12 shows that the evaluation of our queries is efficient and scalable. In our largest scenario, where the database has size 13 GB and represents 10 8·10 6 worlds with 1.4 GBs each world, query Q 3 involving five joins is evaluated in less than two and a half minutes. One explanation for the good performance is the use of attribute-level representation. This allows to first compute the joins locally using only the join attributes and later merge in the remaining attributes of interest. Another important reason for the efficiency is that due to the simplicity of our rewritings, Post-greSQL optimizes the queries in a fairly good way. Figure 13 shows an optimized query plan produced by the Post-greSQL 'explain' statement for the rewriting of Q 2 . The evaluation time varies linearly with all of our parameters. For Q 1 (Q 2 and Q 3 respectively) we witnessed a factor of up to 6 (4 and 10 respectively) in the evaluation time when varying the uncertainty ratio from 0.001 to 0.1. When the correlation ratio is varied from 0.1 to 0.5, the evaluation time increases by a factor of up to 3; this is also explained by the increase in the input and answer sizes, cf. Figures 9 and 11. When the scale parameter is varied from 0.01 to 1, the evaluation time increases by a factor of up to 400; in case of Q 3 and z = 0.5, we also noticed some outliers where the increase factor is around 1000. The considerably smaller evaluation time for Q 3 in case of scale 1, uncertainty 0.1, and correlation 0.25 occurs because for that scenario no 'GERMANY' entry is generated for the nation table, thus the query answer is empty.

Effect of attribute-level representation.
We also performed query evaluation on tuple-level U-relations, which represent the same world-set as the attribute-level Urelations of Figure 9, and on Trio's ULDBs [8] obtained by a (rather direct) mapping from the tuple-level U-relations. To date, Trio has no native support for the poss operator or the removal of erroneous tuples in the query answer, though this effect can be obtained as part of the confidence computation 5 . For that reason, we decided to compare the evaluation times of queries without the poss operator and without the (expensive) removal of erroneous tuples or confidence computation (which is an exponential-time problem). Since our data exhibits a high degree of (randomly generated) dependency, its ULDB representation has lineage and thus join queries can introduce erroneous tuples in the answer. The Trio prototype was set to use the (faster) SPI interface of PostgreSQL (and not its default python implementation).  Figure 14 compares the evaluation time on attribute-and tuple-level U-relations in MayBMS, and ULDBs for small scenarios of 1% uncertainty, our lowest correlation factor 0.1, and scale up to 0.1. On attribute-level U-relations, the queries perform several times better than on tuple-level Urelations and by an order of magnitude better than ULDBs. This is because attribute-level data allows for late materialization: selections and joins can be performed locally and tuple reconstruction is done only for successful tuples. We witnessed that an increase in any of our parameters would create prohibitively large (exponential in the arity) tuplelevel representations. For example, for scale 0.01 and uncertainty 10%, relation lineitem contains more than 15M tuples compared to 80K in each of its vertical partitions.

Conclusion and Future Work
This paper introduces U-relational databases, a simple representation system for uncertain data that combines the advantages of existing systems, like ULDBs and WSDs, without sharing their drawbacks. U-relations are exponentially more succinct than both WSDs and ULDBs. Positive relational algebra queries are evaluated purely relationally on U-relations, a property not shared by any other previous succinct representation system. Also, U-relations are a simple formalism which poses a small burden on implementors.
We next briefly report on two current research directions. Probabilistic U-relations. U-relational databases can be elegantly extended to model probabilistic information by just adding a probability column P to the world table W. For each variable x, the sum of the values π P (σ Var=x )(W) must equal one. We can then assign probability to any subset of the world-set, described by a ws-descriptor d, as the product of probabilities of each variable assignment in d.
The techniques for evaluating the operations of positive relational algebra presented in this paper are applicable in the probabilistic case without changes. Computing the confidences of the answer tuples is an inherently hard problem [10]. Our current research investigates practical approximation techniques for confidence computation. Support for new language constructs. Following our recent investigation on uncertainty-aware language constructs beyond relational algebra [5], we identified common physical operators needed to implement many primitives for the creation and grouping of worlds. It appears that normalizing sets of ws-descriptors in the sense of Section 4 plays an important role in evaluating these operations and in confidence computation. We are currently working on secondary-storage algorithms for normalization.