baza danych

by Piotr Pelczar on Databases, Matematyka, Optymalizacja, Planeta, Przemyślenia, Publikacje, Solutions

Indeksowanie baz danych, funkcje mieszające

Występowanie złożonych baz danych jest coraz bardziej popularne, a komercyjne rozwiązania praktykują składowanie informacji nie tylko na pojedynczych bazach, przestrzeniach, dyskach, czy nawet serwerach. Szybki dostęp do danych to podstawa, dlatego pochylimy się nad czysto teoretycznym problemem dostępu do informacji, które wprawdzie są rozwiązane i zaszyte w mechanizmach poruszania się po większości baz, natomiast ich znajomość pozwoli dodatkowo zoptymalizować struktury, które projektujemy. Z góry podkreślam, że artykuł jest bynajmniej wyczerpujący, specjalistycznej i bardziej szczegółowo zarysowanej teorii baz danych należy szukać w publikacjach i tu zachęcam do odwiedzenia politechnicznych bibliotek.

Baza danych jako zbiór informacji powinna oferować trzy podstawowe operacje:

  • Szukanie jako dostęp do pojedynczego, unikatowego „obiektu” (zazwyczaj rekordu) w bazie danych.
  • Wyszukiwanie jako dostęp do elementów spełniających dane kryteria.
  • Modyfikacja danych.

Pojęcie klucza

Kluczem w bazie danych jest atrybut każdego elementu/rekordu jakiejś klasy (np. pojedynczej tabli danych), który pomoże go zidentyfikować przy szukaniu lub wyszukiwaniu w sposób jednoznaczny (wtedy mówi się o kluczu podstawowym Primary Key) lub niejednoznaczny (wtedy mówi się o indeksie Index). Za pomocą klucza jesteśmy w stanie dostać się do rekordu przeszukując tylko strukturę indeksów, zamiast samą bazę.

Skrócenie drogi dostępu

Przy szukaniu konkretnego elementu, którego unikalny atrybut jest z góry znany używamy właśnie kluczy podstawowych. Jest to gigantyczne przyspieszenie procesu wyszukania elementu. Jak wiemy, niektóre klucze zachowują pewną prawidłowość, na przykład stale rosną. Najprostszym przykładem jest identyfikator rekordu, którego wartość zazwyczaj się inkrementuje. Klucze to nic innego jak para informacji: wartość klucza oraz adres komórki pamięci, do której klucz należy.

Wykorzystanie klucza podstawowego to wskazanie miejsca ulokowania rekordu w dowolnej pamięci (na przykład adresu pamięci, adresu na dysku, offset w pliku, itd.)

Uporządkowany zbiór kluczy podstawowych

Co nam daje uporządkowany zbiór kluczy? Żeby dowiedzieć się, gdzie w pamięci jest ulokowany nasz rekord, najpierw trzeba dostać się do wartości klucza. W przypadku uporządkowanego zbioru danych wartości kluczy możemy w łatwy sposób go odnaleźć, na przykład metodą połowienia zbioru lub dostępu do wcześniej ułożonego drzewa. Najoptymalniejsze do odszukiwania jest drzewo ważone, ponieważ w przypadku nieważonego przy stale wzrastającej wartości klucza przy prawidłowości, że prawe gałęzie drzewa mają wartości większe, drzewo rosłoby tylko w jedną stronę, a w rezultacie otrzymalibyśmy listę, w której odszukiwanie nie jest optymalnym rozwiązaniem. Ważenie drzewa nie jest jednak rozsądnym rozwiązaniem w bazach danych, w których jest więcej żądań (a właściwie czasu propagacji) do zapisu danych, niż odczytu.

Suma sumarum, w zależności od typu bazy (relacyjna, obiektowej, strumieniowej, itd.) oraz jej złożoności, należy wybrać odpowiedni mechanizm układania indeksów.

Funkcja mieszająca

