Jak utrzymać strukturę danych wykresu w relacyjnej bazie danych?

Zastanawiałem się nad tworzeniem tabeli wierzchołków i tabeli krawędzi, ale czy tworzenie wykresów w pamięci i przechodzenie między podrysami wymagałoby dużej liczby wyszukiwań? Chciałbym uniknąć nadmiernego czytania bazy danych. Czy istnieje inny sposób utrzymywania wykresu?Jak utrzymać strukturę danych wykresu w relacyjnej bazie danych?

Uwaga boczna: Słyszałem o Neo4j, ale moje pytanie brzmi tak naprawdę, jak koncepcyjnie przedstawiać wykres w standardowej bazie danych. Jestem otwarty na niektóre rozwiązania NoSQL, takie jak mongodb.

Źródło

2013-09-03 Frank Flannigan

W celu udzielenia cennej porady potrzebuję więcej informacji z Twojej strony. Ile węzłów i ile relacji mówimy? –

Cóż, powiedziałbym, miliardy węzłów. Tak jak powiedziałem, jest to w większości konceptualna, ale jestem ciekawa jak skalować na wiele rekordów. Mam na myśli bardzo duże wykresy. –

Nie open source, ale dokładnie to, czego szukasz: nowy Aster 6.0 jest wyposażony w silnik graficzny w relacyjnej bazie danych - o nazwie SQL-GR i ma na celu wykorzystanie istniejących i nowych funkcji na wykresach przechowywanych w tabelach relacyjnych (w Aster): reprezentowane za pomocą tabeli węzłów i tabeli krawędzi. – topchef

Odpowiedź jest niestety: Twoje zdanie jest całkowicie poprawne w każdym punkcie. Musisz przechowywać węzły (wierzchołki) w jednej tabeli oraz krawędzie odwołujące się do węzła FromNode i ToNode, aby przekonwertować strukturę danych wykresu na relacyjną strukturę danych. I masz również rację, że kończy się to dużą liczbą odnośników, ponieważ nie jesteś w stanie podzielić go na podgrafy, które mogą być natychmiast zapytane. Musisz przejść od węzła do krawędzi do węzła do krawędzi do węzła ... i tak dalej (rekurencyjnie, podczas gdy SQL działa z zestawami).

Chodzi o to ...

relacyjny, wykres zorientowany, obiektowe, Dokument oparte są różne typy struktur danych, które spełniają różne wymagania. O tym wszystkim chodzi i dlaczego powstało tak wiele różnych baz danych NoSQL (większość z nich to proste sklepy z dokumentami), ponieważ po prostu nie ma sensu organizować dużych danych w sposób relacyjny.

Alternatywa 1 - wykres zorientowany w bazie

Ale są też zorientowany wykres baz danych NoSQL, które sprawiają, że model danych wykresu pierwszej klasy obywatel jak OrientDB której jestem zabawy z odrobiną na chwilę. Zaletą jest to, że chociaż dane są nadal widoczne w formie wykresu, nadal można go używać w sposób relacyjny lub nawet zorientowany obiektowo lub dokumentowo (np. Za pomocą zwykłego zapytania SQL). Niemniej jednak, Traversing the graph jest optymalnym sposobem na uzyskanie danych z tego na pewno.

Alternative 2 - praca z wykresami w pamięci

Jeśli chodzi o szybki routing, ramy routingu jak Graphhopper budować graf pełny (miliardy węzłów) wewnątrz pamięci. Ponieważ Graphhopper wykorzystuje implementację MemoryMapped w swoim GraphStore, która działa nawet na urządzeniach z Androidem z tylko kilkoma MB pamięci. Kompletny wykres jest odczytywany z bazy danych na pamięć podczas uruchamiania, a następnie odbywa się tam rutowanie, więc nie trzeba sprawdzać bazy danych.

Źródło

2013-11-30 19:19:43

+1 BTW: jedyna różnica między "DB wykresu" i "relacyjnym DB" jest ** implementacją ** wyszukiwania. Jeśli lista krawędzi przywołana w tabeli węzłów zostanie osiągnięta za pomocą wskaźnika bezpośredniego, można nazwać ją DB, chociaż dane nadal mogą być uporządkowane w tabelach! Tak więc, jeśli to wyszukiwanie jest log (n) na liście krawędzi lub nawet na krawędzi, to ludzie nazywają to "relacyjnym DB" i przechodzenie przez wykres jest dość kosztowne (niezależnie od tego, czy pamięć jest przechowywana w pamięci, czy w pamięci) . – Karussell

@Karussell Warto zauważyć, że większość baz danych SQL obsługuje indeksy oparte na hashach, przy czym wyszukiwanie krawędzi/wierzchołków to O (1), podobnie jak w przypadku bazy danych wykresów. Czas zapytania O (log (n)) jest zwykle powiązany z indeksami opartymi na drzewie B, które są najczęściej używane, gdy ważne jest sortowanie danych (które dla identyfikatorów krawędzi/wierzchołków zwykle nie są istotne). – ThePhysicist

Prawdopodobnie masz rację. Wciąż indeks bazujący na hashu ma narzut (przestrzeń i czas) w praktyce IMO w porównaniu z bezpośrednim wskaźnikiem. Ale prawdopodobnie zastosowana technologia jest bardzo podobna dla obu DB i tylko marketing blabla sprawia, że wyglądają zupełnie inaczej :) – Karussell

I w obliczu tego samego problemu i postanowił wreszcie pójść o następującej strukturze, która wymaga 2 zapytań do bazy danych, a następnie reszta pracy jest w pamięci:

Przechowuj węzłów w tabeli i odniesienie do wykresu z każdym rekord węzeł:

Table Nodes 

id | title | graph_id 
--------------------- 
105 | node1 | 2 
106 | node2 | 2

przechowywania także w innej krawędzi stołu i ponownie odniesienia wykres krawędzie te należą do każdej z krawędzi:

Table Edges 

id | from_node_id | to_node_id | graph_id 
----------------------------------------- 
1 | 105   | 106  | 2 
2 | 106   | 105  | 2

Uzyskaj wszystkie węzły za pomocą jednego zapytania, a następnie uzyskaj wszystkie krawędzie za pomocą innego.

Teraz utwórz preferowany sposób przechowywania wykresu (np. Listę sąsiedztwa) i kontynuuj przepływ aplikacji.

Źródło

2017-10-29 09:40:00 linkinu

Jak utrzymać strukturę danych wykresu w relacyjnej bazie danych?

Odpowiedz

Powiązane problemy