The Dichotomy of Conjunctive Queries on Probabilistic Structures

Simple item page
dc.creatorDalvi, Nilesh
dc.creatorSuciu, Dan
dc.date2006-12-20
dc.date2007-01-13
dc.date.accessioned2026-07-07T07:40:08Z
dc.date.available2026-07-07T07:40:08Z
dc.descriptionWe show that for every conjunctive query, the complexity of evaluating it on a probabilistic database is either \PTIME or #¶-complete, and we give an algorithm for deciding whether a given conjunctive query is \PTIME or #¶-complete. The dichotomy property is a fundamental result on query evaluation on probabilistic databases and it gives a complete classification of the complexity of conjunctive queries.
dc.identifierhttps://arxiv.org/abs/cs/0612102
dc.identifierhttp://arxiv.org/abs/cs/0612102
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/121692
dc.subjectDatabases
dc.titleThe Dichotomy of Conjunctive Queries on Probabilistic Structures
dc.typetext

Files

Collections

arXiv