Jak zbudować model, aby właściwie i wydajnie reprezentować drzewiaste dane w relacyjnych bazach danych?

13

Opierając się na przemierzaniu drzewopodobnych danych w relacyjnej bazie danych za pomocą pytania SQL , chciałbym wiedzieć, w jaki sposób regularnie używany do opisywania drzewiastych danych w relacyjnych bazach danych z uwzględnieniem implikacji fizycznych?

Zakładam, że RDBMS nie ma specjalnych funkcji do obsługi innych niż zwykły SQL ANSI lub powszechnie dostępne funkcje.

Wątpliwości zawsze interesują mnie MySQL i PostgreSQL, a ostatecznie SQLite.

tree relational-theory database-design erd Maniero
źródło

Odpowiedzi:

8

Wierzę, że wybiera coś w rodzaju drzewa binarnego. Chciałbym tylko dołączyć trzy klucze, które są powiązane z unikalnym identyfikatorem tego samego stołu, jeden dla lewej, jeden dla prawego dziecka i jeden dla rodzica.

ie- (bardzo pseudokod)

TABLE tree
int         id                  autoinc
varchar(16) data_you_care_about
int         parent_id
int         left_child_id
int         right_child_id

FOREIGN KEY parent_id = tree.id
FOREIGN KEY left_child_id = tree.id
FOREIGN KEY right_child_id = tree.id
Patrick
źródło
W przypadku podwójnie połączonego elementu należy wziąć pod uwagę, że wszelkie zmiany pozycji drzewa w tym schemacie spowodowałyby nie mniej niż 3 aktualizacje zamiast jednej. Jak twierdzisz, jest to również duże założenie, że wymagane jest drzewo binarne do przodu / do tyłu.
REW
bardzo prawda, z moich doświadczeń wolę podatek od aktualizacji podwójnie połączonej listy niż pojedynczo połączonej listy, ponieważ często muszę przemierzać drzewo. ale w wielu przypadkach nie byłoby to konieczne
Patrick
Z pewnością zależy to od modelu bazowego. Myślę, że odpowiedź udzielona przez Patricka jest wystarczająca, jeśli jest to właściwy model.
jcolebrand
6

Jeśli każdy węzeł jest tak naprawdę tą samą jednostką danych, wówczas paradygmat nadal oznaczałby jedną tabelę na jednostkę i kolumnę łączącą dla przejścia drzewa, gdzie każdy węzeł jest połączony tylko raz.

W przypadku jednostek, które są połączone w wielu punktach drzewa, zastosowana zostanie osobna tabela łączenia lub kolumna z wieloma odrębnymi wartościami.

REW
źródło