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-relational 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.

• Publication year

  2007

• Venue

  IEEE International Conference on Data Engineering

• Publication date

  2007-07-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ICDE.2008.4497507arXiv 0707.1644
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Worlds and Beyond : Effcient Representation and Processing of Incomplete Information

  2007influential reference
• World-set decompositions: Expressiveness and efficient algorithms

  2007cited by this paper
• From complete to incomplete information and back

  2007cited by this paper
• Representing and Querying Correlated Tuples in Probabilistic Databases

  2007cited by this paper
• Efficient Top-k Query Evaluation on Probabilistic Data

  2007cited by this paper
• Clean Answers over Dirty Databases: A Probabilistic Approach

  2006cited by this paper
• ULDBs: databases with uncertainty and lineage

  2006influential reference
• $${10^{(10^{6})}}$$ worlds and beyond: efficient representation and processing of incomplete information

  2006influential reference
• U-DBMS: A Database System for Managing Constantly-Evolving Data

  2005cited by this paper
• C-Store: A Column-oriented DBMS

  2005cited by this paper
• Incomplete Objects - A Data Model for Design and Planning Applications

  1991cited by this paper
• Incomplete object—a data model for design and planning applications

  1991influential reference
• On the representation and querying of sets of possible worlds

  1987cited by this paper
• Dependency Satisfaction in Databases with Incomplete Information

  1984cited by this paper
• Incomplete Information in Relational Databases

  1984influential reference
• On searching transposed files

  1978cited by this paper
• The VLDB Journal manuscript No. (will be inserted by the editor)

  year unknowninfluential reference

• ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data

  2025cites this paper
• FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds

  2025cites this paper
• Marrying Top-k with Skyline Queries: Operators with Relaxed Preference Input and Controllable Output Size

  2024cites this paper
• Probabilistic Reasoning at Scale: Trigger Graphs to the Rescue

  2023cites this paper
• A Relational Data Model for Uncertain Data

  2022cites this paper
• Comparing modern techniques for querying data starting from top-k and skyline queries

  2022cites this paper
• Computing expected multiplicities for bag-TIDBs with bounded multiplicities

  2022cites this paper
• LinCQA: Faster Consistent Query Answering with Linear Time Guarantees

  2022cites this paper
• Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size

  2021cites this paper
• A probabilistic database approach to autoencoder-based data cleaning

  2021cites this paper
• Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds

  2021influential citation
• Probabilistic Counting in Uncertain Spatial Databases Using Generating Functions

  2021cites this paper
• Autoencoder-based cleaning in probabilistic databases

  2021cites this paper
• Consistent Answers of Aggregation Queries using SAT Solvers

  2021influential citation
• Benchmarking Approximate Consistent Query Answering

  2021cites this paper
• U4U - Taming Uncertainty with Uncertainty-Annotated Databases

  2021cites this paper
• Efficient Algorithm for Mining Probabilistic Frequent Itemsets of Uncertain Data

  2020cites this paper
• Uncertain Spatial Data Management: An Overview

  2020cites this paper
• AuthPDB: Authentication of Probabilistic Queries on Outsourced Uncertain Data

  2020cites this paper
• Complexity of fundamental problems in probabilistic abstract argumentation: Beyond independence

  2019cites this paper
• Uncertainty Annotated Databases - A Lightweight Approach for Approximating Certain Answers

  2019cites this paper
• VisPrAF: A system for visually specifying and reasoning over probabilistic abstract argumentation frameworks

  2019cites this paper
• Review Previous Solutions To Query Based Uncertain Object Determining

  2019cites this paper
• PgCuckoo: Laying Plan Eggs in PostgreSQL's Nest

  2019cites this paper
• An Efficient Approximation of Betweenness Centrality for Uncertain Graphs

  2019cites this paper
• AuthPDB: Query Authentication for Outsourced Probabilistic Databases

  2018cites this paper
• Recent Advances in Querying Probabilistic Knowledge Bases

  2018cites this paper
• Uncertainty Annotated Databases - A Lightweight Approach for Dealing with Uncertainty

  2018cites this paper
• Transforming Fuzzy Spatiotemporal Data From Relational Databases to XML

  2018cites this paper
• SIGMOD officers, committees, and awardees

  2018cites this paper
• Learning From Query-Answers

  2018influential citation
• Supporting Scientific Analytics under Data Uncertainty and Query Uncertainty

  2018influential citation
• Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings

  2018cites this paper
• Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning

  2017cites this paper
• Processing over Probabilistic Data

  2017cites this paper
• A literature study on clustering the uncertainty data

  2016cites this paper
• Cardinality Constraints for Probabilistic and Possibilistic Databases

  2016cites this paper
• Association Rules Discovery via Approximate Method from Probabilistic Database

  2016cites this paper
• On efficient conditioning of probabilistic relational databases

  2016cites this paper
• An Improved Data Model for Uncertain Data

  2016influential citation
