Temat: Pomysły na strukturę bazy danych do przechowywania...

Witajcie.

Projektuje bazę danych do szybkiego wyszukiwania miejscowości pomiędzy dwoma podanymi w zapytaniu.

Generalnie chodzi o to, że danymi wejściowymi do zapytania jest miejscowość A i miejscowość B i na tej podstawie trzeba wyszukać wszystkie miejscowości w odpowiedniej kolejności jakie mogą wystąpić na trasie z miejscowości A do B. Dane na początku będą tylko dla kilku głównych miast, ale w miarę upływu czasu będą coraz bardziej szczegółowe. Do tej struktury powinno się dać w łatwy sposób dodawać nowe miejscowości. Powinno być też połączenie między miejscowościami. Każde takie połączenie powinno dać się podzielić na dwie części bo np. gdy mamy w bazie:

Połączenie    |    Z    |    Do

1             |Poznań   |Warszawa

i gdy dodamy np. miejscowość Łódź do połączenia 1 to powinno to połączenie zostać podzielone na dwa i teraz połączenia powinny wyglądać jakoś tak:

Połączenie    |    Z    |    Do

1             |Poznań   |Warszawa

1a            |Poznań   |Łódź

1b            |Łódź     |Warszawa

Każde połączenie powinno dać się podzielić gdyż w miarę jak będziemy dodawać miejscowości na danych połączeniach będzie je trzeba dzielić.

Następnie gdy zadamy pytanie do bazy o miejscowości z miasta Poznań do Warszawa baza powinna zwrócić najlepiej w jednym zapytaniu sekwencję rekordów z tabeli miejscowości:

Poznań
Łódź
Warszawa

Jeśli później dodamy do połączenia 1a np. miejscowość Konin
to połączenia powinny wyglądać tak:

Połączenie    |    Z    |    Do

1             |Poznań   |Warszawa

1a            |Poznań   |Łódź

1aa           |Poznań   |Konin

1ab           |Konin    |Łódź

1b            |Łódź     |Warszawa

Widzę, że robi się z tego takie drzewko:

                      1 [Poznań-Warszawa]

                               |

                 ----------------------------

                 |                          |

          1a [Poznań-Łódź]          1b [Łódź-Warszawa]

                 |

      ------------------------

      |                      |

1aa [Poznań-Konin]    1ab [Konin-Łódź]

I trzeba przy wyszukiwaniu odnaleźć liście tego drzewa bo one zawierają informacje na temat najbardziej szczegółowych miejscowości na trasie.

Teraz po wykonaniu zapytania Poznań - Warszawa baza powinna zwrócić sekwencję rekordów:

Poznań
Konin
Łódź
Warszawa

Idealnie by było, jeśli wykorzystując te dane dało by się wyszukać miejscowości na trasie odwrotnej - z Warszawy do Poznania czyli baza wówczas by zwróciła sekwencję rekordów:

Warszawa
Łódź
Konin
Poznań

Powinna być też możliwość odpytania o miejscowości podając jako dane wejściowe np. Poznań - Łódź lub Konin - Warszawa.

Poznań - Łódź powinno zwrócić
Poznań, Konin, Łódź

a Konin - Warszawa powinno zwrócić
Konin, Łódź, Warszawa

Czy macie może jakieś pomysły jak podejść do tego, żeby to było efektywne i działało szybko i jak powinna wyglądać struktura bazy danych do przechowywania tego.

Mam do dyspozycji bazę danych MySQL.

Z góry dziękuje za jakiekolwiek pomysły.Marcin Kapusta edytował(a) ten post dnia 29.03.12 o godzinie 09:47

Temat: Pomysły na strukturę bazy danych do przechowywania...

Hmmm,
wszystko fajnie tylko nie podałeś na jakiej bazie danych chcesz to zrobić...

Przy tych informacjach jakie podałeś polecałbym poczytać o zapytaniach hierarchicznych.

pozdrawiam,

Temat: Pomysły na strukturę bazy danych do przechowywania...

