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

We present a decomposition-based approach to managing probabilistic information. We introduce world-set decompositions (WSDs), a space-efficient and complete representation system for finite sets of worlds. We study the problem of efficiently evaluating relational algebra queries on world-sets represented by WSDs. We also evaluate our technique experimentally in a large census data scenario and show that it is both scalable and efficient.

• Publication year

  2006

• Venue

  IEEE International Conference on Data Engineering

• Publication date

  2006-06-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00778-009-0149-yarXiv cs/0606075
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A compositional framework for complex queries over uncertain data

  2009influential reference
• Database Support for Probabilistic Attributes and Tuples

  2008cited by this paper
• Conditioning probabilistic databases

  2008cited by this paper
• Approximating predicates and expressive queries on probabilistic databases

  2008cited by this paper
• Worlds and Beyond : Effcient Representation and Processing of Incomplete Information

  2007cited by this paper
• Representing Tuple and Attribute Uncertainty in Probabilistic Databases

  2007cited by this paper
• World-set decompositions: Expressiveness and efficient algorithms

  2007influential reference
• From complete to incomplete information and back

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

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

  2007cited by this paper
• Fast and Simple Relational Processing of Uncertain Data

  2007influential reference
• Working Models for Uncertain Data

  2006cited by this paper
• Creating probabilistic databases from information extraction models

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

  2006influential reference
• ULDBs: databases with uncertainty and lineage

  2006cited by this paper
• Maybms: a Possible Worlds Base Management System

  2006cited by this paper
• Efficient Representation and Processing of Incomplete Information

  2006cited by this paper
• A cost-based model and effective heuristic for repairing constraints by value modification

  2005cited by this paper
• Probabilistic Databases : Where and How

  2005cited by this paper
• U-DBMS: A Database System for Managing Constantly-Evolving Data

  2005cited by this paper
• Trio: A System for Integrated Management of Data, Accuracy, and Lineage

  2004cited by this paper
• On the decidability and complexity of query answering over inconsistent and incomplete databases

  2003cited by this paper
• Potter's Wheel: An Interactive Data Cleaning System

  2001cited by this paper
• AJAX: an extensible data cleaning tool

  2000cited by this paper
• Data Cleaning: Problems and Current Approaches.

  2000cited by this paper
• Consistent query answers in inconsistent databases

  1999influential reference
• Foundations of Databases

  1994influential reference
• The Problem of Incomplete Information in Relational Databases

  1991cited 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

  1991cited by this paper
• Principles of Database and Knowledge-Base Systems, Volume II

  1988cited by this paper
• 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
• The complexity of relational query languages (Extended Abstract)

  1982cited by this paper
• Testing implications of data dependencies

  1979influential reference
• The theory of joins in relational data bases

  1977influential reference

• Tuple-Independent Representations of Infinite Probabilistic Databases

  2025cites this paper
• StarfishDB: A Query Execution Engine for Relational Probabilistic Programming

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

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

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

  2021cites this paper
• Tuple-Independent Representations of Infinite Probabilistic Databases

  2020cites this paper
• QSAN: A Quantum-probability based Signed Attention Network for Explainable False Information Detection

  2020cites this paper
• Independence in Infinite Probabilistic Databases

  2020cites this paper
• The Complexity of Counting Problems over Incomplete Databases

  2020cites this paper
• Managing Measurement and Occurrence Uncertainty in Complex Event Processing Systems

  2019cites this paper
• Counting Problems over Incomplete Databases

  2019cites this paper
• Updating Probabilistic Knowledge on Condition/Event Nets using Bayesian Networks

  2018cites this paper
• Indexing Uncertain Data

  2018cites this paper
• The Effect of Aging on Memory for Recent and Remote Egocentric and Allocentric Information

  2018cites this paper
• Missing values estimation for skylines in incomplete database

  2018cites this paper
• Combined geo-social search: computing top-k join queries over incomplete information

  2018cites this paper
• Stop the Truthiness and Just Be Wrong

  2017cites this paper
• Adaptive Schema Databases

  2017cites this paper
• Holistic Query Evaluation over Information Extraction Pipelines

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

  2016influential citation
• Evidence combination for incremental decision-making processes

  2016cites this paper
• Authentication of uncertain data based on k-means clustering

  2016cites this paper
• Integration of Probabilistic Uncertain Information

  2016cites this paper
• Uncertainty in the Last Mile

  2016influential citation
• An Improved Data Model for Uncertain Data

  2016cites this paper
• Duplicate Detection in Probabilistic Relational Databases

  2015cites this paper
• Modélisation sémantique du cloud computing : vers une composition de services DaaS à sémantique incertaine. (Semantic modeling for cloud computing : toward Daas service composition with uncertain semantics)

  2015cites this paper
• Entity resolution based EM for integrating heterogeneous distributed probabilistic data

  2015cites this paper
• Schema Integration Based Merging and Matching Algorithm for Agricultural HDDBs

  2015cites this paper
• Novel Semantics of the Top-k Queries on Uncertainly Fused Multi-Sensory Data

  2015cites this paper
