Author: depesz

drzewa w sql’u – metoda wielu tabel

tak naprawdę to nazwa "metoda wielu tabel" nie oddaje w pełni tego o co chodzi, natomiast jest pewnym przybliżeniem.
zgodnie z tą metodą należy stworzyć dla każdego poziomu zagnieżdżenia tabelę.
w oparciu o nasze dane testowe należy stworzyć system tabel:

CREATE TABLE categories_1 (
    id       BIGSERIAL PRIMARY KEY,
    codename TEXT NOT NULL DEFAULT ''
);
CREATE UNIQUE INDEX ui_categories_1_cn ON categories_1 (codename);

CREATE TABLE categories_2 (
    id        BIGSERIAL PRIMARY KEY,
    parent_id INT8 NOT NULL DEFAULT 0,
    codename  TEXT NOT NULL DEFAULT ''
);
ALTER TABLE categories_2 ADD FOREIGN KEY (parent_id) REFERENCES categories_1 (id);
CREATE UNIQUE INDEX ui_categories_2_picn ON categories_2 (parent_id, codename);

CREATE TABLE categories_3 (
    id        BIGSERIAL PRIMARY KEY,
    parent_id INT8 NOT NULL DEFAULT 0,
    codename  TEXT NOT NULL DEFAULT ''
);
ALTER TABLE categories_3 ADD FOREIGN KEY (parent_id) REFERENCES categories_2 (id);
CREATE UNIQUE INDEX ui_categories_3_picn ON categories_3 (parent_id, codename);

CREATE TABLE categories_4 (
    id        BIGSERIAL PRIMARY KEY,
    parent_id INT8 NOT NULL DEFAULT 0,
    codename  TEXT NOT NULL DEFAULT ''
);
ALTER TABLE categories_4 ADD FOREIGN KEY (parent_id) REFERENCES categories_3 (id);
CREATE UNIQUE INDEX ui_categories_4_picn ON categories_4 (parent_id, codename);

i w nim dane:

# select * from categories_1;
 id | codename
----+----------
  1 | sql
(1 row)

# select * from categories_2;
 id | parent_id |  codename
----+-----------+------------
  1 |         1 | oracle
  2 |         1 | postgresql
(2 rows)

# select * from categories_3;
 id | parent_id | codename
----+-----------+----------
  1 |         2 | linux
  2 |         1 | linux
  3 |         1 | solaris
  4 |         1 | windows
(4 rows)

# select * from categories_4;
 id | parent_id | codename
----+-----------+----------
  1 |         2 | glibc1
  2 |         2 | glibc2
(2 rows)

jak widać pojawia się pewien problem – nieobecny w innych systemach tabel – aby prawidłowo zidentyfikować element drzewa nie wystarczy nam jego numer, ale musimy też znać poziom zagłębienia.
oczywiście możliwe jest wymuszenie nadawania numerów kolejnych tak aby nie powtarzały się w różnych tabelach, ale wtedy znalezienie który element jest w której tabeli będzie nietrywialne.

teraz pora na zadania testowe dla tego układu tabel:
1. pobranie listy elementów głównych (top-levelowych)

 > SELECT * FROM categories_1;

proste i miłe.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.

jeśli X == 1 to:
brak danych
w innym przypadku:

 > SELECT p.* FROM categories_[X] c join categories_[X-1] p ON c.parent_id = p.id WHERE c.id = [ID]

pojawia się problem. zapytania są zmienne. nie jest to bardzo duży problem, ale np. utrudnia wykorzystywanie rzeczy typu "prepared statements".

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia. 
> SELECT c.* FROM categories_[X] p join categories_[X+1] c ON c.parent_id = p.id WHERE p.id = [ID]

znowu pojawia sie problem z zapytaniami o zmiennej treści (nie parametrach – treści – nazwach tabel!). dodatkowo – musimy gdzieś przechowywać informację o maksymalnym zagnieżdżeniu i sprawdzać ją przed wykonaniem zapytania – aby się nie okazało, że odwołujemy się do nieistniejącej tabeli.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.

jeśli X == 1 to:
brak danych
jeśli X == 2 to:

 > SELECT c1.* FROM categories_2 c2 join categories_1 c1 ON c2.parent_id = c1.id WHERE c2.id = [ID]

jeśli X == 3 to:

 > SELECT c1.*, c2.*
