Liczby pierwsze a dziedziczenie w drzewie w bazach relacyjnych


Wstępem niech będzie prosty praktyczny przykład, który zobrazuje pewien problem. W relacyjnej bazie danych mamy stworzyć obsługę struktury drzewa, czyli powiązanej struktury węzłów, z których każdy ma maksymalnie jednego rodzica (korzeń drzewa nie ma rodzica w ogóle). Liście tego drzewa mają „dziedziczyć” po swoich rodzicach jakieś wartości – nazwijmy je atrybutami. Interesuje nas pozyskiwanie pełnej listy atrybutów dla danego węzła.

Podejście najbardziej oczywiste

Sprawa wydaje się dosyć prosta:

CREATE TABLE `nodes` (
    `node_id` INT(11) NOT NULL AUTO_INCREMENT,
    `parent_id` INT(11) NULL DEFAULT NULL,
    `attribute` VARCHAR(8) NULL DEFAULT NULL COLLATE 'utf8_bin',
    PRIMARY KEY (`node_id`),
);

Wprowadźmy jakieś przykładowe dane:

INSERT INTO nodes (`node_id`, `parent_id`, `attribute`)
VALUES
    (1, NULL, 'name'),
    (2, 1, 'value'),
    (3, 1, 'link'),
    (4, 2, NULL),
    (5, 6, 'port'),
    (6, 3, 'password'),
    (7, 2, NULL),
    (8, 6, 'protocol'),
    (9, 3, NULL);

Obrazują one strukturę następującego drzewa:

ROOT
--(1) name
----(2) value
------(4)
------(7)
----(3) link
------(6) password
--------(5) port
--------(8) protocol
------(9)
Schemat drzewa węzłów z atrybutami
Schemat drzewa węzłów z atrybutami

W jaki sposób dowiedzieć się jakie atrybuty ostateczne posiada węzeł nr 8? Ze struktury wzrokowo możemy odczytać, że są to „protocol”, „password”, „link” oraz „name”. A jak uzyskać te dane za pomocą zapytania SQL? Musimy w mniej lub bardziej bezpośredni sposób wykonać przynajmniej trzy JOINy:

select n.attribute from 
nodes as n,
nodes as n1
join (nodes as n2
    join (nodes as n3 
        join nodes as n4 on n4.node_id = n3.parent_id)
    on n3.node_id = n2.parent_id)
on n2.node_id = n1.parent_id
where (n.node_id = n1.node_id or n.node_id = n2.node_id or n.node_id = n3.node_id or n.node_id = n4.node_id)
and n1.node_id = 8

Dla jasności można to też zapisać tak:

select n.attribute from 
nodes as n,
nodes as n1,
nodes as n2,
nodes as n3,
nodes as n4
where (n.node_id = n1.node_id or n.node_id = n2.node_id or n.node_id = n3.node_id or n.node_id = n4.node_id)
and n1.node_id = 8
and n2.node_id = n1.parent_id
and n3.node_id = n2.parent_id
and n4.node_id = n3.parent_id

No właśnie – jak widać, jest to dosyć złożona konstrukcja. I ujawnia też bardzo poważną wadę. Aby napisać odpowiednie zapytanie musimy wiedzieć z góry ile ma być JOINów, czyli na jaką głębokość drzewa schodzimy! Jak sobie z tym poradzić?

Kodowanie liczbami pierwszymi

Przez lata opracowano wiele metod radzenia sobie z tego typu problemami, bo struktury hierarchiczne generalnie nie są tym, do czego bazy relacyjne najlepiej pasują. Ciekawym rozwiązaniem, które chcę przedstawić jest zastosowanie kodowania liczbami pierwszymi. Liczby pierwsze mają to do siebie, że nie da się ich utworzyć przez mnożenie żadnych innych. Liczbami pierwszymi są np. 2, 3, 5, 7, 11, 13, 17, 19. Natomiast z nich samych można tworzyć poprzez mnożenie liczby, które nazywa się liczbami złożonymi – np. 35 jest liczbą złożoną, bo można ją złożyć mnożąc 5 razy 7.

Dla naszych zastosowań ważne jest jeszcze to, że możemy łatwo sprawdzać, czy dana liczba złożona składa się z pewnej liczby pierwszej. Wystarczy, że spróbujemy uzyskać resztę z dzielenia całkowitego liczby złożonej przez daną liczbę pierwszą. Jeżeli reszta będzie równa zero, to jest to potwierdzeniem, że liczba złożona „ma w sobie” daną liczbę pierwszą.

