Project Topics
Get Complete Project Material File(s) Now! »
Key properties and examples
We now give an example of such algorithms. We consider that our query language L only contains the query q(x; y) = :P(x; y). The input for the dierent problems is a database D that contains a binary relation P. The way this input is given is simply the list of all pair (a; b) of elements that are in PD. Moreover, we can assume this list to be lexicographically sorted as this operation can be performed in linear time by Theorem 2.2.1.
The easiest of the problems in this setting is the counting problem because jq(D)j = jDj2 jPDj: A single pass through the input allows us to compute jq(D)j. Hence the counting problem can be solved in linear time.
The evaluation problem is also solved by an easy algorithm: Iterate through all pairs (a; b) 2 D2. For every pair, test whether D j= P(a; b). If it is not the case, then (a; b) is a solution and we can output it. Otherwise we go to the next pair. In the following, L is the ordered list of all pairs (a; b) that are in PD.
Graphs with bounded degree
Given a graph G = (V;E), and a node a in V the degree of a in G is the number of nodes that share an edge with a. The degree of a graph G is the maximal degree amongst the nodes of G.
Denition 2.6.7. A class of graphs C has bounded degree if there is an integer d such that for every graph G 2 C, we have that the degree of G does not exceed d.
Graphs with bounded expansion
The notion of a class of graphs with bounded expansion was introduced by Nešetril and Ossona de Mendez in [58]. It generalizes the notions of bounded tree-width and bounded degree. It also generalizes other well known classes such as planar graphs or graphs that exclude a minor. The denition of bounded expansion we give here uses the notion of minor of a graph that we dene rst.
Denition 2.6.8. Let G = (V;E) be an undirected graph and r be an integer. A graph H = (V 0;E0) is an r-minor of G if:
• V 0 V .
• for every ai in V 0, there is a set Si in V such that:
– Si NG r (ai).
– for every i 6= j we have Si \ Sj = ;, and.
– for every i 6= j we have (ai; aj) is in E0 if and only if in G there is an edge from a node in Si to a node in Sj .
Nowhere and somewhere dense classes of graphs
The notion of nowhere dense classes of graphs was introduced in [60] as a formalization of classes of “sparse” graphs and generalizes many well known classes of graphs such as graphs with bounded tree-width, graphs with bounded degree or bounded expansion [61]. Here we just give the basic denition of nowhere dense graphs. But since this notion is at the core of this thesis, we provide additional details and information in Section 4.2.
The rst denitions of nowhere dense classes of graphs use again the notion of graphs minor. Denition 2.6.10 ([60]). Let C be a class of graphs. C is nowhere dense if and only if for all r 2 N there is a Nr 2 N such that KNr 62 COr. Here, Kn is the clique with n elements i.e. a graph with n vertices and every possible edges.
Nowhere dense is a very robust notion that can be dened by many other equivalent properties [60]. Moreover, nowhere dense seems to be one of the broadest classes of graphs that admit good algorithmic properties.
In opposition to nowhere dense, we can dene somewhere dense classes of graphs.
Denition 2.6.11 ([60]). A class of graphs C is somewhere dense if and only if it is not nowhere dense.
Note that none of those two denitions imply that a nowhere dense (or somewhere dense) class is closed under subgraphs. However, if a class is nowhere dense (resp. somewhere dense) then its closure by adding every possible subgraph remains nowhere dense (resp. somewhere dense). Furthermore, there are sharp dichotomy results that use those two notions.
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
