# XBUP - Dokumentace: Transformace bloků

### Úvod

Tento dokument je součástí dokumentace projektu eXtensible Binary Universal Protocol. Obsahuje techniky a specifikace pro transformaci bloků.

O úroveň výše

### Obsah

1. Transformace
1.1. Implicitní transformace
1.2. Transformační graf
1.2.1. Transformační rozhraní
1.3. Omezující podmínky
1.3.1. Definice omezujících podmínek
2. Transformační funkce
2.1. Datové transformace
2.1.1. Komprese
2.1.2. Šifrování
2.2. Extrakční blok
2.2.1. Přímá extrakce
2.3. Kontrolní bloky
2.3.1. Kontrola mladších sourozenců
2.4. Převodní bloky
2.5. Analyzovatelnost dokumentu

### 1. Transformace

Transformace představují rozšíření typů bloků o možnost zpracování dat pomocí výpočtu. Transformační operace převádějí data z jednoho tvaru na druhý (ne nutně ekvivaletní) a umožňují tak definovat parametry bloků, tedy povolené typy podbloků. Data by měla být převáděna na různé tvary automaticky podle potřeby a obvykle bez nutnosti zásahu uživatele.

Na jednotlivé bloky je nahlíženo jako na funkce, které kromě vlastního typu mají také návratový typ definovaný transformací a podbloky mají taktéž definován výchozí typ.

Mezi základní transformace patří převod na předky (typová dedičnost):

- Generalizace / Specializace - Zde představuje blok u něhož je pevně stanoven atribut či podblok (např. UTF-Řetězec -> Řetězec)
- Parametrické typy - Je také možné použít jako předka (např. Seznam obrázků -> Seznam)

Dalším typem je pak isomorfismus / homomorfismus (ekvivalence). Příkladem může být komprese, šifrování, odkazy, či například převod mezi vyjádřením matematického grafu maticí souslednosti a seznamem sousedů.

Pro potřeby implementace je nutné definovat:

- Získání seznamu bloků na které je možné transformovat - pro daný blok by měl být definován způsob, jak zjistit bloky, na které je možné jej algoritmicky převést a to jak pro případ, kdy je zachována celá informace, tak i když je ji část ztracena.
- Aplikace transformace a předání výsledku - výsledek je možné v některých případech například možné generovat za běhu, někdy může být nutné zkonstruovat kompletní výsledek v paměti
- Řetězení transformací - je možné více transformací provádět po sobě jako posloupnost, určení posloupnosti (použití svazů?)
- Obecná transformace - bude vhodné rozlišit obecné manipulační bloky, které umožňují transformovat libovolná data na jiný tvar od transformace dat z jedné reprezentace na jinou

Relace transformovatelnosti je reflexivní a tranzitivní.

### 1.1. Implicitní transformace

Některé z transformací by měly být upřednostněny jako výchozí.

K běžným transformacím patří:

- Převod starší verze dokumentu na novější a naopak
- Komprimace a dekomprimace
- Šifrování a dešifrování
- Vkládání částí dokumentů z jiných zdrojů (odkazy)
- Bloky s fixovanými atributy
- Speciální případ na případ obecný

Při rozšiřování definice bloku je možné kromě počtu atributů určit transformací i kompatibilního rodiče. Tento princip je vhodné využít především v případě, kdy chceme, aby aplikace byla schopna částečně zpracovat blok i v případě, kdy nezná kompletní definici dokumentu.

### 1.2. Transformační graf

V případě, že jsme schopni provést jednu transformaci, je možné transformace řetězit do posloupnosti a tím rozšířit seznam možných výsledných bloků. Obecně je navíc možné, že k jednomu výsledku povede více možných posloupností (cest v grafu).

Protože prohledávaný graf může být potenciálně velmi rozsáhlý, bude vhodné mezi transformacemi zavést uspořádání. Pak by mělo být možné se omezit na prohledávání svazů a hledaná transformace by pak byla cesta vedená nejbližším uzávěrem (ať už horním, či dolním). Toho by mělo být možné docílit tím, že pro každou transformaci bude uvedeno, zda se jedná o transformaci nahoru či dolů. Problém rozhodnutí směru je netriviální pravděpodobně se bude provádět podle náročnosti transformace a odpovídající složitostní třídy.

