Skip to Main content Skip to Navigation
Conference papers

Tractable Lineages on Treelike Instances: Limits and Extensions

Antoine Amarilli 1, 2 Pierre Bourhis 3 Pierre Senellart 1, 2
1 DIG - Data, Intelligence and Graphs
LTCI - Laboratoire Traitement et Communication de l'Information
3 LINKS - Linking Dynamic Data
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract :

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.

Document type :
Conference papers
Complete list of metadatas
Contributor : Admin Télécom Paristech <>
Submitted on : Thursday, June 23, 2016 - 11:26:34 AM
Last modification on : Friday, July 31, 2020 - 11:28:03 AM


  • HAL Id : hal-01336514, version 1


Antoine Amarilli, Pierre Bourhis, Pierre Senellart. Tractable Lineages on Treelike Instances: Limits and Extensions. PODS (Principles of Database Systems), Jun 2016, San Francisco, United States. pp.355-370. ⟨hal-01336514⟩



Record views