Tutorial on Foundations of Probabilistic Answers to Queries

Опубликовано 6 сентября 2016, 5:44

Probabilistic query answering is a set of techniques used in several, very recent database applications: exploratory queries in databases, novel IR-style approaches to data integration, querying information extracted from the Web, queries over sensor networks, data acquisition, querying data sources that violate integrity constraints, controlling information disclosure in data exchange, and reasoning about privacy breaches. This is a surprisingly diverse range of applications, most of which have either emerged recently, or have seen a recent increased interest. They all share a common fundamental abstraction: that an item being a query answer is no longer a Boolean value, but a probabilistic event. This is a different paradigm to query answering, whose foundations lie in random graphs and probabilistic model theory. The results from these fields, and their relevance to the probabilistic query answering method, are little known in the database research community. This tutorial presents the applications, the foundations, and some processing techniques for probabilistic query answering. Goals: First, the tutorial gives a brief overview of the class of applications mentioned above and to highlight their underlying theme: that the answer to a query is a probabilistic, rather than a deterministic event. Second, it presents a simple definition for probabilistic query answers that will hopefully help researchers in the field adopt a unified framework. Third, it presents in an accessible fashion some of the relevant results from random graphs and probabilistic finite models, and highlights what they mean in the context of probabilistic query answering. Fourth, it describes several techniques, systems, and results from probabilistic databases. Target Audience: This tutorial is intended for both systems oriented and theoretical researchers interested in any of the applications mentioned above, or in exploring a new data management paradigm based on probabilities.