Guest Talk: Nofar Carmeli: The Complexity of Answering Unions of Conjunctive Queries

Tuesday, February 18, 2020, 2:00pm

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, E1, seminar room 4116

Speaker: Nofar Carmeli (Technion)

 

Abstract:

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.