Accelerating XPath location steps

České vysoké učení technické v Praze Fakulta elektrotechnická

Accelerating XPath location steps Semestrální práce (36SEM)

Autor: Lukáš Skřivánek Email: [email protected] 2006/2007

36SEM

Accelerating XPath location steps

Lukáš Skřivánek

Obsah Zadání..................................................................................................................................2 Úvod.....................................................................................................................................3 Použité standardy.................................................................................................................5 XML..................................................................................................................................5 Syntaxe........................................................................................................................5 XPath...............................................................................................................................8 Syntaxe........................................................................................................................9 Zkratky.......................................................................................................................11 Příklady......................................................................................................................11 Implementace.....................................................................................................................13 Teoretická část...............................................................................................................13 Optimalizace..................................................................................................................16 Sjednocení pre a post pořadí.....................................................................................16 Omezení nekonečných intervalů................................................................................17 Přístup k listovým uzlům............................................................................................17 Praktická část.................................................................................................................18 Uživatelský manuál............................................................................................................20 Textové UI......................................................................................................................20 Grafické UI.....................................................................................................................21 Měření náročnosti a výkonnosti..........................................................................................22 Závěr..................................................................................................................................24 Zdroje.................................................................................................................................25

-1-

36SEM


Lukáš Skřivánek

Zadání Prostudujte a implementujte indexační algoritmus pro urychlení provádění XPath výrazů podle dokumentu “Accelerating XPath Location Steps” - autor Torsten Grust.

-2-

36SEM


Lukáš Skřivánek

Úvod Základním úkolem počítače je práce s daty, ať již jde o jejich uchovávání, transformaci, výpočty, přesuny v různorodých systémech nebo považování těchto dat za instrukce a jejich provádění. Vždy je nutné vědět v jakém formátu jsou tato data uložena jinak není možné je zpracovávat. Znalost formátu dat a formát dat samotný zásadně ovlivňuje použitelnost dat. Pokud si každý programátor vymyslí pro svůj program vlastní formát dat, jehož popis není nikde k dispozici, může to mít za výhodu pouze optimalizaci využívající specifik zpracovávaných dat z hlediska úspory paměťového místa a efektivnost práce s daty. Nevýhod je však celá řada. Takto uložená data jsou pro veškeré ostatní programy nečitelná, což vylučuje spolupráci jako např. další výpočty, indexace, jednoduché editace, vyhledávání pomocí dalších programů. Pokud další verze tohoto programu přestane starší formát podporovat, je třeba data složitě převádět nebo jsou navždy ztracena. Nástroje pro manipulaci s daty ve vlastním formátu si musí napsat každý vývojář sám. Naproti tomu pokud použijeme formát již vymyšlený s veřejnou specifikací můžeme využít nástroje již vytvořené, odpadá problém se spoluprací s ostatními programy a uživatel není odkázaný pouze na naši podporu formátu. Formát dat může být v zásadě dvojího druhu: textový nebo binární. Binární může šetřit paměťové místo a lze ho přímo číst a provádět, není třeba ho složitě načítat – parsovat. Je výhodný obzvláště pro uchování spustitelných souborů, multimediálních dat (obraz a zvuk) a komprimovaných souborů. Textový formát je velmi jednoduchý, snadno čitelný obyčejným textovým editorem a na platformě nezávislý. Aby v tomto formátu bylo možné ukládat obecná data, musí umožňovat strukturování dat, vyjádření vztahů mezi daty a vyznačení významu jednotlivých částí textu. To se provádí pomocí tzv. značek a proto se takovým jazykům říká značkovací jazyky (markup language). Asi prvním známým značkovacím jazykem vytvořeným pro IBM byl GML (Generalized Markup Language), kde se autoři Charles Goldfarb, Edward Mosher a Raymond Lorie museli vypořádat s nekompatibilitou jednotlivých systémů a programů. Princip GML se osvědčil a byl předchůdcem vzniku jazyka, který umožňoval definici vlastních značkovacích jazyků – uživatel si dle potřeb mohl vytvořit vlastní sadu značek vhodnou pro daný druh dokumentů. Tím jazykem je SGML (Standard Generalized Markup Language), který je definován v ISO normě 8879 z roku 1986. Jazyk SGML je velmi obecný metajazyk umožňující definici vlastních značkovacích jazyků pomocí DTD (Document Type Definition). DTD určuje strukturu dokumentu (jak se mohou jednotlivé značky používat např. která značka může obsahovat kterou). SGML má spoustu volitelných parametrů – počínaje maximální délkou názvů značek a konče určením znaků použitelných jako oddělovače značek od textu. Tato komplexnost standardu SGML poněkud zbrzdila jeho praktické využívání. Asi nejznámější aplikací SGML je jazyk HTML (Hypertext Markup Language), který se používá pro tvorbu webových stránek. To jaké značky můžeme na stránkách používat určuje příslušné DTD, které je pro každou verzi HTML trošku jiné. -3-

36SEM


Lukáš Skřivánek