FROM categories_3 c3 join categories_2 c2 on c3.parent_id = c2.id join categories_1 c1 ON c2.parent_id = c1.id
WHERE c3.id = [ID]

itd.

jak widać tu problem się multiplikuje. nie tylko zmieniają nam się nazwy tabel, ale wręcz cała konstrukcja zapytania zaczyna przypominać harmonijkę – z każdym ruchem (wgłąb struktury) wyciąga się.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.
  • MaxX : maksymalny poziom zagłębienia w systemie
SELECT c[X+1].* FROM categories_[X+1] c[X+1] WHERE c[X+1].parent_id = [ID]
UNION
SELECT c[X+2].*
FROM categories_[X+1] c[X+1] join categories_[X+2] c[X+2] ON c[X+1].id = c[X+2].parent_id
WHERE c[X+1].parent_id = [ID]
UNION
SELECT c[X+3].*
    FROM categories_[X+1] c[X+1]
    join categories_[X+2] c[X+2] ON c[X+1].id = c[X+2].parent_id
    join categories_[X+3] c[X+3] ON c[X+2].id = c[X+3].parent_id
WHERE c[X+1].parent_id = [ID]
...

łaaaał. robi się coraz gorzej. napisanie tego dla np. 16 poziomów zagnieżdżenia przerasta moje chęci.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.
SELECT count(*) from categories_[X+1] WHERE parent_id = [ID]

zasadniczo proste, ale trzeba pamiętać o wcześniejszym sprawdzeniu czy przypadkiem X+1 nie jest większe od maksymalnie obsługiwanego limitu – aby uniknąć błędów w bazie.

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

dane wejściowe:

  • ID : id elementu
  • X : poziom zagłębienia.

jeśli X == 1 to:

 > SELECT c1.* FROM categories_1 c1 WHERE id = [ID]

jeśli X == 2 to:

 > SELECT c1.* FROM categories_2 c2 join categories_1 c1 ON c2.parent_id = c1.id WHERE c2.id = [ID]

jeśli X == 3 to:

 > SELECT c1.*
FROM categories_3 c3 join categories_2 c2 on c3.parent_id = c2.id join categories_1 c1 ON c2.parent_id = c1.id
WHERE c3.id = [ID]

itd.

eh. chyba widzicie do czego to zmierza.

jak widać – zapisywanie tak drzew ma swoje problemy. i raczej niewiele rzeczy można w tym zrobić ładnie szybko i porządnie.
zasadniczo – nie opisywałbym tej metody gdyby nie fakt iż z nieznanych powodów jest ona bardzo często sugerowana przez ludzi których odpytuję w ramach rozmowy kwalifikacyjnej.  no – a skoro się pojawia, to trzeba ją omówić. choćby pobieżnie.

drzewa w sql’u – wstęp

