Source-linked AI summary
Fast and Simple Relational Processing of Uncertain Data
Lyublena Antova, Thomas Jansen, Christoph Koch, Dan Olteanu
TL;DR
Uncertain databases need representations that are expressive, succinct, and support efficient query evaluation. The paper introduces U-relations, using vertical partitioning and relational rewritings to process positive relational algebra with possible answers; U-relations are exponentially more succinct than ULDBs and WSDs, while queries are evaluated purely relationally.
Problem
Representation systems for incomplete information must balance expressiveness, succinctness, and efficient evaluation of relational queries.
Method
U-relations represent attribute-level uncertainty through vertical partitioning, and queries are translated into relational algebra over reconstructed partitions while discarding inconsistent world-set descriptors.
Results
U-relations are exponentially more succinct than WSDs and ULDBs, while positive relational algebra queries are evaluated purely relationally on the representation.
Takeaways & Limitations
U-relations combine succinct attribute-level uncertainty representation with query processing that can leverage standard relational database technology.
Takeaways & Limitations
Computing answer-tuple confidences is inherently hard, so practical approximation techniques remain under investigation.
Abstract
from arXiv · showhide
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.
1 Introduction
U-relations provide a complete, succinct, attribute-level representation of uncertain databases that can be queried using relational algebra and standard RDBMS technology.
- Motivation: U-relations address the need for expressive, succinct, efficiently queryable, and easily deployable representations of incomplete information.The introduction identifies these properties as important desiderata for uncertain-data systems.
- Motivation: Attribute-level uncertainty represents independently uncertain fields within the same tuple, supporting applications such as data cleaning across many columns.This finer granularity distinguishes attribute-level systems from tuple-level approaches.
- Representation: The representation uses vertical partitions for relation attributes plus an auxiliary world table, and partitions can be reconstructed by joining on tuple identifiers.This purely relational design supports query evaluation and implementation with existing database systems.
- U-relations: U-relations represent any finite set of possible worlds and are exponentially more succinct than ULDBs and WSDs.Their vertical partitioning supports attribute-level representation while retaining completeness.
- Query processing: U-relations translate positive relational algebra with possible-answer computation into relational algebra over the physical representation.Selections, projections, and joins remain corresponding operations, while possible-answer computation becomes a projection.
- Contributions: The paper contributes query-optimization equivalences, normalization for certain-answer computation, and experimental evidence of efficiency and relevance.The approach is presented as usable by both dedicated uncertain-database systems and researchers handling uncertain data.
2 U-relational databases
U-relational databases represent finite world-sets using relational world-tables, ws-descriptors, tuple ids, and vertically partitioned value relations. Their semantics selects tuples compatible with valuations, and the system is complete for finite world-sets.
- World-sets: A world-set is represented as the finite set of all total valuations of variables over finite domains.The world-table W stores each variable and its domain values as pairs (x, v).
- World-sets: A ws-descriptor is a partial valuation whose graph is contained in W, while a total valuation represents one possible world.An empty ws-descriptor can represent the entire world-set as a shortcut.
- U-relational databases: A U-relational database combines a world-table W with vertically partitioned relations carrying descriptors, tuple ids, and value attributes.Each descriptor column D_i,j encodes variable assignments, and T_R identifies tuples.
- U-relational databases: Vertical partitions need not be disjoint: overlapping value columns may be useful for speeding query evaluation.The representation permits overlap even though it is described as vertical partitioning.
- Semantics: A possible world is formed by choosing a total valuation and retaining values from tuples whose descriptors it extends; incomplete tuples are removed.Vertical decomposition can be resolved by joining partitions on tuple-id columns after filtering inconsistent assignments.
- Validity: U-relational databases must prevent contradictory values for the same tuple field when descriptors can coexist in one world.The validity condition is illustrated by conflicting values for a shared field across vertical partitions.
- Expressiveness: Any finite set of worlds can be represented as a U-relational database.This establishes completeness for finite world-sets.
3 Query Processing
Query processing reconstructs only the necessary vertical partitions and translates positive relational algebra with possible answers into relational algebra over U-relations. Merge, descriptor-consistency conditions, and standard optimization techniques support efficient evaluation.
- Vertical decompositions: The merge operation reconstructs relations by joining partitions on tuple ids and discarding combinations with inconsistent ws-descriptors.The conditions α enforce tuple-id matching, while ψ enforces descriptor consistency.
- Query evaluation: Queries need not reconstruct entire relations: only the necessary vertical partitions are merged during evaluation.This supports flexible tuple materialization and can apply even to simple projection queries on reduced databases.
- Reduction: A relational algebra query can reduce a U-relational database, and evaluating a positive query on a reduced database yields a reduced U-relational database.Reduction filters each U-relation using semijoins based on α- and ψ-conditions.
- Optimization: Merge is commutative and associative and commutes with selections, joins, and projections, enabling algebraic query-plan transformations.These equivalences support pushing selections and projections down and delaying merges when beneficial.
- Optimization: Among three equivalent plans, reconstructing Ord before selection and joining is least efficient; choosing between later merges depends on selectivity and statistics.If DATE>2003 is highly selective, merging immediately after selection can filter earlier.
- Query translation: Positive relational algebra queries extended with the possible operator can be evaluated on U-relational databases using relational algebra only.The translation maps possible to projection and preserves the corresponding relational operators, with modified join conditions where needed.
- Example: For enemy-tank queries, the translated plan selects and projects relevant partition attributes before merging them, while preserving descriptor-consistency checks.The resulting U-relation encodes the query answer.
4 Normalization of U-relations
Normalization converts U-relations with co-occurring variables into an equivalent representation whose ws-descriptors have size one. The algorithm preserves the represented world-set while producing a normalized reduced database.
- Trade-off: Normalization is expensive, but uncertain data may initially be in normal form and subsequently maintained in that form.
- Definition: A U-relational database is normalized when every ws-descriptor in its U-relations has size one.
- Normalization algorithm: Normalization replaces each connected class of variables that co-occur in ws-descriptors with one variable whose domain is their product.The classes are found from variable co-occurrence, using a graph and its connected components.
- Correctness: The normalization algorithm takes a reduced U-relational database as input and outputs a normalized reduced database representing the same world-set.
- Certain answers: Tuple certainty is generally coNP-hard for several representation systems, but it can be computed efficiently using relational algebra for tuple-level normalized U-relations.
5 Succinctness and Efficiency
U-relations combine attribute-level uncertainty with relational-algebra query processing and provide greater succinctness than WSDs and ULDBs. Their query evaluation remains polynomial for positive relational queries, while translations stay within relational algebra.
- WSDs vs. U-relations: U-relational databases are exponentially more succinct than WSDs.
- Query evaluation: Positive relational queries have polynomial data complexity for U-relations, compared with exponential data complexity for WSDs.U-relations store dependencies created during query evaluation by enlarging ws-descriptors, whereas normalized WSD-like representations can incur exponential blowup.
- Example comparison: A U-relation answer to σA=B(R) uses 2 · n tuples, whereas the corresponding WSD representation uses 2^n tuples.The U-relational answer is efficiently computed as πA,B(U3).
- Query evaluation: U-relations evaluate positive relational queries using relational algebra only, unlike WSD translations that can require fixpoint programs for projection and join.
- ULDBs vs. U-relations: U-relational databases are exponentially more succinct than ULDBs.
- Overall comparison: U-relations combine WSD attribute-level representation and ULDB polynomial evaluation while being exponentially more succinct than both.
6 Experiments
The experiments evaluate U-relations across scale, uncertainty, and correlation, finding scalable query processing and strong benefits from attribute-level representation. U-relational databases also represent exponentially many worlds with modest storage growth.
- Experimental setup: The generator creates uncertain TPC-H data with varying scale, uncertainty, correlation, and dependency factors while preserving one-world relation sizes and approximate join selectivities.Uncertain fields are randomly assigned to variables, allowing correlations across fields, tuples, and relations.
- Query answers: At scale 1, answer sizes range from tens of thousands to tens of millions of tuples and generally increase with uncertainty and correlation.Only one reported setting produced an empty answer for Q3.
- Representation size: Increasing the scaling factor causes an exponential increase in worlds but only a linear increase in U-relational database size.Variable domain sizes reached 3392 in the reported settings.
- Query evaluation: The largest 13 GB scenario represents 108·106 worlds with 1.4 GB each, while Q3 with five joins completes in less than two and a half minutes.Attribute-level representation supports local joins followed by late merging of remaining attributes, and PostgreSQL optimizes the rewritten queries effectively.
- Query evaluation: Evaluation time varies linearly with the parameters, increasing by up to 6×, 4×, and 10× for Q1, Q2, and Q3 when uncertainty rises from 0.001 to 0.1.Changing correlation from 0.1 to 0.5 increases evaluation time by up to 3×.
- Representation comparison: Attribute-level U-relations run several times faster than tuple-level U-relations and an order of magnitude faster than ULDBs in the tested small scenarios.Late materialization avoids constructing full tuples until successful tuples need reconstruction; tuple-level representations became prohibitively large.
7 Conclusion and Future Work
The paper concludes that U-relations combine succinctness, relational query processing, and a simple formalism for uncertain data. Future work extends them to probabilistic information and broader uncertainty-aware language constructs, while confidence computation remains difficult.
- Conclusion: U-relations are exponentially more succinct than WSDs and ULDBs, while positive relational algebra queries can be evaluated purely relationally.The conclusion presents these properties as central advantages over prior succinct representation systems.
- Future work: Probabilistic U-relations add a probability column to the world table, with variable assignments constrained to have probabilities summing to one.Probabilities of world-set descriptors are computed as products of the probabilities of their variable assignments.
- Future work: The positive relational algebra evaluation techniques apply unchanged to the probabilistic case, but computing answer-tuple confidences is inherently hard.The authors are investigating practical approximation techniques for confidence computation.
- Future work: Future language constructs require normalization of world-set descriptors, and secondary-storage algorithms for normalization remain under development.Normalization is identified as important for evaluating operations that create and group worlds and for confidence computation.