Vnořený model sady - Nested set model

The vnořený model sady je technika reprezentace vnořené sady (také známý jako stromy nebo hierarchie ) v relační databáze.

Motivace

Standardní relační algebra a relační počet a SQL operace na nich založené nejsou schopny vyjádřit přímo všechny žádoucí operace na hierarchiích. Vnořený model množiny je řešením tohoto problému.

Alternativním řešením je vyjádření hierarchie jako vztahu rodič-dítě. Celko tomu říkal model seznamu sousedství. Pokud může mít hierarchie libovolnou hloubku, model seznamu sousedství neumožňuje vyjádření operací, jako je porovnání obsahu hierarchií dvou prvků nebo určení, zda je prvek někde v podhierarchii jiného prvku. Když je hierarchie pevné nebo ohraničené hloubky, operace jsou možné, ale drahé, kvůli nutnosti provedení jedné relační spojení za úroveň. Toto je často známé jako Kusovník problém.^{[Citace je zapotřebí ]}

Hierarchie lze snadno vyjádřit přepnutím na a grafová databáze. Alternativně existuje několik rozlišení pro relační model a v některých je k dispozici jako řešení systémy pro správu relačních databází:

• podpora vyhrazeného hierarchický datový typ, například v SQL hierarchický dotaz zařízení;
• rozšíření relačního jazyka o hierarchické manipulace, jako například v vnořená relační algebra.
• rozšíření relačního jazyka o přechodné uzavření, například příkaz SQL CONNECT; to umožňuje použít vztah rodič-dítě, ale provedení zůstává nákladné;
• dotazy mohou být vyjádřeny v jazyce, který podporuje iteraci a je zabalen kolem relačních operací, jako například PL / SQL, T-SQL nebo a univerzální programovací jazyk

Pokud tato řešení nejsou k dispozici nebo nejsou proveditelná, je třeba zvolit jiný přístup.

Technika

Model vnořené sady má očíslovat uzly podle a traversal strom, který navštíví každý uzel dvakrát, přiřadí čísla v pořadí podle návštěv a při obou návštěvách. To ponechává dvě čísla pro každý uzel, která jsou uložena jako dva atributy. Dotazování se stává levným: členství v hierarchii lze otestovat porovnáním těchto čísel. Aktualizace vyžaduje přečíslování a je proto nákladná. Vylepšení, která používají racionální čísla místo celých čísel se lze vyhnout přečíslování, a tak se rychleji aktualizují, i když mnohem komplikovanější.^[1]

Příklad

V katalogu oděvů lze oblečení rozdělit do kategorií podle hierarchie uvedené vlevo:

Hierarchie: druhy oděvů

Číslování přidělené procházením stromu

Kategorie „Oděvy“ s nejvyšší pozicí v hierarchii zahrnuje všechny podřízené kategorie. Je proto dána hodnota levé a pravé domény 1 a 22, přičemž druhá hodnota je dvojnásobkem celkového počtu zastoupených uzlů. Další hierarchická úroveň obsahuje „Pánské“ a „Dámské“, přičemž obě obsahují úrovně v sobě, které je třeba zohlednit. Datovému uzlu každé úrovně jsou přiřazeny hodnoty levé a pravé domény podle počtu podúrovní obsažených uvnitř, jak je uvedeno v datech tabulky.

Výkon

Lze očekávat, že dotazy používající vnořené sady budou rychlejší než dotazy používající a uložené procedury procházet seznamem sousedství, a tak jsou rychlejší volbou pro databáze, které postrádají nativní rekurzivní konstrukty dotazů, jako například MySQL.^[2] Lze však očekávat, že rekurzivní dotazy SQL budou fungovat srovnatelně pro dotazy „najít okamžité potomky“ a mnohem rychleji pro jiné dotazy na hloubkové vyhledávání, stejně jako rychlejší volba pro databáze, které je poskytují, jako například PostgreSQL,^[3] Věštec,^[4] a Microsoft SQL Server.^[5]

Nevýhody

Případ použití pro dynamickou hierarchii nekonečných databázových stromů je vzácný. Model vnořené sady je vhodný tam, kde jsou jedinými daty prvek stromu a jeden nebo dva atributy, ale je špatnou volbou, pokud pro prvky ve stromu existují složitější relační data. Vzhledem k libovolné počáteční hloubce pro kategorii „Vozidla“ a dítě „Cars“ s dítětem „Mercedes“ musí být vytvořen vztah tabulky cizích klíčů, pokud tabulka stromu není nativně nenormalizovaná. Atributy nově vytvořené položky stromu nemusí sdílet všechny atributy s rodičem, dítětem nebo dokonce sourozencem. Pokud je pro tabulku atributů „Plants“ vytvořena tabulka cizích klíčů, není dána žádná integrita datům podřízených atributů „Trees“ a jejich podřízených „Oak“. Proto v každém případě položky vložené do stromu musí být vytvořena tabulka cizích klíčů atributů položky pro všechny případy použití kromě těch nejtriviálnějších.