jakiś czas temu zainteresowała mnie metoda przechowywania wszelkiego rodzaju struktur drzewiastych w bazach danych.
dla wyjaśnienia – struktura drzewiasta jest to taki uporządkowany zbiór danych gdzie każdy element ma swój element nadrzędny, chyba, że jest elementem najwyższego rzędu.
dając przykłady z życia – drzewami są opisane wszelkiego rodzaju hierarchie – służbowe, kategorie (np. w sklepie internetowym), różnego rodzaju podziały. drzewami są też wiadomości na forach dyskusyjnych – a dokładniej – w drzewa są poukładane wątki z tych wiadomości.
ogólnie – struktury drzewiaste mają sporo zastosowań.
z tego powodu stały się one obiektem mojego zainteresowania, testów i badań. o struktury drzewiaste pytam potencjalnych pracowników na rozmowie kwalifikacyjnej.
w czasie swojej pracy z "drzewami" wyodrębniłem kilka metod które kiedyś już opisałem (link do http://www.dbf.pl/faq/tresc.html?rozdzial=1#o1_9), ale tu postaram się opisać je dokładniej i podając przy okazji wyniki pewnych testów na wydajność.
ze względu na obfitość materiału tekst ten podzielę na kilka wpisów: wstęp (to co czytacie), następnie po jednym wpisie na każdą z opisywanych metod, potem jakieś podsumowanie i na koniec kilka uwag praktycznych do wybranej przeze mnie metody.
ponieważ testowanie wydajności powinno odbywać się na sporych zestawach danych, a jednocześnie pokazywanie "o co mi chodzi" powinno być na możliwie małych ilościach – na potrzeby tego tematu przygotowałem 2 zupełnie różne zestawy danych:

1. małe drzewko w celach dydaktycznych:

to drzewko, zgodnie z konwencjami stosowanymi w tym dokumencie, ma następujące elementy:

  • sql
  • sql.oracle
  • sql.oracle.linux
  • sql.oracle.linux.glibc2
  • sql.oracle.linux.glibc1
  • sql.oracle.solaris
  • sql.oracle.windows
  • sql.postgresql
  • sql.postgresql.linux

2. spory zestaw danych  pobrany z katalogu dmoz – lista kategorii

dane z dmoza poddałem obróbce usuwając z nich znaki spoza zestawu A-Za-z0-9_, i ustawiając separator elementów drzewa na ".".
powstała lista elementów ma 478,870 elementów.
ścieżki z dmoz zawierają od 3 do 247 znaków, największe zagłębienie w drzewo jest w elemencie Regional.North_America.United_States.New_York.Localities.N.New_York_City.Brooklyn.Society_and_Culture.Religion.Christianity.Catholicism.Eastern_Rites.Maronite

w celu porównania wydajności różnych metod zapisu drzew będę testował następujące scenariusze testowe:

  1. pobranie listy elementów głównych (top-levelowych)
  2. pobranie elementu bezpośrednio "nad" podanym elementem
  3. pobranie listy elementów bezpośrednio "pod" podanym elementem
  4. pobranie listy wszystkich elementów "nad" danym elementem (wylosowanym)
  5. pobranie listy wszystkich elementów "pod" danym elementem (wylosowanym)
  6. sprawdzenie czy dany element jest "liściem" (czy ma pod-elementy)
  7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element

dodatkowo zostanie sprawdzona wielkość tabel i indeksów na założonej strukturze danych.

dla porównania – zapis w postaci takiej jak w pliku źródłowym zajmuje:
– tabela dmoz: 57,319,424 bajtów
– index pkey: 8,609,792 bajtów
– unikalny indeks ścieżki: 51,888,128 bajtów

tak więc – w ciągu najbliższego czasu będę pokazywał kolejne metody oraz wyniki ich testów.

two for the money / podwójna gra

obejrzałem sobie tę (dosyć nową (2005) w sumie) produkcję.
ocena ogólna – około 7/10. film nie jest zły. jest nawet dobry. ogląda sie go przyjemnie.
jedynym problemem tego filmu jest to, że spodziewałem się więcej. w roli głównej al pacino. człowiek legenda. heat (gorączka) oglądam co jakiś czas by zobaczyć kawał wspaniałego kina. ojciec chrzestny, adwokat diabła (film zebrał takie sobie oceny, ale rola ala w nim jest niesamowita).
tu – oczywiście nadal jest tym samym diabłem. świetnym. tyle, że trochę jednak starszym. mającym swoje problemy.
na dokładkę do ala w filmie jest rene russo – z mojego punktu widzenia znana głównie z zabójczej broni 3 i 4, ale zdarzyło jej się zagrać też w innych, nie najgorszych, filmach.
no i trzeci aktor pierwszoplanowy – matthew mcconaughey. ciekawe ile z was kojarzy nazwisko. mnie sie on głównie kojarzy z rolą w świetnym kontakcie (contact) z jodie foster.
i rene i matthew zagrali poprawnie. w/g mnie przemiana brandona w john'a jest mało przekonująca (spokojnie, nie zdradzam tu nic tajnego). russo jest zdecydowanie bardziej przekonująca – może dlatego, że ta rola powstała dla niej i z myślą o niej jako odtwórczyni 🙂
kończąc – co by się nie rozpisywać i nie zdradzać nic z fabuły – film jest przyjemny. nie jest to arcydzieło kina światowego, ale spędziłem miłe 2 godzinki oglądając go. drugi raz nie zamierzam, ale żałować, nie żałuję.

eksperymenty kuchenne – kurczak w porach

od poprzedniego wpisu kuchennego minęło już trochę czasu (w międzyczasie udoskonaliłem przepis na zupę, ale o tym opow iem innym razem).
tym razem inspiracją był post na newsach.
opis jest zasadniczo jasny, ale jeśli ktoś z czytających nie wie jak do tego podejść – poniżej opis ze zdjęciami co i jak.
najpierw kilka uwag ogólnych:

  1. używamy piersi kurczaka, ale one nie będą "suche" jak to zazwyczaj bywa. zdecydowanie nie.
  2. w żarciu jest sporo porów, ale smakują one rewelacyjnie – zupełnie inaczej niż się spodziewałem. naprawdę
  3. przygotowanie żarcia w/g tego co poniżej to około doby, z tym, że to czas oczekiwania. samej roboty jest około 15 minut.
  4. podane ilości są orientacyjne. jak zamiast 4 piersi zrobicie 2, to trzeba też zmniejszyć ilość porów.

ok. jak już podstawy są jasne, to lecimy.
zaczynamy od porów:

na zdjęciu są 2, ale finalnie dałem 3 sztuki.
pory kroimy w tzw. talarki:

taka uwaga – z pora zdejmuje sie zewnetrzna warstwe, potem odkrawa korzonki i tnie na talarki. tniemy pora na takiej długości by talarki wychodziły "spójne". potem znowu zdzieramy warstwę, i dalej kroimy. ze standardowego pora wykorzystuje około 60% jego długości na talarki.
pory wrzucam do garnka:

i solę. ilość soli – w/g uznania. na 3 pory wsypałem do środka mniej więcej 1 łyżeczkę soli.
garnek (czy cokolwiek tak naprawdę) wstawiam do lodówki. na kilka godzin.

realnie – pory "robię" wieczorem – i na następny wieczór je używam. czyli w lodówce spędzają około 20 godzin.
następnego dnia rano wyciągam z lodówki kurczaki – piersi, i rozmrażam. jeśli masz rozmrożone, to ten etap można pominąć 🙂
po rozmrożeniu (w moim przypadku to koło 12:00 jest – co utrudnia robienie tego dania w czasie chodzenia do pracy), wykładamy kurczaki na deskę:

jak widać – oddzieliłem z piersi mniejsze kawałki tak aby były "luzem". nie jest to konieczne – tak mi po prostu było wygodniej przygotować.
nasŧępnie – biorę czosnek

wyłuskuję z niego ząbki – mniej więcej po dwa ząbki na pierś.

tu uwaga – w oryginalnym przepisie czosnku nie było. ja dodałem i sobie chwalę. można dodać więcej jak ktoś lubi, jak nie – bez czosnku też smakuje super.
czosnek zgniatam:

i wcieram w kurczaki:

następnie, biorę "warzywko" (inne nazwy: wegeta, kucharek, pewnie są też inne):

i lekko obsypuję nim kurczaki:

nastepnie, biorę sporą miskę i układam w niej kurczaki:

w międzyczasie podsypuję warzywko, tak aby każdy kurczak był z obu stron obsypany.

po wrzuceniu wszystkich kurczaków do miski wstawiam ją do lodówki:

i mam znowu kilka godzin wolnego. ciąg dalszy następuje wieczorem – można o 16, można później. im później tym zasadniczo lepiej dla smaku, gorzej dla zdrowia (bo kto późno je i potem idzie spać …). jak już mnie najdzie głód, nastawiam piekarnik na 180 stopni, i biorę brytfannę:

tu uwaga – ja mam taką szklaną, ale każda może być. w szczególności – pierwsze 2 "iteracje" robienia kurczaka robiłem w takich jednorazowych foremkach "jana niezbędnego" z supermarketu.
nastepnie, biorę masło:

i smaruję dno i boki, aż całość będzie wysmarowana:

tu kolejna uwaga – tych jednorazowych nie trzeba smarować. a przynajmniej – ja nie smarowałem i wyszło ok.
następnie – do brytfanny wrzucam pory z lodówki. jak coś z nich "wyciekło" – to też wlewam:

pory układam równo i na nich kurczaka. jeśli jest możliwość – dobrze jest zostawić trochę miejsca między kurczakami – ja nie miałem takiej możliwości:

następnie, biorę majonez – sam używam kieleckiego, ale pewnie na każdym wyjdzie dobrze:

i układam grubą warstwę na kurczakach (jeśli są przerwy między kurczakami, to w nich nie dajemy majonezu):

następnie na to – tzn. na majonez, czyli w moim przypadku na całą powierzchnię, układamy plasterki (nie za grube, takie standardowe, kanapkowe) żółtego sera. ser musi być bez-dziurkowy. innych specjalnych życzeń nie ma – sam użyłem morskiego:

gotowe. w międzyczasie piekarnik powinien się już dobrze rozgrzać. więc przykrywam brytfannę (ale np. tych jednorazowych nie przykrywałem, a jak raz przykryłem to wyszło nie za dobrze) i wsadzam do piekarnika – tak po środku:

i czekam godzinę. po godzinie całość wygląda tak:

po wyłożeniu na talerz wygląda w ten sposób – może mało apetycznie, ale to naprawdę jest fenomenalnie dobre:

i to wszystko. całość przygotowań trwała krócej niż pisanie tego wpisu 🙂
smacznego.

grafika komputerowa

rendering. raytracing. cg. wiele nazw, ta sama (mniej więcej) technologia.
technologia używana od dawna służyła w założeniach do tworzenia foto-realistycznych grafik w komputerze. rozmieszczamy kilka obiektów na scenie, nadajemy im tekstury, światło, umieszczamy kamerę i robimy "zdjęcie".
jak to wyglądało widać było w filmach – terminator 2, jurrasic park. są filmy gdzie ta grafika z definicji ma wyglądać nierealistycznie (toy story i inne filmy dla dzieci), są takie gdzie ma wyglądać jak najlepiej (final fantasy). są też takie – i jest ich najwięcej, gdzie grafika komputerowa daje tylko efekty. coś dodatkowego, trudnego, bądź nierealnego do zrobienia – day after tomorrow, harry potter.
zawsze jednak przy dokładniejszym przyjrzeniu można się dopatrzyć gdzie jest granica między rzeczywistością, a wykreowanym sztucznie światem 3d.
czy jednak zawsze? autodesk pokazał krótki test – 10 zdjęć. trzeba tylko wybrać które z nich są zdjęciami, a które grafiką komputerową. mnie poszło podobno nie źle – 8 trafień. ale nie było to zbyt łatwe

arabski tuning

arabowie potrafią. robią różne dziwne rzeczy. zapewne 70% internetu widziało film z pokazami driftingu. może z 30% widziało film pokazujący co się dzieje jak taki drift nie wychodzi.
ale dziś zobaczyłem coś nowego – nie film. serię zdjęć hondy accord ztuningowanej wizualnie przez arabów. zasadniczo – nie da się tego opisać. nie będę próbował. obejrzyjcie sami.

anonimowość w sieci

jak przy większości zagadnień technicznych tak i przy kwestii anonimowości jest wiele punktów widzenia i wiele opinii.

  • na samym początku ludzie czują się bezpieczni, bo skąd ktoś ma wiedzieć, że "jozia17@onet.pl" (adres zmyśliłem, mam nadzieję, że nie trafiłem w niczyj 🙂 to józia krakowiak, mająca 17 lat i mieszkająca w opolu?
  • potem, ludzie już wiedzą, że z adresu maila czy nagłówków można wiele wydobyć informacji, połączyć kilka informacji z różnych stron google'em i już mieć wszystkie potrzebne dane
  • potem mamy ludzi którzy myślą, że jak zmieniają adresy email i mają dynamiczne ip to są anonimowi
  • następna grupa wie, że dynamiczne ip nie zabezpiecza anonimowości, a w szczególności, że 90% ludzi z grupy poprzedniej nie potrafi korzystać z tego "zabezpieczenia"
  • następna (ostatnia, z mojego punktu widzenia, ale może ktoś mi udowodni, że są następne grupy) grupa – ludzie wiedzą, że anonimowość da się uzyskać, ale nie jest to trywialne i wymaga trochę pracy.

jednym z celów uzyskania anonimowości w sieci jest wysyłanie maili i/lub postów na grupy newsowe w sposób uniemożliwiający wykrycie nadawcy.
przyczyny tego typu zachowania mogą być różne. część z nich jest nie-fajna, ale część całkowicie legalna i sensowna.
jedną z metod (i chyba najprostszą w warunkach "domowych") do wysyłania anonimowych maili i postów na newsy jest korzystanie z usług tzw. remailerów. służy do tego protokół mixmaster i jego bazowa implementacja – pod tą samą nazwą.
nie wdając się w szczegóły techniczne – mixmaster zapewnia wystarczający poziom bezpieczeństwa do olbrzymiej większości zastosowań.
o tym ja go skonfigurować – można przeczytać w dzisiaj opublikowanym poście na debian administration – tekst jest po angielsku, ale wydaje mi się, że nie będziecie mieli problemu ze zrozumieniem.