Skip to Main content Skip to Navigation

Leveraging the structure of uncertain data

Abstract : The management of data uncertainty can lead to intractability, in the case of probabilistic databases, or even undecidability, in the case of open-world reasoning under logical rules. My thesis studies how to mitigate these problems by restricting the structure of uncertain data and rules. My first contribution investigates conditions on probabilistic relational instances that ensure the tractability of query evaluation and lineage computation. I show that these tasks are tractable when we bound the treewidth of instances, for various probabilistic frameworks and provenance representations. Conversely, I show intractability under mild assumptions for any other condition on instances. The second contribution concerns query evaluation on incomplete data under logical rules, and under the finiteness assumption usually made in database theory. I show that this task is decidable for unary inclusion dependencies and functional dependencies. This establishes the first positive result for finite open-world query answering on an arbitrary-arity language featuring both referential constraints and number restrictions.
Document type :
Complete list of metadata

Cited literature [139 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Wednesday, October 26, 2016 - 10:41:11 AM
Last modification on : Wednesday, October 14, 2020 - 12:53:30 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01345836, version 2


Antoine Amarilli. Leveraging the structure of uncertain data. Databases [cs.DB]. Télécom ParisTech, 2016. English. ⟨NNT : 2016ENST0021⟩. ⟨tel-01345836v2⟩



Record views


Files downloads