• Searching and mining in enriched geo-spatial data

  2016cites this paper
• JudgeD: A Probabilistic Datalog with Dependencies

  2016cites this paper
• Probabilistic nearest neighbor query processing on distributed uncertain data

  2016cites this paper
• An uncertain data model construction method based on nonparametric estimation

  2016cites this paper
• Complex event processing over uncertain events: Techniques, challenges, and future directions

  2016cites this paper
• REQUEST AWARE STRENGTH OF CHARACTER OF INDEFINITE OBJECTS

  2016cites this paper
• Fusing uncertain data with probabilities

  2016cites this paper
• Evidence combination for incremental decision-making processes

  2016cites this paper
• Learning Tuple Probabilities

  2016cites this paper
• Integration of Probabilistic Information

  2016cites this paper
• Integration of Probabilistic Uncertain Information

  2016cites this paper
• Uncertainty in the Last Mile

  2016influential citation
• Efficient and flexible lineage construction for probabilistic databases

  2016cites this paper
• Soft Computing in Database and Information Management

  2015cites this paper
• Handling Uncertainty in Database: An Introduction and Brief Survey

  2015cites this paper
• Belief Revision in Uncertain Data Integration

  2015cites this paper
• Certain Answers over Incomplete XML Documents: Extending Tractability Boundary

  2015cites this paper
• Supporting Data Uncertainty in Array Databases

  2015cites this paper
• An Effective GPU-Based Approach to Probabilistic Query Confidence Computation

  2015cites this paper
• Predicting Rare Disease of Patient by Using Infrequent Weighted Itemset

  2015cites this paper
• Query Aware Determinization of Uncertain Objects

  2015cites this paper
• Effective Aggregation and Querying of Probabilistic RFID Data in a Location Tracking Context

  2015cites this paper
• Forecasting Unusual Infection of Patient used by Irregular Weighted Point Set

  2015cites this paper
• Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates

  2015cites this paper
• Managing large-scale scientific hypotheses as uncertain and probabilistic data

  2015cites this paper
• Probabilistic estimation of link travel times in dynamic road networks

  2015cites this paper
• Managing Uncertainty in Spatio-Temporal Series

  2015cites this paper
• Large scale mining and evidence combination to support medical diagnosis

  2015cites this paper
• Processing of Probabilistic Skyline Queries Using MapReduce

  2015cites this paper
• A Framework for Clustering Uncertain Data

  2015cites this paper
• Revisiting the formal foundation of Probabilistic Databases

  2015influential citation
• Efficient querying and learning in probabilistic and temporal databases

  2014cites this paper
• Uncertain Groupings: Probabilistic Combination of Grouping Data

  2014influential citation
• Managing Scientific Hypotheses as Data with Support for Predictive Analytics

  2014cites this paper
• Online filtering and uncertainty management techniques for rfid data processing

  2014cites this paper
• Privacy-preserving Sanitization in Data Sharing

  2014cites this paper
• MINING FREQUENT PATTERN USING PROBABILITY BASED INCREMENTAL DATABASE DISCOVERY

  2014cites this paper
• Approximation and Search Optimization on Massive Data Bases and Data Streams

  2014cites this paper
• Ranking distributed database in tuple-level uncertainty

  2014cites this paper
• The analytical bootstrap: a new method for fast error estimation in approximate query processing

  2014cites this paper
• Querying Uncertain Data in XML

  2014cites this paper
• Querying and Learning in Probabilistic Databases

  2014cites this paper
• A Survey of Uncertain Data Handling

  2014cites this paper
• Reasoning in many dimensions: uncertainty and products of modal logics

  2014influential citation
• Beyond Itemsets: Mining Frequent Featuresets over Structured Items

  2014cites this paper
• A framework for ranking uncertain distributed database

  2014cites this paper
• Semantics Representation of Probabilistic Data by Using Topk-Queries for Uncertain Data 1

  2014cites this paper
• Advanced Techniques for Mapping and Cleaning

  2014cites this paper
• Mapping and Cleaning: the LLUNATIC Way

  2014cites this paper
• Entity resolution for probabilistic data

  2014cites this paper
• Sum Query Evaluation over Uncertain Data

  2014cites this paper
• Learning Tuple Probabilities in Probabilistic Databases

  2014cites this paper
• Approximate Lifted Inference with Probabilistic Databases

  2014cites this paper
• Coping with distance and location dependencies in spatial, temporal and uncertain data

  2013cites this paper
• Exploiting Business Process Knowledge for Process Improvement

  2013cites this paper
• The Skyline of a Probabilistic Relation

  2013cites this paper
• Top-k query processing in probabilistic databases with non-materialized views

  2013influential citation
• Dealing with Uncertainty: A Survey of Theories and Practices

  2013cites this paper
• The LLUNATIC Data-Cleaning Framework

  2013cites this paper
• A possibility-theory-based model for relational databases containing uncertain attribute values

  2013cites this paper