"Heavy Tails and Web Models"
Prabhakar Raghavan (Yahoo! Research, USA)
The literature is rich with (re)discoveries of power law phenomena; this is especially true of observations of link and traffic behavior on the Web. We survey the origins of these phenomena and several (yet incomplete) attempts to model them. We then present a number of open problems in Web research arising from these observations.
"Managing Probabilistic Data with MystiQ:
The Can-Do, the Could-Do, and the Can't-Do"
Dan Suciu (University of Washington, USA)
MystiQ is a scalable probabilistic database system that allows users to keep their data in a relational database system and run SQL queries with probabilistic semantics. The main goal in MystiQ is to achieve scalability and performance for the probabilistic inference of SQL query evaluation. To achieve this, MystiQ incorporates several research results and techniques developed over the years at the University of Washington. In this talk I will describe how we transferred the research results into the MystiQ product: some results are fully integrated in MystiQ (the "can do"), others are not yet integrated but could be added to future versions or can be deployed manually by the administrator (the "could do"), yet other results are not yet complete and cannot be fully used in a general purpose probabilistic database system (the "can't do").
"Consistent Query Answering: The First Ten Years"
Jan Chomicki (State University of NY-Buffalo, USA)
The data in a database instance may be inconsistent (fail to satisfy
the integrity constraints) for a variety of reasons: it may be
erroneous, out of date, or come from mutually inconsistent sources.
In order to deal with inconsistency in a flexible manner, database research and practice have developed many different approaches. In this tutorial, we discuss a class of responses to inconsistency based on the notion of "repair": a consistent instance minimally different from the given one. We focus on "consistent query answering": computing query answers that are true in all repairs. These notions were introduced by Arenas, Bertossi, and Chomicki in their PODS'99 paper and extensively studied in follow-up research.
We address the following issues: (1) formal semantics of repairs and consistent query answers; (2) different methods for computing consistent query answers: query rewriting, space-efficient representation of repairs, and logic programming; (3) computational complexity analysis; (4) future directions.
Although proposals for repairing and consistent query answering exist also in the context of XML, we will focus on relational databases.