Pokud se neočekává, že se strom bude často měnit, lze v počátečním návrhu systému vytvořit správně normalizovanou hierarchii tabulek atributů, což povede k jednodušším a přenosnějším příkazům SQL; konkrétně ty, které nevyžadují libovolný počet runtime, programově vytvořené nebo odstraněné tabulky pro změny ve stromu. U složitějších systémů lze hierarchii rozvíjet spíše prostřednictvím relačních modelů než pomocí implicitní numerické stromové struktury. Hloubka položky je prostě jiný atribut, nikoli základ pro celou architekturu DB. Jak je uvedeno v Antipatterns SQL:^[6]

Vnořené sady jsou chytré řešení - možná příliš chytré. Rovněž nedokáže podporovat referenční integritu. Nejlépe se to používá, když potřebujete dotazovat strom častěji, než potřebujete strom upravit.^[7]

Model neumožňuje více nadřazených kategorií. Například „dub“ může být dítětem typu „strom“, ale také „dřeva“. Aby to bylo možné přizpůsobit, je třeba zavést další značení nebo taxonomii, což opět povede ke složitějšímu designu než přímý pevný model.

Vnořené sady jsou pro vložky velmi pomalé, protože vyžaduje aktualizaci hodnot levé a pravé domény pro všechny záznamy v tabulce po vložení. To může způsobit velké namáhání databáze, protože je přepsáno mnoho řádků a znovu sestaveny indexy. Pokud je však možné uložit les malých stromů do tabulky namísto jediného velkého stromu, může být režie výrazně snížena, protože musí být aktualizován pouze jeden malý strom.

The model vnořeného intervalu netrpí tímto problémem, ale jeho implementace je složitější a není tak dobře známá. Stále trpí problémem relační tabulky cizích klíčů. Model vnořeného intervalu ukládá polohu uzlů jako racionální čísla vyjádřená jako kvocienty (n / d). [1]

Variace

Použití modelu vnořené sady, jak je popsáno výše, má určitá omezení výkonu během určitých operací procházení stromu. Například pokus najít okamžité podřízené uzly dané nadřazeným uzlem vyžaduje prořezávání podstromu na konkrétní úroveň, jak je uvedeno v následujícím příkladu SQL příklad kódu:

VYBRAT Dítě.Uzel, Dítě.Vlevo, odjet, Dítě.Že joZ Strom tak jako Rodič, Strom tak jako DítěKDE	Dítě.Vlevo, odjet MEZI Rodič.Vlevo, odjet A Rodič.Že jo	A NE EXISTUJE (    - Žádný střední uzel		VYBRAT *		Z Strom tak jako Střední		KDE Střední.Vlevo, odjet MEZI Rodič.Vlevo, odjet A Rodič.Že jo     			A Dítě.Vlevo, odjet MEZI Střední.Vlevo, odjet A Střední.Že jo			A Střední.Uzel NE V (Rodič.Uzel, Dítě.Uzel)	)	A Rodič.Vlevo, odjet = 1  - Vzhledem k levému indexu nadřazeného uzlu

Nebo ekvivalentně:

VYBRAT ODLIŠNÝ Dítě.Uzel, Dítě.Vlevo, odjet, Dítě.Že joZ Strom tak jako Dítě, Strom tak jako Rodič KDE Rodič.Vlevo, odjet < Dítě.Vlevo, odjet A Rodič.Že jo > Dítě.Že jo  - přidružit dětské uzly s předkySKUPINA PODLE Dítě.Uzel, Dítě.Vlevo, odjet, Dítě.Že joMÁM max(Rodič.Vlevo, odjet) = 1  - Podmnožina pro ty, kteří mají daný rodičovský uzel jako nejbližšího předka

Dotaz bude komplikovanější při hledání dětí hlubších než jedna úroveň. K překonání tohoto omezení a zjednodušení traversal strom do modelu je přidán další sloupec, který udržuje hloubku uzlu ve stromu.

V tomto modelu lze najít bezprostřední potomky dané nadřazeným uzlem dosáhnout následujícím způsobem SQL kód:

VYBRAT Dítě.Uzel, Dítě.Vlevo, odjet, Dítě.Že joZ Strom tak jako Dítě, Strom tak jako RodičKDE	Dítě.Hloubka = Rodič.Hloubka + 1	A Dítě.Vlevo, odjet > Rodič.Vlevo, odjet	A Dítě.Že jo < Rodič.Že jo	A Rodič.Hloubka = 1  - Vzhledem k levému indexu nadřazeného uzlu

Viz také

• Traverz stromu
• Strom (datová struktura)
• Seznam sousedů

Reference

externí odkazy

• Odkazy společnosti Troels na hierarchická data v RDBMS
• Správa hierarchických dat v relačních databázích
• Implementace PHP PEAR pro vnořené sady - Daniel Khan
• Transformujte libovolný seznam sousedství na vnořené sady pomocí uložených procedur MySQL
• Implementace PHP Doctrine DBAL pro vnořené sady - podle PreviousNext
• R Vnořená sada - Vnořený příklad v R