Michał G.:
Hmmm,
wszystko fajnie tylko nie podałeś na jakiej bazie danych chcesz to zrobić...

Już uzupełniłem Pytanie. Baza danych to MySQL.

Temat: Pomysły na strukturę bazy danych do przechowywania...

Marcin Kapusta:

Czy macie może jakieś pomysły jak podejść do tego, żeby to było efektywne i działało szybko i jak powinna wyglądać struktura bazy danych do przechowywania tego.

Mam do dyspozycji bazę danych MySQL.

Z góry dziękuje za jakiekolwiek pomysły.

Do tego potrzeba jest tabela z kluczaem głownym id i kluczem obcym parent_id w relacji sama do siebie, tabela pomocnicza ze zmaterializowaną ścieżką dziedziczenia oraz trigger na każdą operację CRUD.

Temat: Pomysły na strukturę bazy danych do przechowywania...

Aleksander Olszewski:

Do tego potrzeba jest tabela z kluczaem głownym id i kluczem obcym parent_id w relacji sama do siebie

Czyli standardowy zapis hierarhii

tabela pomocnicza ze zmaterializowaną ścieżką dziedziczenia oraz trigger na każdą operację CRUD.

Rozumiem, że trigger powinien aktualizować tą dodatkową tabele pomocniczą, ale czy mógłbyś mi przybliżyć nieco temat zmaterializowanej ścieżki dziedziczenia. Szukałem w google, ale praktycznie nic nie ma na ten temat. Czy masz więcej informacji na ten temat?

Temat: Pomysły na strukturę bazy danych do przechowywania...

Czy macie może jakieś pomysły jak podejść do tego, żeby to było efektywne i działało szybko i jak powinna wyglądać struktura bazy danych do przechowywania tego.

Nie wiem jak duże to będą tabele ...

Tabela: Routes

route_id| From | To | parent_route_id | is_leaf | distance_to_theleftmostleaf

Tabela: RoutesRelations -- dla każdej trasy lista wszystkich pod-tras

parent_route_id | chilid_route_id

Teraz po wykonaniu zapytania Poznań - Warszawa baza powinna zwrócić sekwencję rekordów:
Poznań
Konin
Łódź
Warszawa

Select [FROM] From Routes WHERE is_leaf = TRUE AND route_id in (SELECT child_route_id WHERE parent_route_id = ( SELECT route_id FROM Routes WHERE [FROM] = @From AND [TO] = @To) )
ORDER BY distance_to_theleftmostleaf

UNION

SELECT @To

@ - parametry
[...] - nazwy kolumn

Reszta jest chyba oczywista.Jakub Wojt edytował(a) ten post dnia 30.03.12 o godzinie 10:46

Temat: Pomysły na strukturę bazy danych do przechowywania...

To nie jest hierarchia - to jest graf. Dla sieci społecznościowych temat jest dość dobrze rozpoznany - pierwszy strzał z googla:
http://techportal.ibuildings.com/2009/09/07/graphs-in-...

Zapytanie - podaj wszystkie wiadomości między A i B - powinno zwrócić wszystkie. Można jechać z Warszawy do Gdańska - przez Kraków. Kto bogatemu zabroni? Żeby nie było takiego problemu - trzeba ustalić odległość minimalną i wypisać - powiedzmy - wszystkie miejscowości, dla których całkowita droga nie przekroczy 125% najkrótszej. Może - top 10? Pomijane są trasy, które zawierają powtórzenia... :)

Jeżeli tak - jest graf, nieskierowany, z ważonymi połączeniami. Konkretne wyszukiwanie jest rzeczywiście hierarchią, bo tak wygląda rozpinanie grafu z wybranego wierzchołka. Przeszukiwanie grafu i w zasadzie po temacie. Teoretycznie. W praktyce - nie do końca. Każdy kolejny krok w przeszukiwaniu to strzał w bazę. Rozwiązaniem mogłoby być określenie współrzędnych geograficznych miast i wyciągnięcie wszystkich miejscowości z zadanego obszaru - prostokąta o wierzchołkach A i B + może 20% marginesu. No, ale jak się tak zrobi i ktoś poda Zakopane - Szczecin - wszystkie wsie i miasteczka z całego kraju zabiją system, a może nie? Może jak ktoś jedzie przez cały kraj - zwraca uwagę na główne miasta - powiedzmy do powiatowych, reszta ginie w tłumie?

