Tractable Lineages on Treelike Instances: Limits and Extensions
Résumé
Query evaluation on probabilistic databases is generally intractable (#P-hard). Existing dichotomy results [19, 18, 23] have identified which queries are tractable (or safe), and connected them to tractable lineages [36]. In our previous work [2], using different tools, we showed that query evaluation is linear-time on probabilistic databases for arbitrary monadic second-order queries, if we bound the treewidth of the instance.
In this paper, we study limitations and extensions of this result. First, for probabilistic query evaluation, we show that MSO tractability cannot extend beyond bounded treewidth: there are even FO queries that are hard on any efficiently constructible unbounded-treewidth class of graphs. This dichotomy relies on recent polynomial bounds on the extraction of planar graphs as minors [10], and implies lower bounds in non-probabilistic settings, for query evaluation and match counting in subinstance-closed families. Second, we show how to explain our tractability result in terms of lineage: the lineage of MSO queries on bounded-treewidth instances can be represented as bounded-treewidth circuits, polynomial-size OBDDs, and linear-size d-DNNFs. By contrast, we can strengthen the previous dichotomy to lineages, and show that there are even UCQs with disequalities that have superpolynomial OBDDs on all unbounded-treewidth graph classes; we give a characterization of such queries. Last, we show how bounded-treewidth tractability explains the tractability of the inversion-free safe queries: we can rewrite their input instances to have bounded-treewidth.