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.
| Identifer | oai:union.ndltd.org:HUMBOLT/oai:edoc.hu-berlin.de:18452/22264 |
| Date | 26 June 2020 |
| Creators | Keppeler, Jens |
| Contributors | Schweikardt, Nicole, Kratsch, Stefan, Martens, Wim |
| Publisher | Humboldt-Universität zu Berlin |
| Source Sets | Humboldt University of Berlin |
| Language | English |
| Detected Language | English |
| Type | doctoralThesis, doc-type:doctoralThesis |
| Format | application/pdf |
| Rights | (CC BY-NC-ND 4.0) Attribution-NonCommercial-NoDerivatives 4.0 International, https://creativecommons.org/licenses/by-nc-nd/4.0/ |
Page generated in 0.0027 seconds