Alexandra Meliou will be visiting the LSV on Monday 13 May, she will give a talk at 10:30 in the LSV library at ENS-Cachan.
Reverse-engineering data transformations: A new perspective on data management
Current trends have seen data grow larger, more intertwined, and more diverse, as more and more users contribute to and use it. This trend has given rise to the need to support richer data analysis tasks. Such tasks involve determining the causes of observations, finding and correcting the sources of error in query results, as well as modifying the data in order to make it conform to complex desirable properties.
In this talk, I will discuss data analysis tasks that require tracing the history of data and reverse-engineering the transformations that it undergoes. I will discuss two tasks in particular: (1) providing explanations through support for causal queries, and (2) modifying datasets based on high-level declarative constraints . First, I will show how to apply causal reasoning to tuple provenance in order to determine the causes of query results, and to identify the source of possible errors. I will present extensive analysis of the data complexity for the case of conjunctive queries, and focus on a complete dichotomy between NP-hard and PTIME cases for the problem of computing responsibility.
Finally, I will demonstrate the Tiresias system, the first how-to query engine, which seamlessly integrates database systems with constrained problem solving capabilities. The contributions of the system are threefold: (a) a declarative interface for defining how-to queries over a database, (b) translation rules from the declarative statements to the constrained problem specification, and (c) a suite of data-specific optimizations that allow scaling to large data sizes. Initial results of our prototype system implementation show order-of-magnitude speedups to state-of-the-art solver runtimes, which indicates that there are significant gains in pushing this functionality within the database engine. I will conclude with a discussion of the next steps with the Tiresias system, and the bigger vision of reverse data management.
Alexandra Meliou is an Assistant Professor and the Department of Computer Science, at the University of Massachusetts, Amherst. She has held this position since September 2012. Prior to that, she was a Post-Doctoral Research Associate at the University of Washington, working with Dan Suciu. Alexandra received her Ph.D and M.S. degrees from the Electrical Engineering and Computer Sciences Department at the University of California, Berkeley, in 2009 and 2005 respectively. She is a 2008 Siebel Scholar, and her research interests are in the area of data and information management, with a current emphasis on provenance, causality, and reverse data management.