A może zbudować tabelę, która - dla zadanej pary odda zestaw list miejscowości - wcześniej przygotowany? Skoro miejscowości się nie poruszają? Może prościej raz przeliczyć i będzie szybsze jak cokolwiek innego. Jeżeli odległość mierzymy w kilometrach, a nie w godzinach - nie widzę problemu.

Temat: Pomysły na strukturę bazy danych do przechowywania...

A może warto zamiast robić to trochę na siłę w SQLu, użyć dedykowanej bazy do grafów?
http://neo4j.org/

Temat: Pomysły na strukturę bazy danych do przechowywania...

Popieram że to nie jest drzewo.

Gdyby jednak jakimś cudem właśnie taka miała być struktura, to najlepsza struktura już gdzieś była opisywana, nie pamiętam dokładnie, ale to szło mniej więcej tak:

(każdy rodzić z każdym swoim dzieckiem):

rec_id, desc

1, Poznan-Warszawa

2, Poznań-Łódź

3, Łódź-Warszawa

4, Poznań-Konin

5, Konin-Łódź



rec_id, parent_id, depth, sort

1, 0, 0, 0

2, 1, 0, 0

3, 1, 0, 1

4, 2, 1, 0

4, 1, 0, 0

5, 2, 1, 1

5, 1, 0, 1

- depth = 0 dla najważniejszego w hierarchi
- parent_id = 0 dla korzenia
- sort używany do sortowania pododcinków

Temat: Pomysły na strukturę bazy danych do przechowywania...

Marcin Kapusta:

Aleksander Olszewski:

Do tego potrzeba jest tabela z kluczaem głownym id i kluczem obcym parent_id w relacji sama do siebie

Czyli standardowy zapis hierarhii

Na ogół są 3 skuteczne sposoby implementacji struktur drzewiastych:
1. Model sąsiedztwa.
2. Model zmaterializowanej ścieżki.
3. Model zagnieżdżonych zbiorów.

Niektóre silniki, takie jak ORACLE mają wbudowane funkcje obsługi struktur drzewiastych (ostatnio dowiedziałem się, że PostgeSQL też, ale nie wiem w jakim zakresie). Tak więc w przypadku wysokowydajnych aplikacji warto rozważyć jeden z tych silników.

Jednakże mówimy o MySQL, a on tego nie ma. Stąd takie mechanizmy trzeba zrealizować ręcznie. Dlatego jest potrzeba triggerów i tabeli pomocniczej, tak aby cała mechanika logiki danych odbywała się na warstwie danych.

tabela pomocnicza ze zmaterializowaną ścieżką dziedziczenia oraz trigger na każdą operację CRUD.

Rozumiem, że trigger powinien aktualizować tą dodatkową tabele pomocniczą, ale czy mógłbyś mi przybliżyć nieco temat zmaterializowanej ścieżki dziedziczenia. Szukałem w google, ale praktycznie nic nie ma na ten temat. Czy masz więcej informacji na ten temat?

Połączenie modelu sąsiedztwa w tabeli głównej z modelem zmaterializowanej ścieżki w tabeli pomocniczej rzecz jasna powoduje redundancję danych, ale jest to redundancja wtórna, wynikająca z fizyczną implementacją struktury. Przejście w przyszłości na silnik bazodanowy, obsługujący struktury drzewiaste będzie bezproblemowe, jeśli główna tabela spełnia warunki normalizacji, a w tym przypadku będzie. Natomiast tabela pomocnicza zawiera cały zapis hierarchii w postaci np. 1.3.9.43. więc można szybko wyciągać dowolne wycinki drzewa.

