drzewa w sql’u – metoda pełnych ścieżek (metoda nr. 5 w/g starego tekstu)

oj. od ostatniego tekstu nt. drzew już trochę czasu minęło. czas więc dokończyć tę serię 🙂

metodę tę wymyśliliśmy ze znajomymi z firmy w której kiedyś pracowałem.
jest mocno prawdopodobne, że ktoś jeszcze wpadł na taki pomysł, natomiast wiem, że gdy ją wymyślaliśmy – nie korzystaliśmy z niczyich prac.

na czym ona polega? w skrócie na tym, że baza zna wszystkie powiązania między wszystkimi elementami drzewa które są ze sobą powiązaną na zasadzie “ojciec, ojciec ojca, ojciec ojca ojca, …".

w tym celu używamy 2 tabel – pierwszej aby przechowywać informacje o elementach drzewa, a w drugiej – o powiązaniach między nimi.

przykładowo, oryginalne, testowe drzewo:

tabelki:

# create table nodes_5 (
id int4 primary key,
name text
);
# create table tree_5 (
id int4 primary key,
parent_id int4 not null references nodes_5(id),
child_id int4 not null references nodes_5(id),
depth int4
);

wstawianie elementów polega na tym, że wstawiamy rekord do nodes_5, po czym dodajemy do tree_5 rekord którego child_id będzie takie jak aktualnego elementu, depth będzie równy 1, a parent_id będzie wskazywał na element nadrzędny.

następnie w tree_5 należy wstawić rekord którego depth będzie 0, a parent_id i child_id będą ustawione na id nowo wstawionego elementu.

na koniec należy skopiować wszystkie elementy gdzie child_id było takie jak aktualnie parent_id, podbijając depth o 1 i zmieniając child_id na id wstawionego elementu.

uff. skomplikowane?

tak się tylko wydaje. tabelki po wstawieniu danych wyglądają tak – prześledźcie je to zobaczycie, że sprawa jest prosta.

tabelka nodes_5:

id name
1 sql
2 postgresql
3 oracle
4 linux
5 solaris
6 linux
7 windows
8 glibc1
9 glibc2

tabelka tree_5:
# select * from tree_5;

id parent_id child_id depth
1 1 1 0
2 1 2 1
3 2 2 0
4 1 3 1
5 3 3 0
6 2 4 1
7 4 4 0
8 1 4 2
9 3 5 1
10 5 5 0
11 1 5 2
12 3 6 1
13 6 6 0
14 1 6 2
15 3 7 1
16 7 7 0
17 1 7 2
18 6 8 1
19 8 8 0
20 3 8 2
21 1 8 3
22 6 9 1
23 9 9 0
24 3 9 2
25 1 9 3

mam nadzieję, że teraz wygląda to bardziej oczywiście 🙂

ok. jak się pyta taką bazę?

1. pobranie listy elementów głównych (top-levelowych)

SELECT n.* from nodes_5 n left outer join tree_5 t on (n.id = t.child_id and t.depth = 1) where t.id is null

2. pobranie elementu bezpośrednio “nad" podanym elementem:

dane wejściowe:

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.depth = 1 and t.child_id = [ID];

jeśli zapytanie nic nie zwróci – znaczy to, że dany element był “top-levelowy".

3. pobranie listy elementów bezpośrednio “pod" podanym elementem

dane wejściowe:

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.child_id where t.depth = 1 and t.parent_id = [ID];

4. pobranie listy wszystkich elementów “nad" danym elementem (wylosowanym)

dane wejściowe:

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.child_id = [ID];

5. pobranie listy wszystkich elementów “pod" danym elementem (wylosowanym)

dane wejściowe:

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.child_id where t.parent_id = [ID];

6. sprawdzenie czy dany element jest “liściem" (czy ma pod-elementy)

dane wejściowe:

  • ID : id elementu
select count(*) from tree_5 where depth = 1 and parent_id = [ID]

jeśli zwróci 0 – to jest to liść. w innym przypadku zwróci ilość bezpośrednich “dzieci".

7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.child_id = [ID] order by depth desc limit 1;

podstawową zaletą tego rozwiązania jest to, że praktycznie wszystkie operacje można uzyskać prostym “where" po jednej tabeli (tree_5) – join do nodes_5 służy tylko do tego by móc zwrócić coś poza samym id.

wady – nieoczywiste przenoszenie elementów. pewna nadmiarowość informacji.

co do przenoszenia elementów – kiedyś o tym pisałem, ale aby było wszystko w jednym miejscu:

zakładając, że mamy drzewo i w nim element o id X przenosimy tak aby był bezpośrednio pod Y, zapytania które to zrealizują wyglądają tak:

DELETE FROM tree_5 WHERE id in (
                SELECT r2.id FROM tree_5 r1 join tree_5 r2 on r1.child_id = r2.child_id
                WHERE r1.parent_id = X AND r2.depth > r1.depth
                );