• Composing Data Services with Uncertain Semantics

  2015cites this paper
• A Certainty-Based Model for Uncertain Databases

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

  2015cites this paper
• MAPPING DATA BETWEEN PROBABILITY SPACES IN PROBABILISTIC DATABASES

  2015cites this paper
• Self-Correlation and Maximum Independence in Finite Relations

  2015influential citation
• Belief Revision in Uncertain Data Integration

  2015cites this paper
• Query Analytics over Probabilistic Databases with Unmerged Duplicates

  2015cites this paper
• Data Services with uncertain and correlated semantics

  2014cites this paper
• Detecting the Temporal Context of Queries

  2014cites this paper
• Series Relational Database Schema Design for Uncertain Data

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

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

  2014cites this paper
• Deduction with Contradictions in Datalog

  2014cites this paper
• Managing Uncertainty and Conflicts in a Distributed World

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

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

  2014cites this paper
• A survey paper on Frame work for classification of uncertain data

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

  2014cites this paper
• Formalizing Data Quality and its Influence on Business Performance

  2013cites this paper
• Efficient Recovery of Missing Events

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

  2013cites this paper
• A compact representation for efficient uncertain-information integration

  2013cites this paper
• Efficient and scalable monitoring and summarization of large probabilistic data

  2013cites this paper
• Data exchange beyond complete data

  2013influential citation
• PossDB: An Uncertainty Data Management SystemBased on Conditional Tables

  2013cites this paper
• PossDB: An Uncertainty Database Management System

  2013cites this paper
• Efficient Summarization Techniques for Massive Data

  2013cites this paper
• Conditional Tables in practice

  2013cites this paper
• Privacy-Preserving and Usable Data Publishing and Analysis.

  2013cites this paper
• Entity resolution for distributed probabilistic data

  2013cites this paper
• Query Answering over Functional Dependency Repairs

  2013influential citation
• Normal Forms and Normalization for Probabilistic Databases under Sharp Constraints

  2013cites this paper
• A survey of queries over uncertain data

  2013cites this paper
• A Probabilistic Approach for GNN Queries in LBS

  2012cites this paper
• Aggregate Query Answering on Possibilistic Data with Cardinality Constraints

  2012cites this paper
• Querying Uncertain Minimum in Wireless Sensor Networks

  2012cites this paper
• The implication problem of data dependencies over SQL table definitions: Axiomatic, algorithmic and logical characterizations

  2012cites this paper
• Demonstration of the FDB Query Engine for Factorised Databases

  2012cites this paper
• Conflict Resolution in Online Databases *

  2012cites this paper
• Armstrong Databases: Validation, Communication and Consolidation of Conceptual Models with Perfect Test Data

  2012cites this paper
• Semantic Search over the Web

  2012cites this paper
• Bisque: Advances in Bioimage Databases

  2012cites this paper
• On the foundations of probabilistic information integration

  2012cites this paper
• An implementation of a temporal and spatial extension of RDF and SPARQL on top of MonetDB - phase I

  2012cites this paper
• Top-k entities query processing on uncertainly fused multi-sensory data

  2012cites this paper
• Incomplete Information in RDF

  2012cites this paper
• FDB: A Query Engine for Factorised Relational Databases

  2012cites this paper
• Ontology-Based Access to Probabilistic Data

  2012cites this paper
• Supporting Uncertainty in Standard Database Management Systems

  2012cites this paper
• Embracing Uncertainty in Entity Linking

  2012cites this paper
• Continuous Probabilistic Sum Queries in Wireless Sensor Networks with Ranges

  2012cites this paper
• D ec 2 01 2 Incomplete Information in RDF

  2012cites this paper
• Mining Fuzzy Association Rules from Heterogeneous Probabilistic Datasets

  2012cites this paper
• Incomplete Data and Data Dependencies in Relational Databases

  2012cites this paper
• Continuous Probabilistic Count Queries in Wireless Sensor Networks

  2011cites this paper
• Ranking queries on uncertain data

  2011cites this paper
• Chapter 3 Uncertainty in Spatial Trajectories

  2011cites this paper
• Representing and querying uncertain data with complex correlations

  2011cites this paper
• Probabilistic Databases

  2011cites this paper
• Probabilistic inverse ranking queries in uncertain databases

  2011cites this paper
• A Probabilistic Approach for Rendezvous Decisions with Uncertain Data

  2011cites this paper
• Provenance for aggregate queries

  2011cites this paper
• Computing with Spatial Trajectories

  2011cites this paper
• Incomplete information and certain answers in general data models

  2011cites this paper
• DBrev: Dreaming of a Database Revolution

  2011cites this paper
• Efficient Reasoning in Proper Knowledge Bases with Unknown Individuals

  2011cites this paper
• Combining intensional with extensional query evaluation in tuple independent probabilistic databases

  2011cites this paper
• Probabilistic databases

  2011cites this paper
• P-top-k Queries in a Probabilistic Framework from Information Extraction Models

  2011cites this paper
• Queries and materialized views on probabilistic databases

  2011cites this paper