2007/07/11 by Lyublena Antova, Thomas Jansen, Antova, Lyublena +5
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #H.2.1 #H.2.4 #Performance (cs.PF) #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.0707.1644
openalex publication_date 2007/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.