Przykład: liczba 35 „ma wewnątrz” liczbę pierwszą 7, bo 35 dzielone przez 7 daje 5 i zero reszty, a liczba 36 jest zawiera już liczby 7, bo 36 dzielone przez 7 daje 5 i jeden reszty. (W rzeczy samej 36 rozkłada się na liczby pierwsze 2*2*3*3).

Podane wyżej informacje są istotne z dwóch powodów:

  1. Jeżeli każda z liczb pierwszych oznaczałaby czyli kodowała dla nas coś innego – tak jak np. w kodzie ASCII każda liczba oznacza inną literę – to można taki kod liczb pierwszych wymnożyć i zawrzeć w pojedynczej liczbie całkowitej;
  2. Z tej pojedynczej liczby całkowitej można później bardzo łatwo wyciągać („select”!) informacje za pomocą szybkiej funkcji matematycznej modulo – czyli reszty z dzielenia!

Przyjrzyjmy się przykładowi, który ukaże zalety i wady stosowania liczb pierwszych. Załóżmy, że w pewnym prostym kodzie, w którym litera A=1, B=2, C=3, D=4 itd. zapisujemy pewien bardzo długi tekst. Jeżeli chcemy sprawdzić, czy w tym tekście znajduje się litera „K”, to musimy algorytmicznie przejść litera po literze od początku tekstu aż trafimy (lub nie) na literę „K”. Jeżeli tekst ma więc długość 100 000 znaków, to musimy odczytać w najlepszym przypadku 1 znak a w najgorszym 100 000 znaków. Rozpoznajemy tutaj od razu znany problem bazodanowy: wyszukiwanie wewnątrz tekstu. Wiemy z doświadczenia, że jest to względnie długotrwała operacja.

Moglibyśmy jednak zakodować ten tekst inaczej. Gdybyśmy uznali, że każdej kolejnej literze alfabetu przypiszemy inną liczbę pierwszą, np. A=2, B=3, C=5, D=7 itd., wówczas moglibyśmy tekst wymnożyć do postaci pojedynczej liczby całkowitej. No i teraz najlepsze: niezależnie od tego, czy tekst miałby 100 000 czy może 100 milionów znaków, sprawdzenie czy w tekście znajduje się litera „K” realizowalibyśmy tylko przez jedną operację modulo.

Byłby to prawdopodobnie ogromny zysk czasowy!

Prawdopodobnie widzisz już jednak pewne wady albo się ich domyślasz:

  • Tworzona w ten sposób pojedyncza liczba złożona potrafi być bardzo, bardzo duża. Na tyle duża, że do kodowania większych ilości danych trzeba by pewnie specjalistycznych silników bazodanowych, aby móc pracować z liczbami potencjalnie nieograniczonej liczby cyfr, a sama operacja modulo też mogłaby się okazać wcale nie tak szybka jak byśmy chcieli;
  • W swojej „naturalnej” postaci takie kodowanie nie zachowuje kolejności liczb pierwszych. To jest bardzo poważna sprawa, bo o ile w zakodowanym tekście możemy szybko stwierdzać obecność liter, to jednak samego oryginału tekstu już nie odzyskamy i informacja o tym która litera stoi obok której również przepada!

Skoro takie są wady, to kiedy może nam się to przydać?

Liczby pierwsze a dziedziczenie w hierarchii

Wróćmy do naszego pierwotnego przykładu z hierarchią i dziedziczeniem – tutaj jest dobre zastosowanie, gdy hierarchie nie są duże a często nie są (np. struktury menu, proste kategoryzacje obiektów w sklepach czy repozytoriach danych) i też nie interesuje nas kolejność czegokolwiek, bo interesuje nas dziedziczenie atrybutów. Samej kolejności wcale nie musimy się też wyrzekać: to wręcz banalnie proste ją zachować.

Popatrzmy na zmodyfikowaną tabelę oraz dane:

CREATE TABLE `nodes` (
    `node_id` INT(11) NOT NULL AUTO_INCREMENT,
    `parent_id` INT(11) NULL DEFAULT NULL,
    `attribute` VARCHAR(8) NULL DEFAULT NULL COLLATE 'utf8_bin',
    `number` INT(11) NULL DEFAULT NULL,
    PRIMARY KEY (`node_id`),
    UNIQUE INDEX `number_idx` (`number`)
);
INSERT INTO nodes  (`node_id`, `parent_id`, `attribute`, `number`)
VALUES
    (1, NULL, 'name', 11*5*7*3*2),
    (2, 1, 'value', 11*5),
    (3, 1, 'link', 7*3*2),
    (4, 2, NULL, 11),
    (5, 6, 'port', 7),
    (6, 3, 'password', 7*3),
    (7, 2, NULL, 5),
    (8, 6, 'protocol', 3),
    (9, 3, NULL, 2)
;

Tabela węzłów z etykietami liczbowymi
Tabela węzłów z etykietami liczbowymi

Zauważ, że liściom drzewa przyporządkowałem liczby pierwsze a wszystkie węzły-rodzice mają przyporządkowaną wartość liczbową równą iloczynowi wartości ich dzieci. No i zobacz jak teraz wygląda wyszukiwanie dziedziczonych atrybutów dla węzła nr 8:

select attribute from nodes where number mod (select number from nodes where node_id = 8) = 0;

I tutaj właśnie jest cała rewolucja! Zredukowaliśmy problem do pojedynczego zapytania z podzapytaniem korzystającym z indeksu, które w ogóle nie wymaga wiedzy o głębokości drzewa!

Więcej, uzyskaliśmy możliwość łatwego sięgania także i po inne informacje, np. uzyskanie listy wszystkich przodków węzła nr 8:

select node_id from nodes where number mod (select number from nodes where node_id = 8) = 0 and node_id != 8;

Uzyskanie listy wszystkich potomków danego węzła:

select node_id from nodes where (select number from nodes where node_id = 8) mod number = 0 and node_id != 8

Uzyskiwanie rodziców i dzieci danego węzła nie jest takie łatwe przy zastosowaniu wyłącznie kodowania liczbami pierwszymi, ale od tego mamy pozostawioną kolumnę „parent_id”, aby móc sobie łatwo dochodzić tych węzłów.

Zarządzanie drzewem

Jeżeli chodzi o modyfikowanie drzewa, to też nie jest tak źle, jak moglibyśmy przypuszczać. Przykładowe dodanie nowego węzła do już istniejącego węzła nr 4:

INSERT INTO nodes (`parent_id`, `attribute`, `number`) VALUES (4, NULL, 13);

Nowemu węzłowi została przypisana nie używana do tej pory liczba pierwsza o wartości 13. Można trzymać w bazie danych tabelę z sekwencją liczb pierwszych i z niej korzystać dobierając nowe wartości i sprawdzając jakie wartości zostały użyte – to trywialna sprawa. Gdy już utworzymy nowy węzeł, musimy „zaktualizować” etykiety liczbowe jego rodziców. Okazuje się to być bardzo proste. Wystarczy liczbę złożoną przypisaną każdemu rodzicowi pomnożyć przez nową liczbę pierwszą.

update nodes as n 
join (nodes as n1 join nodes as n2 on n1.number mod n2.number = 0 and n2.node_id = 4) on n.node_id = n1.node_id
set n.number = n.number * 13

Jak można się domyślać, usunięcie węzła polega na działaniu odwrotnym, czyli jest to równie proste działanie.

A co w przypadku jakiś bardziej złożonych operacji takich jak np. przenoszenie całych poddrzew? Można spróbować je zrealizować przez jakieś kombinacje podstawowych działań usuwania i dodawania, ale też zawsze można mieć gotową w zanadrzu procedurę prze-etykietowania i przeliczenia wszystkich węzłów na nowo, bo etykiety nie są przecież jakoś szczególnie wiążące.

Nawet jeżeli zarządzanie drzewem nie wydaje się trudne, to można się spodziewać, że edycja drzewa przy korzystaniu z liczb pierwszych będzie obciążająca przy dużych drzewach i częstych jego edycjach, bo będzie się wiązało z dużą ilością UPDATEów.

Podsumowanie

Zaprezentowałem Ci ciekawy sposób, którego opisu nie znalazłem nigdzie indziej w Internecie. Kto wie, może nie szukałem zbyt mocno albo może nie zrozumiałem tego, co inni napisali, bo czasami opisy zastosowań i teorii związanych z liczbami pierwszymi potrafią być bardzo matematyczne i trudne do zrozumienia. Tym nie mniej Internet ma na pewno do zaoferowania jakąś dodatkową lekturę w tym temacie, np.:


Dodaj komentarz