DSpace Repository

Conditioning Probabilistic XML (Extended Version)

Show simple item record

dc.contributor.author Tang, Ruiming en_US
dc.contributor.author Shao, Dongxu en_US
dc.contributor.author Ba, M. Lamine en_US
dc.contributor.author Senellart, Pierre en_US
dc.contributor.author Bressan, Stéphane en_US
dc.date.accessioned 2013-10-24T01:44:52Z en_US
dc.date.accessioned 2017-01-23T07:00:08Z
dc.date.available 2013-10-24T01:44:52Z en_US
dc.date.available 2017-01-23T07:00:08Z
dc.date.issued 2013-10-24T01:44:52Z en_US
dc.identifier.uri http://hdl.handle.net/1900.100/4288 en_US
dc.description.abstract A probabilistic database instance denotes a set of possible non-probabilistic database instances called possible worlds, each of which has a probability. This is often a compact way to represent uncertain data. In addition, direct observations and general knowledge, in the form of constraints, help refining the probabilities of the possible worlds, possibly ruling out some of them. Adding such constraints to the set of possible worlds with their probabilities is conditioning in the probabilistic sense of the term. The problem is to find a new probabilistic database instance that denotes the subset of possible worlds with their new probabilities corresponding to the conditional probabilities. Probabilistic XML allows capturing uncertainty of both values and structure. We consider the conditioning problem for probabilistic XML with a language of formulae of independent events to express the probabilistic dependencies among the nodes of the XML tree. In the most general case, conditioning is intractable. For reference, we present an exponential algorithm. We then focus on the specific case of independent events and mutually exclusive constraints. This case goes beyond local mutually exclusive constraints as considered so far in the literature. We devise and present polynomial algorithms for conditioning probabilistic XML data in tractable cases. en_US
dc.format.extent 441976 bytes en_US
dc.format.mimetype application/pdf en_US
dc.language.iso en en_US
dc.relation.ispartofseries ;TR10/13 en_US
dc.title Conditioning Probabilistic XML (Extended Version) en_US
dc.type Technical Report en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account