Vnořený set model - Nested set model

Model vnořené sady je technika pro reprezentaci vnořených sad (také známých jako stromy nebo hierarchie ) v relačních databázích .

Motivace

Standardní relační algebra a relační počet a na nich založené operace SQL nejsou schopny přímo vyjádřit všechny požadované operace v hierarchiích. Vnořený model sady 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 přilehlostí . Pokud může mít hierarchie libovolnou hloubku, model seznamu sousedností neumožňuje vyjádření operací, jako je porovnávání obsahu hierarchií dvou prvků nebo určování, zda je prvek někde v subhierarchii jiného prvku. Když má hierarchie pevnou nebo ohraničenou hloubku, jsou operace možné, ale nákladné, kvůli nutnosti provedení jednoho relačního spojení na úrovni. Toto je často známé jako problém kusovníku .

Hierarchie lze snadno vyjádřit přepnutím do databáze grafů . Alternativně existuje několik řešení pro relační model a jsou k dispozici jako řešení v některých systémech správy relační databáze :

• podpora vyhrazeného datového typu hierarchie , například v hierarchickém dotazovacím zařízení SQL ;
• rozšíření relačního jazyka o hierarchické manipulace, například ve vnořené relační algebře .
• rozšíření relačního jazyka o přechodné uzavření , jako je 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 obklopen relačními operacemi, jako je PL/SQL , T-SQL nebo univerzální programovací jazyk

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

Technika

Vnořený model sady má očíslovat uzly podle procházení stromem , který každý uzel navštíví dvakrát, přiřadí čísla v pořadí návštěvy a při obou návštěvách. Pro každý uzel tak zůstanou dvě čísla, která jsou uložena jako dva atributy. Dotazování se stává levným: členství v hierarchii lze testovat porovnáním těchto čísel. Aktualizace vyžaduje přečíslování, a proto je drahá. Upřesnění, která používají namísto celých čísel racionální čísla, se mohou vyhnout přečíslování, a proto se rychleji aktualizují, i když jsou mnohem komplikovanější.

Příklad

V katalogu obchodů s oděvy lze oděvy kategorizovat podle hierarchie uvedené vlevo:

Hierarchie: druhy oblečení

Číslování přiřazené procházením stromu

Kategorie „Oblečení“ s nejvyšší pozicí v hierarchii zahrnuje všechny podřízené kategorie. Je proto udávána hodnota levé a pravé domény 1 a 22, přičemž druhá hodnota je dvojnásobkem celkového počtu reprezentovaný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í v nich obsažených, jak je uvedeno v tabulkových datech.

Výkon

Lze očekávat, že dotazy používající vnořené sady budou rychlejší než dotazy používající uloženou proceduru k procházení seznamů sousedících, a stejně tak jsou rychlejší volbou pro databáze, které postrádají nativní rekurzivní konstrukty dotazů, jako je MySQL 5.x. Lze však očekávat, že rekurzivní dotazy SQL budou fungovat srovnatelně pro dotazy „najít bezprostřední potomky“ a mnohem rychleji pro jiné hloubkové vyhledávací dotazy, a tedy i rychlejší možnost pro databáze, které je poskytují, jako jsou PostgreSQL , Oracle a Microsoft SQL Server . MySQL dříve postrádal rekurzivní konstrukce dotazů, ale ve verzi 8 takové funkce přidal.

Nevýhody

Případ použití pro dynamickou nekonečnou hierarchii databázových stromů je vzácný. Model vnořené sady je vhodný tam, kde jsou jediným prvkem stromový prvek 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 podřízenou kategorii „Automobily“ s podřízenou značkou „Mercedes“ musí být navázán vztah mezi tabulkou cizích klíčů, pokud není stromová tabulka nativně normalizována. Atributy nově vytvořené položky stromu nemusí sdílet všechny atributy s rodičem, podřízeným nebo dokonce sourozencem. Pokud je pro tabulku atributů „Rostliny“ vytvořena tabulka cizích klíčů, nebude podřízeným datům atributů „Stromy“ a jeho podřízených „Dubů“ dána žádná integrita. Proto musí být v každém případě položky vložené do stromu vytvořena tabulka cizích klíčů atributů položky pro všechny, kromě nejtriviálnějších případů použití.

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

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

Model nepovoluje více nadřazených kategorií. Například „dub“ může být podřízeným „stromového typu“, ale také „dřevěného typu“. K tomu je třeba zavést další značkování nebo taxonomii, což opět povede ke složitějšímu designu než k přímému pevnému modelu.

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

Vnořené interval modelu netrpí tímto problémem, ale je složitější realizovat, a není tak známý. Stále trpí problémem relační tabulky cizích klíčů. Vnořený intervalový model ukládá polohu uzlů jako racionální čísla vyjádřená jako kvocienty (n/d). [1]

Variace

Použití vnořeného modelu 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 o nalezení bezprostředních podřízených uzlů s nadřazeným uzlem vyžaduje prořezání podstromu na konkrétní úroveň jako v následujícím příkladu kódu SQL :

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Parent, Tree as Child
WHERE
	Child.Left BETWEEN Parent.Left AND Parent.Right
	AND NOT EXISTS (    -- No Middle Node
		SELECT *
		FROM Tree as Mid
		WHERE Mid.Left BETWEEN Parent.Left AND Parent.Right
     			AND Child.Left BETWEEN Mid.Left AND Mid.Right
			AND Mid.Node NOT IN (Parent.Node, Child.Node)
	)
	AND Parent.Left = 1  -- Given Parent Node Left Index

Nebo ekvivalentně:

SELECT DISTINCT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent 
WHERE Parent.Left < Child.Left AND Parent.Right > Child.Right  -- associate Child Nodes with ancestors
GROUP BY Child.Node, Child.Left, Child.Right
HAVING max(Parent.Left) = 1  -- Subset for those with the given Parent Node as the nearest ancestor

Při hledání dětí ve více než jedné úrovni hloubky bude dotaz složitější. K překonání tohoto omezení a zjednodušení procházení stromu je do modelu přidán další sloupec, který udržuje hloubku uzlu ve stromu.

V tomto modelu lze nalezení bezprostředních potomků s nadřazeným uzlem provést pomocí následujícího kódu SQL :

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent
WHERE
	Child.Depth = Parent.Depth + 1
	AND Child.Left > Parent.Left
	AND Child.Right < Parent.Right
	AND Parent.Depth = 1  -- Given Parent Node Left Index

Viz také

• Procházení stromů
• Strom (datová struktura)
• Sousední seznam

Reference

externí odkazy

• Odkazy 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 sousedností na vnořené sady pomocí uložených procedur MySQL
• PHP Doctrine Implementace DBAL pro vnořené sady - podle PreviousNext
• R Vnořená sada - Příklad vnořené sady v R.