Najgłówniejszym jednak pytaniem jest takie: czy drzewo jest odpowiednim rozwiązaniem tego problemu? Jak kolega Michał słusznie zauważył, być może mówimy tu o klasycznym problemie komiwojażera i bardzie właściwym byłoby jakieś rozwiązanie w teorii grafów?

Temat: Pomysły na strukturę bazy danych do przechowywania...

Moim zdaniem robienie takie struktury w "czystej bazie relacyjnej" mija się z celem, no chyba że jest to jakiś projekt studencki, w którym chce się udowodnić że jednak się da i nie szkoda Ci czasu :D
Do takich zadań należy zastosować dedykowane rozwiązania albo bazy danych, które posiadają dodatek do obsługi danych geograficznych np. Oracle Spatial w bazie danych Oracle.
Pomijając fakt że dużo prościej będzie Ci wprowadzić dane do takiej struktury to co najważniejsze, dużo prościej będzie Ci te dane wyciągnąć. Będziesz miał gotowe mechanizmy i rozwiązania wyszukiwania o których pisał Michał. Poza tym oprogramowanie tego w czystym SQL będzie też nie lada wyzwaniem i nie wiem czy jest sens się za to zabierać jeżeli na rynku jest wiele gotowych i dobrych rozwiązań. No chyba, że jak już wspomniałem wcześniej jest to ambitny studencki projekt ;)

Pozdrawiam
Oskar

Temat: Pomysły na strukturę bazy danych do przechowywania...

Oskar Graliński:
Moim zdaniem robienie takie struktury w "czystej bazie relacyjnej" mija się z celem, no chyba że jest to jakiś projekt studencki, w którym chce się udowodnić że jednak się da i nie szkoda Ci czasu :D
Do takich zadań należy zastosować dedykowane rozwiązania albo bazy danych, które posiadają dodatek do obsługi danych geograficznych np. Oracle Spatial w bazie danych Oracle.
Pomijając fakt że dużo prościej będzie Ci wprowadzić dane do takiej struktury to co najważniejsze, dużo prościej będzie Ci te dane wyciągnąć. Będziesz miał gotowe mechanizmy i rozwiązania wyszukiwania o których pisał Michał. Poza tym oprogramowanie tego w czystym SQL będzie też nie lada wyzwaniem i nie wiem czy jest sens się za to zabierać jeżeli na rynku jest wiele gotowych i dobrych rozwiązań. No chyba, że jak już wspomniałem wcześniej jest to ambitny studencki projekt ;)

Albo budżet nie pozwala na wykorzystanie np Oracle Spatia tudzież fragment który opisał jest niewielką częścią wielkiego systemu. Za mało wiadomo o projekcie.

Temat: Pomysły na strukturę bazy danych do przechowywania...

Popieram że to nie jest drzewo.

To nie było by drzewo gdyby istniało np. bezpośrednie połączenie z Poznania do Warszawy a takie najwyraźniej nie istnieje.

A skoro takiego nie ma to znaczy, że może (przynajmniej dla tych danych) modelować to jako drzewo a wyszukiwanie tras jako wyszukiwanie liści w poddrzewach.

Temat: Pomysły na strukturę bazy danych do przechowywania...

Jakub Wojt:

Popieram że to nie jest drzewo.

To nie było by drzewo gdyby istniało np. bezpośrednie połączenie z Poznania do Warszawy a takie najwyraźniej nie istnieje.

A skoro takiego nie ma to znaczy, że może (przynajmniej dla tych danych) modelować to jako drzewo a wyszukiwanie tras jako wyszukiwanie liści w poddrzewach.

Tylko przy tym podejściu mając zdefiniowane trasy:
a) Poznań - Warszawa
b) Warszawa - Lublin

z Poznania nie dojedziemy do Lublina, bo obie trasy są w hierarchii odcinków najwyżej.