INSERT INTO tree_5 (parent_id, child_id, depth)
        SELECT r1.parent_id, r2.child_id, r1.depth + r2.depth + 1
        FROM
                tree_5 r1,
                tree_5 r2
        WHERE
                r1.child_id = Y AND
                r2.parent_id = X;

aha. oczywiście trzeba sprawdzić czy przenosiny elementu nie wygenerują pętli.

dnews

projekt dnews doczekał się wznowienia.

na razie jest site z layoutem który nic nie robi (i nie ma wszystkich elementów), ale będę po kolei dokładał kolejne cegiełki funkcjonalnościowe.

jeśli macie jakieś sugestie/pomysły/idee – proszę o komentarze do tego wpisu.

—- UPDATE z 2007.04.25 —-

projekt (a dokładniej to co w nim jest, czyli na razie niewiele) można ściągnąć:

svn co http://svn.depesz.com/svn/dNews/trunk/ dNews

dostęp anonimowy jest read only.

5 rzeczy których nie chcieliście wiedzieć i nigdy o nie nie pytaliście.

co najmniej 3 osoby mnie naznaczyły (elf, ata i tmarc), więc lecimy:

  1. w 4 czy 5 klasie podstawówki przyniosłem do szkoły penthouse'a. koledzy mieli radochę, ja opierdziel.
  2. wyrzucono mnie ze szkoły (liceum) za to że namalowałem grafitti na korytarzu. tyle, że tego nie zrobiłem.
  3. mam kilka świetnych pomysłów na zarabianie kasy. i jedynie nie potrafię się zebrać w sobie i zabrać za to by je zrealizować. i tak od kilku lat. a pomysłów przybywa.
  4. nie mam w ogóle pamięci do twarzy czy nazwisk. jestem w stanie całkowicie bezstresowo nie zauważyć bądź nie poznać na ulicy osoby z którą pracuję od lat. co gorsza – nie robię tego celowo.
  5. nie czytam książek informatycznych. żadnych. niby jako programista/bazodanowiec powinienem, ale nudzą mnie. uważam, że jest z nimi jak ze świnkami morskimi – ani to świnka ani morska.

co do kolejnych ofiar:

  1. ads
  2. arim
  3. illi
  4. jarek zabiełło
  5. smoku

witajcie inne planety

jak może wiecie naukowcy mają technologiczne możliwości by na podstawie obserwowania światła gwiazd powiedzieć sporo o ich składzie.

jak do tej pory – nie działało to dla planet. po prostu dlatego, że “świecą" zbyt słabo.

ostatnio udało się przeprowadzić jednakże analizę światła z dwóch planet i wyciągnąć na tej podstawie wnioski nt. składu chemicznego atmosfery na nich.

wynik mało spektakularny – nie wykryto niczego co mogłoby sugerować życie (a przynajmniej takie życie jakie jesteśmy w stanie rozpoznać), ale istotnym wynikiem jest empiryczny dowód na to, że jesteśmy w stanie “powąchać" atmosferę planet z odległości kilkudziesięciu lat świetlnych.

co to dla nas oznacza? prostsze, szybsze i tańsze sprawdzanie czy daleka planeta “wygląda" na zamieszkałą lub zdatną do zamieszkania. a to jest coś bardzo ważnego. nie dla codziennego zjadacza chleba. ale dla codziennego zjadacza chleba za 50 lat – już tak.

nagroda turinga za rok 2006 – po raz pierwszy dla kobiety

począwszy od 1966 roku, corocznie przyznawana jest nagroda dla osoby lub osób które odznaczyły się wkładem z szeroko pojętą informatykę.

nagroda ta, traktowana jako informatyczny nobel, była wręczana już 40 razy i za każdym razem lauretem byli faceci. znani. świeni fachowcy – z bardziej znanych nazwisk trzeba wymienić knutha, dijkstrę, edgara codda, niklausa wirtha, kena thompsona i dennisa ritchiego, team rsa (rivest, shamir, adleman) czy niedawno panów cerfa i kahna – twórców internetu jako takiego – protokołów i pomysłów.

w 2006 roku po raz pierwszy uhonorowana została kobieta – frances allen. frances pracowała od 1957 roku w ibm'ie i brała udziała w wielu niesamowitych projektach jak choćby pisanie pierwszych kompilatorów (fortran), tworzenie oprogramowania na blue gene'a czy softu wywiadowczego dla nsa.

mimo, że od 2002 roku jest na emeryturze nadal aktywnie się udziela i zachęca młode pokolenia kobiet do wybrania swojej ścieżki kariery.

dla zainteresowanych – nagroda poza wielkim “szacunem" i “joł" ze środowiska obejmuje $100,000.

porównanie implementacji ruby’ego

dzięki znajomemu (hi tmarc) dowiedziałem się o ciekawym tekście. autor porównał w nim wydajność kilku (41) testów w różnych implementacjach języka ruby.

