tutorial-sigmod2005

Foundations of Probabilistic Answers to QueriesDan Suciu and Nilesh DalviUniversity of Washington1Databases Today are Deterministic• An item either is in the database or is not• A tuple either is in the query answer or is not• This applies to all variety of data models:– Relational, E/R, NF2, hierarchical, XML, …2What is a Probabilistic Database ?• “An item belongs to the database” is a probabilistic event• “A tuple is an answer to the query” is a probabilistic event• Can be extended to all data models; we discuss only probabilistic relational data3Two Types of Probabilistic Data• Database is deterministicQuery answers are probabilistic• Database is probabilisticQuery answers are probabilistic4Long HistoryProbabilistic relational databases have been studied from the late 80’s until today:• Cavallo&Pitarelli:1987• Barbara,Garcia-Molina, Porter:1992• Lakshmanan,Leone,Ross&Subrahmanian:1997• Fuhr&Roellke:1997• Dalvi&S:2004• Widom:20055So, Why Now ?Application pull:• The need to manage imprecisions in dataTechnology push:• Advances in query processing techniquesThe tutorial is built on these two themes6Application PullNeed to manage imprecisions in data• Many types: non-matching data values, imprecise queries, inconsistent data, misaligned schemas, etc, etcThe quest to manage imprecisions = major driving force in the database community• Ultimate cause for many research areas: data mining, semistructured data, schema matching ...