(Downloads - 0)
For more info about our services contact : help@bestpfe.com
Table of contents
1 Introduction
1.1 Databases and query evaluation
1.2 Beyond query evaluation
1.3 Goals and tools
1.4 Structure of the thesis
2 Preliminaries
2.1 Databases and queries
2.2 Model of computation
2.3 Parametrized complexity
2.4 Query languages: logics
2.5 Query problems
2.5.1 Denitions
2.5.2 Key properties and examples
2.5.3 Comparisons
2.5.4 Conclusion
2.6 Classes of Graphs
2.6.1 General denitions
2.6.2 Classes of trees
2.6.3 Graphs with bounded degree
2.6.4 Graphs with bounded expansion
2.6.5 Nowhere and somewhere dense classes of graphs
3 State of the art
3.1 Query answering for static databases
3.1.1 Arbitrary relational structures
3.1.2 Highly expressive queries (MSO)
3.1.3 FO queries and sparse structures
3.1.4 Discussions
3.2 Query answering for databases subject to local updates
3.2.1 Arbitrary relational structures
3.2.2 Highly expressive queries (MSO)
3.2.3 FO queries and sparse structures
3.2.4 DynFO
3.3 Enumeration in other contexts
3.3.1 More theoretical results
3.3.2 More practical results
4 Some results
4.1 The model of computation, Random Access Machines
4.2 Nowhere dense graphs
4.2.1 Denitions
4.2.2 Examples
4.3 From databases to graphs
4.3.1 Representing databases with colored graphs
4.3.2 Gaifman versus adjacency
4.4 Other tools
4.4.1 Rank-Preserving Normal Form
4.4.2 Removal Lemma
5 Testing FO queries
5.1 Introduction
5.1.1 Introduction to Chapters 5, 6 and 7
5.1.2 Introduction to Chapter 5
5.2 Distance queries
5.2.1 The idea of the proof
5.2.2 The proof
5.3 The general algorithm
5.3.1 Some extra tools
5.3.2 The complete proof
5.4 Conclusion
6 Enumerating FO queries
6.1 Introduction
6.2 The main algorithm
6.2.1 The idea of the proof
6.2.2 The proof
6.3 Conclusion
7 Counting FO queries
7.1 Introduction
7.2 The main algorithm
7.2.1 Local normal form
7.2.2 The complete proof
7.3 Conclusion
8 Conclusion
Bibliography
