-
Stand der Technik
-
Die
Erfindung betrifft die Optimierung von Abfragen in Datenbanksystemen
und, genauer gesagt, die Optimierung der Verknüpfungsreihenfolge in relationalen
Datenbanksystemen.
-
Eine
Datenbank stellt eine Sammlung von Daten dar. Eine relationale Datenbank
ist eine Datenbank, die von ihren Benutzern als eine Sammlung von
Tabellen wahrgenommen wird. Jede Tabelle ordnet Objekte (items)
und Attribute der Objekte in Reihen beziehungsweise Spalten an.
Jede Zeile einer Tabelle entspricht einem Objekt (das auch als Datensatz
oder Tupel bezeichnet wird), und jede Spalte einer Tabelle entspricht einem
Attribut des Objekts (das als Feld oder richtiger als ein Attributtyp
oder ein Feldtyp bezeichnet wird). Die Kardinalität einer
Tabelle T ist die Anzahl der Datensätze, die sie enthält, und
wird mit |T| bezeichnet.
-
Ein "Primärschlüssel" für eine Tabelle
ist ein einfaches oder zusammengesetztes Attribut, das Datensätze der
Tabelle eindeutig kennzeichnet. Der Schlüssel muss grundsätzlich eindeutig
und nicht nur zu einem bestimmten Zeitpunkt eindeutig sein. Es ist
möglich,
aber nicht üblich,
dass man eine Tabelle hat, bei der die einzige eindeutige Kennung
das zusammengesetzte Attribut ist, das aus allen Attributen der
Tabelle besteht. Es ist auch möglich,
aber nicht üblich,
dass eine Tabelle mehr als eine eindeutige Kennung hat. In diesem
Fall kann man sagen, dass die Tabelle mehrere in Frage kommende
Schlüssel
hat, von denen einer ausgewählt und
als Primärschlüssel festgelegt
werden könnte;
die verbleibenden in Frage kommenden Schlüssel würden dann als alternative Schlüssel bezeichnet
werden. Primärschlüssel und
alternative Schlüssel
müssen
zwei zeitunabhängige
Eigenschaften erfüllen.
Erstens dürfen
zu keinem Zeitpunkt zwei Datensätze
der Tabelle denselben Wert für
den Schlüssel
haben. Zweitens kann keine Komponente des Schlüssel entfernt werden, ohne die
Eigenschaft der Unverwechselbarkeit zu zerstören, wenn es sich bei dem Schlüssel um
einen zusammengesetzten Schlüssel
handelt.
-
Ein "Fremdschlüssel" ist ein möglicherweise
zusammengesetztes Attribut einer Tabelle, deren Werte notwendig
sind, um sie mit denjenigen des Primärschlüssels von einer Tabelle zu
vergleichen, die sich üblicherweise,
aber nicht notwendigerweise, von der Tabelle unterscheidet, für die der
Fremdschlüssel
festgelegt wird. Der Wert eines Fremdschlüssels stellt einen Verweis
auf den Datensatz dar, der den Wert des passenden Primärschlüssels enthält, wobei
dieser Datensatz als in Bezug genommener Datensatz oder als Zieldatensatz bezeichnet
werden kann. Die Tabelle, die den Fremdschlüssel enthält, kann als die in Bezug nehmende
Tabelle oder als Fremdtabelle bezeichnet werden, und die Tabelle,
die den entsprechenden Primärschlüssel enthält, kann
als die in Bezug genommene Tabelle oder als Zieltabelle oder Primärtabelle
bezeichnet werden.
-
Der
Suchlauf nach Daten in einer relationalen Datenbank erfolgt mittels
einer Abfrage. Eine Abfrage enthält
ein oder mehrere Prädikate,
die die Informationen angeben, welche mittels der Abfrage aus der
Datenbank abgerufen werden sollen. Eine Verknüpfungsabfrage ist eine Abfrage,
bei der Informationen aus mehr als einer Tabelle angefordert werden.
In einer Datenbank beispielsweise, die Telefonverzeichnis-Informationen in einer
Tabelle und Informationen über
das Arbeitsverhältnis
in einer anderen Tabelle speichert, könnte eine Verknüpfungsabfrage
die Namen aller Leute anfordern, die in derselben Stadt leben und
arbeiten.
-
Eine
Verknüpfungsabfrage
muss mindestens ein "Verknüpfungsprädikat" enthalten, das die
Kriterien festlegt, die zur Auswahl von Datensätzen aus den beiden Tabellen
verwendet werden. Eine Verknüpfungsabfrage
kann auch ein oder mehrere Prädikate
einer einzigen Tabelle enthalten, um Datensätze aus den einzelnen Tabellen
auszuwählen
(z.B. Angestellte, deren private Telefonnummern die Vorwahl 876
haben). Die Verknüpfungsselektivität einer
Verknüpfungsabfrage
ist das Verhältnis
der Anzahl der Übereinstimmungen,
die sich aus der Verknüpfung
ergeben (d.h. die Verknüpfungskardinalität), zum
Produkt der Kardinalitäten
der verknüpften
Tabellen.
-
Ein
Primärschlüssel einer
Tabelle P wird als P.Pk bezeichnet. Ein Fremdschlüssel einer
Tabelle S mit Bezug auf einen Primärschlüssel wird als S.Fk bezeichnet.
Eine Verknüpfung
von Primärschlüssel und
Fremdschlüssel
wird als Pk-Fk-Verknüpfung
bezeichnet. Eine Verknüpfung
von zwei Schlüsseln,
die in Bezug auf denselben Primärschlüssel beide
Fremdschlüssel
sind, wird als Fk-Fk-Verknüpfung
bezeichnet.
-
Eine
natürliche
Art und Weise, eine Verknüpfungsabfrage
durchzuführen,
besteht darin, jeden Datensatz in der zweiten Tabelle auf jeden
Datensatz in der ersten Tabelle zu prüfen, um festzustellen, ob es
Datensätze
gibt, die das Verknüpfungsprädikat erfüllen. Solche
Datensätze
gelten als übereinstimmende
Datensätze.
Das Datenbanksystem kann dann ein Zwischenergebnis (oder ein Endergebnis)
erstellen, das die übereinstimmenden
Datensätze,
die miteinander verknüpft
wurden, enthält.
-
Die
Durchführung
von mehreren Verknüpfungsabfragen
in großen
Datenbanken kann sehr zeitaufwendig und ressourcenintensiv sein.
Eine Möglichkeit,
eine Verknüpfungsabfrage
mit mehreren Verknüpfungen
schneller durchzuführen,
besteht darin, die Reihenfolge zu optimieren, in der Tabellen verknüpft werden. Eine
gute Verknüpfungsreihenfolge
kann die Anzahl der durchgeführten
Vergleiche beziehungsweise den Umfang der Zwischenergebnisse und
dadurch die Anzahl der eingesetzten Ressourcen und die zur Durchführung der
gesamten Abfrage insgesamt notwendige Zeit verringern. Es ist im
Allgemeinen jedoch schwierig, eine gute Verknüpfungsreihenfolge zu erhalten.
Herkömmliche
Optimierer für
die Verknüpfungsreihenfolge
stützen sich
stark auf Schätzwerte
der Kardinalitäten
von Zwischenergebnissen. Diese Kardinalitäten zu schätzen, ist im Allgemeinen ebenfalls
sehr schwierig. Die herkömmlicherweise
verwendeten Verfahren sind bestenfalls Näherungsverfahren und können in
manchen Fällen
ziemlich ungenau sein. Ein wirksameres und genaueres Verfahren zum
Schätzen
von optimalen Verknüpfungsreihenfolgen
ist daher wünschenswert.
-
Das
folgende Schriftstück
von Yushi Uno u.a. mit dem Titel "Complexity of the Optimum Join Order Problem
in Relational Databases, IEICE Transactions, JP, Institute of Electronics Information
and Comm. Eng. Tokyo, Band E74, Nr. 7, 1. Juli 1991 (01.07.1991),
Seiten 2067 bis 2075, XP000263060, ISSN: 0917-1673, beschreibt das
Problem, die optimale Verknüpfungsreihenfolge
zu finden (Absatz 2.6), wozu auch die mathematische Darstellung
eines Abfragegraphen und die Berechnung der Kardinalität der Abfrage
mit mehreren Verknüpfungen
gehört
(Seite 2069, Absätze
2.5 und 2.6).
-
Zusammenfassung der Erfindung
-
Die
vorliegende Erfindung stellt ein Verfahren nach Anspruch 1 und ein
entsprechendes System und Rechnerprogramm bereit.
-
Vorzugsweise
betrifft die Erfindung ein von einem Rechner ausgeführtes Verfahren
zur Berechnung einer guten Verknüpfungsreihenfolge
bei einer Abfrage mit mehreren Verknüpfungen, indem eine Maßzahl eingeführt wird,
deren Aufgabe es ist, die relative Wirksamkeit von alternativen
Verknüpfungsreihenfolgen
vergleichbar zu machen.
-
Vorzugsweise
betrifft die Erfindung ein von einem Rechner ausgeführtes Verfahren,
das dazu dient, die Verknüpfungsselektivität einer
Fk-Fk-Verknüpfung
zu schätzen,
das heißt,
einer Verknüpfung,
bei der das Verknüpfungsprädikat im
Wesentlichen die Form R.r = S.s. hat, wobei sowohl R.r als auch
S.s Fremdschlüssel in
Bezug auf einen Primärschlüssel oder
einen alternativen Schlüssel
von einer einzigen Primärtabelle
sind.
-
Vorzugsweise
betrifft die Erfindung ein von einem Rechner ausgeführtes Verfahren,
das dazu dient, die Verknüpfungskardinalität einer
beliebig großen
Zahl von mehreren Verknüpfungen
einschließlich
einer beliebigen Kombination von Pk-Fk-Verknüpfungen und Fk-Fk-Verknüpfungen
wirksam zu schätzen.
-
Zu
den Vorteilen der Erfindung gehört,
dass die Geschwindigkeit und die Leistungsfähigkeit von Verknüpfungsabfragen
verbessert werden. Weitere Vorteile der Erfindung sind in der folgenden
Beschreibung dargelegt und gehen aus der Beschreibung und den Ansprüchen hervor.
-
Kurze Beschreibung der Zeichnungen
-
1 ist
ein Blockschaltbild einer Universalrechnerplattform, die erfindungsgemäß programmiert
werden kann und eine relationale Datenbank enthält.
-
2 ist
ein Ablaufplan eines von einem Rechner ausgeführten Verfahrens, das dazu
dient, eine optimale Verknüpfungsreihenfolge
für einen
bestimmten Satz von Tabellen bei einer Verknüpfungsabfrage in einem relationalen
Datenbanksystem zu berechnen.
-
3 ist
ein Ablaufplan eines von einem Rechner ausgeführten Verfahrens, das dazu
dient, eine Abfrage mit mehreren Verknüpfungen in Form eines Graphen
darzustellen.
-
4 ist
eine Darstellung eines Verknüpfungsgraphen.
-
5 ist
ein Ablaufplan eines von einem Rechner ausgeführten Prozesses, um die Verknüpfungskardinalität einer
Abfrage mit mehreren Verknüpfungen
zu schätzen,
indem eine Darstellung der Verknüpfungsabfrage
in Form eines Graphen verwendet wird.
-
6 ist
eine Darstellung eines Verknüpfungsgraphen.
-
Ausführliche Beschreibung
-
Die
vorliegende Erfindung stellt Verfahren und Vorrichtungen zur Optimierung
der Verarbeitungsreihenfolge von Verknüpfungsabfragen in relationalen
Datenbanksystemen bereit.
-
1 zeigt
eine Universalrechnerplattform 10, die sich zur Unterstützung eines
relationalen Datenbanksystems 26 eignet, das erfindungsgemäß eine auf
Kardinalitäten
beruhende Optimierung von Verknüpfungen
durchführt.
Zur Plattform gehören
ein digitaler Rechner 12 (wie zum Beispiel ein Personal-Computer oder
ein Arbeitsplatzrechner), ein Bildschirm 14, eine Massenspeichereinheit 16 (wie
zum Beispiel ein Diskettenlaufwerk, ein Festplattenlaufwerk, ein
löschbares
CD-ROM-Laufwerk oder ein magneto-optisches Plattenlaufwerk), eine
Tastatur 18 und eine Maus 20 oder eine andere
Eingabeeinheit. Der Rechner 12 ist herkömmlich aufgebaut und enthält einen
Speicher 22, einen Prozessor 24 und andere gewöhnliche
Komponenten wie zum Beispiel einen Speicherbus und einen peripheren
Bus (nicht gezeigt). Der Rechner 12 enthält auch
Datenübertragungs-Hardware
und -Software (nicht gezeigt), mittels derer der Rechner 12 über eine
Datenübertragungsverbindung 36 und
ein Rechnernetzwerk 38 mit anderen Rechnern 40 verbunden
werden kann.
-
Das
Datenbanksystem 26 verwaltet eine Datenbank. Die Datenbank 28 kann
sich zentral auf einem einzigen Rechner befinden oder über das
Rechnernetzwerk 38 verteilt sein. Üblicherweise wird die Datenbank 28 von
einem Datenbanksystem 26 verwaltet, das auf einem Rechner
ausgeführt
wird, der entweder ständig oder
nur vorübergehend
mit der Datenbank verbunden ist. In dieser Darstellung ist das Datenbankverwaltungssystem
als ein System gezeigt, das auf dem Rechner 12 läuft.
-
Wie
zuvor erwähnt
wurde, stellt die Optimierung von Verknüpfungen, d.h. die Berechnung
einer optimalen Reihenfolge, in der Tabellen bei einer Abfrage mit
mehreren Verknüpfungen
verknüpft
werden sollen, eines der Probleme bei der Ausgestaltung und Realisierung
von relationalen Datenbanksystemen dar. Obwohl sich die Reihenfolge,
in der Tabellen miteinander verknüpft werden, nicht auf das Ergebnis
der Verknüpfung auswirkt,
können
verschiedene Verknüpfungsreihenfolgen
für dieselbe
Abfrage unterschiedlich viel Zeit und unterschiedlich viele andere
Ressourcen beanspruchen.
-
Betrachten
wir eine relationale Datenbank, die die Tabellen R, S und T enthält, eine
Verknüpfungsabfrage,
bei der die Tabellen R, S und T miteinander verknüpft werden
sollen, und zwei mögliche
Verknüpfungsreihenfolgen:
(1) Verknüpfe
die Tabellen R und S, und verknüpfe
anschließend
das Ergebnis mit der Tabelle T und (2) verknüpfe die Tabellen S und T, und
verknüpfe
dann das Ergebnis mit der Tabelle R. Betrachten wir zuerst die Verknüpfungsreihenfolge
(1). Wenn |(R join S)| = 20 und |((R join S) join T)| = 60, beträgt die Gesamtzahl
der Tupeln, die während
der Berechnung der Gesamtabfrage erzeugt wurden, 80 (20 + 60). Betrachten
wir dann die Verknüpfungsreihenfolge
(2). Wenn |(S join T)| = 500 und |((S join T) join R)| = 60, beträgt die Gesamtzahl
der Datensätze,
die während
der Berechnung der gesamten Verknüpfung angelegt wurden, 560 (500
+ 60). Die Wahl der Verknüpfungsreihenfolge
kann von großer
Bedeutung sein, insbesondere bei mehreren Verknüpfungen, die große Tabellen
einschließen.
-
Eine
neue Maßzahl
Sigma wird verwendet, um bei einer Abfrage mit mehreren Verknüpfungen
eine Verknüpfungsreihenfolge
aus mehreren möglichen
Verknüpfungsreihenfolgen
auszuwählen.
Die Maßzahl
Sigma gibt einen Hinweis auf die Komplexität einer Verknüpfung, der
auf geschätzten
Kardinalitäten
beruht. Vorzugsweise wird Sigma als die Summe der Anzahl der Tupeln
definiert, die sich schätzungsweise
aus jeder Verknüpfung
ergeben, wenn diese in einer Verknüpfungsreihenfolge durchgeführt wird.
Bei Verwendung der Maßzahl
Sigma wird die Verknüpfungsreihenfolge,
bei der Sigma von allen Verknüpfungsreihenfolgen
den kleinsten Wert hat, als die optimale Verknüpfungsreihenfolge ausgewählt und
zur Durchführung
der Verknüpfung verwendet.
Verbindungen zwischen Verknüpfungsreihenfolgen,
die in Wettbewerb miteinander stehen, können mit Hilfe einer anderen
Heuristik unterbrochen werden, die beispielsweise auf weiteren Kostenschätzungen beruhen
kann. In dem vorstehenden Beispiel beträgt der Wert von Sigma für die Verknüpfungsreihenfolge
(1) 80, und der Wert von Sigma für
die Verknüpfungsreihenfolge
(2) beträgt
560, was anzeigt, dass die Reihenfolge (1) gegenüber der Reihenfolge (2) bevorzugt
wird.
-
2 zeigt
einen von einem Rechner ausgeführten
Prozess 110, der mit Hilfe der Maßzahl Sigma eine Verknüpfungsreihenfolge
aus den möglichen
Verknüpfungsreihenfolgen
für eine
Verknüpfungsabfrage auswählt, die
die Tabellen T = {T1, T2, T3, ... Tn} einschließt. Zuerst wird aus den möglichen
Verknüpfungsreihenfolgen
eine Verknüpfungsreihenfolge
ausgewählt
(Schritt 120). Dann wird die Kardinalität einer jeden Komponentenverknüpfung in
der Verknüpfungsreihenfolge
abgerufen (Schritt 130). Dies kann geschehen, indem man die
Kardinalität
mit Hilfe des nachstehend beschriebenen Verfahrens zur Darstellung
von Graphen schätzt,
einen vorab berechneten Wert abruft oder ein anderes Verfahren anwendet.
Es ist für
die Berechnung des Wertes von Sigma nicht notwendig, dass diese
Kardinalitäten
mit Hilfe eines bestimmten Verfahrens berechnet werden. Ein Wert
für Sigma
wird berechnet, indem jeder dieser Schätzwerte der Kardinalität addiert
wird (Schritt 140). Wenn dieser Sigma-Wert der kleinste Sigma-Wert ist, der
bisher angetroffen wurde, werden sowohl der Wert von Sigma als auch
die entsprechende Verknüpfungsreihenfolge
gespeichert (Schritt 150). Wenn noch weitere Verknüpfungsreihenfolgen
zur Prüfung übrig bleiben,
wird der Prozess für
die nächstmögliche Verknüpfungsreihenfolge
wiederholt (Schritt 160). Andernfalls wird eine Verknüpfungsreihenfolge
mit dem kleinsten Wert von Sigma zur Durchführung der Verknüpfungsabfrage
verwendet (Schritt 170).
-
Verknüpfungskardinalitäten bei
einer Abfrage mit mehreren Verknüpfungen
können
geschätzt
werden, indem man die Abfrage in Form von einem Graphen darstellt
und diese Darstellung verwendet. Bevor beschrieben wird, wie ein
Verknüpfungsgraph
verwendet wird, wird jedoch die Vorgehensweise beim Schätzen einzelner
Verknüpfungskardinalitäten und
Verknüpfungsselektivitäten beschrieben.
-
Betrachten
wir die Verknüpfung
von Pk-Fk mit R.Pk = S.Fk (Pk-Fk
join R.Pk = S.Fk). Die Kardinalität einer solchen Verknüpfung ist
gleich der Kardinalität
der Fremdtabelle (in diesem Beispiel der Tabelle S), da der Wert
eines jeden Fremdschlüssels
genau einem Datensatz in der Primärtabelle entspricht. Betrachten
wir beispielsweise eine Datenbank, die eine Tabelle P mit Universitätsprofessoren
und eine Tabelle S der Klassen, die sie unterrichten, enthält. P.profID
ist ein Primärschlüssel, der
jeden Professor eindeutig ausweist. S.teacher ist ein Attribut,
das den einen Professor ausweist, der eine Klasse unterrichtet.
S.teacher ist daher ein Fremdschlüssel für P. Eine Verknüpfungsabfrage,
die über
das Verknüpfungsprädikat S.teacher
= P.profID verfügt, welches
die Form S.Fk = P.Pk hat, hat eine Kardinalität, die gleich |S| ist, da jede
Klasse von genau einem Professor unterrichtet wird.
-
Die
Verknüpfungsselektivität einer
Verknüpfungsabfrage
ist das Verhältnis
der Anzahl der Übereinstimmungen,
die sich aus der Verknüpfung
ergeben (d.h. die Verknüpfungskardinalität), zum
Produkt der Kardinalitäten
der verknüpften
Tabellen. Folglich ist die Verknüpfungsselektivität einer
Pk-Fk-Verknüpfung
durch die folgende Gleichung gegeben, wobei R die Primärtabelle
ist:
-
Um
die Kardinalität
und Selektivität
einer Fk-Fk-Verknüpfung
zu schätzen,
betrachten wir folgende SQL-Abfrage, die eine Fk-Fk-Verknüpfung einschließt:
-
[Beispiel 1]
-
- WÄHLE·AUS S.
T AUS
- WOBEI S.Fk = T.Fk
-
In
diesem Beispiel ist R.Pk der zugrunde liegende Primärschlüssel für S.Fk und
auch für
T.Fk. Wenn die Werte der Schlüssel,
die bei einer solchen Abfrage verwendet werden, im Wesentlichen
gleichmäßig in ihren
Tabellen verteilt sind und alle Werte der Primärschlüssel hauptsächlich unter den Fremdschlüsseln gefunden
werden, ist |S|/|R| für
jeden einzelnen Wert eines Primärschlüssels ein
guter Schätzwert
für die
Häufigkeit, mit
der der Wert in S.Fk vorkommt, und |T|/|R| ist ein guter Schätzwert für die Häufigkeit,
mit der der Wert in T.Fk vorkommt. Man kann deshalb die Verknüpfungskardinalität der Verknüpfung von
S.Fk = T.Fk wie folgt schätzen:
-
Von
der Definition der Verknüpfungsselektivität und den
zuvor erwähnten
Annahmen kann man die Verknüpfungsselektivität einer
Fk-Fk-Verknüpfung
wie folgt schätzen:
-
Man
beachte, dass die geschätzte
Verknüpfungsselektivität sowohl
bei der Pk-Fk-Verknüpfung
als auch bei der Fk-Fk- Verknüpfung gleich
1/|R| ist, wobei |R| die Kardinalität der Tabelle mit den Primärschlüsseln ist.
-
Wie
in 3 gezeigt ist, kann ein von einem Rechner ausgeführter Prozess 200 genutzt
werden, um eine Abfrage mit mehreren Verknüpfungen in Form von einem Verknüpfungsgraphen
G = (V,E) darzustellen, wobei V die Gruppe der Scheitelpunkte ist,
die den Tabellen in der Abfrage eins zu eins entsprechen, und E eine
Gruppe von Kanten ist, die den Verknüpfungsprädikaten (den ausgedrückten und
inbegriffenen) in der Abfrage eins zu eins entsprechen. Um den Prozess
zu verstehen, betrachten wir die folgende Verknüpfungsabfrage:
-
[Beispiel 2]
-
- WÄHLE·AUS R,
S, T AUS
- WOBEI R.Pk = S.Fk
- UND R.Pk = T.Fk
-
Um
einen Verknüpfungsgraphen
zu bilden, der diese Verknüpfung
darstellt, müssen
im ersten Schritt alle ausgedrückten
Verknüpfungsprädikate erfasst
werden (Schritt 220). Im Beispiel 2 gibt es zwei solche
Prädikate:
R.Pk = S.Fk und R.Pk = T.Fk. Der nächste Schritt dient der Erfassung
aller inbegriffenen Verknüpfungsprädikate (Schritt 230).
Im Beispiel 2 bedeuten R.Pk = S.Fk und R.Pk = T.Fk, dass S.Fk =
T.Fk.
-
Als
Nächstes
werden für
jedes Prädikat,
das erfasst worden ist, ein Paar Scheitelpunkte und eine Kante,
die die Scheitelpunkte verbindet, zu dem Graphen hinzugefügt (Schritte 240 bis 290).
Wenn ein Prädikat vom
Verknüpfungstyp
Pk-Fk ist, ist die entsprechende Kante von der Primärtabelle
auf die Fremdtabelle gerichtet (Schritt 270). Wenn ein
Prädikat
vom Verknüpfungstyp
Fk-Fk oder von einem anderen Verknüpfungstyp ist, ist die entsprechende
Kante nicht gerichtet (Schritt 280). Der Verknüpfungsgraph,
der im Beispiel 2 der Verknüpfungsabfrage
entspricht, ist in 4 gezeigt.
-
Die
Kardinalität
einer Verknüpfungsabfrage,
bei der die Verknüpfungsspalten
unabhängig
sind, kann durch Multiplikation geschätzt werden: (1) das Produkt
der Selektivitäten
der Komponentenverknüpfungen,
(2) das Produkt der Kardinalitäten
der einzelnen Tabellen bei der Verknüpfung und (3) das Produkt der
Selektivitäten
der gegebenenfalls vorgenommenen einzelnen Selektionen in den Tabellen.
Die Unabhängigkeit
der Verknüpfungsspalten
ist eine Annahme, die von allen herkömmlichen Optimierern getroffen
wird. Die Selektivitäten
von Komponentenverknüpfungen
der Form P.Pk = S.Fk und S.Fk = T.Fk kann mit Hilfe der vorstehend
beschriebenen Verfahren geschätzt
werden. Ein Optimierer für
Abfragen an Datenbanksysteme kann ein beliebiges anderes Verfahren
verwenden, das ihm zur Verfügung
steht, um die Selektivität
von anderen Arten von Verknüpfungen
zu berechnen oder zu schätzen.
-
Wenn
man diese Formel auf den Verknüpfungsgraphen
400 (
4)
anwendet, kann die Kardinalität der
Abfrage wie folgt berechnet werden:
-
Obwohl
herkömmliche
Optimierer für
die Verknüpfungsreihenfolge
tatsächlich
zu diesem Ergebnis kommen, wurde ein besserer Schätzwert gefunden,
nämlich:
-
Die
Beobachtung, dass sich N Tupeln ergeben, wenn die Tabellen S und
T zuerst verknüpft
werden, bestätigt
dies. Da in jeder Zeile von (S, T) "S.Fk = T.Fk" gilt, verknüpft sich eine jede solche Tupel
mit genau einer Tupel von R, und folglich ergeben sich keine weiteren
Tupeln.
-
Wie
in 5 gezeigt ist, nutzt ein von einem Rechner ausgeführter Prozess 500,
mit dem mittels der Darstellung des Verknüpfungsgraphen die Kardinalität einer
Mehrfachverknüpfung
geschätzt
wird, diese Einsicht und kommt zu dem korrekten Ergebnis, indem
er den Graphen bei dem Schätzvorgang ändert.
-
Zuerst
wird die Verknüpfungsabfrage
in Form eines Graphen dargestellt, beispielsweise mittels der Prozedur 200 (3).
Als Nächstes
werden alle Endscheitelpunkte aus dem Graphen entfernt (Schritte 530 bis 570).
Ein Endscheitelpunkt ist ein Scheitelpunkt, auf den keine anderen
Scheitelpunkte in dem Graphen zeigen. Der Scheitelpunkt R 410 in 4 ist
zum Beispiel ein Endscheitelpunkt.
-
Um
Endscheitelpunkte zu entfernen, prüft die Prozedur 500 jeden
Scheitelpunkt in dem Graphen (Schritt 540). Wenn der Scheitelpunkt
ein Endscheitelpunkt ist, werden er und alle angrenzenden Kanten
gelöscht
(Schritt 550). Wenn bei diesem Durchlauf des Graphen Endscheitelpunkte
gelöscht
werden, erfolgt daraufhin ein weiterer Durchlauf (Schritt 570),
da das Entfernen eines Endscheitelpunkts dazu führen kann, dass ein weiterer
Endscheitelpunkt erzeugt wird.
-
Sobald
alle Endscheitelpunkte entfernt worden sind, kann die Verknüpfungskardinalität der ursprünglichen
Verknüpfung
mit Hilfe des verbleibenden Graphen geschätzt werden, indem Folgendes
multipliziert wird: (1) die Selektivität der von jeder Kante dargestellten
Verknüpfung,
(2) die Kardinalität
der von jedem Scheitelpunkt dargestellten Tabelle und (3) die einzelne
Selektivität
der von jedem Scheitelpunkt dargestellten Tabelle (Schritt 580).
Wie vorstehend erwähnt
wurde, wird bei dieser Schätzung
davon ausgegangen, dass die Verknüpfungsspalten unabhängig sind.
-
Welche
Auswirkung das Entfernen von Endscheitelpunkten hat, zeigt sich
bei der Verarbeitung der folgenden Abfrage:
-
[Beispiel 3]
-
- WÄHLE·AUS R,
S, T AUS
- WOBEI R.Pk = S.Fk
- UND S.Pk = T.Fk
-
Die
Kardinalität
des Ergebnisses ist |T|. Die Verknüpfung von R und S stimmt mit
allen Zeilen von S überein,
und die anschließende
Verknüpfung
von S und T stimmt mit allen Zeilen von T überein, wobei die Kardinalität dieses
Ergebnisses |T| beträgt.
Dasselbe Ergebnis erhält
man, wenn man die Darstellung des Graphen mit Hilfe des Verfahrens
von 5 auswertet.
-
Der
Verknüpfungsgraph 600 in 6 stellt
die Abfrage im Beispiel 3 dar. Die Kanten 620, 640 sind
mit den jeweiligen Verknüpfungsprädikaten
bezeichnet. Der Scheitelpunkt R 610 ist ein Endscheitelpunkt.
Wenn der Scheitelpunkt R 610 und die daran angrenzende
Kante 620 entfernt werden, bleibt eine einzelne Kante 640 übrig, die
den Scheitelpunkt S 630 mit dem Scheitelpunkt T 650 verbindet.
Der Scheitelpunkt S 630 ist nun ein Endscheitelpunkt, so
dass der Scheitelpunkt S 630 und die daran angrenzende
Kante 640 entfernt werden und damit nur der Scheitelpunkt
T 650 übrig
bleibt. Die Kardinalität
des Verknüpfungsergebnisses
ist daher |T|.
-
Die
vorliegende Erfindung wurde in Bezug auf eine Ausführungsform
beschrieben. Die Erfindung ist jedoch nicht auf die dargestellte
und beschriebene Ausführungsform
beschränkt.
Beispielsweise wurde die Erfindung in Bezug auf eine Software-Ausführung beschrieben,
doch kann die Erfindung in Software oder Hardware oder Firmware
oder einer Kombination der drei ausgeführt werden. Der Umfang der
Erfindung wird von den Ansprüchen
näher angegeben.
