3. Vztahy a struktury

3.3. Typy struktur

Kritéria pro srovnávání struktur
1) Sémantika
typ vyjádřených vztahů (ekvivalence, hierarchie, asociace)
násobnost vyjádřených vztahů
2) Flexibilita
tj. možnost dodatečných změn struktury
3) Případy užití
pro makro-organizaci zdrojů -> kolekce zdrojů
pro mikro-organizaci zdrojů -> strukturování dokumentů


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ý

souvisly       nesouvisly
 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ý

orientovany         neorientovany
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ý

ohodnoceny         neohodnoceny
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


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


Lineární (sekvenční) struktura

linearni 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)

stromová struktura

Ú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:
        
strom    nested


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

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

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