Nofar Carmeli, Technion, Israel Institute of Technology
28 February 2020, 10:30-11:30
ENS, S16
The Complexity of Answering Unions of Conjunctive Queries
We discuss the complexity of enumerating (listing) the answers to a query over a relational database. In particular, we consider three variants: arbitrary order, uniformly random order, and random access. We focus on the class of join queries: Conjunctive Queries (CQs) and Unions of Conjunctive Queries (UCQs), and on the ability to list the answers with linear preprocessing and logarithmic time per answer. A known dichotomy classifies CQs into those that admit such enumeration and those that do not. I will talk about my research towards extending this dichotomy to UCQs. This generalization turns out to be quite challenging. For example, a union of tractable CQs may be intractable w.r.t. random access; on the other hand, a union of intractable CQs may be tractable w.r.t. enumeration.
Bio:
Nofar Carmeli is a Ph.D. student in the Data and Knowledge group at Technion, Israel Institute of Technology, advised by Prof. Benny Kimelfeld. Her research focuses on query optimization with guarantees using enumeration techniques. Nofar completed her BSc in 2015 in the Lapidim excellence program of the Computer Science Department of Technion.
