GSLIS Professor Bertram Ludäscher will present, "Unifying Why and Why-Not Provenance using First-Order Query Evaluation Games," at the Yahoo!-DAIS (Database and Information Systems Laboratory) Seminar from 4:00-5:00 p.m. on October 7 at the Siebel Center for Computer Science (Room 216). He also will be the featured speaker at this month's CIRSS Seminar Series at GSLIS on September 19.
His Yahoo!-DAIS presentation will address the following:
After a brief, high-level overview of my research areas and ongoing projects, I will focus on a foundational problem in database theory; i.e., how to explain the presence or absence of tuples in a query result. To this end, I will present a new model of provenance, based on a game-theoretic approach to query evaluation: First, we study graph-based games G in their own right, and ask how to explain that a position x in a game graph G is won, lost, or drawn. The resulting notion of "game provenance" is closely related to winning strategies, and excludes from provenance all "bad moves"; i.e., those which unnecessarily allow the opponent to improve the outcome of a play. In this way, the value of a position is determined solely by its game provenance. We then define provenance games by viewing the evaluation of a first-order query as a game between two players who argue whether a tuple is in the query answer. For RA+ queries, game provenance is equivalent to the most general semiring of provenance polynomials N[X]. Variants of our game yield other known semirings. However, unlike semiring provenance, game provenance also provides a very natural, "built-in" way to handle negation and thus to answer Why-Not questions: In (provenance) games, the reason why x is not won is the same as why x is lost or drawn (the latter is possible for games with draws). Since first-order provenance games are draw-free, they yield a new provenance model that combines how- and why-not provenance.
A leading figure in data and knowledge management, Ludäscher joined the GSLIS faculty this fall. He also holds an appointment at the National Center for Supercomputing Applications (NCSA) and an affiliate appointment at the Department of Computer Science. He previously served as a professor at the Department of Computer Science and the Genome Center at the University of California, Davis. Until 2004, he was a research scientist at the San Diego Supercomputer Center (SDSC) and an adjunct faculty in the CSE Department at UC San Diego.
Ludäscher's research interests span the whole data to knowledge life-cycle, from modeling and design of databases and workflows, to knowledge representation and reasoning. His current research focus includes both theoretical foundations of provenance and practical applications, in particular to support automated data quality control and workflow-supported data curation. He is one of the founders of the open source Kepler scientific workflow system, and a member of the DataONE leadership team, focusing on data and workflow provenance.