The Data Readiness Problem for Relational Databases

Speaker Name: 
Rada Chirkova
Speaker Title: 
Professor, Computer Science
Speaker Organization: 
North Carolina State University
Start Time: 
Tuesday, February 19, 2019 - 4:00pm
End Time: 
Tuesday, February 19, 2019 - 5:30pm
Phokion Kolaitis


We consider the problem of determining whether organizations facing a new
data-transformation task can avoid building a new transformation procedure
from scratch by reusing their stored procedures. Because it can be
difficult to obtain exact descriptions of what stored procedures do, our
framework abstracts data-transforming tools as black-box procedures, in
which a procedure description indicates the parts of the database that
might be modified by the procedure and constraints on the states of the
database that must hold before and after the application of this procedure.

In this talk we present our framework and study the problem of determining,
given a database and a set of procedures, whether there is a sequence of
procedures from this set such that their application to the database
results in the satisfaction of a boolean query. This data readiness problem
is undecidable in general, but we show decidability for a broad and
realistic class of procedures. This work has been done jointly with Juan
Reutter and Jon Doyle.


Rada Y. Chirkova is a professor of Computer Science at North Carolina State
University. She has received a B.Sc. and a M.Sc., both in Applied
Mathematics, from Moscow State University (Moscow, Russia), and an M.Sc.
and a Ph.D., both in Computer Science, from Stanford University. She is a
senior member of the Association for Computing Machinery. Chirkova served
in 2017 as General Co-Chair of the ACM International Conference on
Management of Data (SIGMOD), and is associate editor of the SIGMOD Record
journal. She has co-authored three books, and has over sixty peer-reviewed
publications on topics ranging from query containment and equivalence,
query processing, view-based reformulation of data and queries, information
security and leakage, to applications of policies to agent behaviors. She
has received the National Science Foundation (NSF) CAREER Award, as well as
numerous IBM Faculty and University Partnership Program Awards. Her
research interests span information and knowledge management, algorithms
and theory of computation, and data sciences and analytics, with
applications including data wrangling, cyber security, and healthcare
information technology.