(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
General Introduction
Limits of Combined Tractability of PQE
Fixed-Parameter Tractability of Provenance Computation
From Cycluits to d-DNNFs and Lower Bounds
d-DNNFs for Safe Queries
Structure of the Thesis
1 Background and General Preliminaries
1.1 Relational Databases, Graphs, Hypergraphs
1.2 Query Languages
1.3 Tuple-Independent Databases
1.4 Complexity Classes
1.5 Trees, Treewidth, Pathwidth
1.6 Tree Automata and Tree Encodings
1.7 Provenance and Knowledge Compilation Circuit Classes
2 Limits of Combined Tractability of PQE
2.1 Introduction
2.2 Preliminaries on Probabilistic Graph Homomorphism
2.3 Disconnected Case
2.4 Labeled Connected Queries
2.5 Unlabeled Connected Queries
3 Fixed Parameter Tractability of Provenance Computation
3.1 Introduction
3.2 Approaches for Tractability
3.3 Conjunctive Queries on Treelike Instances
3.4 CFG-Datalog on Treelike Instances
3.5 Translation to Automata
3.6 Provenance Cycluits
3.7 Proof of Translation
4 From Cycluits to d-DNNFs and Lower Bounds
4.1 Introduction
4.2 Preliminaries on Tree Decompositions
4.3 Upper Bound
4.4 Proof of the Upper Bound
4.5 Application to PQE of CFG-Datalog
4.6 Lower Bounds on OBDDs
4.7 Lower Bounds on (d-)SDNNFs
4.8 Application to Query Lineages
Conclusion and Perspectives
Summary
Open Questions and Directions for Future Work
Perspectives
Appendix: résumé en français
Limites de la tractabilité combinée de PQE
Tractabilité à paramètre fixé du calcul de provenance
Des cycluits aux d-DNNFs et bornes inférieures
Structure de la thèse
Self-References
Other References
