Tractable Lineages on Treelike Instances: Limits and Extensions

Antoine Amarilli 1 Pierre Bourhis 2 Pierre Senellart 1
2 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.

Type de document :
Communication dans un congrès
PODS (Principles of Database Systems), Jun 2016, San Francisco, United States. PODS (Principles of Database Systems), pp.355-370, 2016
Liste complète des métadonnées

https://hal-imt.archives-ouvertes.fr/hal-01336514
Contributeur : Admin Télécom Paristech <>
Soumis le : jeudi 23 juin 2016 - 11:26:34
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27

Identifiants

  • HAL Id : hal-01336514, version 1

Citation

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. PODS (Principles of Database Systems), pp.355-370, 2016. 〈hal-01336514〉

Partager

Métriques

Consultations de la notice

167