Umformungsregeln E1 >◁ E2 ≡ E2 >◁ E1 E1 × E2 ≡ E2

Logische Optimierung
Umformungsregeln
Eine Reihe von Regeln, die auf der Relationalen Algebra
aufbauen, erlauben die Umformung der Anfrage:
Regeln für Verbund und kartesisches Produkt
(1) Kommutativität
E1 E2 ≡ E2 E1
E1 × E2 ≡ E2 × E1
(2) Assoziativität
E1 (E2 E3) ≡ (E1 E2) E3 .
E1 × (E2 × E3) ≡ (E1 × E2) × E3 .
Regeln für Selektion und Projektion
(3) Zusammenfassung von Projektionen
Bedingungen:
{Ai  i = 1, ..., n} ⊆ {Bi i = 1, ..., m}.
πAi,...,An(πB1,...,Bm(E)) ≡ πA1,...An(E).
(3) Zusammenfassung/Kommutativität von
Selektionen:
σF1(σF2(E)) ≡ σF2∧F1(E).
σF1(σF2(E)) ≡ σF2(σF1(E)).
Grundlagen der Datenbanksysteme I
VIII-13
Logische Optimierung
(5) Kommutativität Selektion-Projektion
Bedingung F bezieht sich nur auf Attribute Ai:
πA1,...,An(σF(E)) ≡ σF(πA1,...,An(E)).
Bedingung F bezieht sich auf alle Attribute B
und möglicherweise auf Attribute Ai:
πA1,...,An(σF(E)) ≡
πA1,...,An(σF(πA1,...,An,B1,...,Bm(E))).
(6) Kommutativität Selektion-Kartesisches Produkt
Bedingung F = F1 ∧ F2 bezieht sich auf
Attribute von E1 und E2
Fi bezieht sich nur auf Attribute von Ei
σF(E1 x E2) ≡ σF1(E1) x σF2(E2).
F1 bezieht sich nur auf Attribute von E1, F2
bezieht sich auf Attribute von E1 und E2
σF(E1 x E2) ≡ σF2(σF1(E1) x E2).
(7) Kommutativität Selektion-Vereinigung
σF(E1 ∪ E2) ≡ σF1(E1) ∪ σF2(E2).
(8) Kommutativität Selekton-Mengendifferenz
σF(E1 - E2) ≡ σF1(E1) - σF2(E2).
Grundlagen der Datenbanksysteme I
VIII-14
Logische Optimierung
(9) Kommutativität Projektion-Kartesisches Produkt
Bi sind Attribute von E1, Ci sind Attribute von E2.
{Ai | i = 1,..,n} = {Bi | i = 1,...,m} ∪ {Ci | i = 1,...,k}
πA1,...,An(E1 x E2) ≡
πB1,...,Bm(E1) x πC1,...,Ck(E2).
(10) Kommutativität Projektion-Vereinigung
πA1,...,An(E1 ∪ E2) ≡ πA1,...,An(E1) ∪
πA1,...,An(E2).
Der Verbund ist hierbei darstellbar als Kombination von
kartesischem Produkt, Projektion und Selektion, deshalb
folgen die Regeln für Kommutativität von Selektion und
Verbund aus (4), (5) und (6).
Achtung: Es gilt keine Kommutativität zwischen
Mengendifferenz und Projektion!
Grundlagen der Datenbanksysteme I
VIII-15
Logische Optimierung
Ein einfacher Optimierungsalgorithmus:
(1) Umformulierung der Anfrage, so daß nur noch
Grundoperationen verwendet werden.
(Auflösung der Verbünde und Divisionen)
(2) Zuordnung der Attribute zu den Relationen (Volle
Qualifizierung)
(3) Aufstellen des Operatorbaumes
(4) Zerlegung der Selektionen der Art σF1 ∧ ... ∧ Fn(E)
nach Regel (4) in σF1(...(σFn(E))...).
(5) Verlagerung der Selektionen soweit wie möglich in
Richtung Blätter mit Regeln (4) - (8).
(Selektionen, die sich nur auf ein Attribut und eine
Konstante beziehen, können fast immer zu ihrer
Relation wandern)
(6) Zusammenfassung aller direkt
aufeinanderfolgenden Selektionen zu einer
einzigen Selektion
(7) Verlagerung der obersten Projektion mit Regeln
(3), (5), (9) und (10) durch den Baum bis hin zu den
Blättern. (Bei binären Operationen aufspalten)
(8) Ergebnisangabe als Relationaler Ausdruck.
Grundlagen der Datenbanksysteme I
VIII-16
Logische Optimierung
Beispiele:
BOOKS (TITLE,AUTHOR,PNAME,LC_NO)
PUBLISHERS (PNAME,PADDR,PCITY)
BORROWERS (NAME,ADDR,CITY,CARD_NO)
LOANS (CARD_NO,LC_NO,DATE)
PNAME = publisher’s name
LC_NO = Library of Congress number
PADDR = the street address of a publisher
PCITY = the city in which a publisher is located
CARD_NO = the library card number
DATE = the date on which a book was borrowed
Grundlagen der Datenbanksysteme I
VIII-17
Logische Optimierung
Beispiel 1
σ CITY = ' Frankfurt ' ∧ DATE <1.1.1997 ( BOOKS >< LOANS >< BORROWERS)
σ
BOOKS
BORROWERS
LOANS
Assoziativität des
Verbundes
(2) (6)
Kommutativität
Selektion /
kartesisches
Produkt
BOOKS >< (σ CITY = ' Frankfurt ' ∧ DATE <1.1.1997 ( LOANS >< BORROWERS) )
BOOKS
σ
LOANS
Grundlagen der Datenbanksysteme I
BORROWERS
VIII-18
Logische Optimierung
Beispiel 1 (Fortsetzung)
BOOKS >< (σ CITY = ' Frankfurt ' ∧ DATE <1.1.1997 ( LOANS >< BORROWERS) )
Kommutativität
Selektion /
kartesisches
Produkt
(6)
BOOKS >< ( σ DATE <1.1.1997 ( LOANS) >< σ CITY = ' Frankfurt ' ( BORROWERS) )
BOOKS
σ
LOANS
Grundlagen der Datenbanksysteme I
σ
BORROWERS
VIII-19
Logische Optimierung
Beispiel 2
π NAME,CARD_ NO,DATE (σ TITLE = 'DATABASES' ( BOOKS )
>< ( LOANS >< BORROWERS ) )
π
σ
BOOKS LOANS BORROWERS
Assoziativität
des Verbundes
(2) (3) (9)
Kommutativität
Selektion
(Projektion)/
kartesisches
Produkt
π NAME,CARD_ NO,DATE (
π CARD_ NO,DATE (σ TITLE = 'DATABASES' ( BOOKS )>< LOANS )
>< BORROWERS )
Grundlagen der Datenbanksysteme I
VIII-20
Logische Optimierung
Beispiel 2 (Fortsetzung)
π NAME,CARD_ NO,DATE (
π CARD_ NO,DATE (σ TITLE = 'DATABASES' ( BOOKS )>< LOANS )
>< BORROWERS )
π
π
BORROWERS
σ
LOANS
BOOKS
Grundlagen der Datenbanksysteme I
VIII-21
Logische Optimierung
Beispiel 3 (Ullman)
XLOANS = π S (σ F ( LOANS × BORROWERS × BOOKS ) )
mit:
F ≡ BORR. CARD _ NO = LOANS . CARD _ NO ∧
BOOKS . LC _ NO = LOANS . LC _ NO
S ≡ TITLE , AUTHOR, PNAME , LC _ NO, NAME ,
ADDR, CITY , CARD _ NO, DATE
π TITLE ( σ DATE <1/1/82 ( XLOANS ) )
Schritt 1: Teilen der Selektion F in F1 und F2:
F1 ≡ BORR. LC _ NO = LOANS . LC _ NO
F2 ≡ BOOKS . CARD _ NO = LOANS . CARD _ NO
Schritt 2: Selektionen den Baum „hinunterbewegen“
( (
))
π TITLE π S σ F 2 (σ F 1(σ DATE <1/1/82 ( LOANS ) × BORR) × BOOKS )
Grundlagen der Datenbanksysteme I
VIII-22
Logische Optimierung
Schritt 3: Vereinigung der beiden Projektionen zu:
π TITLE
Schritt 4: Aufspalten der Folge
π TITLE ( σ F 2 (Κ ) )
mit Regel 5 in:
( (
π TITLE σ F 2 π TITLE , BOOKS . LC _ NO , LOANS . LC _ NO (Κ )
))
Dann Aufspalten der zweiten Projektion nach Regel 9:
π TITLE , BOOKS . LC _ NO und π LOANS . LC _ NO
(
π TITLE ( σ F 2 π LOANS . LC _ NO ( σ F 1( σ DATE <1/1/82 ( LOANS )
× BORR ) ) × π TITLE , BOOKS . LC _ NO ( Books) ))
Grundlagen der Datenbanksysteme I
VIII-23
Logische Optimierung
Schritt 5: Aufspalten der Folge
π LOANS . LC _ NO ( σ F 1(Κ ) )
mit Regel 5 in:
( (
π LOANS . LC _ NO σ F 1 π LOANS . LC _ NO , BORR.CARD _ NO , LOANS .CARD _ NO (Κ )
Schritt 6:Die zweite Projektion aufspalten und vor das
kartesische Produkt bringen (Regeln 5 und 9):
(
π TITLE ( σ F 2 π LOANS . LC _ NO ( σ F 1( π LOANS . LC _ NO , LOANS .CARD _ NO (
σ DATE <1/1/82 ( LOANS ) ) × π BORR .CARD _ NO ( BORR ) ))
× π TITLE , BOOKS . LC _ NO ( Books) ))
Grundlagen der Datenbanksysteme I
VIII-24
))
Logische Optimierung
Beispiel: Kartesisches Produkt
AB
CD
nCD (Datensätze)
nAB
Strategie: Lade so viele Blöcke von AB wie möglich in
den Hauptspeicher und lasse dabei Platz für
einen Block von BC.
AB
CD
m Hauptspeicher-Blöcke
•
n AB , nCD : Sätze.
•
bAB , bCD : Sätze/Block.
•
m : Anzahl der Blöcke im Hauptspeicher.
Grundlagen der Datenbanksysteme I
VIII-25
Logische Optimierung
• Anzahl der Block-Zugriffe um AB zu lesen: n AB b AB .
• CD muss
n AB (m − 1) b AB - mal gelesen werden.
Jedes Mal werden dazu nCD bCD Zugriffe benötigt.
Anzahl der Block-Zugriffe:
n AB
n AB
n
+
⋅ CD =
bAB (m − 1) − bAB bCD

n AB 
nCD
⋅ 1 +

bAB  (m − 1) b CD 
Grundlagen der Datenbanksysteme I
VIII-26
Logische Optimierung
Beispiel:
n AB = nCD = 10 000
bAB = bCD = 5
m = 100
Anzahl der Zugriffe = 42.400.
Bei 20 Block-Zugriffen pro Sekunde wird dieses
kartesische Produkt ca. 35 Minuten benötigen.
Wähle AB als die Relation, mit dem kleineren
Quotienten
n AB
.
bAB
Das heißt, die Relation, die in weniger Blocks
passt.
Grundlagen der Datenbanksysteme I
VIII-27