Catching up with research reading (1)

The Dichotomy of Conjunctive Queries on Probabilistic Structures. [cs.DB/0612102]:We show that for every conjunctive query, the complexity of evaluating it on a probabilistic database is either PTIME or #P-complete, and we give an algorithm for deciding whether a given conjunctive query is PTIME o #P-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.

The question about this very interesting line of work: what price do we pay for probabilistic inference, as opposed a weaker semiring-based scoring?

This is also a test of posting from NetNewsWire via ecto.