Cette thèse se concentre autour du problème de l'évaluation des requêtes. Étant donné une requête q et une base de données D, l'objectif est de calculer l'ensemble q(D) des nuplets résultant de l'évaluation de q sur D. Toutefois, l'ensemble q(D) peut être plus grand que la base de données elle-même car elle peut avoir une taille de la forme n^l où n est la taille de la base de données et l est l'arité de la requête. Calculer entièrement q(D) peut donc nécessiter plus que les ressources disponibles. L'objectif principal de cette thèse est une solution particulière à ce problème: une énumération de q(D) avec un délai constant. Intuitivement, cela signifie qu'il existe un algorithme avec deux phases: une phase de pré-traitement qui fonctionne en temps linéaire dans la taille de la base de données, suivie d'une phase d'énumération produisant un à un tous les éléments de q(D) avec un délai constant (indépendant de la taille de la base de données) entre deux éléments consécutifs. En outre, quatre autres problèmes sont considérés: le model-checking (où la requête q est un booléen), le comptage (où on veut calculer la taille |q(D)|), les tests (où on s'intéresse à un test efficace pour savoir si un uplet donné appartient au résultat de la requête) et la j-ième solution (où on veut accéder directement au j-ième élément de q(D)). Les résultats présentés dans cette thèse portent sur les problèmes ci-dessus concernant: - les requêtes du premier ordre sur les classes de structures de degré borné, - les requêtes du second ordre monadique sur les classes de structures de largeur d'arborescente bornée, - les requêtes du premier ordre sur les classes de structures avec expansion bornée.

In dieser Arbeit wird das dynamische Auswertungsproblem über dynamische Datenbanken betrachtet, bei denen Tupel hinzugefügt oder gelöscht werden können. Die Aufgabe besteht darin einen dynamischen Algorithmus zu konstruieren, welcher unmittelbar nachdem die Datenbank aktualisiert wurde, die Datenstruktur, die das Resultat repräsentiert, aktualisiert. Die Datenstruktur soll in konstanter Zeit aktualisiert werden und das Folgende unterstützen: * Teste in konstanter Zeit ob ein Tupel zur Ausgabemenge gehört, * gebe die Anzahl der Tupel in der Ausgabemenge in konstanter Zeit aus, * zähle die Tupel aus der Ausgabemenge mit konstanter Taktung auf und * zähle den Unterschied zwischen der neuen und der alten Ausgabemenge mit konstanter Taktung auf. Im ersten Teil werden konjunktive Anfragen und Vereinigungen konjunktiver Anfragen auf relationalen Datenbanken betrachtet. Die Idee der q-hierarchischen Anfragen (und t-hierarchische Anfragen für das Testen) wird eingeführt und es wird gezeigt, dass das Resultat für jede q-hierarchische Anfrage auf dynamischen Datenbanken effizient in dem oben beschriebenen Szenario ausgewertet werden können. Konjunktive Anfragen mit Aggregaten werden weiterhin betrachtet. Es wird gezeigt, dass das Lernen von polynomiellen Regressionsfunktionen in konstanter Zeit vorbereitet werden kann, falls die Trainingsdaten aus dem Anfrageergebnis kommen. Mit logarithmischer Update-Zeit kann folgende Routine unterstützt werden: Bei Eingabe einer Zahl j, gebe das j-te Tupel aus der Aufzählung aus. Im zweiten Teil werden Anfragen, die Formeln der Logik erster Stufe (FO) und deren Erweiterung mit Modulo-Zähl Quantoren (FO+MOD) sind, betrachtet, und es wird gezeigt, dass diese effizient unter Aktualisierungen ausgewertet können, wobei die dynamische Datenbank die Gradschranke nicht überschreitet, und bei der Auswertung die Zähl-, Test-, Aufzähl- und die Unterschied-Routine unterstützt werden. / This thesis investigates the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that immediately reports the new result of a fixed query after every database update. In particular, the goal is to construct a data structure that allows to support the following scenario. After every database update, the data structure can be updated in constant time such that afterwards we are able * to test within constant time for a given tuple whether or not it belongs to the query result, * to output the number of tuples in the query result, * to enumerate all tuples in the new query result with constant delay and * to enumerate the difference between the old and the new query result with constant delay. In the first part, conjunctive queries and unions of conjunctive queries on arbitrary relational databases are considered. The notion of q-hierarchical conjunctive queries (and t-hierarchical conjunctive queries for testing) is introduced and it is shown that the result of each such query on a dynamic database can be maintained efficiently in the sense described above. Moreover, this notion is extended to aggregate queries. It is shown that the preparation of learning a polynomial regression function can be done in constant time if the training data are taken (and maintained under updates) from the query result of a q-hierarchical query. With logarithmic update time the following routine is supported: upon input of a natural number j, output the j-th tuple that will be enumerated. In the second part, queries in first-order logic (FO) and its extension with modulo-counting quantifiers (FO+MOD) are considered, and it is shown that they can be efficiently evaluated under updates, provided that the dynamic database does not exceed a certain degree bound, and the counting, testing, enumeration and difference routines is supported.