Jazyk HTML si získal velkou oblibu díky své jednoduchosti, brzy se však ukázalo, že pevně daná skupina značek, které HTML používá, nestačí. Pro účely vyhledávání a vůbec efektivnější výměny dat by bylo lepší mít možnost používání vlastních značek, které by přesně vymezily význam textu. Požadavek by tedy mohl bez problémů splnit jazyk SGML. Komplexnost standardu SGML však dělá jeho úplnou implementaci velice náročnou. Přitom se během deseti let používání SGML ukázalo, že se v praxi používá jen část jeho možností. Tato nejdůležitější podmnožina SGML proto byla vybrána jako nový jazyk XML (eXtensible Markup Language). XML si zachovává možnost definování značek pomocí DTD pro jednotlivé skupiny dokumentů. Na rozdíl od SGML je mnoho parametrů předem určeno a nelze je měnit – délka názvů značek, použité oddělovače, speciální znaky atd. Navíc je syntaxe zápisu dokumentů v XML oproti SGML poměrně přísná, což umožní mnohem snazší a levnější vývoj aplikací, které umožňují s XML pracovat. XML tedy pochází z oblasti, která se zaměřuje na uchovávání a zpracování textových dokumentů. Pro tyto účely se XML výborně hodí, není to však jediné uplatnění. Existují standardní DTD pro uchování různých dat např. SVG (Scalable Vector Graphics) – formát pro dvourozměrnou vektorovou grafiku nebo MathML (Mathematical Markup Language) - jazyk určený pro zápis matematických výrazů. Kromě přesného vzhledu výrazu dokáže zachytit i jeho přesný význam. Nic nám však nebraní vytvoření vlastního DTD a uložení jakýkoliv dat např. faktur, evidence aut, zadání hry sudoku atd. XML ovšem také není vše spasitelné a nehodí se pro některé druhy dat (např. zvuk, video) zvláště kvůli nešetrnosti k paměťovému místu a náročnosti načítání. Dovede však jiné formáty do sebe vložit nebo na ně odkazovat. Jsou tedy data, se kterými je výhodné pracovat přímo v XML, data se kterými je výhodné pracovat v jiném formátu a umožňovat export do XML a konečně data pro která se XML nehodí. Velkou výhodou XML je široká podpora v běžných programovacích jazycích (Java, PHP, C++, C#, ...), ale také v nových standardech. Postupem času se z XML stala celá rodina XML standardů, které usnadňují další práci s daty a jsou vzájemně provázané. Pro dotazování nad XML jsou to XPath a XQuery, pro prezentaci dat CSS nebo XSL, pro transformace XSLT. Samotné XSLT pro výběr částí dokumentu využívá dotazovacího jazyka XPath. Tato práce je právě o jazyku XPath a jeho implementaci urychlující vyhledání částí dokumentu. Jde o indexaci dokumentu XML do relační databáze a následné dotazování nad databází.

-4-

36SEM


Lukáš Skřivánek

Použité standardy XML XML (eXtensible Markup Language) je obecný značkovací jazyk, který byl vyvinut a standardizován konsorciem W3C. Umožňuje snadné vytváření konkrétních značkovacích jazyků pro různé účely a široké spektrum různých typů dat. Jde o textový formát s implicitní 32-bitovou znakovou sadou ISO 10646, která dokáže pojmout všechny dnes používané znaky všech jazyků. Můžeme vytvářet dokumenty, které obsahují texty v mnoha jazycích najednou. XML dokument může být v libovolném kódování (např. windows-1250, ISO-8859-2), implicitně je to UTF-8. V každém dokumentu však musí být přesně určeno, v jakém kódování byl vytvořen, čímž odpadají problémy s konverzí z jednoho kódování do druhého. Každému je hned jasné, v jakém kódování dokument je. Specifikace XML konsorcia W3C je zdarma přístupná všem. Každý tak může bez problémů do svých aplikací implementovat podporu XML. Jazyk je určen především pro výměnu dat mezi aplikacemi a pro publikování dokumentů. Umožňuje popsat strukturu dokumentu z hlediska věcného obsahu jednotlivých částí, nezabývá se sám o sobě vzhledem dokumentu nebo jeho částí. Prezentace dokumentu (vzhled) se potom definuje připojeným stylem. Další možností je pomocí různých stylů provést transformaci do jiného typu dokumentu, nebo do jiné struktury XML. Pomocí XML značek (tagů) vyznačujeme v dokumentu význam jednotlivých částí textu. Dokumenty tak obsahují více informací, než kdyby se používalo značkovaní zaměřené na prezentaci (vzhled) – definice písma, odsazení a podobně. XML dokumenty jsou tedy informačně bohatší. To lze samozřejmě s výhodou využít v mnoha oblastech. Největší přínos bude samozřejmě pro prohledávání, kdy můžeme určit i jaký význam má mít hledaný text.

Syntaxe XML soubor může obsahovat ●

obyčejný text,

●

počáteční značky (počáteční tag např. ),

●

ukončovací značky (ukončovací tag např. ),

●

atributy uvnitř počátečních tagů ( např. ),

-5-

36SEM


Lukáš Skřivánek

●

komentáře (text umístěný mezi např. ),

●

instrukce pro zpracování ( např. ),

●

deklaraci XML souboru (např. ),

●

definici typu dokumentu nebo odkaz na definici typu dokumentu ( nebo ),

●

sekce CDATA ( např. Ahoj
]]>),

●

reference na entity (&název_entity; např. <),

●