### 1.2.1. Transformační rozhraní

Funkční rozhraní umožňuje definovat možné vstupy a vstupy jednotlivých modulů zpracovávajících dokument XBUP. V běžném případě je možné ze vstupního rozhraní získat seznam podporovaných formátů a na výstupním rozhraní přijmout výstup v jednom z definovaných výstupních formátů. Moduly jsou řetězeny spolu s dalšími implicitními transformacemi do transformačního grafu.

### 1.3. Omezující podmínky

Jelikož transformace mohou být obecně definovány pouze pro podmnožinu z možných vstupů než jakou je možné definovat typem bloku, bude vhodné zavést definici omezujících podmínek, které stanoví množinu pravidel, které musí daný blok splňovat navíc k pravidlům stanovených v definici. Tyto podmínky je však možné využít i pro jiné účely než jen transformace, například pro specifikaci variant dokumentů s omezenými hodnotami, či omezenými typy podbloků.

Možné způsoby reprezentace bloků s omezením:

- Samostaný typ bloku pro každou variantu omezení - jednou z možností je, že deklarace bloku s omezením bude reprezentována jako samostatná deklarace. Tento přístup by umožňoval snadné zpracování variant, neboť by si byly obě skupiny deklarací rovny a bylo by tak na ně možno odkazovat jednotným způsobem.
- Zahrnutí omezení do definice typu bloku - blok je definován pomocí vazeb několika typů, které by bylo možné rozšířit o omezující podmínky. I v tomto případě by byl pro každou variantu omezení vytvořen samostatný typ bloku, omezení by však byla definována nad definicí bloku a omezení by tak bylo možné přenášet z komponent na složené typy bloků.
- Samostatná deklarace omezení - další možností je umožnit pro každý typ definovat více variant podle stanovených omezení. Tento přístup má několik výhod i nevýhod. Jelikož struktura bloku je rozlišována pomocí typu bloku, nebylo by možné v dokumentu snadno rozpoznat, jaké má daný blok splňovat omezení a bylo by nutné zpracovat deklaraci.

Prozatím je jako řešení zvolena třetí varianta, protože předchozí dvě varianty by špatně fungovali jako rozšíření stávajícího modelu a zvyšovali by počet typů bloků nesoucích stejnou informaci, lišících se jenom v některých omezeních. Vhodnější bude definovat vždy jediný typ bloku včetně názvu a popisu a teprve k němu dodefinovávat sadu omezení. Bylo by také vhodné nějakým způsobem umožnit použít omezení jiných typů bloků.

Omezení mohou tvořit hierarchii (svaz) a je možné je kombinovat. Toto však bude ponecháno k řešení až na vyšší úroveň protokolu, zahrnujícího definice omezení. Omezení jsou vyjádřeny pomocí jediného indexu, tedy podobně jako typy bloku a pravděpodobně budou moci disponovat stejnou sadou rozšíření (například název, popis).

### 1.3.1. Definice omezujících podmínek

I pro způsob, jakým budou omezující podmínky vyjádřeny, bude vhodné zvážit několik aspektů:

- Omezení hodnoty na konstantní či omezení výčtem
- Omezení velikosti atributové části
- Omezení velikosti datové části
- Omezení počtu, či typu podbloků
- Způsob omezení datového bloku
- Vyloučení či vynucení bloků s nekonečnou délkou (ukončených terminátorem)
- Problém výpočetní složitosti omezení
- Způsob a směr omezení bitových posloupností a hodnot parametrů

V případě omezení hodnot parametrů je možné se například omezit na regulární výrazy, které disponují dostatečnou vyjadřovací silou pro vyjádření jednoduchých podmínek, jako například = < > a různé konečné výčty. Vyjádření podmínek menší než by však v definici vyžadovalo velký počet stavů. Vhodnější bude definice prozatím odložit a ponechat jejich vyjádření na aplikaci.

