Kolloquiumsvortrag von Bertram Ludäscher

ABSTRACT. A query is a question about a concept. Given a graph database we might want to know, e.g., whether it has cycles or what triangles it contains (i.e., cyclic paths of length three). When asking a question of a database, i.e., evaluating a query on a given database instance, the system returns the answers, but no explanation why we got a particular answer or how the answer was derived from the given input instance. Database provenance research has focused on providing various levels of explanations for answers to positive database queries, culminating in an elegant theory of provenance semirings and provenance polynomials that unifies several earlier approaches. However, when asking complementary questions, e.g., "why are there no triangles in this graph", or similarly, asking how the answers to a query involving negation were obtained, provenance semiring approaches don't seem to be directly applicable and the situation is much more "messy".
In this talk, I will first present the challenges that arise for queries with negation and for the related "why-not provenance" questions.  I will then summarize current approaches to overcome the difficulties with negation and "why-not". For example, one can employ a game-theoretic approach that interprets query evaluation as a game between two opponents that argue whether a particular answer should be returned or not, resulting in a more symmetric treatment of why and why-not provenance.  Finally, I will conclude by highlighting some promising directions for future research.

ABOUT THE SPEAKER. Bertram Ludäscher is a professor at the School of Information Sciences at the University of Illinois, Urbana-Champaign, where he directs the Center for Informatics Research in Science and Scholarship (CIRSS). He is also a faculty affiliate with the National Center for Supercomputing Applications (NCSA) and the Department of Computer Science at Illinois.  Until 2014 he was a professor at the Department of Computer Science at the University of California, Davis. His research interests range from practical questions in scientific data and workflow management, to database theory, knowledge representation and reasoning. Prior to his faculty appointments, he was a research scientist at the San Diego Supercomputer Center (SDSC) and an adjunct faculty at the CSE Department at UC San Diego. He received his M.S. (Dipl.-Inform.) in computer science from the University of Karlsruhe (now K.I.T.), and his PhD (Dr. rer. nat.) from the University of Freiburg, Germany, respectively.