reference na znaky (&#desítkové_číslo_znaku; nebo &#xšestnáctkové_číslo_znaku; např. ñ nebo ñ).

Segment XML dokumentu s počáteční a odpovídající ukončovací značkou se nazývá element. Pozor na velikost písmen: a nejsou odpovídající značky. Část dokumentu mezi těmito značkami je obsah elementu, ve kterém mohou být další elementy, text, komentáře, instrukce pro zpracování, sekce CDATA i reference. Element může být také prázdný tj. nemá žádný obsah kromě atributů (např. nebo také ). Atributy smí být zapsány pouze v počátečních značkách a slouží většinou k upřesnění obsahu elementu. Hodnotu atributu musíme vždy uzavřít do apostrofů nebo uvozovek. U jedné značky je možné použít více atributů najednou, stačí je oddělit mezerou. Komentáře slouží pro autory XML dokumentů pokud potřebují něco vysvětlit, něco si poznamenat nebo skrýt část dokumentu. Komentář je součást dokumentu, ale je ignorován. Může obsahovat cokoliv kromě posloupnosti znaků “--”. Při čtení XML dokumentu pokud parser (program určený na čtení XML dokumentu) narazí na instrukci pro zpracování, pak podle identifikátoru zjistí pro jaký program jsou určeny data v instrukci pro zpracování, předá je tomuto programu, ale sám je ignoruje. Tento mechanismus slouží k vložení nestandardních informací do XML dokumentu a umožňuje umístit do jednoho dokumentu instrukce pro několik různých programů. Data mohou obsahovat libovolnou sekvenci znaků vyjma sekvence “?>”. Deklarace XML souboru by měla být na začátku dokumentu a musí obsahovat verzi XML dokumentu z důvodu zpětné kompatibility v případě vzniku dalších verzí XML. Dále může obsahovat deklaraci kódování, ve kterém je XML dokument vytvořen, pokud deklarace chybí je kódování považováno za UTF-8.

-6-

36SEM


Lukáš Skřivánek

Definice typu dokumentu nebo odkaz na definici typu dokumentu se v dokumentu objeví hned za deklarací XML souboru, čímž určujeme typ XML dokumentu a omezení, jaké elementy se mohou v dokumentu použít, jaké mají atributy, v jakých jsou vztazích a další omezení. XML označuje text dokumentu jako PCDATA (parsed character data). Pokud parser narazí na značku je považována za začátek nebo konec elementu. Sekce CDATA znamená znaková data (character data), tedy data, kde výskyt značky není považován za začátek nebo konec elementu a text je považován za text prostý, bez značek a jiných prvků. Toho lze s výhodou využít pokud potřebujeme do textu vložit větší kus textu, kde se hojně používají znaky se speciálním významem jako '<', '>' a '&', a je nepohodlné je zapisovat pomocí znakových entit. Sekce CDATA oceníme zejména v případech, kdy je součástí XML dokumentu kód nějakého programu. Vzhledem k tomu, že některé znaky mají zvláštní význam (znaky '<' a '>' se používají k oddělení značek od textu, znak '&' znamená začátek reference a apostrof nebo uvozovky oddělují hodnotu atributu) nelze tyto znaky napsat do dokumentu jen tak. Pro zápis těchto znaků se používají takzvané pojmenované entity (pro '<' - < pro '>' > pro '&' - & pro apostrof - ' pro uvozovky - "). Vlastní entity je možné definovat v DTD. Pokud píšeme XML dokument a nevíme jak nějaký znak napsat nebo naše kódování tento znak neobsahuje, můžeme využít reference na znak (znakové entity). Tvar reference na znak je &#desítkové_číslo_znaku; nebo &#xšestnáctkové_číslo_znaku;, kde číslo znaku určuje kód znaku ze znakové sady ISO 10646. Aby byl dokument považován za správně strukturovaný (well-formed) musí splňovat podmínky uvedené výše a navíc musí mít následující vlastnosti: ●

Musí mít právě jeden kořenový (root) element (to znamená, že všechny elementy musí být obaleny právě jedním, kořenovým elementem).

●

Všechny neprázdné elementy musí být ohraničeny počáteční a ukončovací značkou (pro každý počáteční tag musí dokument obsahovat odpovídající ukončovací tag a opačně). Prázdné elementy mohou být označeny zkrácenou značkou.

●

Všechny hodnoty atributů musí být uzavřeny v uvozovkách nebo apostrofech.

●

Elementy mohou být vnořeny, ale nemohou se překrývat; to znamená, že každý (ne kořenový) element musí být celý obsažen v jiném elementu (nelze dělat ).

Pokud je XML dokument správně strukturovaný (well-formed) a zároveň splňuje podmínky daného DTD je tzv. validní (valid).

-7-

36SEM


Lukáš Skřivánek

Příklad Škoda Favorit bílá 15 000 1990 Ford Escort modrá 12 000 1987 XML má stromovou strukturu

Obr. 1: XML dokument – stromová struktura

XPath XPath (XML Path Language) je dotazovací jazyk nad XML pocházející od konsorcia W3C umožňující adresovat část XML dokumentu. Lze jím popsat cestu k elementům, atributům, textům, komentářům a instrukcím pro zpracování, které tvoří uzly XML dokumentu. Nelze popsat cestu k referencím nebo CDATA sekcím, protože ty jsou nahrazeny už parserem. Výrazu může odpovídat buď právě jeden uzel, pak lze výraz chápat jako adresu v rámci dokumentu, nebo více uzlů, pak lze výraz chápat jako vyhledávání v dokumentu. Dotazovací jazyk XPath je naproti např. jazyku SQL, který pracuje s tabulkami, navržen pro práci s datovou strukturou stromu, což odpovídá datové struktuře XML. XPath se nejčastěji používá v XSLT pro výběr množiny zpracovávaných uzlů a v XPointer pro označení adresy uvnitř dokumentu. -8-

36SEM


Lukáš Skřivánek

Syntaxe Výraz v jazyce XPath je posloupnost přechodů (mezi jednotlivými sadami uzlů), oddělených lomítky a tvoří cestu mezi uzly. Odtud získal i své jméno XML Path Language (path - cesta). Každý přechod je určen pomocí tří složek ●

osy (axis),

●

testu uzlu (node test),

●

predikátu (predicate),

ve tvaru osa::testUzlu[predikát]. Specifikace osy popisuje směr pohybu po stromové reprezentaci XML dokumentu. Osa může nabývat hodnot ancestor (předci), ancestor-or-self (předci nebo aktuální uzel), attribute (atributy), child (děti), descendant (potomci), descendant-or-self (potomci nebo aktuální uzel), following (následníci), following-sibling (následníci sourozenci), namespace (prostor jmen), parent (rodič), preceding (předchůdci), preceding-sibling (předchůdci sourozenci), self (aktuální uzel). Pokud není osa uvedena, použije se implicitní hodnota child (děti). Podle osy lze poznat typ uzlů, se kterými se bude pracovat. U osy attribute jsou to atributy, pro namespace je to namespace a pro ostatní jsou to elementy.

Obr. 2: Osy jazyka XPath

-9-

36SEM


Lukáš Skřivánek

Test uzlu se provádí na uzlech určených osou a je pravdivý tehdy pokud odpovídá typ a název uzlu. Například descendant::auto vybere všechny elementy s názvem auto, které jsou potomkem aktuálního uzlu. Pokud aktuální uzel nemá potomky s názvem auto je výsledkem prázdná množina uzlů. attribute::měna vybere všechny atributy měna aktuálního uzlu. Pokud takové atributy nemá, výsledkem je opět prázdná množina uzlů. Pokud za test uzlu uvedeme * jsou vybrány všechny uzly daného typu. Například child::* vybere všechny elementy, které jsou dětmi aktuálního uzlu. Test uzlu text() je pravdivý pro všechny textové uzly. Například descendant::text() vybere všechny textové uzly, které jsou potomky aktuálního uzlu. Obdobně test uzlu comment() je pravdivý pro všechny uzly typu komentář a test uzlu processing-instruction() je splněný pro všechny uzly instrukcí pro zpracování. Test uzlu node() je pravdivý pro všechny uzly všech typů. Z celého XML dokumentu jsme nejprve pomocí specifikace osy vybrali uzly odpovídající směru osy vzhledem k aktuálnímu uzlu, dále jsme tyto uzly zredukovali na uzly vyhovující testu uzlu podle jména a typu a jako poslední filtr máme k dispozici predikáty. Predikáty nejsou povinné, může jich být v každém kroku nula, jeden nebo více. Pokud jich je více, jsou vyhodnocovány postupně zleva doprava. Predikát je pravdivostní výraz, který se vyhodnocuje pro každý uzel, který zatím vyhovuje cestě. Pokud je pro daný uzel splněný, zůstává tento uzel ve vybrané množině uzlů, pokud ne, je uzel z množiny vyřazen. Predikáty tedy snižují počet vyhovujících uzlů. Predikát kromě standardních výrazů (porovnání, aritmetické operace …) může obsahovat i volání funkcí. Existuje sada funkcí, kterou by měla každá implementace jazyka XPath umět, jde o funkce pro práci s pořadím uzlů (např. poslední uzel), s textem (např. zřetězení), s logickými výrazy (např. negace) a s čísly (např. suma nebo zaokrouhlení). Jazyk XPath pracuje nad stromovou strukturou dokumentu XML, která má ale umělý kořenový uzel '/', který neodpovídá žádnému elementu ani atributu v dokumentu, jeho dítětem je vždy kořenový element dokumentu a případně další uzly (komentáře, instrukce pro zpracování). Cesta jazyka XPath může být dvou druhů: absolutní nebo relativní. Absolutní začíná znakem '/' a vychází vždy z kořenového uzlu, relativní nezačíná znakem '/' a počáteční aktuální uzel může být určen mimo XPath, například v XSLT je to právě zpracovávaný uzel dokumentu. Dotaz v jazyce XPath tedy není ve formátu XML i když patří do rodiny standardů XML. Mohlo by se to zdát zvláštní, protože stejné dotazy by bylo možné zapsat i ve formátu XML. Syntaxe jazyka XPath však byla tvořena s ohledem na využití uvnitř URI (Uniform Resource Identifier - jedinečná identifikace zdroje) a v atributech elementů XML dokumentů. Výsledná množina uzlů XPath dotazu je vždy uspořádána ve stejném pořadí jako se vyskytuje v dokumentu a obsahuje každý uzel maximálně jednou.

- 10 -

36SEM


Lukáš Skřivánek

Zkratky K nejčastěji používaným konstrukcím jazyka XPath existují zkratky pro zkrácení a hlavně zpřehlednění zápisu: ●

Jak již bylo řečeno implicitní hodnota osy je child::, proto child::auto = auto.

●

Pokud chceme pohyb po ose atributů můžeme místo attribute:: použít zavináč ('@'), proto attribute::id = @id.

●

Pro prohledávání do libovolné hloubky včetně aktuálního uzlu můžeme místo /descendant-or-self::node()/ použít dvě lomítka ('//'), proto /descendant-or-self::node()/auto = //auto.

●

Na aktuální uzel se lze odkazovat místo self::node() pomocí tečky ('.'), ale při použití tečky nemůžeme použít predikát, například .//para je stejné jako self::node()/descendant-or-self::node()/child::para.

●

Na rodičovský uzel se lze odkazovat parent::node(), zkratka pro to jsou dvě tečky ('..'), při použití dvou teček opět nemůžeme použít predikát

Příklady ●

auto (= child::auto) – vybere všechny elementy auto, které jsou dětmi aktuálního uzlu

●

* (= child::*) – vybere všechny elementy, které jsou dětmi aktuálního uzlu

●

/* (= /child::*) – vybere kořenový element

●

auto/* (= child::auto/child::*) – vybere všechny elementy, které jsou dětmi elementu auto, který je dítětem aktuálního uzlu

●

text() (= child::text()) – vybere všechny textové uzly, které jsou dětmi aktuálního uzlu

●

@měna (= attribute::měna) – vybere všechny atributy měna aktuálního uzlu

●

auto/@id (= child::auto/attribute::id) – vybere atribut id elementu auto, které je dítětem aktuálního uzlu

●

para[1] (= child::para[position()=1]) – vybere první element para, který je dítětem aktuálního uzlu

●

para[last()] (= child::para[position()=last()]) – vybere poslední element para, který je dítětem aktuálního uzlu

- 11 -

36SEM


Lukáš Skřivánek

●

/dokument/kapitola[5]/část[2] (= /child::dokument/child::kapitola[position()=5]/child::část[ position()=2]) – vybere druhou část páté kapitoly uvnitř elementu dokument

●

//cena (= /descendant-or-self::node()/child::cena) – vybere všechny elementy cena, které jsou potomky kořenového uzlu. To v praxi znamená, že jsou vybrány všechny elementy cena, které se nacházejí ve stejném dokumentu jako aktuální uzel.

- 12 -

36SEM


Lukáš Skřivánek

Implementace Teoretická část Běžné implementace jazyka XPath nejprve pomocí parseru přečtou celý XML dokument a vytvoří si v paměti stromovou reprezentaci. Dále zpracují do vnitřní formy zadaný XPath dotaz a začnou ho postupně vykonávat nad stromovou reprezentací XML dokumentu. Takto je XPath implementován snad pro všechny běžné programovací jazyky (Java, C++, PHP, C# ...). Toto řešení má však několik nevýhod. Asi nejpalčivějším problémem je náročnost na operační paměť. Způsobuje ji uchování celého stromu XML dokumentu, který v paměti zabírá několikanásobně více místa než samotný dokument, což je způsobeno uložením řady pomocných informací. V případě větších XML dokumentů (řádově desítky, stovky, tisíce MB) a nedostatku operační paměti začne docházet k přesunům dat mezi operační pamětí a pevným diskem (tzv. swapování), což způsobí pomalejší načítání XML dokumentu i pomalejší vykonávání XPath dotazů. Jako alternativní řešení nabízí Torsten Grust ve své práci “Accelerating XPath Location Steps” načtení a uložení XML dokumentu do relační databáze a provádění XPath dotazů nad databází. Základní otázkou je, jak do tabulky uložit stromovou strukturu. Dále budeme potřebovat efektivně provádět nad touto tabulkou XPath dotazy pracující s původní stromovou reprezentací XML dokumentu. Jak již bylo řečeno, každý krok XPath dotazu se skládá ze tří částí: osy, testu uzlu a predikátu. Specifikace osy a test uzlu jsou v každém kroku povinné (pokud není uvedena osa je použita osa child::), predikát povinný není, může jich být nula, jeden a více. Predikáty v této práci zanedbáváme a zaměřujeme se pouze na osu a test uzlu tedy na pohyb ve stromové struktuře a test názvu a typu uzlu a tím na adresování (vyhledávání) částí dokumentů (hlavní účel jazyka XPath). Pro uložení stromové struktury do tabulky přiřadíme každému uzlu preorder a postorder pořadí (označíme je pre a post). Průchod preorder vždy nejprve přiřadí číslo aktuálnímu uzlu, poté přejde na levý podstrom a nakonec na pravý podstrom. Průchod postorder nejprve přejde na levý podstrom aktuálního uzlu, následně na pravý podstrom a až nakonec přiřadí číslo aktuálnímu uzlu. Je dobré si uvědomit, že preorder průchod přiřazuje elementům pořadí ve chvíli počáteční značky zatímco postoder ve chvíli ukončovací značky, pokud by procházel XML dokumentem v textové podobě. Z toho vyplývá, že všechny elementy uvnitř nadřazeného elementu mají vyšší hodnotu preorder pořadí a nižší hodnotu postorder pořadí než nadřazený element (mají počáteční značku v dokumentu později a ukončovací dříve). Takto tedy lze určit elementy ve směru osy descendant (potomci). Analogicky elementy ve směru ancestor (předci) mají nižší hodnotu preorder pořadí (počáteční značku mají v pořadí XML dokumentu dříve) a zároveň vyšší hodnotu postorder pořadí

- 13 -

36SEM


Lukáš Skřivánek

(ukončovací značku mají později). U os descendant-or-self (potomci nebo aktuální uzel) a ancestor-or-self (předci nebo aktuální uzel) stačí zaměnit vetší za větší nebo rovno a menší za menší nebo rovno.

Obr. 3: Přiřazení preorder a postorder pořadí

Elementy ve směru osy preceding (předchůdci) mají nižší hodnotu preorder i postorder pořadí naproti tomu ve směru following (následníci) mají obě hodnoty vyšší. Pro určení os parent (rodič) a child (děti) budeme u každého uzlu evidovat hodnotu preorder pořadí rodiče a označíme ji par (parent). Rodičovský uzel je pak vždy uzel s hodnotou preorder rovnou hodnotě par aktuálního uzlu. Děti jsou potom všechny uzly s par hodnotou rovnou hodnotě pre aktuálního uzlu. Osy following-sibling (následníci sourozenci) a preceding-sibling (předchůdci sourozenci) jsou jako following (následníci) a preceding (předchůdci) jen navíc par hodnota uzlů musí být rovna par hodnotě aktuálního uzlu. Konečně osa attribute (atributy) jsou uzly, které mají hodnotu par rovnou hodnotě pre aktuálního uzlu (aktuální uzel je rodič) a typ uzlu mají atribut. Pro uložení každého uzlu potřebujeme tedy šestici pre (preorder pořadí), post (postorder pořadí), par (pre hodnota rodiče), kind (druh uzlu – kořenový uzel, element, atribut, textový uzel, komentář, instrukce pro zpracování), name (název – název elementu nebo atributu) a cdata (character data – znaková data – hodnota textového uzlu, atributu, komentáře nebo instrukce pro zpracování). Buď lze tuto šestici jednoduše uložit jako jednu tabulku nebo výhodnější řešení je uložit do tabulky pětici pre, post, par, kind a name v relaci s tabulkou obsahující pre a cdata. Primárním klíčem je u obou tabulek hodnota pre, v druhé tabulce je pre zároveň cizím klíčem relace.

- 14 -

36SEM


Lukáš Skřivánek

Obr. 4: Určení základních os jazyka XPath

Tabulka 1: Určení os jazyka XPath osa jazyka Xpath pre post child (pre(u), ∞) (0, post(u)) descendant (pre(u), ∞) (0, post(u)) descendant-or-self <pre(u), ∞) (0, post(u)> parent par(u) * ancestor (0, pre(u)) (post(u), ∞) ancestor-or-self (0, pre(u)> <post(u), ∞) following (pre(u), ∞) (post(u), ∞) preceding (0, pre(u)) (0, post(u)) following-sibling (pre(u), ∞) (post(u), ∞) preceding-sibling (0, pre(u)) (0, post(u)) self pre(u) * attribute (pre(u), ∞) (0, post(u))

par pre(u) * * * * * * * par(u) par(u) * pre(u)

kind element element element element element element element element element element element atribut

name * * * * * * * * * * * *

Načtení XML dokumentu se standardně provádí pomocí rozhraní DOM (Document Object Model) nebo SAX (Simple API for XML). DOM je objektově orientované rozhraní, které vrací stromovou strukturu korespondující s XML dokumentem a navíc poskytuje metody pro čtení a modifikace stromu. Pro naše využití je však DOM zbytečně časově (vytváří celý strom) i paměťově (celý dokument je v paměti) náročný.

- 15 -

36SEM


Lukáš Skřivánek

Rozhraní SAX převádí XML dokument na proud událostí ●

počátek dokumentu,

●

konec dokumentu,

●

počáteční značka,

●

ukončovací značka,

●

znaková data,

●

komentář,

●

instrukce pro zpracování.

Každá událost vyvolá korespondující obsluhující metodu a předá ji načtené hodnoty. Při použití rozhraní SAX budeme potřebovat paměť úměrnou pouze výšce stromu odpovídajícího XML dokumentu, ne velikosti XML dokumentu. U počáteční značky vždy přiřadíme pre hodnotu a název a uložíme je do zásobníku (velikost maximálně výška stromu XML dokumentu) a při ukončovací značky vyjmeme ze zásobníku a doplníme zbývající hodnoty. Při vykonávání XPath dotazu musíme vybrat správnou množinu řádek, reprezentující uzly XML dokumentu. XPath výraz převedeme na SQL dotaz zřetězením podmínek jednotlivých kroků XPath dotazu. Například dotaz /descendant::n1/precedingsibling::n2 převedeme na: SELECT DISTINCT x2.* FROM Xpath x0, Xpath x1, Xpath x2 WHERE x0.pre=0 AND x1.pre>x0.pre AND x1.post<x0.post AND x1.kind=1 AND x1.name='n1' AND x2.pre<x1.pre AND x2.post<x1.post AND x2.par=x1.par AND x2.kind=1 AND x2.name='n2' ORDER BY x2.pre; Kde x0 reprezentuje kontext, v našem případě kořenový uzel '/', x1 reprezentuje descendant::n1 a x2 reprezentuje preceding-sibling::n2. Pro tento typ dotazu (intervalový) jsou výhodné indexy pomocí R-stromu nebo Bstromu.

Optimalizace Následující postupy nejsou nutné pro správnou funkci XPath dotazování, slouží pro snížení počtu testovaných uzlů a tím zrychlení vykonávání dotazů.

Sjednocení pre a post pořadí Pokud přiřazujeme pořadí pre a post nezávisle na sobě pak při výběru uzlů na základě pravidla o pre pořadí vybereme i řadu uzlů, které vyfiltrujeme později na základě pravidla o post pořadí a obráceně. Nás však nezajímají absolutní hodnoty pre a post pořadí, - 16 -

36SEM


Lukáš Skřivánek

zajímají nás jejich vzájemné vztahy (větší než, menší než). Je proto možné a výhodné přiřazovat pre i post pořadí z jedné číselné řady. Všechny uvedené vztahy zůstávají platné, protože pořadí zůstává stejné a pre i post jsou stále unikátní.

Obr. 5: Sjednocení pre a post pořadí

Omezení nekonečných intervalů Pro osy child, descendant, descendant-or-self a attribute jsme schopni určit nejen dolní hranici pre pořadí, ale i horní hranici a pro post nejen horní hranici, ale i dolní. Tím se nám zmenší počet prohledávaných uzlů a zrychlí vykonávání dotazů. Při použití sjednocení pre a post pořadí (jedna číselná řada) je horní hranicí pre pořadí potomka uzlu v post pořadí uzlu v a pro post je dolní hranicí pre pořadí uzlu v. Lze tedy použít window (descendat, v) = {(pre(v), post(v)), *, *, element, *} nebo window (descendat, v) = {*, (pre(v), post(v)), *, element, *} Jak již bylo řečeno obdobně pro child, descendant-or-self a attribute.

Přístup k listovým uzlům Pro některé kroky XPath dotazu je předem zřejmé, že výstupem budou listové uzly. Například jde o všechny dotazy po ose atributů, kroky s testem uzlu text(), comment() nebo processing-instruction(). Všechny listové uzly při sjednocení pre a post pořadí (jedna číselná řada) splňují post(v) = pre (v) + 1

- 17 -

36SEM


Lukáš Skřivánek

Praktická část Implementace byla provedena v programovacím jazyku Java 1.5.0 s připojením do MySQL 5.0 databáze. Blokové schéma celé implementace by mohlo být:

Obr. 6: Blokové schéma implementace jazyka XPath

Vstupem je XML soubor, který se pomocí SAXu celý naindexuje do databáze. Toto obstarává objekt SAXHandler, který je vytvořen v jádru XPathu. SAXHandler obsahuje metody, které reagují na jednotlivé události průchodu XML souborem. Na začátku si vytvoří pomocný zásobník, do kterého při průchodu počáteční značkou uloží název elementu a pre pořadí. Dále postupně vkládá do databáze případné atributy. Při pozdějším průchodu ukončovací značkou vyjme název elementu a pre pořadí ze zásobníku a přidá zbylé informace (post pořadí, par, kind) a uloží je do databáze. Když narazí na komentář nebo instrukci pro zpracování přímo je vloží do databáze. Vkládání textových uzlů (hodnot atributů, textů elementů, komentářů a instrukcí pro zpracování) je úkolem metody characters. Veškerou komunikaci s databází zajišťuje objekt SQL, který je také vytvořen jádrem XPathu. Sám využívá ovladač pro připojení k databázi. Umožňuje samotné připojení k databázi, vytvoření databáze, vytvoření tabulek s danou strukturou, poté provádění dotazů nad těmito tabulkami a nakonec případné zrušení tabulek, databáze a odpojení. Databáze obsahuje pouze dvě tabulky, první se sloupci pre, post, par, kind a name a druhá se sloupci pre a cdata, které jsou v relaci přes sloupec pre. Z důvodu urychlení vykonávání XPath dotazů jsou všechny sloupce vyjma sloupce cdata indexovány pomocí B stromů. To ovšem bohužel značně zpomaluje načtení dokumentu do databáze, protože kromě vkládání jednotlivých uzlů je třeba ještě vytvářet indexy. Po načtení dokumentu přichází na řadu vykonávání Xpath dotazu. K tomu slouží jádro XPathu a XPath parser. Objekt jádra XPath jazyka se při vytvoření připojí k databázi a v případě, že se bude indexovat nový dokument vytvoří databázi a tabulky. Dále obsahuje metody index pro indexaci dokumentu, eval pro vykonání XPath dotazu a destroy pro případné zrušení vytvořených tabulek a databáze a odpojení od databáze. - 18 -

36SEM


Lukáš Skřivánek

Metoda eval je složena z volání 4 dalších metod jádra XPath, které lze volat i samostatně. Jde o metody praseXPath, createQuery, executeSQL a printTree. Metoda praseXPath vytvoří objekt XPath parser a předá mu zadaný XPath dotaz v textové podobě a zpět získá stromovou reprezentaci dotazu, z které vytvoří posloupnost queryWindow (podmínek pro pre, post, par, kind a name, které musí splňovat) odpovídající jednotlivým krokům XPath dotazu. XPath parser byl vytvořen pomocí JavaCC a JJTree. Posloupnost queryWindow je vstupem pro metodu createQuery, ta z ní vytvoří SQL dotaz, který vykoná metoda executeSQL. Výsledkem SQL dotazu je ResultSet s vybranými uzly. Nakonec metoda printTree výsledek SQL dotazu převede do textové formy. Poslední částí je rozhraní pro komunikaci s uživatelem nebo jiným programem. Protože není jádro XPath ani jiná část implementace nijak pevně svázána s objektem UI, je velmi snadné nové rozhraní dotvořit. Stačí v něm využít objekt jádra XPath a jeho metod k indexaci a dotazování, viz. výše. Lze si tedy stejně snadno představit textové nebo grafické rozhraní pro uživatele jako aplikaci na webovém serveru, který generuje webové stránky. Další možností je XPath server poslouchající na zvoleném portu TCP/IP protokolu a odpovídající na dotazy klientů. Na důkaz jsou implementovány dvě rozhraní: textové a grafické. Obě jsou velice jednoduché, určené hlavně pro demonstraci celé implementace. Bližší informace o implementaci poskytuje javadoc dokumentace zdrojových textů a samotné zdrojové texty.

- 19 -

36SEM


Lukáš Skřivánek

Uživatelský manuál Textové UI Aplikace XPath se spouští příkazem java -jar Xpath_text.jar, následuje sada dotazů ohledně připojení k databázi, dále názvů tabulek a databáze a XML souboru. Za dotazem je vždy v hranatých závorkách implicitní hodnota odpovědi, která slouží zároveň jako příklad možné odpovědi a pokud naše odpověď je shodná stačí zadat enter.

Obr. 7: Textové uživatelské rozhraní

Po odpovězení dotazů a připojení k databázi se zobrazí výzva XPath dotazu a je očekáván XPath dotaz nebo příkaz exit,který ukončí program. Po zadání XPath dotazu se zobrazí výsledek dotazu a je očekáván další XPath dotaz nebo exit. Po zadání příkazu exit je ještě uživatel dotazován, zda se mají smazat veškeré tabulky i databáze vytvořené programem nebo zda se mají zachovat a potom je možné je příště znovu využít a tedy není nutné stejné XML soubory indexovat znovu a znovu. Nevýhodou je, že název databáze a tabulek si musí uživatel pamatovat sám, kde má jaký dokument, proto se doporučuje nechávat implicitní názvy tabulek (XPath a XPathCDATA) a měnit pouze název databáze.

- 20 -

36SEM


Lukáš Skřivánek

Grafické UI Aplikace XPath se v grafickém režimu spouští příkazem java -jar Xpath_gui.jar. Nebo s přidělením větší paměti java -Xms512m -Xmx512m -jar Xpath_gui.jar. Měla by se zobrazit obrazovka s jednoduchým menu, vstupním okénkem pro XPath dotaz, tlačítkem „Proveď!“, oknem pro XML dokument a oknem pro výsledek XPath dotazu.

Obr. 8: Grafické uživatelské rozhraní

Po spuštění musíme zvolit nad jakým dokumentem budeme provádět XPath dotazy a buď máme dokument již indexován v databázi nebo chceme indexaci nejprve provést. Pro indexaci zvolíme „Soubor->Otevřít a naindexovat XML dokument …“ . Standardně vybere XML soubor, následuje okno „Připojení k databázi“, kde je třeba vyplnit připojovací údaje a názvy tabulek a databáze. Nebo máme dokument již v databázi indexován pak zvolíme „Soubor->Otevřít již naindexovaný XML dokument ...“, ale musíme vědět v jaké databázi a v jakých tabulkách je dokument umístěn. Po otevření XML dokumentu by se měl text dokumentu zobrazit v levém okénku zdrojového XML dokumentu. Do okénka pro XPath dotaz vložíme dotaz a klikneme na tlačítko „Proveď!“. V okénku pro výsledek by se měl objevit výsledek. Pro ukončení stačí z menu vybrat „Soubor->Konec“. Následují dotazy, zda se mají odstranit vytvořené tabulky a databáze nebo ponechat dokument v databázi. V případě mazání databáze je nutné vědět, že pokud obsahuje tabulky jiného programu budou odstraněny! - 21 -

36SEM


Lukáš Skřivánek

Měření náročnosti a výkonnosti Paměťová náročnost se samozřejmě odvíjí od objemu dat XML dokumentu, ale samotná vnitřní implementace vyžaduje paměť při indexaci pouze úměrnou hloubce stromu XML dokumentu. Nevyžaduje paměť na vytváření DOM stromu nebo něčeho podobného. Při dotazech vyžaduje paměť pouze na výsledek dotazu. Bohužel však v případě grafického uživatelského rozhraní je paměťově velmi náročné zobrazení dokumentu a výsledku XPath dotazu obzvláště ve swing komponentech. Časová náročnost se také odvíjí od velikosti XML dokumentu, od počtu uzlů. Rychlost vykonání XPath dotazů závisí na výkonnosti počítače, na kterém se dotaz provádí (výkon CPU, velikost a rychlost operační paměti, doba přístupu k médiu s daty) a programovém vybavení počítače (operační systém, souborový systém, databázový systém). Následující testy byli provedeny na počítači s parametry: AMD 1,9 GHz CPU, 1GB RAM 400MHz DDR, EIDE HDD 320GB, 8MB cache.

Tabulka 2: Testované XML dokumenty Název autobazar.xml docbook_xsl.xml docbook.xml nasa.xml

Popis demonstrační dokument z textu docbook dokument o XSL docbook dokument o fomátu docbook data z NASA

Velikost Počet uzlů 351 B 23 32 KB 1362 3 MB 164556 25 MB 848240

Tabulka 3: Naměřené doby vykonávání XPath dotazů Soubor autobazar.xml docbook_xsl.xml docbook_xsl.xml docbook.xml docbook.xml docbook.xml nasa.xml nasa.xml nasa.xml nasa.xml

XPath dotaz //typ /article/articleinfo/* //title/text() //LISTITEM/PARA/text() //LINK //ENTRY //author/initial //title //para/text() //units/parent::*

XPath Accelerator 1s 1s 1s 1s 2s 4s 4s 5s 19 s 33 s

Stylus Studio 2007 XML Professional Suite 1s 1s 1s 2s 34 s 17 s 40 s 50 s 235 s 690 s

- 22 -

XPath builder by XPath Explorer by buba software Purple Technology 1s 1s 1s 1s 1s 1s 5s neotevřel 30 s neotevřel 25 s neotevřel 35 s neotevřel 36 s neotevřel 170 s neotevřel 620 s neotevřel

36SEM


Lukáš Skřivánek

Naměřené doby vykonávání XPath dotazů 700

Doba vykonávání dotazu [s]

650

XPath Accelerator Stylus Studio 2007 XML Professional Suite XPath builder by buba software

600 550 500 450 400 350 300 250 200 150 100 50 0 //typ

/article/articleinfo/* //title/text()

//LINK

//ENTRY

XPath dotazy

- 23 -

//author/initial

//title

//para/text()

//units/parent::*

36SEM


Lukáš Skřivánek

Závěr Z naměřených výsledků je vidět, že tato metoda je použitelná, avšak samozřejmě není dokonalá. Nejprve je důležité si uvědomit, že dotazování předcházela indexace dokumentu do databáze, což může trvat několik minut, ale také několik hodin (v případě souboru nasa.xml to byla téměř hodina). Dále je implementována jen část XPath jazyka, chybí predikáty, které nemusí být snadné přidat při zachování efektivnosti vykonávání dotazů. Další vadou je nutnost celé nové indexace XML dokumentu při změně XML dokumentu. Pokud bychom chtěli měnit indexovaný XML dokument v databázi museli bychom použít jinou celou indexační strategii. Budoucnost ukládání XML dokumentů a dotazování se nad nimi patří zřejmě spíše objektovým nebo XML nativním databázím než relačním databázím, přesto metoda popsaná v tomto dokumentu v současné době dosahuje dobrých výsledků zvláště u velkých XML dokumentů.

- 24 -

36SEM


Lukáš Skřivánek

Zdroje [1] Torsten Grust: Accelerating XPath Location Steps [2] XML Path Language - http://www.w3.org/TR/xpath [3] Extensible Markup Language – http://www.w3.org/TR/REC-xml [4] Jiří Kosek: XML pro každého [5] XML pro každého – http://www.kosek.cz/xml/ [6] XPath – http://www.kosek.cz/xml/xslt/xpath.html [7] Brendan Briody: Accelerating XPath Location Steps [8] MySQL 5.0 Reference Manual – http://dev.mysql.com/doc/refman/5.0/en/ [9] Java[TM] 2 Platform Standard Edition 5.0 – http://java.sun.com/j2se/1.5.0/docs/api/

- 25 -

Accelerating XPath location steps

Recommend Documents