OLAP over uncertain and imprecise data
The VLDB JournalPublished 28 September 2006
Doug Burdick, Prasad Deshpande, T. S. Jayram, Raghu Ramakrishnan, Shivakumar Vaithyanathan
Citations178
SJR quartileQ1
SJR score1.18
SNIP2.29
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This is the first paper to handle both imprecision and uncertainty in an OLAP setting and identify three natural query properties and use them to shed light on alternative query semantics.
Abstract
We extend the OLAP data model to represent data ambiguity, specifically imprecision and uncertainty, and introduce an allocation-based approach to the semantics of aggregation queries over such data. We identify three natural query properties and use them to shed light on alternative query semantics. While there is much work on representing and querying ambiguous data, to our knowledge this is the first paper to handle both imprecision and uncertainty in an OLAP setting.
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Elements of Information Theory
37,533 Citations2001Thomas M. Cover, Joy A. Thomas
Statistical ScienceCombining Probability Distributions: A Critique and an Annotated Bibliography
1,000 Citations1986Christian Genest, James V. Zidek
A taxonomy of solutions is presented which serves as the framework for a survey of recent theoretical developments in the area and a number of current research directions are mentioned and an extensive, current annotated bibliography is included.
Consistent query answers in inconsistent databases
883 Citations1999Marcelo Arenas, Leopoldo Bertossi +1 more
The problem of the logical characterization of the notion of consistent answer in a relational database that may violate given integrity constraints is considered and its soundness and completeness are proved.
Evaluating probabilistic queries over imprecise data
578 Citations2003Reynold Cheng, Dmitri V. Kalashnikov +1 more
This paper addresses the important issue of measuring the quality of the answers to query evaluation based upon uncertain data, and provides algorithms for efficiently pulling data from relevant sensors or moving objects in order to improve thequality of the executing queries.
IEEE Transactions on Knowledge and Data EngineeringThe management of probabilistic data
451 Citations1992Daniel Barbará, Héctor García-Molina +1 more
A data model that includes probabilities associated with the values of the attributes, and the notion of missing probabilities is introduced for partially specified probability distributions, offers a richer descriptive language allowing the database to more accurately reflect the uncertain real world.
ACM Transactions on Information SystemsA probabilistic relational algebra for the integration of information retrieval and database systems
406 Citations1997Norbert Fuhr, Thomas Rölleke
The concept of vague predicates which yield probabilistic weights instead of Boolean values are introduced, thus allowing for queries with vague selection conditions and implements uncertainty and vagueness in combination with the relational model.
ACM Transactions on Database SystemsProbView
345 Citations1997Laks V. S. Lakshmanan, Nicola Leone +2 more
This article characterize, using postulates, whole classes of strategies for conjunction, disjunction, and negation, meaningful from the viewpoint of probability theory, and shows that as long as the chosen strategies can be computed in polynomial time, queries in the positive fragment of the probabilistic relational algebra have essentially the same data complexity as classical relational algebra.
Summarizability in OLAP and statistical data bases
292 Citations2002H. Lenz, Arie Shoshani
A framework for precisely specifying the context in which statistical objects are defined is introduced, which uses a three-step process to define normalized statistical objects.
Very Large Data BasesThe Theory of Probabilistic Databases
270 Citations1987Roger E. Cavallo, Michael Pittarelli
A new project-join mapping for relational databases that is based on transf orming a relational to a probabilistic database is defined and shown to have more fmed points than the standard one.
OLAP and statistical databases
171 Citations1997Arie Shoshani
It is argued for the support of a Statistical Object data type as one of the fundamental structures that object-oriented data models and systems should support.
On the representation and querying of sets of possible worlds
155 Citations1987Serge Abiteboul, Paris C. Kanellakis +1 more
The approach is algebraic but the authors' bounds also apply to logical databases, and it is shown that the approach is, in a sense, the best possible, by deriving two NP-completeness lower bounds for the bounded possible fact problem when the fixed query contains either negation or recursion.
Theoretical Computer ScienceScalar aggregation in inconsistent databases
144 Citations2003Marcelo Arenas, Leopoldo Bertossi +4 more
This work provides a complete characterization of the computational complexity of scalar aggregation queries in databases that may violate a given set of functional dependencies and shows how tractability can be improved in several special cases.
Expectation-Maximization as lower bound maximization
90 Citations1998Thomas P. Minka
This note derives EM from the lower bounding viewpoint Luttrell which better illustrates the convergence properties of the Expectation Maximization algorithm and its variants.
IEEE Transactions on Knowledge and Data EngineeringEvaluating aggregate operations over imprecise data
90 Citations1996A.L.P. Chen, Jui-Shang Chiu +1 more
A set of extended aggregate operations, namely sum, average, count, maximum, and minimum, are defined, which can be applied to an attribute containing partial values, and it is pointed out that in general it takes exponential time complexity to do the computations.
IEEE Transactions on Knowledge and Data EngineeringAggregation of imprecise and uncertain information in databases
88 Citations2001Sally McClean, Bryan Scotney +1 more
This work considers the problem of aggregation using an imprecise probability data model that allows us to represent imprecision by partial probabilities and uncertainty using probability distributions to perform the operations necessary for knowledge discovery in databases.
Journal of the ACMAggregate operators in probabilistic databases
81 Citations2005Robert Ross, V. S. Subrahmanian +1 more
This article devise a formal linear programming based semantics for computing aggregates over probabilistic DBMSs, develop algorithms that satisfy this semantics, analyze their complexity, and introduce several families of approximation algorithms that run in polynomial time.
ACM SIGMOD RecordAccommodating imprecision in database systems
70 Citations1990Amihai Motro
The major solutions for accommodating imprecision in database systems are reviewed, and issues that have yet to addressed are described, offering possible research directions.
Supporting imprecision in multidimensional databases using granularities
53 Citations2003Torben Bach Pedersen, Christian S. Jensen +1 more
Techniques for handling imprecision are developed that aim to maximally reuse existing OLAP modeling constructs such as dimension hierarchies and granularities, yielding an effective approach with low computational overhead and that may be implemented using current technology.
Data & Knowledge EngineeringGeneralized union and project operations for pooling uncertain and imprecise information
50 Citations1996David Bell, Jiao Guan +1 more
The idea here is to define a new combine operation as a primitive for handling inconsistency in relations, which uses the orthogonal sum, which generalizes results from traditional probability theory in a natural and correct manner, for pooling evidence during the combine computation.
OLAP databases and aggregation functions
46 Citations2002H. Lenz, Bernhard Thalheim
This work characterize the case where the aggregation functions can be correctly applied on macrodata (data cube) which are computed on the microdata.
Data & Knowledge EngineeringEvaluating aggregates in possibilistic relational databases
40 Citations1992Elke A. Rundensteiner, Lubomir Bic
This paper presents a framework for handling two types of aggregate operators, namely, scalar aggregates and aggregate functions, in the context of imprecise information and considers three cases, specifically, aggregates within vague queries on precise data, aggregate within precisely specified queries on possibilistic data.
ACM SIGKDD Explorations NewsletterLearning missing values from summary constraints
25 Citations2002Xintao Wu, Daniel Barbará
This paper uses linear algebra and constraint programming techniques to learn the missing values using apriori-known summary information and that derived from the raw data, and reconstruct theMissing values by different methods in three scenarios: ideal-constrained, under-conStrained, and over- Constrained.
Sources of Uncertainty, Imprecision, and Inconsistency in Information Systems
20 Citations1997Amihai Motro
An information system is a computer model that captures an abstracted version of the real world, using a level of abstraction that is implied by the expected applications, i.e., the accuracy of the representation.
Data & Knowledge EngineeringPSQL: A query language for probabilistic relational data
19 Citations1998Debabrata Dey, Sumit Sarkar
The contribution of this work is the development of a non-procedural probabilistic query language—structured around the popular SQL—that can be built on top of the conventional relational algebra.
Lecture notes in computer scienceLazy Aggregates for Real-Time OLAP
14 Citations1999Jukka Kiviniemi, Antoni Wolski +2 more
In OLAP models, or data cubes, aggregates have to be recalculated when the underlying base data changes, which may cause performance problems in real-time OLAP systems, which continuously accommodate huge amounts of measurement data.
Lecture notes in computer scienceModeling and Imputation of Large Incomplete Multidimensional Datasets
9 Citations2002Xintao Wu, Daniel Barbará
A two-part mixture model is proposed, which combines the logistic model and loglinear model together, to predict and impute the missing values in the measure dimension of data cube.
Lecture notes in computer scienceTopic Learning from Few Examples
3 Citations2003Huaiyu Zhu, Shivakumar Vaithyanathan +1 more
It is demonstrated that with very few positive examples, the semi-supervised algorithm performs better than training all layers in a single stage, and it is shown that the latter is equivalent to training a single layer model with corresponding parameters.