Gastvortrag: Nofar Carmeli: The Complexity of Answering Unions of Conjunctive Queries

Dienstag, 18.02.2020, 14.00 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, E1, seminar Raum 4116

Vortragender: 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.