This habilitation thesis focuses on the query evaluation problem in database theory and neighboring areas, and considers three extended forms of query evaluation: enumeration, maintenance, and reliability. Enumeration focuses on producing query results in streaming while minimizing the delay between two successive results; maintenance studies how to efficiently reevaluate queries when the underlying data is updated; and reliability computes the probability of query results when the underlying data is uncertain. The thesis presents the state of the art of these areas and new results on these three problems. A recurring theme is the use of tractable circuit classes from the area of knowledge compilation as a way to extend query evaluation and give a unified explanation for the tractability of these tasks. In particular, circuits can serve as a factorized representation of query answers, they may be efficiently updatable, and they may allow tractable probabilistic computation.
soutenue le 04/04/2023
This habilitation thesis focuses on the query evaluation problem in database theory and neighboring areas, and considers three extended forms of query evaluation: enumeration, maintenance, and reliability. Enumeration focuses on producing query results in streaming while minimizing the delay between two successive results; maintenance studies how to efficiently reevaluate queries when the underlying data is updated; and reliability computes the probability of query results when the underlying data is uncertain. The thesis presents the state of the art of these areas and new results on these three problems. A recurring theme is the use of tractable circuit classes from the area of knowledge compilation as a way to extend query evaluation and give a unified explanation for the tractability of these tasks. In particular, circuits can serve as a factorized representation of query answers, they may be efficiently updatable, and they may allow tractable probabilistic computation.
soutenue le 04/04/2023
français
English