### 2. Transformační funkce

Pro potřeby transformací je vhodné umožnit definici funkcí. Pro jednoduchost uvažujme funkci jako předpis, který pro prvek vstupní množiny vrací prvek z výstupní množiny. Tedy cílem je vyhnout se například existenci negativních jevů, například vnějších změn mimo funkci. Opět je možné vybrat některou z více možných variant:

- Samostatný typ bloku pro každou funkci - Tato varianta by umožňovala rozšířit konkrétní deklarace bloku na funkce. Výhodou je, že by tyto bloky pak samotnou funkci reprezentovali.
- Definovat seznam funkcí jako součást definice typu - V této variantě by byly funkce přidruženy ke konkrétním typům bloku a odkazovalo by se na ně přes tento typ.

Vybrána byla prozatím první varianta, neboť umožňuje efektivně definovat funkční předpisy. Kromě toho je možné takto určit vstupní parametry funkce jakožto entici, bez nutné vazby na konkrétní typ bloku.

Funkce je definována jako rozšíření definice bloku o seznam výsledků funkce, parametrizovaných chybovým stavem. Výsledkem funkce může být vždy pouze jediný typ, ten je však závislý na chybovém stavu a může být libovolně složený. Kromě toho může mít jak vstup, tak výstup definováno omezení.

### 2.1. Datové transformace

Speciálním případem transformačních bloků je podpora bloků pro manipulace s daty. Tyto bloky umožňují převést datový blok na jiný tvar pomocí volitelného algoritmu a úroveň protokolu podporující tyto manipulace pak poskytuje prostředky pro transparentní práci s takto realizovanými bloky. Tyto transformace nemají definovány buď typ vstupu, či výstupu, což je zaměňováno za právě jeden datový blok.

K dispozici je základní blok pro uvedené transformace. Má tyto hodnoty:

UBPointer - TransformMethod
UBPointer - DataSource

Ukazatel DataSource ukazuje na datový blok, který je zdrojem dat pro transformaci a ukazatel TransformMethod ukazuje na metodu, kterou je pro transformaci použít. Tento blok je možné použít místo datového bloku a transformace je na 2. úrovni implicitně prováděna. Pokud není transformační metoda uvedena, použijí se data přímo.

### 2.1.1. Komprese

Cílem kompresních metod je snížit velikost dat, obvykle pomocí snížení redundance dat, nebo pomocí statistických metod --- (teď si nevzpomenu na termín).

Pozn.: Součástí by měla být později implementace algoritmu v jazyce PROGJAZY

### 2.1.2. Šifrování

Cílem šifrování je zamezit čtení dat bez znalosti přístupového klíče. Má tak umožnit zabezpečený přenos dat, případně ověřování identity a nepopiratelnost doručení, případně další služby.

### 2.2. Extrakční blok

Vyšší formou je extrakce stromové struktury z datového bloku, která má stejné atributy jako transformační blok, ale liší se ve významu:

UBPointer - DataSource
UBPointer - ExtractMethod

Výsledkem extrakce je posloupnost bloků protokolu XBUP, kódována standardním způsobem. Tento blok je tak možné využít k šifrování celých podstromů dokumentu.

### 2.2.1. Přímá extrakce

Pokud je extrakční metoda neuvedena (hodnota 0), je vstupní datový blok přímo interpretován jako posloupnost bloků ve formátu XBUP.

### 2.2.2. Fragmentační blok

Další z možných využití je konstruovat datový blok tak, že data z tohoto datového bloku jsou před přímou extrakcí spojovány pomocí schématu. To umožňuje, aby byl datový blok fragmentován na menší části a menší změna dokumentu nutně neznamenala nutnost přepsání celého obsahu dokumentu. Vhodná se jeví například varianta se vstupním datovým blokem z rozšířené oblasti dokumentu.

### 2.3. Kontrolní bloky

Tyto bloky umějí naopak zpřístupnit datový obsah části podstromu a převést jej na virtuální datový blok pomocí volitelného algoritmu. To lze například využít pro kontrolu platnosti bloků.

