Skip to main content

Enumeration of UCQs with Constant Delay

Nofar Carmeli ( Technion )

We discuss the complexity of enumerating the answers of Unions of Conjunctive Queries (UCQs), and focus on the ability to list output tuples with constant delay following linear-time preprocessing. A known dichotomy classifies the 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. In such cases, some queries classified as hard are in fact tractable, and we generalize the dichotomy to accommodate Functional Dependencies (FDs). Next, we aspire to have a similar characterization for UCQs, even when there are no FDs. It was claimed in the past that a UCQ is hard if one of its queries is hard. We examine the task of enumerating UCQs, and show that some unions containing a hard query are tractable. In fact, a UCQ may be tractable even if it does not contain a single tractable CQ.

Speaker bio

Nofar is a PhD student in the Data and Knowledge group at the Technion, advised by Prof. Benny Kimelfeld. She is currently a visiting researcher in the FDB group at Oxford. Her research focuses on query optimization using enumeration techniques. Nofar completed her BSc in 2015 in the Lapidim excellence program of the Computer Science department of the Technion.

Share this: