Refine
Document Type
- Doctoral Thesis (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Relationale Datenbank (2) (remove)
Institute
- Informatik (2)
Relational data exchange deals with translating relational data according to a given specification. This problem is one of the many tasks that arise in data integration, for example, in data restructuring, in ETL (Extract-Transform-Load) processes used for updating data warehouses, or in data exchange between different, possibly independently created, applications. Systems for relational data exchange exist for several decades now. Motivated by their experiences with one of those systems, Fagin, Kolaitis, Miller, and Popa (2003) studied fundamental and algorithmic issues arising in relational data exchange. One of these issues is how to answer queries that are posed against the target schema (i.e., against the result of the data exchange) so that the answers are consistent with the source data. For monotonic queries, the certain answers semantics proposed by Fagin, Kolaitis, Miller, and Popa (2003) is appropriate. For many non-monotonic queries, however, the certain answers semantics was shown to yield counter-intuitive results. This thesis deals with computing the certain answers for monotonic queries on the one hand, and on the other hand, it deals with the issue of which semantics are appropriate for answering non-monotonic queries, and how hard it is to evaluate non-monotonic queries under these semantics. As shown by Fagin, Kolaitis, Miller, and Popa (2003), computing the certain answers for unions of conjunctive queries - a subclass of the monotonic queries - basically reduces to computing universal solutions, provided the data transformation is specified by a set of tgds (tuple-generating dependencies) and egds (equality-generating dependencies). If M is such a specification and S is a source database, then T is called a solution for S under M if T is a possible result of translating S according to M. Intuitively, universal solutions are most general solutions. Since the above-mentioned work by Fagin, Kolaitis, Miller, and Popa it was unknown whether it is decidable if a source database has a universal solution under a given data exchange specification. In this thesis, we show that this problem is undecidable. More precisely, we construct a specification M that consists of tgds only so that it is undecidable whether a given source database has a universal solution under M. From the proof it also follows that it is undecidable whether the chase procedure - by which universal models can be obtained - terminates on a given source database and the set of tgds in M. The above results in particular strengthen results of Deutsch, Nash, and Remmel (2008). Concerning the issue of which semantics are appropriate for answering non-monotonic queries, we study several semantics for answering such queries. All of these semantics are based on the closed world assumption (CWA). First, the CWA-semantics of Libkin (2006) are extended so that they can be applied to specifications consisting of tgds and egds. The key is to extend the concept of CWA-solution, on which the CWA-semantics are based. CWA-solutions are characterized as universal solutions that are derivable from the source database using a suitably controlled version of the chase procedure. In particular, if CWA-solutions exist, then there is a minimal CWA-solution that is unique up to isomorphism: the core of the universal solutions introduced by Fagin, Kolaitis, and Popa (2003). We show that evaluation of a query under some of the CWA-semantics reduces to computing the certain answers to the query on the minimal CWA-solution. The CWA-semantics resolve some the known problems with answering non-monotonic queries. There are, however, two natural properties that are not possessed by the CWA-semantics. On the one hand, queries may be answered differently with respect to data exchange specifications that are logically equivalent. On the other hand, there are queries whose answer under the CWA-semantics intuitively contradicts the information derivable from the source database and the data exchange specification. To find an alternative semantics, we first test several CWA-based semantics from the area of deductive databases for their suitability regarding non-monotonic query answering in relational data exchange. More precisely, we focus on the CWA-semantics by Reiter (1978), the GCWA-semantics (Minker 1982), the EGCWA-semantics (Yahya, Henschen 1985) and the PWS-semantics (Chan 1993). It turns out that these semantics are either too weak or too strong, or do not possess the desired properties. Finally, based on the GCWA-semantics we develop the GCWA*-semantics which intuitively possesses the desired properties. For monotonic queries, some of the CWA-semantics as well as the GCWA*-semantics coincide with the certain answers semantics, that is, results obtained for the certain answers semantics carry over to those semantics. When studying the complexity of evaluating non-monotonic queries under the above-mentioned semantics, we focus on the data complexity, that is, the complexity when the data exchange specification and the query are fixed. We show that in many cases, evaluating non-monotonic queries is hard: co-NP- or NP-complete, or even undecidable. For example, evaluating conjunctive queries with at least one negative literal under simple specifications may be co-NP-hard. Notice, however, that this result only says that there is such a query and such a specification for which the problem is hard, but not that the problem is hard for all such queries and specifications. On the other hand, we identify a broad class of queries - the class of universal queries - which can be evaluated in polynomial time under the GCWA*-semantics, provided the data exchange specification is suitably restricted. More precisely, we show that universal queries can be evaluated on the core of the universal solutions, independent of the source database and the specification.
Durch das Semantische Web soll es Maschinen ermöglicht werden Metadaten zu verstehen. Hierin steckt ein enormes Potenzial, wodurch sich der Umgang mit dem heutigen Internet grundlegend ändern kann. Das Semantische Web steht jedoch noch am Anfang. Es gilt noch einige offene und strittige Punkte zu klären. Das Fundament des Semantischen Webs wird durch das Resource Description Framework (RDF) gebildet, worauf sich diese Arbeit konzentriert. Hauptziel meiner Arbeit war die Verbesserung der Funktionalität und der Nutzungsfreundlichkeit für RDF-Speicher- und Anfragesysteme. Dabei stand die allgemeine Nutzung für ein Informationsportal oder eine Internetsuchmaschine im Vordergrund. Meine Überlegungen hierzu wurden in dem Speichersystem RDF-Source related Storage System (RDF-S3) und der darauf aufsetzenden Anfragesprache easy RDF Query Language (eRQL) umgesetzt. Insbesondere wurden die folgende Kernpunkte berücksichtigt: • Allgemeine Nutzbarkeit der Anfragesprache, sodass auch unerfahrene Nutzer einfach und schnell Anfragen erstellen können. Um auch von unerfahrenen Nutzern bedient werden zu können, konnte keine komplexe Syntax verwendet werden, wie dies bei den meisten existierenden Anfragesprachen der Fall ist. Es wurde sich daher an Anfragesprachen existierender Suchmaschinen angelehnt. Entsprechend bilden sogenannte Ein-Wort-Anfragen, die den Suchbegriffen entsprechen, eine wichtige Rolle. Um gezieltere Anfragen stellen zu können, sind jedoch die Schemainformationen der gespeicherten Daten sehr wichtig. Hier bietet bereits die RDF Query Language (RQL) viele hilfreiche Kurzschreibweisen, an die sich eRQL anlehnt. • Bereitstellung glaubwürdiger Metadaten, sodass den Anfrageergebnissen vertraut werden kann. Das Semantische Web ist ein verteiltes System, wobei keine Kontrolle auf die Datenquellen ausgeübt werden kann. Den Daten kann daher nicht ohne weiteres vertraut werden. Anders ist dies mit Metadaten, die von eigenen Systemen erzeugt wurden. Man weiß wie sie erzeugt wurden und kann ihnen entsprechend vertrauen. Wichtig ist eine klare Trennung zwischen den Daten und den Metadaten über diese, da sonst eine absichtliche Nachbildung der Metadaten von außen (Suchmaschinen-Spamming) das System unterlaufen kann. Für die Glaubwürdigkeit von Anfrageergebnissen sind vor allem die Herkunft der Daten und deren Aktualität entscheidend. In den umgesetzten Entwicklungen zu dieser Arbeit wurde sich daher auf diese Informationen konzentriert. In RDF-S3 wird die Verknüpfung der RDF-Aussage mit ihren Herkunftsdaten im Speichermodell abgebildet. Dies ermöglicht eine gezielte Ausnutzung dieser Daten in eRQL-Anfragen. Durch den sogenannten Dokumenten-Modus bietet eRQL die Möglichkeit Anfragen auf eine Gruppe von Quellen zu begrenzen oder bestimmte unglaubwürdige Quellen auszuschließen. Auch können die Herkunftsdaten das Anfrageergebniss erweitern und dadurch das Verständnis und die Glaubwürdigkeit für das Ergebnis erhöhen. • Anfrageergebnisse können um ihre Umgebung erweitert werden, sodass sie besser verstanden werden können. Für eRQL-Anfragen besteht die Möglichkeit die Umgebnung zu den Treffern (RDF-Aussagen) mit zu berücksichtigen und im Ergebnis mit anzuzeigen. Dies erhöht das Verständnis für die Ergebnisse. Weiterhin ergeben sich hierdurch neue Möglichkeiten wie das Auffinden von Pfaden zwischen Teilergebnissen einer Anfrage. • Unterstützung und Kombination von Daten- und Schemaanfragen. Mit eRQL werden beide Anfragetypen unterstützt und können sinnvoll miteinander kombiniert werden. Die Einbeziehung der Umgebung ermöglicht für die Kombination von Daten- und Schemaanfragen neue Möglichkeiten. Dabei werden sowohl Daten- als auch Schemaanfragen (oder deren Kombination) durch das Speichermodell von RDF-S3 optimal unterstützt. Weitere nennenswerte Eigenschaften von RDF-S3 und eRQL sind: • Durch die Möglichkeit gezielt einzelne Quellen wieder zu entfernen oder zu aktualisieren, bietet RDF-S3 eine gute Wartbarkeit der gespeicherten Daten. • RDF-S3 und eRQL sind zu 100 % in Java entwickelt, wodurch ihr Einsatz unabhängig vom Betriebssystem möglich ist. • Der Datenbankzugriff erfolgt über JDBC, wobei keine besonderen Eigenschaften für die verwendete RDBMS nötig sind . Dies sorgt für eine hohe Portabilität. RDF-S3 und eRQL wurden als Beispielimplementierungen entwickelt. Für einen produktiven Einsatz sollten die Systeme an die gegebene Hardware-Umgebung und Anwendungsfall angepasst werden. In Kapitel 6 werden Erweiterungen und Änderungsmöglichkeiten genannt, die je nach Situation geprüft werden sollten. Ein noch vorhandenes Problem für einen produktiven Einsatz auf großen Datenmengen ist die aufwendige Berechnung der Umgebungen für Anfrageergebnisse. Die Berechnung von Umgebungen im Vorhinein könnte hier eine Lösung sein, die jedoch durch die Möglichkeit der Einschränkung auf glaubwürdige Quellen erschwert wird.