Rodzi się pytanie. Gdy mamy taką strukturę składowania indeksów niejednoznacznych, tj. kilka rekordów może mieć dokładnie taką samą wartość klucza. Prostym przykładem jest indeksowanie dłuższych ciągów znaków, do których chcemy mieć natychmiastowy dostęp bez wyszukiwania ich w bazie danych w sposób bezpośredni. Do identyfikacji takich struktur służą funkcje mieszające. Przykład. Wyobraźmy sobie, że podczas zapisu danych podając dane jako argument funkcji mieszającej, zamieniamy każdy znak ciągu znaków na odpowiadający mu kod ASCII, następnie sumujemy liczby i dzielimy modulo 90, nasz wynik to wartość indeksu. Tę samą operację wykonujemy dla kryterium późniejszego wyszukiwania podając go jako argument funkcji mieszającej. Wystarczy porównać nasze kryterium z kluczami. Mamy 90 możliwości otrzymanych wyników.

Działanie funkcji mieszającej:

Im większe modulo, tym bardziej rozległy indeks i bardziej unikatowy indeks. Niestety, pod jednym kluczem może znajdować się wiele rekordów, przykładowo: ABC, CAB, AAD, AE, F, itd… wówczas występuje tzw. kolizja. Podstawową wadą funkcji mieszającej może być złożoność obliczeniowa dla zwracanej wartości. Ponadto obecne systemy baz danych zapewniają ciągłość z góry zadeklarowanej pamięci, zatem przeszukiwanie takich komórek może być znacznie szybsze, od przeszukiwania kluczy. Funkcja mieszająca plus indeksowanie adresów jest zdecydowanie dobrym rozwiązaniem, gdy przeszukiwanie indeksów jest korzystniejsze pod względem czasu dostępu do informacji (np. czas propagacji dysku, odszukanie fragmentu pliku, etc.).

Występowanie kolizji

Metod obsługi kolizji jest bardzo wiele. Podstawową jest stworzenie listy elementów, które są przypisane do danego klucza. Może ich być wiele, natomiast to i tak bardzo dobra optymalizacja przeszukiwania bazy danych.

Częstotliwość występowania kolizji w grubym przybliżeniu obrazuje wykres. Zauważmy, że jeżeli wyczerpiemy ~60% możliwości wystąpienia tych samych kluczy, kolizyjność wzrasta wykładniczo, a używanie funkcji mieszących przy wstawianiu rekordu bazy danych staje się nieoptymalne, w zależności od implementacji korekcji kolizji (powtórzenia rozwiązania kolizji). Przy dołączaniu elementu do listy jednokierunkowej (wcześniejszy obraz) nie stanowi to jednak większego problemu. Gdy < 60% możliwości kluczy jest niewykorzystanych, występowanie kolizji jest znikome.

Idealna funkcja mieszająca

Mówiąc o idealnej funkcji mieszającej mamy na myśli skonstruowanie takiej funkcji, która przyporządkuje mniej więcej po tej samej liczbie swoich zwracanych wartości, tj. dla naszego przykładu modulo 90, każdy klucz będzie miał porównywalną liczbę rekordów przypisanych do danego indeksu. Intuicyjnie: można to wykonać tylko wtedy, kiedy z góry znamy dziedzinę tej funkcji bądź w przybliżeniu spodziewamy się znanych danych wejściowych. Budowanie idealnych funkcji mieszających jest skomplikowaną operacją matematyczną. Jednym ze sposobów do naszego przykładu, przy znanej dziedzinie funkcji mieszającej jest przypisywanie kolejnym literom wag, które po zsumowaniu i podzieleniu przez modulo, jest wygenerowanie takiej kombinacji wag, żeby zwracane wartości były równie często obliczane dla całej dziedziny funkcji (każda liczba modulo jest wykorzystywana po mniej więcej N razy).

Zakończenie

