Semantische Abfrageoptimierung
Der überwältigende Erfolg relationaler Datenbanksysteme ist vor allem auf die Verwirklichung des Begriffs der Datenunabhängigkeit zurückzuführen. Dadurch können Anwender für ihren jeweiligen Anwendungsbereich Datenbanken benutzen, ohne daß aus der fehlenden Kenntnis von systemnahen Details wie Zugriffspfade und Speicherstrukturen längere Antwortzeiten der Anfragen folgen oder gar die Formulierung von Anfragen beeinträchtigt wird. Dies vereinfachte die Anfrageformulierung für bisherige Nutzer und erweiterte die Akzeptanz von Datenbanksystemen erheblich.
Der damit verbundene Übergang von einer prozeduralen zu einer nichtprozeduralen Formulierung der Anfragen erfordert die Einführung einer weiteren Übersetzungsphase. Diese Ubersetzung muß die fehlende Information in Anfragen über Zugriffspfade und Speicherstrukturen durch beispielsweise algebraische Gesetze und Kostenmodelle kompensieren, um eine möglichst kostengünstige Beantwortung zu gewährleisten. Solche Techniken werden unter dem Begriff Anfrageoptimierung zusammengefaßt. Nach dem ökonomischen Prinzip wird durch Optimierung entweder das Ergebnis bei festem Verbrauch von Betriebsmitteln maximiert oder der Verbrauch von Betriebsmitteln bei gleichem Ergebnis minimiert. Durch Anfrageoptimierung wird immer der Verbrauch der Betriebsmittel minimiert, da das Ergebnis fest definiert ist.
Der Schwerpunkt bisheriger Optimierungen liegt dabei auf einer möglichst direkten Abbildung der nichtprozeduralen Sicht auf die physischen Objekte eines Datenbanksystems, wie Härder betont. Das dafür dem System zur Verfügung stehende notwendige Wissen bezieht allerdings kein Wissen über den Anwendungsbereich selbst mit ein, obwohl dies zu erheblichen Verbesserungen der Leistungsmerkmale eines Datenbanksystems führen würde, wie Chakravarthy et al. vermerken. Deshalb schlagen sie eine Erweiterung der Optimierung vor, die auch Wissen über die Bedeutung des Anwendungsbereichs miteinbezieht und bezeichnen dies als semantische Anfrageoptimierung. Date sieht in dieser Anfrageoptimierung ein enormes Potential:
So far as this writer is aware, few commercial products do much in the way of semantic optimization. In principle, however, such optimization could provide very significant performance improvements - much greater improvements, very likely, than are obtained by any today's traditional optimization techniques.
Nun interessieren natürlich die Gründe für die Diskrepanz zwischen Potential und wirklichem Einsatz. Dazu sollen zuerst drei exemplarische Arbeiten betrachtet werden, die auch drei prinzipielle Strategien der semantischen Anfrageoptimierung verdeutlichen.
Erfüllbarkeitsbasierte Strategie
Zur Überprüfung der Erfüllbarkeit von Anfragen eignen sich gut logikbasierte Anfragesprachen wie DATALOG. Basierend auf der Erfüllbarkeit können nun Probleme wie die Gleichheit oder Minimierung von Anfragen unter Berücksichtigung von Integritätsbedingungen untersucht werden. Levy und Sagiv definieren semantische Anfrageoptimierung generell als einen Prozeß, Integritätsbedingungen zur Optimierung von Anfragen zu verwenden. Diese Definition ist allerdings zu eng gefaßt, wie im weiteren gezeigt wird.
Heuristikbasierte Strategie
Hier werden Heuristiken zur Anfrageoptimierung verwendet. King verwendet beispielsweise die Heuristik in dem System QUIST: Füge in jede Anfrage Bedingungen über indexierte Attribute ein. Generell gilt, daß indexierte Attribute in einer Anfrage den Zugriff über eine Baumstruktur ermöglichen. Ohne indexierte Attribute muß sequentiell gesucht werden. Das verwendete Wissen besteht dabei aus Integritätsbedingungen, die Werte verschiedener Attribute einer Relation in Bezug setzen, unter anderem auch die Werte von indexierten Attributen.
Regelbasierte Strategie
Bei dieser Strategie werden Bedingungen aus Anfragen extrahiert, die bei Erfüllung durch die Wissensbasis immer zu einer Reformulierung führen. Beispielsweise verwenden Paulley und Larson die Schlüssel einer Relation, um zu zeigen, daß Antwortmengen keine Duplikate enthalten können. Dementsprechend können distinct-Anweisungen in SQL-Anfragen entfernt werden, die sonst eine unnötige Prozedur zur Duplikateliminierung veranlassen.
Allerdings erklären diese Ansätze noch nicht die Diskrepanz von Potential und tatsächlichem Einsatz. Deshalb soll die Anfrageoptimierungen noch genauer betrachtet werden. Ein Datenbanksystem besteht nach Ullman aus einem Datenbankmanagementsystem (DBMS), das alle Programme zur Datenverwaltung umfaßt, und den einzelnen Datenbanken, die die Daten beinhalten. Betrachtet man die Optimierungen unter dem Aspekt der Nutzung von Wissen, dann ist ein qualitativer Unterschied die Verfügbarkeit des Wissens: Zugriffspfade und Speicherungsstrukturen sind jeweils pro DBMS fest vorgegeben. Algebraische Gesetze gelten für alle DBMSe, und die Kostenmodelle basieren auf einfachen statistischen Merkmalen einer Datenbank. Dagegen impliziert der Inhalt einer Datenbank eine große Bandbreite für das zur semantischen Anfrageoptimierung vorausgesetzte Wissen. Wird semantische Anfrageoptimierung nun ausschließlich über Integritätsbedingungen definiert, dann ist der Erfolg der Anfrageoptimierung von Wissen abhängig, das Benutzer zuvor spezifizieren müssen.
Siegel schlägt deshalb eine neue Definition für die semantische Anfrageoptimierung vor:
. . . defining semantic query transformation as the addition or removal of constraints to a query in accordance with a given rule set. The transformed query is semantically equivalent to the original query in the sense that if the database state satisfies the rules, then the transformed query will return the same answer from the database.
Damit werden Constraints nicht mehr als Integritätsbedingungen einer Datenbank, sondern als Wissen über einen Datenbankzustand betrachtet. Zur besseren Unterscheidung soll dieses Wissen als Metadaten bezeichnet werden. Diese neue Sichtweise erlaubt nicht nur, einzelne Datenbankzustände genauer zu beschreiben, sondern ermöglicht auch, maschinelle Verfahren zur Entdeckung der Metadaten einzusetzen. Beispiele hierfür sind:
- Hsu und Knoblock verwenden Anfrageergebnisse, um mit Techniken des maschinellen Lernens allgemeine Bedingungen abzuleiten, die sie dann zur Reformulierung neuer Anfragen benützen.
- Bell stellt Methoden zur Entdeckung aller derzeit in einer Datenbank gültigen funktionalen Abhängigkeiten und eine Optimierung durch das Entfernen unnötiger distinct- und group by-Anweisungen vor. Dabei werden bei Änderungen des Datenbankzustands die Metadaten auch gewartet.
Der Nachteil von Siegels Lösung ist, daß die Entdeckung und Wartung der Metadaten Kosten verursacht. Die Kosten der Entdeckung müssen allerdings nicht in die Kosten der Optimierung einfließen, da sie zu Zeiten niedriger Auslastung des Systems stattfinden kann. Damit kann die semantische Anfrageoptimierung auch als eine Art Lastverteilung betrachtet werden: Zu Zeiten niedriger Auslastung werden Metadaten entdeckt, die dann zu Zeiten höherer Auslastung die Beantwortung der Anfragen beschleunigen.
Die bisherigen Ansätze erlauben allerdings noch keine Aussage, ob Siegels Lösung Dates Prognose unterstützt, daß semantische Anfrageoptimierung einmal gewinnbringender als die anderen Optimierungen sein wird.
Literatur
- Bell, S.: Deciding distinctness of query result by discovered constraints. In Practical Application of Constraint Technology (1996)
- Chakravarthy, U. S., Grant, J., Minker, J.: Logicbased Approach to semantic query optimisation. ACM Transaction on Database Systems 15, 2 (June 1990)
- Date, C.: An Introduction to Database Systems, 6th ed. The Systems Programming Series. Addison-Wesley Publishing Company, 1995
- Härder, T.: Realisierung von operationalen Schnittstellen. In Datenbankhandbuch.
Springer Verlag, 1987 - Hsu, C. N., Knoblock, C. A.: Using inductive learning to generate rules for semantic query optimization. In Advances of Knowledge Discovery and Data Mining. AAAI Press, 1995, ch. 17
- King, J. J.: Query optimization by semantic reasoning. Tech. Rep.
STAN-CS-81-857, Stanford University, May 198 - Levy, A. Y., Sagiv, Y.: Semantic query optimization in datalog programs. In Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (May 1995), ACM
- Pauley, G., Larson, P.-A.: Exploiting uniqueness in query optimization.
In Proceedings of the 10th Conference on Data Engineering (1994), IEEE - Siegel, M. D. Automatic rule derivation for semantic query optimization.
In: Second internastional Conference on Expert Database Systems (198 - Ullman, J. D. Principles of Database and Knowledgebase Systems, vol. 1. Computer Science Press, 1988
Autor und Copyright
Siegfried Bell,
Universtät Dortmund,
Informatik VIII,
D-44221 Dortmund
bell@informatik.unidortmund.de
© 1996 Informatik Spektrum, Springer-Verlag Berlin Heidelberg