Abstract:

In this talk we discuss the complexity of enumerating the answers of Conjunctive Queries (CQs) in the presence of Functional Dependencies (FDs). Our focus is on the ability to list output tuples with a constant delay in between, following a linear-time preprocessing. A known dichotomy classifies the acyclic self-join-free CQs into those that admit such enumeration, and those that do not. However, this classification no longer holds in the common case where the database exhibits dependencies among attributes. That is, some queries that are classified as hard are in fact tractable if dependencies are accounted for. We establish a generalization of the dichotomy to accommodate FDs; hence, our classification determines which combination of a CQ and a set of FDs admits constant-delay enumeration with a linear-time preprocessing.

Bio:

Nofar is a graduate student in the Data and Knowledge group at the Technion, advised by Prof. Benny Kimelfeld. Nofar has completed her graduate studies in 2015 in the Lapidim excellence program of the computer science faculty of the Technion, and has been awarded the Intel and Final awards for academic excellence.