  Query evaluation on probabilistic databases is generally intractable
(#P-hard). Existing dichotomy results have identified which queries are
tractable (or safe), and connected them to tractable lineages. In our previous
work, 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, 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.
