Klasifikace a systémová analýza - AISPV1001

Kritéria pro srovnávání struktur

1) Sémantika
2) Flexibilita
3) Případy užití

---

Lineární, stromové a síťové struktury

Lineární, stromové a síťové struktury jsou založeny na teorii grafů. Přístup k datům je realizován technikou navigace. Tato technika umožňuje přímý přístup (skok) od jednoho souvisejícího prvku ke druhému. Vztahy mezi prvky struktury jsou trvalé: vazby ve všech předpokládaných směrech jsou definovány před vyhledáváním/přístupem. Chceme-li vyjádřit jiné vztahy mezi prvky, musíme celý soubor fyzicky přeuspořádat.

graf (diagram)
určitý útvar (rovinný, prostorový), znázorňující vztahy (vazby, relace) mezi prvky systému prostřednictvím množiny uzlů a hran

uzel (angl. node)
při znázorňování grafu v rovině se uzly zobrazují zpravidla jako body této roviny
hrana (angl. edge)
spojnice dvou uzlů v grafu, popř. čára začínající a končící v témže uzlu (tzv. smyčka); hrany značíme koncovými uzly
cesta
posloupnost navazujících hran

Typy grafů

a) souvislý – nesouvislý

souvislý graf		nesouvislý graf

 

souvislý graf: mezi každými dvěma uzly existuje alespoň jedno spojení (mezi libovolnou dvojicí uzlů existuje nějaká cesta)

b) orientovaný – neorientovaný

orientovaný graf		neorientovaný graf

hranám je/není přiřazena orientace (směr)
orientovaný graf (angl. directed graph) - též usměrněný graf, postupový diagram

c) ohodnocený – neohodnocený

ohodnocený graf		neohodnocený graf

hranám či uzlům jsou/nejsou přiřazeny hodnoty
ohodnocená (angl. labeled) hrana či uzel: má přiřazenu sémantiku, tj. jednu nebo více hodnot (např. trvání, nároky na zdroje, vzdálenost, čas, náklady...)

d) hranově definovaný – uzlově definovaný

činnost/data (zdroj, informaci), jež chceme grafem znázornit, zobrazují buď hrany nebo uzly

---

strukturní prvek (dokument, záznam, či jejich prvky - elementy)

Lineární (sekvenční) struktura

Všechny údaje stejného typu jsou ukládány sekvenčně (za sebou) do jednoho souboru.

vztahy mezi strukturními prvky:

• mezi údaji není žádný vzájemný vztah kromě posloupnosti jejich uložení (vztah sekvenční asymetrické asociace)
• 1 : 1 - každý prvek může mít max. 1 následující a 1 předcházející, příp. 1 nadřazený a 1 podřazený prvek

technika přístupu:

sekvenční procházení celým souborem (dokumentem, kolekcí, databází) od začátku až do konce

klad		zápory
jednoduchost návrhu		nemožnost vyjádření vztahů 1 : N a N : M (pouze za cenu redundance dat) problémy s integritou dat neexistuje způsob, jak přímo vyhledat určitý údaj (nutnost sekvenčního prohledávání) obtížnost dodatečných změn struktury (celý soubor je nutné fyzicky znovu uspořádat)
užití		standardy
zálohy dat (sekvenční ukládání na magnetickou pásku) fulltextové systémy (doplněné indexovými soubory)		ISO 2709 – výměnný formát pro bibliografické záznamy

Stromová (hierarchická) struktura

terminologie: strom (angl. tree), kořen (angl. root), větev (angl. branch), potomek (angl. child), sourozenec (angl. sibling), rodič (angl. parent), list (angl. leaf)

Údaje stejného typu jsou umístěny v jednotlivých úrovních. Mezi úrovněmi jsou definovány vztahy inkluze (nadřazenosti a podřazenosti). Prvek hierarchicky nadřazený může souviset s libovolným počtem prvků v podřazené úrovni, prvek v podřazené úrovni může souviset pouze s jedním hierarchicky nadřazeným prvkem.

vztahy mezi strukturními prvky:

• 1 : N - jednosměrné (k podřazeným prvkům lze přistupovat pouze přes nadřazené prvky)
• rodičovský vztah - synovský prvek obsahuje data, která doplňují rodičovský prvek

technika přístupu:

sekvenční procházení zvolenou větví stromu

klady		zápory
možnost vyjádřit hierarchické vztahy (nadřazenost - podřazenost, celek - část, 1 : N) rychlejší vyhledávání dat (neprohledává se celý dokument, ale jen příslušné části - větve)		nemožnost jednoduchého vyjádření vztahů N : M mezi prvky (bez duplicit) strukturu je třeba předem pevně stanovit obtížnost dodatečných změn struktury
užití		standardy
indexové soubory HTML a XML dokumenty objektově orientovaná technologie		ISO 8879 – SGML HTML XML

Typy hierarchických struktur