Temat teoretycznych rozważań budowy baz danych na pewno będę kontynuował. Tak, jak zaznaczyłem we stępie, artykuł bynajmniej wyczerpuje tematykę, a zainteresowanych zapraszam do przekroczenia progów politechnicznych bibliotek.

 
by Piotr Pelczar on Databases, Internet, Optymalizacja, Planeta, Publikacje

„Rekurencja” w funkcjach/procedurach MySQL

Odzwyczajony od blogowania, zaabsorbowany przez niekorzystnego dla planet i blogosfery stanu rzeczy Social Media, postanowiłem wrzucić kolejny wpis, w podzięce za porady uzyskane z blogów kolegów z branży. Ostatnio moim zadaniem było zaprojektowanie struktury tabel bazy danych, która wraz z drzewem z zagłębieniem kategorii, ma przechowywać dane na temat cen za ogłoszenia publikowane w tych kategoriach.

Założenia wstępne wyglądały następująco:

  1. Każda kategoria może mieć rodzica, ale nie musi.
    Jak komu wygodnie, postanowiłem wybrać rozwiązanie z polem category_parent int(11) UNSIGNED, domyślnie NULL (bez rodzica).
  2. Kategorie mogą mieć ustaloną cenę za opublikowanie ogłoszenia, ale nie muszą.
    Dodałem pole category_data_price float(6,2) UNSIGNED, domyślnie NULL (niezdefiniowana).
  3. Kategorie, które nie mają zdefiniowanej ceny, a mają rodzica, przejmują cenę rodzica w zagłębieniu do nieskończoności. W przypadku, kiedy cena jest niezdefiniowana również dla rodziców, cena stanowi NULL.

Potrzebne mi było zapytanie, które zwróci mi zwyczajnie listę wszystkich kategorii wraz z cenami, uwzględniając zagłębienia, w jakich dana kategoria się znajduje. Podejścia składowania cen są dwa:

  1. Można zapisywać tylko cenę kategorii, która jest dla niej zdefiniowana, a przy wyciąganiu danych rekurencyjnie sprawdzać procedurą/funkcją cenę rodzica, jeżeli jest niezdefiniowana. I tak w kółko do przypadku, gdy któraś z kategorii będzie już miała zdefiniowaną cenę, bądź nie będzie się już gdzie zagłębić (kategoria nie ma rodzica).
  2. Można zapisać dwie ceny dodając pole dodatkowe, które przy będzie przechowywało wartość ceny, biorąc ją przy sprawdzaniu cen tylko przy zapisie rekordu do bazy danych.

Sposób drugi wydaje się być bardziej rozsądny w przypadku większej ilości zapytań podejmujących dane z bazy. Pierwszy odwrotnie – częściej wpisujemy coś do bazy. Z początku wybrałem pierwszy sposób, przy założeniu, że ceny będą generowane tylko w panelu administracyjnym, zatem zapytanie nie będzie wykonywane często. Niestety, moje myślenie jest bardziej abstrakcyjne, nastawione na elastyczność rozwiązań, w przyszłości cel istnienia bazy może się zmienić.

Tak czy siak, dla obu rozwiązań, trzeba stworzyć procedurę sprawdzającą ceny po rodzicach. Wygląda mniej więcej tak:

CREATE FUNCTION AnnouncementsCategoriesGetPrice(iCategoryId int(11)) RETURNS float(6,2)
BEGIN
DECLARE iResult FLOAT(6,2);
DECLARE iPointer INT(11);

SET iPointer = iCategoryId;
SET iResult  = (SELECT category_data_price FROM cms_announcements_categories WHERE category_id = iPointer);

WHILE (iResult IS NULL AND iPointer IS NOT NULL) DO
SET iResult  = (SELECT category_data_price FROM cms_announcements_categories WHERE category_id = iPointer);
SET iPointer = (SELECT category_parent FROM cms_announcements_categories WHERE category_id = iPointer);
END WHILE;

RETURN iResult;
END

Stosować ją można dla SELECT’u kategorii lub do pozyskania wartości pola tymczasowego przy zapisie do bazy.

Mam nadzieję, że komuś się przyda.