Information ausblenden
Willkommen im Forum für alle Datenbanken! Registriere Dich kostenlos und diskutiere über DBs wie Mysql, MariaDB, Oracle, Sql-Server, Postgres, Access uvm

Sort-Merge-Verbund

Dieses Thema im Forum "Datenmodellierung, Datenbank-Design" wurde erstellt von Miime, 16 September 2014.

  1. Miime

    Miime Neuer Benutzer

    Hallo ihr :)

    Leider wusste ich nicht so genau wo ich meine Frage hier im Forum posten soll, falls es eine unpassende Stelle ist, tut es mir Leid und bitte um die Verschiebung meiner Frage.

    Jetzt aber zum eigentlichen Problem.
    Ich schreibe demnächst eine Prüfung zum Thema Datenbanken, dazu bearbeite ich alte Klausuren. Jetzt bin ich auf eine Aufgabe gestoßen, die ich einfach nicht gelöst bekomme. Ich würde mich freuen wenn mir jemand helfen könnte.

    Aufgabe:

    Gegeben seien die folgenden zwei Tabellen Employee und Department:

    Employee =
    | EmpID | Salary | ... | DepID |
    | 4711 | 40000| ... | 42 |
    | ... | ... | ... | ... |​

    Department =
    | DepID | Manager | Project | ... |
    | 42 | Peter | P1175 | ... |
    | ... | ... | ... | ... |​

    Primärschlüssel sind durch Unterstreichen gekennzeichnet.
    Es soll folgende SQL-Anfrage ausgewertet werden:

    SELECT *
    FROM Employee, Department
    WHERE Employee.DepID = Department.DepID

    Es gelten folgende Annahmen:
    - die Tabelle Employe beinhalte t_E = 2000 Tupel
    - die Tabelle Department beinhalte t_D = 200 Tupel
    - ein Tupel von Employee sei 1kB groß, ein Tupel von Department 2 kB
    - die Seitengröße s beträgt 10 kb

    (a) Wie viele Tupel enthält das Ergebnis der Anfrage mindestens, wie viele maximal?

    (b) Angenommen die Tabellen sind jeweils bzgl. DepID sortiert. Geben Sie die mindestens und die höchstens benötigte Anzahl der lesenden Seitenzugriffe bezogen auf obige Größen für die Berechnung der Anfrage unter Verwendung des Sort-Merge-Verbundes an.

    Leider komme ich mit der Aufgabe gar nicht klar :(

    Ich weiß, dass der Aufwand des externen Sortierens einer Relation R beim Sort-Merge-Verbund

    x_R = (⌈log_k−1⌈N/k⌉⌉ + 1)2 · N

    beträgt, wobei k die Größe des Datenbakpuffers und N die Anzahl der Tupel der zur sortierenden Relation ist. Unter der Annahme, dass die Berücksichtigung von mehrfach auftretenden Werten in den Verbundattributen keine zusätzlichen Seitenzugriffe implizieren,
    ergibt sich der Aufwand zur Berechnung des Verbundes aus M + N + x_R1 + x_R2 = Aufwand.

    Leider weiß ich nicht einmal ob mir das großartig hilft, da in (b) steht, das die Tabellen jeweils bzgl. DepID sortiert sind.

    Würde mich über ein paar Ansätze, Tipps oder Lösungen freuen und bedanke mich schon im Vorraus :)

    Gruß,
    Mime
     
Die Seite wird geladen...

Diese Seite empfehlen

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies.
    Information ausblenden