a) podle sémantiky vztahů (podrobněji viz kapitola 3.1 Vztahy)

založeno na nepodstatné vlastnosti obecná, hledisková hierarchie		založeno na podstatné (esenciální) vlastnosti speciální, "logická hierarchie
vyjadřuje pouze vztah zahrnutí (inkluze) užší - širší obsah / rozsah		generická: zahrnutí rod - druh + dědičnost vlastností + vlastní specifické vlastnosti (vztah třída - třída) instanční: zahrnutí + dědičnost vlastností + specifické označení (vztah třída - prvek) partitivní: zahrnutí celek - část + rozdílné vlastnosti (vztah třída - třída)

b) podle počtu kritérií členění

stejné kritérium na všech úrovních členění		různá kritéria na různých úrovních členění
stromová (angl. tree) hierarchie postupné zvyšování / zjemňování specializace / granularity		vnořená/zanořená (angl. nested) víceúrovňová / vícestupňová hierarchie řetězení
Příklad - třídy MDT zahrnující textilní vlákna členěné jednotně na všech úrovních podle původu vlákna:		Příklad - třídy MDT zahrnující oděvy členěné na první úrovni podle určení (kdo nosí oděv) a na druhé úrovni podle stylu oděvu:

c) podle řešení složených témat
 

enumerativní		fasetová (podrobněji viz kapitola 6 Fasetová analýza)
Příklad - třídy MDT zahrnující textilní vlákna: 677.1/.5 Textilní vlákna     677.1/.3 Přírodní vlákna         677.1/.2 Rostlinná vlákna             677.1 Lýková vlákna             677.2 Rostlinná vlákna ze semen nebo plodů             677.3 Živočišná vlákna                 677.31 Ovčí vlna             677.4 Umělá vlákna. Chemická vlákna             677.5 Minerální a kovová vlákna. Pletivové materiály. Gumová vlákna. Papírové příze               677.51 Přírodní minerální vlákna               677.52 Umělá minerální vlákna               677.53 Kovová vlákna               677.54 Rostlinné materiály pro pletení a splétání               677.55 Vlákna z gumy a podobných elastických materiálů               677.57 Papírová vlákna a papírové příze		Příklad - hypotetická fasetová struktura pro dané třídy MDT zahrnující textilní vlákna:
		původ vlákna	materiál vlákna	užití vlákna
		přírodní    rostlinný    živočišný    nerostný umělý	guma kov lýko minerál papír plod semeno vlna	pletení splétání

Síťová struktura

vztahy mezi strukturními prvky:

• 1 : N, N : 1, N : M - obousměrné
• každý prvek může být spojen libovolným způsobem se všemi ostatními prvky

technika přístupu:

sekvenční procházení zvolenou cestou v síti

klady		zápory
flexibilita při vytváření vztahů 1 : N, N : 1 a N : M rychlé vyhledávání (neprohledáváme celý dokument, ale sledujeme přímou cestu k danému prvku stanovenou definovanou vazbou - přímé skoky) odstranění duplicity údajů		vzájemné vztahy mezi množinami se mohou stát velmi komplikovanými a obtížně se mapují strukturu je třeba předem pevně stanovit: jakmile je vytvořena, každá změna na jiný systém množin vyžaduje vytvoření zcela nové struktury umožňuje rychle zodpovídat pouze předem připravené dotazy, komplikované dotazy vyžadují provést více kroků
užití		standardy
hypertext, hypermédia World Wide Web (uzly = zdroje/dokumenty, hrany = hypertextové odkazy) znalostní grafy		CODASYL RDF

Relační struktura

vztahy mezi strukturními prvky:

• data jsou organizována do uspořádaných n-tic
• možnost vyjádřit všechny typy vztahů (1 : 1, 1 : N, N : 1, N : M) prostřednictvím stejných údajů v dvojici položek v souvisejících záznamech
• technická (fyzická) realizace: relace (podmnožina kartézského součinu)

technika přístupu:

množinové operace nad množinami vybraných sloupců a řádků (projekce, selekce, spojení, průnik)

klady:

• flexibilita při vytváření vztahů mezi různými prvky (spojení není trvalé - vztahy definujeme až v okamžiku, kdy je potřebujeme např. k zodpovězení dotazu)
• jednoduchost
• změna struktury spočívá v pouhém přidání nebo zrušení sloupce v tabulce a nijak neovlivní ostatní tabulky (přínos pro zachování integrity dat)
• neprocedurálnost (určujeme, co chceme s daty dělat, nikoli, jak toho dosáhnout)

zápory:

• nároky na paměť a výkon počítače (pracuje se neprocedurálním způsobem s celými množinami dat)
• neefektivní vyhledávání: načítáme nejprve do paměti celé množiny dat, z nichž pak vybíráme průnik

užití: transakční (relační) databáze

standardy:

ISO/IEC 9075 – SQL