UBPointer - DataSource
UBPointer - ExtractMethod

### 2.3.1. Kontrola mladších sourozenců

Pozn.: Bylo by asi vhodné, aby bylo možné zkontrolovat i platnost celého dokumentu, ovšem bez platnosti samotného kontrolního bloku. To by bylo možné ověřit například pomocí postupu, kdy by datový vstup pro kontrolní blok byl vytvořen z datového obsahu bloků, které jsou jeho mladšími sourozenci.

### 2.4. Převodní bloky

Poslední z variant manipulačních blok je blok určený pro převod blokové struktury do jiného tvaru.

UBPointer - DataSource
UBPointer - ExtractMethod

### 2.4.1. Odkazovací bloky

Dále jsou definovány základní základní bloky, jejich plná podpora je doporučená pro všechny aplikace, které uvádějí, že podporují protokol XBUP úrovně 1 a vyšší. Tyto bloky umožňují základní rozšiřování typů bloků a několik dalších funkcí.

### 2.4.1.1. Odkaz (6)

Odkaz umožňuje adresovat jiný blok ze stejného datového proudu. Jednotlivé bloky jsou číslovány ve standardním pořadí (dle pořadí, ve kterém jsou uvedeny) a to tak, že hodnota 0 odkazuje na datovou část bloku samotného a vyšší indexy pak na jednotlivé podřízené bloky. V dalších rozšířených variantách lze případně adresovat jakoukoli datovou strukturu, libovolný blok ve stejném nebo jiném souboru ať již v místní složce, nebo kdekoli jinde v lokální sítí nebo internetu. (Obdoba URL) V základní verzi je způsob získání bloku plně ponechán na aplikaci, a tedy to, zda bude blok stáhnut z Internetu, nebo bude použita jeho verze uložená v místní vyrovnávací paměti by nemělo být podstatné. Pro adresaci položky v rámci souboru jsou hodnoty následující:

UBPath - LinkPath
UBNatural - UpCount
UBPointer - LinkRoot

Tyto hodnoty jednoznačným způsobem určují cestu k bloku. Pro LinkRoot = 0 se jedná o vnitřní odkaz v datovém proudu. Hodnota UpCount = 0 odpovídá odkazu na nadřazený blok. Pokud hodnota UpCount přesáhne hloubku kořenové hloubky souboru, nebo pokud kterákoliv z hodnot PathPointer přesáhne počet bloků na dané úrovni, je celý odkaz považován za neplatný. Nutno ještě zmínit případ, kdy odkaz odkazuje na jiný odkaz, což není obecně zakázáno. V takovém případě je nutné ověřovat posloupnost odkazů na zacyklení. Obecně není omezena ani délka takové cesty.

Pro nenulové hodnoty se jedná o ukazatel na interpretaci kořene odkazu. Pokud ukazuje na jiný blok typu odkaz, pak odkazy typu 0 následuje a odkazy jiného typu považuje za kořen své cesty.

V případě, že nerozpozná typ odkazovaného bloku, je celý odkaz neplatný s chybou UnknownLinkRoot.

Pozn. Je vhodné odlišit odkaz na jeden blok/celý podstrom?

### 2.4.1.2. Kořen internetového katalogu (7)

Uvedením tohoto bloku jako cílového určujete, že odkazované definice bloku jsou dostupné pomocí internetového katalogu.

### 2.5. Analyzovatelnost dokumentu

Dokument lze označit jako analyzovatelný, pokud má aplikace k dispozici všechny prostředky nutné pro úplné čtení dokumentu do úrovně 0. V případě komprese se tak jedná o dostupné kompresní algoritmy, podobně v případě šifrování o znalost požadovaného tajemství.

Pozn.:
- definovat typ položek včetně např. UBPointer na další úrovni + relevantní typy odkazovaných podbloků
- "systémové bloky" přejmenovat na něco rozumějšího
- argumentace pro pořadí systémových bloků
- argumentace pro pořadí atributů

Homepage: http://xbup.sf.net
License: GNU Free Documentation License (FDL)
Latest update: 2010-01-09