Oskar Skibski, grupa nr 4, sala 2043

Bazy danych 2015/16

Laboratorium 13 (18.01.2016) - QP / Plany zapytań

Podstawy teoretyczne były na wykładzie. Parę rzeczy które musimy wiedzieć zanim przejdziemy dalej:

Tabela jest reprezentowana przez plik. Plik składa się ze stron. Strona składa się z rekordów, które odpowiadają wierszom tabeli.
Dane są przechowywane na dysku. Aby na nich operować musimy je sprowadzić do pamięci RAM. Jest ona podzielona na ramki takiej samej wielkości jak strony. Koszt operacji bazodanowej wyrażamy w ilości stron przesłanych pomiędzy dyskiem a RAMem (ilość odczytów plus ilość zapisów).

Więcej: http://edu.pjwstk.edu.pl/wyklady/szb/scb/rW8.htm
Indeks to dodatkowa struktura danych, której celem jest przyśpieszenie wyszukiwania rekordu podług konkretnego "klucza wyszukiwania" (pola lub paru pól). Dwie podstawowe implementacje: indeks na B+ drzewach (link) i indeks hashowany (link). Jeżeli w pliku indeksu mamy tylko wskaźniki do rekordów danych, to indeks jest zewnętrzny. Jeżeli plik indeksu zawiera plik danych to indeks jest wewnętrzny.

Więcej: http://edu.pjwstk.edu.pl/wyklady/szb/scb/rW9.htm
Każdą instrukcję SQL możemy przedstawić jako żłożenie operatorów relacyjnych. Podstawowe operatory: selekcja, projekcja (ograniczenie zbioru kolumn), złączenie, agregacja i operatory algebraiczne. Najbardziej złożona i najkosztowniejsza jest oczywiście operacja złączenia. Możemy ją wykonać na parę sposobów:
- Simple Nested Loops Join - dla każdego wiersza tabeli zewnętrznej przeglądamy wszystkie wiersze tabeli wewnętrznej
- Index Nested Loops Join - dla każdego wiersza tabeli zewnętrznej szukamy pasujących wierszy w tabeli wewnętrznej z użyciem indeksu
- Sort Merge Join - sortujemy obie tabele i "scalamy" do wspólnego wyniku
- Hash Join - rozrzucamy rekordy do "kubełków" podług kolumny złączenia, łączymy "kubełki" z takimi samymi wartościami
Staramy się wybrać plan zapytania który będzie działał w miejscu (czyli nie używał dodatkowej pamięci dyskowej), a zatem staramy się uzyskać przetwarzanie potokowe - wynik danej operacji jest wejściem dla kolejnej.

Więcej: http://edu.pjwstk.edu.pl/wyklady/szb/scb/rW10.htm

Zadanie 1. (egzamin 2008)

Dany jest następujący schemat tabeli reprezentującej odcinki dwukierunkowych linii kolejowych (w tabeli odcinki nie powtarzają się):

CREATE TABLE odcinki (
  stacjaA VARCHAR(15) NOT NULL,
  stacjaB VARCHAR(15) NOT NULL,
  dlugosc INTEGER
);

Napisz w algebrze relacji zapytanie o to, czy z Warszawy można dojechać do Gdyni w co najwyżej dwóch przesiadkach.

Zadanie 2. (egzamin 200?)

Napisać w algebrze relacji następujące zapytanie:

SELECT o.PESEL klient
FROM Osoby o
WHERE NOT EXISTS (SELECT 6+7 FROM Telefony WHERE o.PESEL = PESEL);

Zadanie 3. (egzamin 2008)

SZBD ma bufory pamięci operacyjnej na 100 bloków dyskowych. Tabela Zamowienia (numer NUMBER(10), towar VARCHAR(20), ilosc NUMBER(10)) zajmuje 10000 bloków dyskowych. W jednym bloku mieszczą się informacje o 50 zamówieniach. Wykonano następujące zapytanie:

SELECT towar
FROM Zamowienia
GROUP BY towar
HAVING SUM(ilosc) >= ALL (SELECT SUM(ilosc) FROM Zamowienia GROUP BY towar);

Podaj jak najefektywniejszy plan wykonania tego zapytania i oszacuj kost tego planu (podaj liczbę operacji odczytu i zapisu bloku dyskowego) przy założeniu, że nie korzystamy z żadnych indeksów i że na początku wszystkie bufory są puste, a dane są tylko na dysku.

Zadanie 4. (egzamin 200?)

Schemat danych:
Osoby(PESEL (PK), Imie, Nazwisko, Miasto); Telefony(Numer (PK), PESEL, Abonament);

Dane jest zapytanie:

SELECT PESEL
FROM Telefony, Osoby
WHERE Telefony.PESEL = Osoby.PESEL
 AND Miasto BETWEEN 'A' AND 'CZZZZ'
 AND Abonament = 'Standardowy';

Wskazać struktury pomocnicze, które najlepiej wspierają wykonanie tego zapytania. Podać najlepszy plan wykonania zapytania działający przy założeniu istnienia tych struktur. Oszacować jego koszt w terminach operacji wejścia-wyjścia.