Probabilistic Object Bases
Probabilistic Object Bases
Files
Publication or External Link
Date
1999-11-23
Authors
Eiter, Thomas
Lu, James
Lukasiewicz, Thomas
Subrahmanian, V.S.
Advisor
Citation
DRUM DOI
Abstract
There are many applications where an object oriented data model is a
good way of representing and querying data. However, current object
database systems are unable to handle the case of objects whose
attributes are uncertain. In this paper, extending previous pioneering
work by Kornatzky and Shimony, we develop an extension of the
relational algebra to the case of object bases with uncertainty. We
propose concepts of consistency for such object bases, together with
an NP-completeness result, and classes of probabilistic object bases
for which consistency is polynomially checkable. In addition, as
certain operations involve conjunctions and disjunctions of events,
and as the probability of conjunctive and disjunctive events
depends both on the probabilities of the primitive events involved as
well as on what is known (if anything) about the relationship between
the events, we show how all our algebraic operations may be performed
under arbitrary probabilistic conjunction and disjunction
strategies. We also develop a host of equivalence results in our
algebra, which may be used as rewrite rules for query optimization.
Last but not least, we have developed a prototype probabilistic object
base server using the VisiBroker ORB on top of ObjectStore. We
describe experiments to assess the efficiency of different possible
rewrite rules.
(Also cross-referenced as UMIACS-TR-99-77)