Query enumeration and nowhere dense graphs
Énumération des requêtes et graphes nulle-part denses
Résumé
Query evaluation is one of the most central tasks of a database system, and a vast amount
of literature is devoted to the complexity of this problem. Given a database D and a query
q, the goal is to compute the set q(D) of all solutions for q over D. Unfortunately, the
set q(D) might be much bigger than the database itself, as the number of solutions may
be exponential in the arity of the query. It can therefore be insufficient to measure the
complexity of answering q on D only in terms of the total time needed to compute the
complete result set q(D). One can imagine many scenarios to overcome this situation.
We could for instance only want to compute the number of solutions or just compute
the k most relevant solutions relative to some ranking function.
In this thesis we mainly consider the complexity of enumerating the set q(D), i.e.,
generating one by one all the solutions for q on D. In this context two parameters play
an important role. The first one is the preprocessing time, i.e. the time it takes to produce
the first solution. The second one is the delay, i.e. the maximum time between the output
of any two consecutive solutions. An enumeration algorithm is then said to be efficient if
these two parameters are small. For the delay, the best we can hope for is constant time:
depending only on the query and independent from the size of the database. For the
preprocessing time an ideal goal would be linear time: linear in the size of the database
with a constant factor depending on the query. When both are achieved we say that the
query can be enumerated with constant delay after linear preprocessing.
A special case of enumeration is when the query is boolean. In this case the prepro-
cessing computes the answer to the query (yes or no). In order to be able to enumerate
queries of a given language efficiently, it is therefore necessary to be able to solve the
boolean case efficiently.
It has been shown recently that boolean first-order (FO) queries can be evaluated in
pseudo-linear time over nowhere dense classes of databases [43]. The notion of nowhere
dense classes was introduced in [60] as a formalization of classes of “sparse” graphs and
generalizes many well known classes of databases. Among classes of databases that
are closed under subdatabases, the nowhere dense classes are the largest possible classes
enjoying efficient evaluation of FO queries [55] (modulo an assumption in parameterized
complexity theory). It has also been shown that over nowhere dense classes of databases,
counting the number of solutions to a given FO query can be achieved in pseudo-linear
time [45].
In this thesis, we show that enumerating FO queries on nowhere dense classes of
databases can be done with constant delay after pseudo-linear preprocessing. This com-
pletes the picture of the complexity of FO query evaluation on nowhere dense classes
and, due to the above mentioned result of [55], on all classes that are closed under sub-
databases. We also show that for any nowhere dense class of databases, given a FO query
q and a database D in the class, after a pseudo-linear time preprocessing we can test in
constant time whether an arbitrary input tuple belongs to the result set q(D).
L’évaluation des requêtes est l’une des tâches les plus importantes en base de données et
beaucoup de recherche a été consacrée à l’étude de la complexité de ce problème. Étant
donné une base de données D et une requête q, le but est de calculer l’ensemble q(D) des
solutions de q sur D. Malheureusement, l’ensemble q(D) peut être beaucoup plus grand
que la base de données elle-même, car le nombre de solutions peut être exponentiel en
l’arité de la requête. Il n’est donc pas judicieux de mesurer la complexité de l’évaluation
de q sur D uniquement en termes de temps nécessaire pour calculer l’ensemble q(D).
On peut imaginer de nombreux scénarios pour contourner cette difficulté. On peut par
exemple seulement vouloir calculer le nombre de solutions ou juste les k solutions les
plus pertinentes selon un certain ordre.
Dans cette thèse, nous considérons principalement la complexité de l’énumération de
l’ensemble q(D), c’est-à-dire de générer une par une toutes les solutions de q sur D. Dans
ce contexte deux paramètres jouent un rôle important. Le premier est le pré-calcul, c’est-
à-dire le temps qu’il faut pour produire la première solution. Le deuxième est le délai,
c’est-à-dire le temps maximum entre la production de deux solutions consécutives. On
dit qu’un algorithme d’énumération est efficace si ces deux paramètres sont petits. Pour
le délai, on ne peut pas espérer mieux qu’un temps constant: dépendant uniquement de la
requête et indépendant de la taille de la base de données. Pour le pré-calcul, on souhaite
une exécution en temps linéaire: linéaire dans la taille de la base de données avec un
facteur constant dépendant de la requête. Lorsque les deux objectifs sont atteints, on dit
que la requête peut être énumérée à délai constant après un pré-calcul linéaire.
Un cas particulier d’énumération est lorsque la requête est booléenne. Dans ce cas,
le pré-calcul calcule simplement la réponse à la requête (oui ou non). Afin de pouvoir
énumérer efficacement les requêtes d’un langage donné, il est donc nécessaire d’être
capable de résoudre le cas booléen efficacement.
Il a été montré récemment que les requêtes booléennes du premier ordre (FO) peu-
vent être évaluées en temps pseudo-linéaire sur les classes de base de données nulle-part
denses [43]. La notion de classe nulle-part dense a été introduite dans [60] comme une
formalisation des classes de graphes “éparses” et généralise de nombreuse classes de
base de données. Parmi les classes de bases de données qui sont closes par sous bases
de données, les classes nulle-part dense sont les plus grandes bénéficiant d’une éval-
uation efficace des requêtes FO [55] (modulo une hypothèse en théorie de complexité
paramétrée). Il a également été montré que sur les bases de données nulle-part dense,
compter le nombre de solutions d’une requête FO peut être réalisée en temps pseudo-
linéaire [45].
Dans cette thèse, nous montrons que l’énumération des questions FO sur les classes
de bases de données nulle-part denses peut se faire à délai constant après un pré-calcul
pseudo-linéaire. Cela complète l’étude de la complexité de l’évaluation des requêtes FO
sur les classes nulle-part denses et, grâce au résultat de [55], sur toutes les classes close
par sous bases de données. Nous montrons également que pour toute classe de bases de
données nulle-part dense, étant donné une requête FO q et une base de données D de
cette classe, après un pré-calcul pseudo-linéaire, nous pouvons tester en temps constant
si un tuple donné appartient à l’ensemble des solutions q(D).
Origine : Fichiers produits par l'(les) auteur(s)
Loading...