Poza tym, zakładając że używamy hierarchii i wygenerujemy wszystkie możliwe pododcinki (co będzie chyba "eksplozją" danych - coś więcej niż iloczyn kartezjański) to i tak jak zapisać w ten sposób trasy alternatywne? Powiedzmy suboptymalne? Np. chcę jechać z Poznania do Warszawy przez Wrocław - bo tak...

Temat: Pomysły na strukturę bazy danych do przechowywania...

Tylko przy tym podejściu mając zdefiniowane trasy:
a) Poznań - Warszawa
b) Warszawa - Lublin

Ok. Ale to już będą inne dane :)

z Poznania nie dojedziemy do Lublina, bo obie trasy są w hierarchii odcinków najwyżej.

W takiej sytuacji drzewo zmieniło by się na takie:

                               [Poznań - Lublin]

                                /              \

                               /                \

               [Poznań - Warszawa]    [Warszawa - Lublin]

:)

Poza tym, zakładając że używamy hierarchii i wygenerujemy wszystkie możliwe pododcinki (co będzie chyba "eksplozją" danych - coś więcej niż iloczyn kartezjański)

Nie będzie eksplozji. Pod odcinków będzie ~ tyle co odcinków elementarnych.

Dużo większym problemem będzie znalezienie czegoś w rodzaju cyklu Hamiltona na grafie połączeń między dworcami (problem NP - complete) a bez tego nie będzie możliwości zbudowania drzewa na połączeniach.

to i tak jak zapisać w ten sposób trasy alternatywne? Powiedzmy suboptymalne? Np. chcę jechać z Poznania do Warszawy przez Wrocław - bo tak...

Zadanie brzmi 'szybko znaleźć trasę' a nie 'znaleźć szybką trasę' ;D
Trasa Gdańsk -> Gdynia przez Wrocław, Warszawa to też trasa ;)

W tym drugim przypadku (szybka trasa bez obliczania cyklu Hamiltona) to rzeczywiście tylko graf (dworce - węzły, połączenia - krawędzie) i algorytm Dikstry (albo jakiś inny).

I zła wiadomość dla autora wątku - tego się nie da zrobić w standardowym SQL.Jakub Wojt edytował(a) ten post dnia 30.03.12 o godzinie 14:48

Temat: Pomysły na strukturę bazy danych do przechowywania...

Bardzo Wam dziękuje za porady.

Daniel Podlejski:
A może warto zamiast robić to trochę na siłę w SQLu, użyć dedykowanej bazy do grafów?
http://neo4j.org/

Rzeczywiście pisząc ten temat nie miałem pojęcia, że można zastosować graf do tego celu. W ogóle mi to wyleciało z głowy. Być może dlatego bo nie używałem nigdy grafowych rozwiązań a tu proszę. Jest Neo4j i jest Graphserver pod pythona. Poza tym jest fajna aplikacja do wizualizacji i edycji całej struktury, która się nazywa Gephi.

Jakub Wojt:
I zła wiadomość dla autora wątku - tego się nie da zrobić w standardowym SQL.

Ojtam ojtam. Od razu zła wiadomość. Zmienia to troche koncepcję no i też hosting trzeba szukać inny bo jak się ma tylko MySQL'a i PHP to rzeczywiście można czasami utknąć przy bardziej ambitnych i nowocześniejszych projektach.

Pozdrawiam...

Temat: Pomysły na strukturę bazy danych do przechowywania...

Ojtam ojtam. Od razu zła wiadomość. Zmienia to troche koncepcję no i też hosting trzeba szukać inny bo jak się ma tylko MySQL'a i PHP to rzeczywiście można czasami utknąć przy bardziej ambitnych i nowocześniejszych projektach.

Niektórzy utykają a inni nie :) (http://en.wikipedia.org/wiki/AdWords#Technology)

MySQL i PHP to tylko technologia... i da się nad nią zapanować.Jakub Wojt edytował(a) ten post dnia 02.04.12 o godzinie 19:34