udział wzięły kanony:

  • ruby 1.8 (na linuksie i na windows vista
  • ruby 1.9

ale także wersje mniej standardowe:

  • jruby
  • gardens point ruby .net (wersja beta, na windows vista)
  • rubinius
  • cardinal

porównano wydajność każdej z implementacji w stosunkdu do złotego wzorca – czyli 1.8 na linuksie.

efekt? no cóż. 1.9 zdecydowanie rządzi. ruby 1.8 na linuksie ma drugie miejsce. wersja na windowsach jest trochę wolniejsza, ale (co ważniejsze) wywala się na 2 testach!

pozostałe implementacje: wolno i kiepsko. “hitem" jest cardinal – większość testów zakończona błędem, dwa trwały powyżej  15 minut i zostały ręcznie ubite (te testy były “zrobione" przez 1.8 w czasach 9.5 i 0.5 sekundy!). choć trzeba przyznać, że w 3 testach cardinal osiągnął najlepszy wynik. wydajnościowo gorszy był rubinius, ale on miał mniej errorów (“ledwie" koło połowy).

można spojrzeć by rozwiać złudzenia, lub nauczyć się czegoś z testów.

nowa technologia kości ram

ibm ogłosił, że opracowali właśnie nową technologię produkcji kości ram.

nowe kości są rozwinięciem idei i metody produkcji dram, ale prędkością zbliżone do sram. czyli około 2 krotnie szybsze od obecnych kostek.

sram od zawsze był szybszy, ale te kości były sporo większe niż standardowe dramy. więc się nie przyjmowały w standardowych zastosowaniach. teraz jednakże – gdy nowy dram ma osiągnąć wydajność sram, można liczyć na spory przełom.

poza zwiększoną szybkością nowe kości mają być też pojemniejsze. trzykrotnie!.

podsumowując: 3 razy więcej ramu, działającego 2 razy szybciej. ciekawe tylko kiedy to wejdzie do seryjnej produkcji i sprzedaży – na razie ibm szacuje, że pierwsze handlowe kości pojawią się w 2008 roku i będą to pamięci serwerowe. inne typy pamięci pojawią się później. a kiedy do laptopów?

postgres 8.3 – wishlist

dobrze wiedzieć co się pojawi w nowej wersji. ten site przedstawia skrótowo to co ma być, może być, fajnie by było jakby było, a co prawie na pewno spadnie do 8.4.

z ciekawszych rzeczy – “grouped index tuples", osbługa xml'a w bazowym postgresie, identity/generated (rany, jak mi tego brakowało), tsearch2 w postgresie bazowym, no i enumy.

co z tego faktycznie wejdzie – zobaczymy. ale zapowiada się miło.

aha. spojrzałem, że mają się też pojawić indeksy bitmapowe. sama funkcjonalność miła, ale jak dla mnie indeksy bitmapowe są ultra-ciekawe z prostego i poza technologicznego powodu. już teraz od groma ludzi myli to co jest w postgresie “bitmapy indeksowe" z tym co by chcieli by było “indeksy bitmapowe". co zrobią ci wszyscy jak do postgresa wejdą te prawdziwe indeksy?

heh.

nieoczekiwany sojusznik w walce z drm’em

czy napiszę o jobsie i jego otwartym liście do riaa? nie. w/g mnie to tani chwyt pod publiczkę.

o kolesiu z linspire który zażądał od jobsa czynów a nie gadania? też nie. to jest koleś który w ogóle się w świecie nie liczy i wykorzystuje sytuację aby zdobyć chwilę “widoczności antenowej".

o czym więc?

otóż – dosyć nieoczekiwanym sojusznikiem okazała się być firma emi. kojarzycie? 3 na świecie wydawca muzyki (biorąc pod uwagę wartość sprzedaży). w ich “portfolio" wchodzą takie grupy/wykonawcy jak kate bush, pet shop boys, paul mccartney, tomoyashu hotei, massive attack, iggy pop, nick cave and the bad seeds, coldplay, queen, robbie williams, radiohead, depeche mode, liz phair, tina turner, the beach boys, enigma, the rolling stones, kraftwerk, david bowie, ub40, pink floyd, moby, gorillaz, sarah brightman, lenny kravitz, iron maiden, blur, the chemical brothers, koЯn, beastie boys, the beatles czy placebo. a to nawet nie jest połowa artystów tworzących w barwach emi.

co takiego zrobiło emi? otóż emi od jakiegoś już czasu sprzedaje muzykę swojej trzódki (małej jej części na razie) całkowicie bez żadnych ograniczeń, drm'ów czy innego badziewstwa. i jak mówią – oni są zadowoleni i klienci sa zadowoleni.

podobno już teraz planują sprzedaż całości swojej dyskografii w takiej właśnie bez-drm'owej postaci.

jak widać – wyłomy się pojawiają nawet w, zdawałoby się monolitycznej,  strukturze riaa.