Enumeration of UCQs with Constant Delay

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.