Conjunctive Queries on Probabilistic Graphs: Combined Complexity

Abstract : Query evaluation over probabilistic databases is known to be intractable in many cases, even in data complexity, i.e., when the query is fixed. Although some restrictions of the queries [20] and instances [4] have been proposed to lower the complexity, these known tractable cases usually do not apply to combined complexity, i.e., when the query is not fixed. This leaves open the question of which query and instance languages ensure the tractability of probabilistic query evaluation in combined complexity. This paper proposes the first general study of the combined complexity of conjunctive query evaluation on probabilistic instances over binary signatures, which we can alternatively phrase as a probabilistic version of the graph homomor-phism problem, or of a constraint satisfaction problem (CSP) variant. We study the complexity of this problem depending on whether instances and queries can use features such as edge labels, disconnectedness, branching, and edges in both directions. We show that the complexity landscape is surprisingly rich, using a variety of technical tools: automata-based compilation to d-DNNF lineages as in [4], β-acyclic lin-eages using [11], the X-property for tractable CSP from [25], graded DAGs [28] and various coding techniques for hardness proofs.
Type de document :
Communication dans un congrès
Principles of Database Systems (PODS), May 2017, Chicago, United States. 〈http://sigmod2017.org/〉. 〈10.1145/3034786.3056121〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01486634
Contributeur : Pierre Senellart <>
Soumis le : vendredi 10 mars 2017 - 11:13:05
Dernière modification le : mardi 19 juin 2018 - 10:44:02
Document(s) archivé(s) le : dimanche 11 juin 2017 - 14:20:17

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Antoine Amarilli, Mikaël Monet, Pierre Senellart. Conjunctive Queries on Probabilistic Graphs: Combined Complexity. Principles of Database Systems (PODS), May 2017, Chicago, United States. 〈http://sigmod2017.org/〉. 〈10.1145/3034786.3056121〉. 〈hal-01486634〉

Partager

Métriques

Consultations de la notice

281

Téléchargements de fichiers

28