XQuery algebra XQuery Algebra

ˇ – Technicka´ univerzita Ostrava VSB Fakulta elektrotechniky a informatiky Katedra informatiky

XQuery algebra XQuery Algebra

2012

´s Bc. Petr Lukaˇ

Chtˇel bych podˇekovat svému vedouc´ımu diplomové práce, panu Ing. Radimu Baˇcovi, Ph.D za poskytnut´ı velmi zaj´ımavého tématu a za prubˇ ˚ ezˇ nou ochotnou odbornou pomoc.

Abstrakt Tato diplomová práce se zabyv´ ´ a návrhem a implementac´ı procesoru dotazovac´ıho jazyka XQuery, ktery´ slouˇz´ı k prohledáván´ı stromovˇe organizovanych XML dokumentu˚ a databáz´ı. C´ılem je ´ navrhnout a vytvoˇrit procesor pracuj´ıc´ı na principu algebraickych operátoru, ´ ˚ které umoˇznuj´ ˇ ı efektivnˇejˇs´ı vyhodnocován´ı vstupn´ıch dotazu˚ neˇz pˇr´ımá interpretace. V uvodu práce je podán struˇcny´ pˇrehled aktuálnˇe pouˇz´ıvanych ´ ´ technologi´ı, které se k dotazován´ı nad XML uzce vázˇ ou, vˇcetnˇe krátkého popisu samotného jazyka XQuery. Následuje návrh ´ algebraickych ´ operátoru˚ a návrh pˇrekladovych ´ pravidel pro transformaci dotazu˚ na tyto operátory zahrnuj´ıc´ı také optimalizaˇcn´ı postupy, které umoˇznuj´ ˇ ı v pˇreloˇzeném dotazu provést urˇcité upravy ´ tak, aby vysledek zustal zachován, ale vypoˇ ´ ˚ ´ cet probˇehl efektivnˇeji. Teoretické návrhy jsou dále pˇrevedeny do skuteˇcné podoby ve formˇe implementace procesoru. V závˇeru práce je vysledn y´ ´ procesor porovnán s jinymi existuj´ıc´ımi a bˇezˇ nˇe pouˇz´ıvanymi implementacemi. ´ ´ Kl´ıcˇ ová slova: XML, XQuery, XPath, dotazován´ı nad XML, dotazovac´ı jazyky, procesor, algebra, optimalizace, operátor, plán dotazu, pˇrekladaˇc

Abstract This diploma thesis deals with design and implementation of a processor of the XQuery computer language used for searching data in tree organized XML documents and databases. The goal of this work is to design and create a processor based on algebraic operators which can give better performance in evaluation of the input queries than direct interpretation. At the beginning of this work a breaf overview of currently used technologies for querying XML including a short description of the XQuery language is given. It is followed by a proposal of algebraic operators and proposal of compilation rules transforming queries into those operators. There are also included optimization techniques enabling to make such modifications in the compiled query as the result is preserved, but the evaluation is more effective. Those proposals are subsequently transformed into the real form of processor implementation. The final part of this work compares the implemented processor to other existing and commonly used implementations. Keywords: XML, XQuery, XPath, querying XML, data query languages, processor, algebra, optimization, operator, query plan, compiler

Seznam pouˇzitych ´ zkratek a symbolu˚ DOM DQL EBNF HTML PDF PI SOAP SQL TPNF TPQ XML XSLT

– – – – – – – – – – – –

Document Object Model Data Query Languages Extended Backus–Naur Form HyperText Markup Language Portable File Format Processing Instruction Simple Object Access Protocol Structured Query Language Tree Pattern Normal Form Tree Pattern Query eXtensible Markup Language eXtensible Stylesheet Language Transformation

Obsah 1

´ Uvod

2

Dotazován´ı nad XML 2.1 Zamyˇslen´ı na uvod . . . . . ´ 2.2 XML . . . . . . . . . . . . . 2.3 Dotazovac´ı jazyky nad XML 2.3.1 XPath . . . . . . . . . 2.3.2 XQuery . . . . . . . . 2.3.3 XQuery Core . . . . 2.3.4 XSLT . . . . . . . . .

3

4

1

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

2 2 2 4 4 5 8 9

XQuery algebra 3.1 Datovy´ model . . . . . . . . . . . . . . . . . . 3.1.1 Poloˇzka (item) . . . . . . . . . . . . . . 3.1.2 Sekvence (sequence) . . . . . . . . . . 3.1.3 N-tice (tuple) . . . . . . . . . . . . . . 3.1.4 Schéma n-tice . . . . . . . . . . . . . . 3.1.5 Tabulka (table) . . . . . . . . . . . . . 3.2 Operátory . . . . . . . . . . . . . . . . . . . . 3.2.1 Strom operátoru˚ . . . . . . . . . . . . 3.2.2 Vypoˇ ´ cet . . . . . . . . . . . . . . . . . 3.2.3 Operátor IN . . . . . . . . . . . . . . . 3.3 Kompilaˇcn´ı pravidla . . . . . . . . . . . . . . 3.3.1 Kompilace elementárn´ıch konstrukc´ı 3.3.2 FLWOR vyrazy . . . . . . . . . . . . . ´ 3.3.3 XPath vyrazy . . . . . . . . . . . . . . ´ 3.3.4 Kompilace dalˇs´ıch konstrukc´ı . . . . . 3.4 Optimalizace . . . . . . . . . . . . . . . . . . . 3.4.1 Odstranˇen´ı MapConcat . . . . . . . . 3.4.2 Odstranˇen´ı MapToItem . . . . . . . . 3.4.3 Vloˇzen´ı Product . . . . . . . . . . . . . 3.4.4 Vloˇzen´ı Join . . . . . . . . . . . . . . . 3.4.5 Spojen´ı kroku˚ XPath . . . . . . . . . . 3.4.6 Dalˇs´ı moˇznosti optimalizace . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

10 10 10 10 10 10 11 11 11 12 12 13 15 18 23 28 28 29 30 31 31 31 33

Implementace XQuery procesoru 4.1 Standard W3C a zjednoduˇsen´ı . . . . . . . . . . . . . . . . . . . . 4.1.1 Podporované konstrukce . . . . . . . . . . . . . . . . . . 4.1.2 Nepodporované nebo cˇ a´ steˇcnˇe podporované konstrukce 4.2 Implementaˇcn´ı prostˇred´ı . . . . . . . . . . . . . . . . . . . . . . . 4.3 Univerzáln´ı datové struktury . . . . . . . . . . . . . . . . . . . . 4.3.1 MyList . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 MyStack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 MyQueue . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

35 35 35 37 37 37 37 38 38

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

38 38 39 39 41 42 43 43 43 44 45 46 47 49 49 52 53 54 55 55 56 60 60 61

5

Experimentáln´ı vyhodnocován´ı 5.1 Srovnán´ı jinych ´ implementac´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Shrnut´ı cˇ asovych ´ srovnán´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Vliv optimalizac´ı na délku bˇehu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63 63 70 70

6

Závˇer 6.1 Vlastn´ı pˇr´ınos a moˇznosti rozˇs´ırˇ en´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Osobn´ı zhodnocen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72 72 72

4.4

4.5

4.6

4.7 4.8

4.3.4 MyHashSet . . . . . . . . . . . . . . . . . 4.3.5 MyIterator . . . . . . . . . . . . . . . . . . Datovy´ model . . . . . . . . . . . . . . . . . . . . 4.4.1 Typovy´ systém . . . . . . . . . . . . . . . 4.4.2 Správa datovych ´ objektu˚ . . . . . . . . . 4.4.3 Implementace DataSequence a DataTable 4.4.4 DOM . . . . . . . . . . . . . . . . . . . . . 4.4.5 Symbolické názvy promˇennych ´ . . . . . . Parser . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Termináln´ı symboly . . . . . . . . . . . . 4.5.2 Syntakticky´ strom . . . . . . . . . . . . . 4.5.3 Scanner . . . . . . . . . . . . . . . . . . . 4.5.4 Syntaktická analyza . . . . . . . . . . . . ´ Kompiler . . . . . . . . . . . . . . . . . . . . . . . 4.6.1 Kompilace . . . . . . . . . . . . . . . . . . 4.6.2 Kompilace sloˇzitˇejˇs´ıch konstrukc´ı . . . . Optimalizace . . . . . . . . . . . . . . . . . . . . . Vyhodnocován´ı . . . . . . . . . . . . . . . . . . . 4.8.1 Vyhodnocen´ı statickych ´ sloˇzek operátoru˚ 4.8.2 Operátor Select . . . . . . . . . . . . . . . 4.8.3 Operátor TreeJoin . . . . . . . . . . . . . . 4.8.4 Operátor IN . . . . . . . . . . . . . . . . . 4.8.5 Operátor Call . . . . . . . . . . . . . . . . 4.8.6 Dalˇs´ı operátory . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

A Vestavˇené funkce

75

B Kompatibilita datovych ´ typu˚

83

C Spustitelny´ procesor

84

Seznam obrázku˚ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Osy XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ukázka stromu operátoru˚ . . . . . . . . . . . . . . . . . . . . . . . . . . Kompilace sekvence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kompilace XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˇ Cinnost operátoru MapConcat . . . . . . . . . . . . . . . . . . . . . . . Blokové schéma kompilace FLWOR . . . . . . . . . . . . . . . . . . . . Kompilace FLWOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Struktura XPath vyrazu . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ Pˇreklad ukázkového XPath vyrazu . . . . . . . . . . . . . . . . . . . . . ´ Mezivysledky ukázkového pˇrekladu XPath . . . . . . . . . . . . . . . . ´ Kompilace skalárn´ı hodnoty bez optimalizace . . . . . . . . . . . . . . Kompilace skalárn´ı hodnoty po optimalizaci odstranˇen´ım MapConcat Plán dotazu a//b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rozbor optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bloková struktura procesoru . . . . . . . . . . . . . . . . . . . . . . . . . Tˇr´ıdn´ı diagram datového modelu . . . . . . . . . . . . . . . . . . . . . . Tˇr´ıdn´ı diagram datové poloˇzky . . . . . . . . . . . . . . . . . . . . . . . Tˇr´ıdn´ı diagram správy datovych ´ objektu˚ . . . . . . . . . . . . . . . . . Lexikáln´ı a syntaktická analyza ´ (viz [8]) . . . . . . . . . . . . . . . . . . Tˇr´ıdn´ı diagram scanneru . . . . . . . . . . . . . . . . . . . . . . . . . . . Tˇr´ıdn´ı diagram parseru . . . . . . . . . . . . . . . . . . . . . . . . . . . . Princip parsován´ı XML elementu . . . . . . . . . . . . . . . . . . . . . . Tˇr´ıdn´ı diagram pˇrekladaˇce . . . . . . . . . . . . . . . . . . . . . . . . . . Princip substituce promˇennych . . . . . . . . . . . . . . . . . . . . . . . ´ Tˇr´ıdn´ı diagram optimalizace . . . . . . . . . . . . . . . . . . . . . . . . . Postorder seznam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Preorder seznam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tˇr´ıdn´ı diagram modulárn´ı stavby funkc´ı . . . . . . . . . . . . . . . . . . Srovnán´ı cˇ asu˚ jednotlivych ´ procesoru˚ . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 12 16 17 19 21 22 23 26 27 29 30 31 32 35 39 40 42 44 46 47 49 50 52 53 58 58 61 70

Seznam tabulek 1 2 3 4 5 6 7 8 9 10 11 12

Operátory algebry . . . . . . . . . . . . . . . . . . . . . . . Mezivysledky vyhodnocován´ı . . . . . . . . . . . . . . . . ´ Mezivysledek MapFromItem . . . . . . . . . . . . . . . . ´ Mezivysledek MapConcat . . . . . . . . . . . . . . . . . . ´ Podporované vestavˇené funkce . . . . . . . . . . . . . . . Prvoˇc´ısla pro volbu velikosti tabulky hash . . . . . . . . . Datové typy procesoru . . . . . . . . . . . . . . . . . . . . Pˇr´ıklady termináln´ıch symbolu˚ bez obsahu a s obsahem . Srovnán´ı algoritmu˚ pro navigaci na osu descendant . . . . Konfigurace testovac´ıho PC . . . . . . . . . . . . . . . . . Parametry testovac´ıho XML dokumentu . . . . . . . . . . Kompatibilita datovych ´ typu˚ . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

14 22 29 30 37 38 41 44 57 63 63 83

Seznam algoritmu˚ 1 2 3 4 5 6 7

ˇ ast metody expandExpr pro pˇreklad podm´ınky . C´ Transformace operátoru Select . . . . . . . . . . . . Transformace vloˇzen´ı Product . . . . . . . . . . . . Vyhodnocen´ı operátoru Select . . . . . . . . . . . . Implementace TreeJoin . . . . . . . . . . . . . . . . . Implementace IN . . . . . . . . . . . . . . . . . . . . Puvodn´ ı implementace Call . . . . . . . . . . . . . . ˚

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

51 54 55 56 59 60 60

´ 1 Uvod Jedn´ım z nejv´ıce prakticky uplatnovan ych oboru˚ dneˇsn´ıch informaˇcn´ıch technologi´ı je tvorba ˇ ´ informaˇcn´ıch systému. ˚ Zejména v souˇcasné dobˇe nut´ı politická situace pˇrecházet menˇs´ı cˇ i vˇetˇs´ı firmy na komplexn´ı informaˇcn´ı systémy obvykle z duvodu zefektivnˇen´ı vyroby nebo sluˇzeb. ˚ ´ Je duleˇ ˚ zité umˇet shromázˇ dit potˇrebná data, naj´ıt mezi nimi patˇriˇcné vztahy a co je hlavn´ı, je nutné v nich umˇet rychle vyhledávat. Dotazovac´ı jazyky (DQL - Data Query Languages) jsou vyv´ıjeny jiˇz celou rˇ adu let a zamˇerˇ uj´ı se pˇredevˇs´ım na relaˇcn´ı databáze, kde jsou data organizovány v tzv. relac´ıch nebo zjednoduˇsenˇe rˇ eˇceno v tabulkách. Jednoznaˇcnˇe nejpouˇz´ıvanˇejˇs´ım pˇredstavitelem tˇechto jazyku˚ je SQL (Structured Query Language). Relace ale nejsou jedinou moˇznost´ı jak organizovat data. Trendem modern´ı doby je stále v´ıce se uplatnuj´ ˇ ıc´ı stromová struktura v podán´ı XML, která je v mnoha pˇr´ıpadech schopna lépe a pruˇznˇeji reprezentovat urˇcitou reálnou situaci. S t´ım roste potˇreba umˇet v takovychto stromovych ´ ´ organizac´ıch efektivnˇe a hlavnˇe snadno vyhledávat. Zat´ımco v relaˇcn´ıch databáz´ıch má jazyk SQL své m´ısto v´ıce neohrozitelné a vyvoj´ ´ arˇ i informaˇcn´ıch systému˚ se bez nˇej neobejdou, v pˇr´ıpadˇe XML databáz´ı jsou vzniklé standardy pomˇernˇe cˇ erstvé a do podvˇedom´ı veˇrejnosti teprve postupnˇe pronikaj´ı. Uˇz v tuto chv´ıli lze ale rˇ´ıci, zˇ e nejvˇetˇs´ımi kandidáty na sˇ iroké uplatnˇen´ı jsou XPath a XQuery. Je vhodné pˇredeslat, zˇ e XQuery je v uvozovkách pouze rozˇs´ırˇ en´ım jazyka XPath, cˇ ili zˇ e se nejedná o dva naprosto odliˇsné jazyky. C´ılem práce je naimplementovat zjednoduˇseny´ procesor pomˇernˇe nároˇcného deklarativn´ıho jazyka XQuery za pouˇzit´ı algebraickych ´ operátoru. ˚ Práce se bude skládat ze cˇ tyˇr hlavn´ıch kapitol. Prvn´ı z nich, Dotazován´ı nad XML, bude vˇenována pˇredstaven´ı souˇcasnˇe nejpouˇz´ıvanˇejˇs´ıch technologi´ı pro dotazován´ı nad XML. V dalˇs´ı kapitole, XQuery algebra, budou prezentovány principy pˇrekladu dotazu˚ na algebraické operátory. Pujde o teoreticky´ základ pro nadefinován´ı funkˇcnosti ˚ procesoru. Kapitola Implementace XQuery procesoru bude tento teoreticky´ základ pˇrevádˇet do praktické podoby. Posledn´ı kapitola, Experimentáln´ı vyhodnocován´ı, pˇredstav´ı naimplementovany´ procesor a provede srovnán´ı s jinymi existuj´ıc´ımi. ´

1

2

Dotazován´ı nad XML

Tato uvodn´ ı kapitola má nast´ınit základn´ı principy spojené s XML a podat struˇcny´ pˇrehled technik, ´ které souvis´ı s dotazován´ım.

2.1

Zamyˇslen´ı na uvod ´

V dneˇsn´ı dobˇe se lze setkat s XML témˇerˇ ve vˇsech oblastech informaˇcn´ıch technologi´ı. Nab´ız´ı se menˇs´ı zamyˇslen´ı, co je duvodem tak velké popularity tak jednoduchého jazyka. Pokud se ˚ zamˇerˇ´ıme na vyvoj moˇznost´ı poˇc´ıtaˇcového hardwaru v prubˇ ´ ˚ ehu posledn´ıch 20-ti let a v´ıce, muˇ ˚ zeme pozorovat obvykle exponenciáln´ı rust ˚ hodnot mnoha parametru. ˚ Jedná se pˇredevˇs´ım o velikost pamˇet´ı, rychlost procesoru, ˚ pˇrenosovou rychlost komunikaˇcn´ıch technologi´ı a dalˇs´ı. Takovéto podm´ınky umoˇznuj´ ˇ ı odprostit se od uvaˇzován´ı nad kaˇzdym ´ bajtem zvlásˇ t’ a vyuˇz´ıvat vyˇssˇ´ı urovnˇ e abstrakce. ´ Pohledem napˇr. na souborové formáty pouˇz´ıvané 15 let zpˇet zjist´ıme, zˇ e se obvykle vˇse ukládalo v binárn´ı podobˇe. Kaˇzdy´ aplikaˇcn´ı software mˇel definovany´ svuj ˚ vlastn´ı formát, jehoˇz specifikace byla v mnoha pˇr´ıpadech z obchodn´ıch duvod u˚ utajená. Modern´ı informaˇcn´ı tech˚ nologie vˇsak kladou duraz na modulárn´ı stavbu, schopnost komunikace, dodrˇzován´ı standardu˚ ˚ a informaˇcn´ı dostupnost. Individualisticky´ pˇr´ıstup k rˇ eˇsen´ı problému˚ sice muˇ ˚ ze byt ´ v uzk ´ ych ´ oblastech pouˇzit´ı efektivnˇejˇs´ı, avˇsak z principu pak zabranuje sˇ irˇs´ımu uplatnˇen´ı. ˇ Mezi nejduleˇ XML patˇr´ı jednoduchá, striktn´ı, ale pˇresto velmi pruˇzná syn˚ zitˇejˇs´ı vyhody ´ taxe. Dále bezesporu bezplatné vyuˇz´ıván´ı tohoto standardu a stromová organizace, která dokázˇ e naprosto pˇrirozenym popsat stavbu a okamˇzitych ´ zpusobem ˚ ´ stav reálnych ´ objektu. ˚ V pˇr´ıpadˇe rozumné volby názvu˚ znaˇcek pro konkrétn´ı pouˇzit´ı, je nav´ıc XML samopopisné, coˇz ve vˇetˇsinˇe pˇr´ıpadu˚ umoˇznuje správnou interpretaci jeho obsahu i bez dostupnosti nˇejaké oficiáln´ı specifikace. ˇ Konkrétnˇe tedy XML nacház´ı uplatnˇen´ı od oblasti konfiguraˇcn´ıch souboru, ˚ pˇres internetové technologie (XHTML, SOAP), souborové formáty (Open Document, Office Open XML) aˇz po celé stromové XML databáze. Mimo to lze tento jazyk pouˇz´ıt samozˇrejmˇe kdykoli pˇri potˇrebˇe serializace programovych ´ objektu. ˚

2.2

XML

eXtensible Markup Language, cˇ ili cˇ esky rozˇsiˇritelny´ znaˇckovac´ı jazyk, je vyv´ıjen a standardizován organizac´ı W3C momentálnˇe ve verzi 1.1 [3]. Element tvoˇr´ı základn´ı stavebn´ı stvaben´ı jednotku XML dokumentu. Zaˇca´ tek a konec elementu tvoˇr´ı znaˇcky a , kde a pˇredstavuje jeho název. Obsah mezi poˇca´ teˇcn´ı a koncovou znaˇckou je tvoˇren dalˇs´ımi elementy, komentárˇ i, textem, procesn´ımi instrukcemi nebo odkazy na entity. Souˇca´ st´ı elementu mohou byt ´ atributy, které se uvád´ı pˇr´ımo do uvozovac´ı znaˇcky. Je-li obsah mezi znaˇckami prázdny, ´ je moˇzné vynechat ukonˇcovac´ı znaˇcku s t´ım, zˇ e je uvozovac´ı znaˇcka doplnˇena o jednoduché lom´ıtko pˇred pravou závorkou (). Atribut je tvoˇren vˇzdy dvojic´ı kl´ıcˇ ="hodnota". Hodnota mus´ı byt ´ uvedena v uvozovkách, mezi sebou jsou atributy navzájem oddˇelovány mezerou. Atributy jsou vˇzdy souˇca´ st´ı elementu˚ nebo procesn´ıch instrukc´ı.

2

Textovy´ obsah pˇredstavuje jakykoli obecny´ text bez dalˇs´ı struktury. Je nutné vyvarovat se ´ znakum, které mohou souviset se zápisem znaˇcky, tzn. minimálnˇe ,,<“ a ,,>“. Pro jejich ˚ vyjádˇren´ı slouˇz´ı tzv. znakové entity ,,<“ a ,,>“. Komentárˇ je zapsán mezi dvojici znaˇcek ,,“. Jak bude pozdˇeji uvedeno, XQuery je schopen dotazovat se i na obsah komentárˇ u, ˚ takˇze z hlediska zpracováván´ı nen´ı moˇzné komentárˇ e jednoduˇse zanedbat napˇr. preprocesorem. Procesn´ı instrukce (PI) si lze pˇredstavit jako speciáln´ı elementy ohraniˇcené mezi ,,“. Kaˇzdá PI má podobnˇe jako element svuj ˚ název. Obsah PI je tvoˇren pouze atributy. Procesn´ı instrukce se obvykle pouˇz´ıvaj´ı ke specifikován´ı duleˇ ˚ zitych ´ pokynu˚ pro aplikaci, která dané XML zpracovává. Entity umoˇznuj´ textu. Pozdˇeji se na tyto entity ˇ ı pˇreddefinovat nˇejaké delˇs´ı opakuj´ıc´ı se useky ´ muˇ tak do jisté m´ıry eliminovat nadbyteˇcnost ˚ zeme jednoduˇse odkazovat a svym ´ zpusobem ˚ dat v XML. Pˇresné informace o entitách je moˇzné nalézt v [3]. Sekce CDATA slouˇz´ı pro zápis surového textu. Typickym zdrojového ´ vyuˇzit´ım je zápis useku ´ kodu. Obsah CDATA se uvád´ı mezi znaˇcky ,,“ ´ XML dokument je dobˇre formovany´ (well-formed), jestliˇze jsou splnˇena vˇsechna pravidla pro zápis vyˇ cˇ a´ st´ı. Kaˇzdy´ XML dokument mus´ı obsahovat pˇresnˇe jeden ´ se definovanych ´ koˇrenovy´ element. Dále by se v dokumentu mˇela objevit procesn´ı instrukce udávaj´ıc´ı verzi XML a pouˇzité kodov´ an´ı (viz ukázka 1). ´ Vˇsechny vyˇ ´ se uvedené cˇ a´ sti XML kromˇe atributu˚ byvaj´ ´ ı zobecnov´ ˇ any na pojem XML uzel. <section id="1"> Uˇ cebnice XQuery John Black Uˇ cebnice XPath Jack White Uˇ cebnice XML Jimm Green

Ukázka 1: Ukázka XML dokumentu

3

2.3

Dotazovac´ı jazyky nad XML

Dotazovac´ıch jazyku˚ pro XML existuje v souˇcasnosti celá rˇ ada. Jednotlivé jazyky jsou v´ıce cˇ i ménˇe pouˇz´ıvané, liˇs´ı se v principech, v syntaxi, ale vˇsechny se op´ıraj´ı o stromovou strukturu XML. 2.3.1

XPath

Jedná se o jednoho z prakticky nejpouˇz´ıvanˇejˇs´ıch zástupcu˚ jazyku˚ pro dotazován´ı nad XML. Syntaxe tohoto jazyka je velmi snadná a intuitivn´ı, takˇze je ho moˇzné plnˇe vyuˇz´ıvat uˇz po krátkém seznámen´ı. XPath je podobnˇe jako vˇse okolo XML standardizován organizac´ı W3C momentálnˇe ve verzi 2.0 [4]. Filter vyrazy a axis kroky ´ Cely´ XPath vyraz se skládá z nˇekolika kroku˚ dvoj´ıho typu – axis steps a filter výrazu˚ (neplést s pre´ dikáty). Jeho vyhodnocován´ı prob´ıhá zleva doprava 1 . Vysledkem kaˇzdého kroku je uspoˇra´ daná ´ mnoˇzina XML uzlu. ˚ Pro kaˇzdy´ z uzlu˚ této mnoˇziny pak probˇehne zpracován´ı kroku následuj´ıc´ıho, kde dany´ uzel figuruje jako kontextový. Axis step vyjadˇruje pohyb po urˇcené ose (viz obr. 1), filter výraz pˇredstavuje operaci na základˇe kontextového XML uzlu, napˇr. vypoˇ ´ cet aritmetického vyrazu. ´ Vysledn´ a mnoˇzina kaˇzdého kroku muˇ ´ ˚ ze byt ´ dále filtrována pomoc´ı predikátu˚ v hranatych ´ závorkách. /library//book[@isbn="978-3-16-148410-0"]/author

Ukázka 2: Demonstraˇcn´ı XPath dotaz

Na ukázce 2 je zachycen jednoduchy´ XPath dotaz, jehoˇz ukolem je navrátit jméno autora knihy ´ s urˇcitym ´ ISBN. Dotaz bude provádˇen nad dokumentem z ukázky 1. Zápis /library vybere ze zdrojového dokumentu koˇrenovy´ element. Pomoc´ı //book dojde k vyhledán´ı vˇsech elementu˚ – potomku˚ s názvem ,,book“. Dále následuje zápis predikátu [@isbn="978-3-16-148410-0"], ktery´ zajist´ı filtrován´ı vˇsech uzlu˚ – knih s hodnotou atributu isbn rovnou ,,978-3-16-148410-0“. Z takto vzniklé mnoˇziny (obsahuj´ıc´ı vzhledem k dotazovanému dokumentu pouze jeden element) jsou nakonec vybráni vˇsichni pˇr´ım´ı potomci – uzly s názvem ,,author“. Uvedeny´ vyraz je ve skuteˇcnosti zjednoduˇsen´ım dotazu z ukázky 3. ´ /child::library/descendant-or-self::node()/book [attribute::isbn="978-3-16-148410-0"]/child::author

Ukázka 3: XPath dotaz bez zkratkovych ´ zápisu˚

1 Vyhodnocov´ an´ı zleva doprava má symbolicky´ vyznam pro uˇzivatele, ve skuteˇcnosti muˇ ´ ˚ ze procesor pohl´ızˇ et na vyraz ´ jako na celek a vyhodnotit jej tak efektivnˇeji.

4

Osy XML Je vidˇet, zˇ e zjednoduˇseny´ (zkratkovy) ´ zápis na ukázce 2 neobsahoval kl´ıcˇ ová slova child, descendant-or-self a attribute. Jedná se o specifikaci tzv. os. Uvedené 3 osy jsou totiˇz prakticky nejpouˇz´ıvanˇejˇs´ı, a tak by byl jejich plny´ zápis zbyteˇcnˇe zdlouhavy. ´ Osy pˇredstavuj´ı urˇcen´ı prohledávané cˇ a´ sti XML dokumentu vzhledem k uzlu, na kterém se aktuálnˇe nacház´ıme, tj. kontextovému uzlu. Zápis node() pˇredstavuje na ukázce 3 vybˇ ´ er libovolného XML uzlu. Pˇrehled os je ilustrován na obrázku 1. Aktuáln´ı kontextovy´ uzel je zvyraznˇ en. ´ ancestor preceding

following ancestor-or-self

parent

self

preceding-sibling

following-sibling

child

descendant descendant-or-self

Obrázek 1: Osy XML

Zbyv´ ´ a podotknout, zˇ e XPath je case-sensitive, tzn. rozliˇsuje velikost znaku˚ a to nejen vzhledem ke kl´ıcˇ ovym ale také vzhledem k názvum ´ slovum, ˚ ˚ XML uzlu. ˚ 2.3.2

XQuery

Jazyk XQuery je pˇredstavitelem deklarativn´ıch programovac´ıch jazyku. ˚ To znamená, zˇ e program, resp. v tomto pˇr´ıpadˇe dotaz specifikuje, co je poˇzadováno na vystupu bez pˇresného udán´ı ele´ mentárn´ıch kroku, povedou. Jedná se o pomˇernˇe mlady´ jazyk, ktery´ vznikl ˚ které k vysledku ´ na základˇe dotazovac´ıho jazyka Quilt [15]. Snahou XQuery je poskytnout podobny´ komfort pˇri dotazován´ı nad XML databázemi jako poskytuje SQL nad databázemi relaˇcn´ımi. XQuery je opˇet standardizován W3C, momentálnˇe ve verzi 1.0 (od roku 2007). Standard definuje tento jazyk nejen pro tvorbu dotazu, ˚ ale také pro tvorbu celych ´ funkc´ı a modulu. ˚ Souˇca´ st´ı XQuery je moˇznost pouˇz´ıván´ı dotazu˚ XPath. XQuery k tˇemto dotazum ˚ pˇridává nˇekteré velmi uˇziteˇcné sloˇzitˇejˇs´ı konstrukce. Aktuálnˇe platné standardy obou jazyku˚ – XPath a XQuery pracuj´ı se spoleˇcnym ´ datovym ´ modelem [6]. Stejnˇe jako XPath je tento jazyk case-sensitive. FLWOR vyrazy ´ FLWOR vyrazy [ˇcteno jako flower] pˇredstavuj´ı základn´ı a nejv´ıce pouˇz´ıvanou konstrukc´ı XQuery. ´ Název FLWOR vycház´ı z prvn´ıch p´ısmen jednotlivych ´ klauzul´ı, tj. cˇ a´ st´ı této konstrukce. Jedná se 5

o klauzule for, let, where, order by a return. Pro uˇ ´ cely této práce budou vysvˇetleny pouze základn´ı principy tˇechto vyraz u, ´ ˚ pro detailnˇejˇs´ı a názornˇejˇs´ı studium lze vyuˇz´ıt napˇr. [1]. for $b at $i in /library//book let $a := $b/author where $s = "John Smith" and $i > 1 order by $b/isbn return $b

Ukázka 4: Demonstraˇcn´ı FLWOR vyraz ´

Vyznam jednotlivych ´ ´ klauzul´ı bude vysvˇetlen na ukázkovém dotazu 4. Jako dotazovany´ dokument opˇet poslouˇz´ı XML z ukázky 1. Klauzule for rˇ´ıká, zˇ e bude cely´ zbytek vyrazu iterován pro promˇennou b na pozici i pˇres nˇejakou ´ uspoˇra´ danou mnoˇzinu XML uzlu, ˚ které obdrˇz´ıme XPath dotazem /library//book. Ve zbytku vyrazu bude promˇenná b postupnˇe nabyvat hodnot jednotlivych XML uzlu. ´ ´ ´ ˚ Promˇenná i (tzv. poziˇcn´ı promˇenná) bude pˇredstavovat cˇ ´ıtaˇc jednotlivych u. ´ pruchod ˚ ˚ Klauzul´ı for se ve FLWOR muˇ z hlediska uˇzivatele o zanoˇrené ˚ ze objevit v´ıce, v tom pˇr´ıpadˇe pujde ˚ iterace. Specifikace poziˇcn´ı promˇenné at $i nen´ı povinná. Klauzule let slouˇz´ı pro zaveden´ı pomocné promˇenné a, do které bude v kaˇzdé iteraci for pˇriˇrazena hodnota XPath vyrazem $b/author. Kromˇe XPath se zde mohou objevovat ´ napˇr. aritmetické vyrazy, volán´ı vestavˇenych nebo uˇzivatelskych funkc´ı. Klauzul´ı for a ´ ´ ´ let se ve FLWOR muˇ ˚ ze zopakovat libovolnˇe mnoho minimálnˇe vˇsak vˇzdy alesponˇ jedna z nich. Klauzule where následuje aˇz po vˇsech for a let. Tato klauzule specifikuje podm´ınku, za jakych ´ okolnost´ı dojde skuteˇcnˇe k vyhodnocen´ı d´ılˇc´ıho vysledku následuj´ıc´ı klauzule return. ´ V ukázkovém dotazu si lze vˇsimnout pouˇzit´ı vyraz u˚ pro porovnáván´ı a jejich spojen´ı lo´ gickym ´ souˇcinem. V pˇr´ıpadˇe, zˇ e podm´ınku specifikovat nepotˇrebujeme, je moˇzné celou klauzuli where vynechat. Klauzule order by umoˇznuje provést setˇr´ızen´ı dle specifikovanych ˇ ´ kritéri´ı. V tomto pˇr´ıpadˇe jde o vzestupné abecedn´ı tˇr´ızen´ı podle ISBN jednotlivych ´ knih, které vyhovˇely podm´ınce z klauzule where. XQuery umoˇznuje provádˇet i sestupné tˇr´ızen´ı kl´ıcˇ ovym ˇ ´ slovem descending, které pˇridáme za tˇr´ıd´ıc´ı kritérium. Kritéri´ı pro tˇr´ızen´ı muˇ ˚ ze byt ´ v´ıce, v tom pˇr´ıpadˇe jsou mezi sebou oddˇeleny cˇ a´ rkou. Celá klauzule order by stejnˇe jako where nen´ı povinná. Klauzule return je povinnou posledn´ı klauzul´ı kaˇzdého FLWOR vyrazu. Udáváme zde, co ´ nakonec poˇzadujeme na vystupu. Pomoc´ı XPath je zde moˇzné vracet existuj´ıc´ı XML uzly, ´ popˇr. s nimi provádˇet nˇejaké rˇ etˇezcové nebo aritmetické operace. Velmi cˇ asto se zde objevuj´ı konstrukce novych ´ XML uzlu. ˚ XML konstruktory Duleˇ ˚ zitou souˇca´ st´ı XQuery jazyka je moˇznost vytvárˇ et vlastn´ı XML uzly, popˇr. celé XML stromy, jejichˇz obsah muˇ u. ˚ ze byt ´ vytvárˇ en napˇr. pomoc´ı FLWOR vyraz ´ ˚ Existuj´ı dva typy XML konstruk6

toru˚ – pˇr´ımé (direct) a vypoˇctené (computed). Z praktickych duvod u˚ se obvykle pouˇz´ıvaj´ı pouze ´ ˚ konstruktory pˇr´ımé. V pˇr´ıpadˇe vypoˇctených konstruktoru˚ se XML strom vytvárˇ´ı pomoc´ı speciáln´ıch kl´ıcˇ ovych ´ slov jako element, attribute, text, comment a processing-instruction. Na ukázce 5 je pˇr´ıklad konstrukce XML elementu s názvem ,,a“ a textovym obsahem tvoˇrenym obsahem ´ ´ promˇenné x a textem ,,test“. Konstrukce XML prob´ıhá tak, zˇ e kl´ıcˇ ovym ´ slovem specifikujeme typ XML uzlu (element, atribut, textovy´ uzel atd.), za nˇej (pokud to dany´ typ vyˇzaduje – elementy, atributy, procesn´ı instrukce) um´ıst´ıme jeho název a nakonec do sloˇzenych ´ závorek obsah, ktery´ se v pˇr´ıpadˇe elementu˚ muˇ ˚ ze skládat z dalˇs´ıch XML uzlu, ˚ v pˇr´ıpadˇe atributu˚ z rˇ etˇezcové hodnoty. Jednotlivé cˇ a´ sti obsahu oddˇelujeme cˇ a´ rkou. element a { text { $x }, text { "test" } }

Ukázka 5: Pouˇzit´ı vypoˇctenych ´ konstruktoru˚

Pˇr´ımé konstruktory jsou na pouˇzit´ı mnohem intuitivnˇejˇs´ı. Nové XML uzly konstruujeme velmi jednoduˇse tak, zˇ e je zap´ısˇ eme v jejich XML podobˇe, tzn. podle pravidel uvedenych ´ v kapitole 2.2. Pokud nastane situace, zˇ e v obsahu elementu nebo hodnoty atributu potˇrebujeme z´ıskat hodnotu nˇejaké promˇenné napˇr. z let klauzule FLWOR vyrazu, um´ıst´ıme do XML konstruktoru vnoˇreny´ ´ vyraz do sloˇzenych závorek. Stejného vysledku jako u konstruktoru z ukázky 5 dosáhneme ´ ´ ´ vyrazem na ukázce 6. ´ Pˇrestoˇze se muˇ ˚ ze pˇr´ıtomnost vypoˇctenych ´ konstruktoru˚ jevit jako zbyteˇcná, nen´ı tomu tak. Vypoˇctené konstruktory totiˇz na rozd´ıl od pˇr´ımych ´ neumoˇznuj´ ˇ ı specifikovat názvy uzlu˚ pomoc´ı promˇennych ´ ve vyrazu. ´ { $x } test

Ukázka 6: Pouˇzit´ı pˇr´ımych ´ konstruktoru˚

Na XQuery nelze pohl´ızˇ et pouze jako na filtr vstupn´ıho dokumentu. Na ukázce 7 je pˇr´ıklad dotazu, jehoˇz vnitˇrn´ı cˇ a´ st pomoc´ı pˇr´ımych ´ konstruktoru˚ vytvoˇr´ı sekvenci XML uzlu, ˚ nad kterou probˇehne jednoduchy´ XPath. U kaˇzdého vyrazu, ktery´ pracuje nad XML, nezáleˇz´ı na tom, zda ´ jsou XML uzly pouze vysledkem filtrován´ı vstupn´ıho dokumentu nebo byly vytvoˇreny bˇehem ´ vyhodnocován´ı dotazu. (for $n in (, , , ) return $n)/@id

Ukázka 7: XQuery s konstrukc´ı XML

7

Dalˇs´ı konstrukce XQuery FLWOR vyrazy nejsou zdaleka jedinou konstrukc´ı, kterou XQuery obohacuje syntaxi XPath. ´ Minimálnˇe za zm´ınku zde stoj´ı pouˇz´ıván´ı alternativy, pˇrep´ınaˇce typeswitch nebo kvantifikovanych u. tvorbu vlastn´ıch uˇzivatelskych ´ vyraz ´ ˚ Specifikace dále umoˇznuje ˇ ´ datovych ´ typu, ˚ modulu˚ a funkc´ı. Lze ukázat [11], zˇ e XQuery je Turing-kompletn´ı jazyk. 2.3.3

XQuery Core

XQuery poskytuje velkou sadu pravidel, které umoˇznuj´ ˇ ı jeho pohodlné pouˇz´ıván´ı bez nutnosti dlouhodobého studia. Z hlediska vyhodnocován´ı dotazu˚ je vˇsak vydefinována podmnoˇzina tohoto jazyka známá jako XQuery core obsahuj´ıc´ı pouze omezené mnoˇzstv´ı konstrukc´ı, na které lze kaˇzdy´ XQuery dotaz pˇrepsat. Proces pˇrepisu dotazu XQuery na XQuery Core byv´ ´ a nazyv´ ´ an jako tzv. normalizace. Normalizace vstupn´ıho dotazu je bˇezˇ nym ´ poˇca´ teˇcn´ım krokem vyhodnocován´ı u vˇetˇsiny procesoru. ˚ Ukázka 8 pˇredstavuje normalizovanou podobu jednoduchého XPath vyrazu $a/book/isbn. ´ Z uvedené ukázky je patrné, zˇ e z relativnˇe jednoduchého vyrazu vznikla pomˇernˇe sloˇzitá kon´ strukce skládaj´ıc´ı se ze dvou FLWOR a pomocné funkce ddo, která eliminuje duplicitn´ı vyskyty ´ uzlu˚ a rˇ ad´ı uzly podle puvodn´ ıho poˇrad´ı v dokumentu. ˚ ddo( let $seq := ddo($a) let $last := fn:count($seq) for $dot at $position in $seq return let $seq := ddo(child::book) let $last := fn:count($seq) for $dot at $position in $seq return child::isbn)

Ukázka 8: Normalizace XPath vyrazu $a/book/isbn ´

XQuery Core napˇr. nepodporuje aritmetické vyrazy, vyrazy pro porovnáván´ı, logické spojky ´ ´ – to vˇse se obvykle nahrazuje volán´ım vestavˇenych funkc´ı, dále nejsou definovány vyrazy ´ ´ XPath, pˇr´ımé konstruktory nebo klauzule order by FLWOR vyraz u. ym ´ ˚ Normalizace je vyborn ´ ´ nástrojem pro specifikaci sémantiky XQuery [7], avˇsak ne vˇzdy je vhodné provést normalizaci pˇresnˇe dle doporuˇcen´ı W3C, jelikoˇz se tak v urˇcitych ´ pˇr´ıpadech muˇ ˚ zeme pˇripravit o efektivnˇejˇs´ı variantu vyhodnocován´ı. Puvodn´ ı zadán´ı práce se omezuje pouze na pˇreklad normalizovanych XQuery dotazu. ˚ ´ ˚ Vysledkem je vˇsak procesor, ktery´ si porad´ı i s mnoha dotazy, které normalizac´ı neproˇsly. Jsou tedy ´ podporovány pˇr´ımé konstruktory, XPath vyrazy a dalˇs´ı konstrukce, které XQuery Core nedefinuje ´ (viz kapitola 4.1).

8

2.3.4

XSLT

Posledn´ım jazykem, ktery´ zde bude sp´ısˇ e pro uplnost zm´ınˇen je XSLT (eXtensible Stylesheet ´ Language Transformation). Nejedná se o dotazovac´ı jazyk v pravém slova smyslu, XSLT je primárnˇe navrˇzen k provádˇen´ı transformac´ı XML dokumentu˚ napˇr. do prezentovatelné podoby ve formˇe HTML. V kombinaci s jazykem XSL Formatting Objects je pak moˇzné provádˇet napˇr. exporty do formátu PDF. Podobnˇe jako u XQuery tvoˇr´ı XPath souˇca´ st jazyka tohoto jazyka. Je zde opˇet pouˇzity´ stejny´ datovy´ model [6]. Podrobnˇejˇs´ı informace o XSLT vˇcetnˇe ukázkovych ´ tutoriálu˚ lze nalézt v [1]. Vzhledem k tomu, zˇ e se vˇsechny tˇri uvedené jazyky (XPath, XQuery a XSLT) cˇ asto pˇrekryvaj´ ´ ı (minimálnˇe v datovém modelu), je bˇezˇ nou prax´ı, zˇ e dostupné implementace (napˇr. Saxon [10] nebo XML Prime [2]) nejsou zamˇerˇ ené pouze na jeden jediny´ jazyk, ale poskytuj´ı komplexn´ı rˇ eˇsen´ı od zpracován´ı XML pˇres v´ıce ruzn u˚ dotazován´ı. ˚ ych ´ zpusob ˚

9

3

XQuery algebra

Nejen v pˇr´ıpadˇe XQuery, ale také napˇr. jazyka SQL, neprob´ıhá vyhodnocován´ı vstupn´ıho dotazu interpretac´ı. Dotaz je obvykle nejprve zkompilován na strom operátoru, ˚ které jsou pozdˇeji v pˇresnˇe urˇceném poˇrad´ı vyhodnocovány. Co to operátory jsou a jakym pracuj´ı popi´ zpusobem ˚ suje právˇe algebra. Algeber existuje celá rˇ ada, liˇs´ı se jak svym ´ uˇ ´ celem (relaˇcn´ı databáze, stromové databáze), tak mnoˇzinou definovanych ´ operátoru˚ a datovym ´ modelem. V souvislosti s XQuery se obvykle pouˇz´ıvá algebra zaloˇzená na n-ticovém datovém modelu. Algebra zde popsaná a pozdˇeji implementovaná vycház´ı z cˇ lánku [16] a kombinuje vyhodnocován´ı na základˇe toku n-tic s vyhodnocován´ım na základˇe toku datovych ´ poloˇzek.

3.1

Datovy´ model

Pˇred vysvˇetlen´ım samotné algebry je nutné nejprve ustanovit datovy´ model a nadefinovat vhodné formáln´ı znaˇcen´ı, které pak bude pouˇz´ıváno k popisu funkˇcnosti jednotlivych ´ operátoru. ˚ Pozdˇeji v implementaˇcn´ıch detailech bude tento model pˇresnˇeji specifikován na tˇr´ıdn´ım diagramu, ktery´ vymez´ı základn´ı datové typy celého procesoru (viz kapitola 4.4). 3.1.1

Poloˇzka (item)

Poloˇzkou muˇ ˚ ze byt ´ libovolná atomická hodnota, tzn. cˇ ´ıslo, textovy´ rˇ etˇezec nebo hodnota typu boolean (true / false). Za poloˇzku se rovnˇezˇ povaˇzuje jakykoli XML uzel, tzn. element, atribut, ´ textovy´ uzel nebo komentárˇ . Entity, sekce CDATA a procesn´ı instrukce jsou zde pro zjednoduˇsen´ı vynechány. Poloˇzky budou formálnˇe znaˇceny jako ik . Ve speciáln´ım pˇr´ıpadˇe, pokud pujde o ato˚ mické hodnoty pak ak . 3.1.2

Sekvence (sequence)

Sekvenc´ı se rozum´ı uspoˇra´ daná multimnoˇzina poloˇzek. Formálnˇe bude sekvence znaˇcena jako S = ⟨i1 , i2 , . . . , in ⟩, kde ik (1 ≤ k ≤ n) je poloˇzka sekvence S a n znaˇc´ı délku této sekvence. Prázdná sekvence, tj. sekvence bez poloˇzek, je znaˇcena jednoduˇse ⟨⟩. V dalˇs´ı cˇ a´ sti textu bude moˇzné pohl´ızˇ et na jednoprvkové sekvence jako na poloˇzky a naopak. 3.1.3

N-tice (tuple)

N-tice pˇredstavuje n-rozmˇerny´ vektor s jednoznaˇcnˇe pojmenovanymi ´ sloˇzkami, které jsou tvoˇreny vyˇ sekvencemi. V terminologii relaˇcn´ıch databáz´ı je ekvivalentem n-tice záznam. ´ se definovanymi ´ Formáln´ı zápis n-tice bude vypadat jako τ = [q1 : S1 , q2 : S2 , . . . , qn : Sn ], kde q1 , q2 , . . . , qn pˇredstavuj´ı oznaˇcen´ı (názvy) sloˇzek a S1 , S2 , . . . , Sn jednotlivé sekvence. Opˇet v návaznosti na relaˇcn´ı databáze bychom mohli rˇ´ıci, zˇ e q1 , q2 , . . . , qn pˇredstavuj´ı názvy atributu. ˚ V pˇr´ıpadˇe, zˇ e n = 0 obsahuje n-tice nulovy´ poˇcet sloˇzek a jde o tzv. prázdnou n-tici, kterou zapisujeme pˇrirozenˇe jako []. 3.1.4

Schéma n-tice

Z pˇredchoz´ı definice vyplyv´ strukturou, tzn. s ruzn ´ a nutnost rozliˇsovat n-tice s ruznou ˚ ˚ ym ´ znaˇcen´ım q1 , q2 , . . . , qn . Takové znaˇcen´ı bude nazyv´ ´ ano schématem Q = ⟨q1 , q2 , . . . , qn ⟩. 10

3.1.5

Tabulka (table)

Stejnˇe tak jako poloˇzky mohly vytvárˇ et sekvence, mohou n-tice vytvárˇ et tabulky. Tabulka tedy pˇredstavuje uspoˇra´ danou multimnoˇzinu n-tic a formálnˇe ji znaˇc´ıme jako σ = ⟨τ1 , τ2 , . . . , τn ⟩. Uvedená definice tabulky obecnˇe umoˇznuje sdruˇzovat libovolné n-tice, tzn. i s ruzn ˇ ˚ ym ´ schématem. Nás ale budou zaj´ımat pˇredevˇs´ım tzv. homogenn´ı tabulky, kde budou m´ıt vˇsechny n-tice stejné schéma.

3.2

Operátory

Operátorem se obecnˇe rozum´ı nˇejaká funkce, která transformuje jeden nebo v´ıce vstupu˚ podle urˇcitych V pˇr´ıpadˇe napˇr. základn´ıch aritmetickych ´ pravidel na vystup. ´ ´ operátoru˚ (+, −, ∗, :) je situace pomˇernˇe snadná – máme dva nezávislé vstupy (levy´ a pravy´ operand), na základˇe kterych ´ operátor spoˇc´ıtá vystup. ´ V pˇr´ıpadˇe XQuery (a nejen XQuery) je ale situace trochu komplikovanˇejˇs´ı. Koneˇcny´ vysledek ´ totiˇz muˇ vstupech, ale také na nˇejakém pˇredem neznámém ˚ ze záviset nejen na nezávislych ´ vysledku mezivypoˇ ´ ´ ctu. Typickym ´ pˇr´ıkladem je bˇezˇ ny´ operátor relaˇcn´ı algebry – selekce, kterému je potˇreba kromˇe nezávislé vstupn´ı mnoˇziny záznamu˚ specifikovat také podm´ınku, za jakych ´ okolnost´ı bude zpracovávany´ záznam souˇca´ st´ı vystupu. ´ Obecná struktura operátoru vypadá následovnˇe: Op[q1 , . . . , qk ]{DOp1 , . . . , DOpl }(Op1 , . . . , Opm ) q1 , . . . , qk jsou statické sloˇzky operátoru. Muˇ specifikaci ˚ ze se jednat napˇr. o názvy promˇennych, ´ datového typu nebo specifikaci názvu XML elementu. Podm´ınkou je, aby byly tyto hodnoty známé jeˇstˇe pˇred zaˇca´ tkem vyhodnocován´ı. DOp1 , . . . , DOpl jsou tzv. závislé operátory (dependent). Jedná se právˇe o ty operátory, které slouˇz´ı pro vypoˇ ´ cet mezivysledku. ´ Op1 , . . . , Opm jsou nezávislé operátory – vstupy. Najdeme je témˇerˇ ve vˇsech operátorech. Vyjimku ´ tvoˇr´ı pouze ty, které vracej´ı nˇejakou staticky danou skalárn´ı hodnotu nebo pˇristupuj´ı ke kontextovym Jak závislé, tak nezávislé operátory jsou vˇzdy operátory. To ´ promˇennym. ´ znamená, zˇ e se na m´ıstˇe operátoru nikdy nevyskytne zˇ a´ dná skalárn´ı hodnota. Pro vytvoˇren´ı skalárn´ı hodnoty existuje speciáln´ı operátor, ktery´ má skuteˇcnou skalárn´ı hodnotu danou pomoc´ı statické sloˇzky (viz kapitola 3.3.1). 3.2.1

Strom operátoru˚

Vzhledem k tomu, zˇ e se operátor obvykle skládá z dalˇs´ıch závislych nebo nezávislych ´ ´ suboperátoru, ˚ vznikne kompilac´ı hierarchie reprezentovatelná stromem, kde kaˇzdy´ operátor pˇredstavuje jeden vrchol a hrana odkaz na suboperátor. Operátory bez závislych ´ a nezávislych ´ suboperátoru˚ utvoˇr´ı listy. Cely´ strom operátoru, kompilace, byv´ ˚ ktery´ je vysledkem ´ ´ a nazyv´ ´ an také jako plán vykonáván´ı dotazu. Ukázkovy´ strom operátoru˚ je moˇzné vidˇet napˇr. na obrázku 2 n´ızˇ e.

11

3.2.2

Vypoˇ ´ cet

Plán vykonáván´ı dotazu udává poˇrad´ı v jakém budou jednotlivé operátory vyhodnocovány. Vypoˇ ´ cet vˇzdy zaˇc´ıná a konˇc´ı koˇrenovým operátorem, tzn. t´ım, ktery´ tvoˇr´ı koˇren stromu. Kaˇzdy´ operátor nejprve vyhodnot´ı vˇsechny své nezávislé vstupy a aˇz poté na jejich základˇe pˇr´ıpadnˇe vyhodnot´ı vstupy závislé, cˇ ili mezivysledky. Podle vysledk u˚ nezávislych vstupu, ´ ´ ´ ˚ d´ılˇc´ıch mezivysledk u˚ nebo pˇr´ıpadnˇe statickych a vrát´ı vysledek. Vysledek ´ ´ sloˇzek provede svou vlastn´ı ulohu ´ ´ ´ koˇrenového operátoru je vysledkem vyhodnocován´ı celého dotazu. ´ 3.2.3

Operátor IN

Kaˇzdy´ operátor je vyhodnocován v rámci nˇejaké kontextové hodnoty – n-tice nebo poloˇzky. Tuto kontextovou hodnotu (zkrácenˇe kontext) nastav´ı nˇejaky´ operátor Op se závislym ´ suboperátorem Opsub pˇri poˇzadavku na jeho vyhodnocen´ı. Obsahuje-li Op vstupy nezávislé, pak jsou tyto vyhod´ celem operátoru IN je pouhé navrácen´ı tohoto kontextu. noceny se stejnym ´ kontextem jako Op. Uˇ

Pˇr´ıklad 1: Význam operátoru IN V ukázkovém stromu na obrázku 2 je IN pouˇzity´ celkem 4 krát. Pro lepˇs´ı orientaci jsou jeho vyskyty rozliˇseny spodn´ım indexem. Co pˇresnˇe které operátory znamenaj´ı nen´ı momentálnˇe ´ duleˇ ˚ zité. Podstatné je uvˇedomit si, ktery´ operátor nastavil kterou kontextovou hodnotu, jeˇz z´ıskáváme operátorem IN. To je moˇzné zjistit jednoduˇse tak, zˇ e budeme procházet strom od konkrétn´ıho listu IN postupnˇe na rodiˇce tak dlouho, neˇz projdeme hranou pˇredstavuj´ıc´ı odkaz na závisly´ suboperátor. Výsledek

𝑀𝑎𝑝𝑇𝑜𝐼𝑡𝑒𝑚

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[attribute, Message] 𝐽𝑜𝑖𝑛 𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠 event

𝑰𝑵𝟏

𝑀𝑎𝑝𝐹𝑟𝑜𝑚𝐼𝑡𝑒𝑚

𝐶𝑎𝑙𝑙[eq]

𝑰𝑵𝟒

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[child, LogEvent]

𝑇𝑢𝑝𝑙𝑒 event

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[attribute, entryType]

𝐶𝑎𝑙𝑙 root

𝑰𝑵𝟐

𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠 event

𝑆𝑐𝑎𝑙𝑎𝑟 error

𝑰𝑵𝟑

Odkaz na závislý suboperátor Odkaz na nezávislý suboperátor

Obrázek 2: Ukázka stromu operátoru˚

12

Pro IN2 je to tedy operátor MapFromItem, pro IN3 operátor Join a pro IN4 operátor MapToItem. IN1 je jediny´ pˇr´ıpad, ktery´ nesouvis´ı s zˇ a´ dnym ´ operátorem se závislym ´ vstupem. Je moˇzné si pˇredstavit, zˇ e koˇrenovy´ operátor MapToItem je vyhodnocován jako závisly´ vstup vzhledem k nˇejaké programové funkci, která zahajuje vypoˇ dotazu s nˇejakym ´ cet vysledku ´ ´ vychoz´ ım kontextem n-tic´ı, jej´ızˇ obsahem mohou byt ´ ´ napˇr. globáln´ı promˇenné nebo kontextovy´ XML uzel nastaveny´ na dotazovany´ XML dokument. V tuto chv´ıli sp´ısˇ e pro zaj´ımavost – strom na obr. 2 je plánem pro XQuery dotaz na ukázce 9. for $event in /EventLogeEvent where $event/@Entry_Type = "Error" return $event/@Message

Ukázka 9: Ukázkovy´ XQuery dotaz

Kompletn´ı seznam operátoru˚ je k dispozici v tabulce 1, která je s malymi upravami pˇrebrána ´ ´ z cˇ lánku [16], tabulky 1. Oproti [16] jsou zde vynechány nepouˇzité operátory, naopak se zde nav´ıc vyskytuj´ı And, Or a IN. Funkce nˇekterych ´ ménˇe známych ´ duleˇ ˚ zitych ´ operátoru˚ bude vysvˇetlena pozdˇeji pˇri popisu kompilaˇcn´ıch pravidel.

3.3

Kompilaˇcn´ı pravidla

Tato podkapitola je vˇenována problematice, jak seskládat strom operátoru˚ tak, aby jeho vyhodnocen´ı vedlo ke korektn´ımu vysledku. Nejprve budou popsány elementárn´ı kompilaˇcn´ı kroky, na ´ nichˇz bude ilustrována funkˇcnost jednoduchych ´ operátoru. ˚ Pozdˇeji pak bude rozebrán pˇreklad sloˇzitˇejˇs´ıch konstrukc´ı – FLWOR a XPath vyraz u. ´ ˚ Pro formáln´ı popis sémantiky kompilaˇcn´ıch pravidel bude pouˇzita následuj´ıc´ı notace: · · · JexprKcontextOp ⇒ Opout

Tato notace pˇredstavuje pˇreklad vyrazu expr na strom operátoru˚ s koˇrenem Opout v kontextu ´ operátoru contextOp (pozor, neplést s kontextovou hodnotou) podle pravidel uvedenych nad ´ cˇ arou. Kontextovy´ operátor contextOp se pouˇz´ıvá pouze pˇri popisován´ı kompilace FLWOR a XPath vyraz u. y´ operátor ´ ˚ Kompilace tˇechto konstrukc´ı je rozdˇelena na nˇekolik cˇ a´ st´ı, kde vysledn ´ pˇrekladu jedné cˇ a´ sti vstupuje jako kontextovy´ operátor do pˇrekladu cˇ a´ sti následuj´ıc´ı. Pravidla nad cˇ arou jsou dvoj´ıho typu. Zápis expr ⇒ Op znamená d´ılˇc´ı pˇreklad vyrazu expr na ´ operátor Op. O tom, jaká kompilaˇcn´ı pravidla se pouˇzij´ı rozhodne aˇz konkrétn´ı podoba vyrazu ´ expr. Druhym ´ pravidlem je prosté pˇriˇrazen´ı ve tvaru Op = (rozklad na operátory). Jedná se o dále nedˇelitelny´ kompilaˇcn´ı krok, ktery´ pˇredstavuje konstrukci podstromu operátoru˚ podle pravé strany a pˇriˇrazen´ı do operátoru na levé stranˇe. 13

Operátory pracuj´ıc´ı nad poloˇzkami Sequence(S1 , S2 , . . . , Sn ) Empty() Scalar[a]() Element[q](Sin ) Attribute[q](a) Text(a) Comment(a) TreeJoin[axis, nodetest](Sin ) Castable[type](a) Cast[type](ain ) TypeMatches[type](Sin ) Var[q] Call[q](S1 , S2 , . . . , Sn ) Cond{Sa , Sb }(boolean) Or{b1 , b2 , . . . , bn }() And{b1 , b2 , . . . , bn }() Operátory pracuj´ıc´ı nad n-ticemi Konstrukce n-tice Tuple[q1 , . . . , qn ](S1 , . . . , Sn ) Spojen´ı n-tice TupleConcat(τ1 , τ2 ) Pˇr´ıstup ke sloˇzce TupleAccess[q](τ) Selekce Select{boolean}(σin ) Kartézsky´ souˇcin Product(σ1 , σ2 ) Spojen´ı Join{boolean}(σ1 , σ2 ) Závislé spojen´ı MapConcat{boolean}(σ1 , σ2 ) Mapován´ı indexu MapIndex[q](σin ) Tˇr´ıdˇen´ı OrderBy[q1 , . . . , qn , mod1 , . . . , modn ](σin ) Hybridn´ı operátory Pˇrevod sekvence na tabulku MapFromItem{τ}(Sin ) Pˇrevod tabulky na sekvenci MapToItem{i}(σin ) Existenˇcn´ı kvantifikátor MapSome{boolean}(Sin ) Vˇseobecny´ kvantifikátor MapEvery{boolean}(Sin ) Speciáln´ı operátory Navrácen´ı kontextu IN() Sekvence Prázdná sekvence Skalárn´ı hodnota XML element XML atribut XML text XML komentárˇ Tree join Test pˇretypovatelnosti Pˇretypován´ı Kontrola datového typu Pˇr´ıstup k promˇenné Volán´ı funkce Alternativa Logicky´ souˇcet Logicky´ souˇcin

Tabulka 1: Operátory algebry

14

→ → → → → → → → → → → → → → → →

Sout Sout a element q {Sin } attribute q {a} text q {a} comment q {a} Sout boolean aout boolean a Sout Sout boolean boolean

→ → → → → → → → →

[q1 : S1 , . . . , qn : Sn ] τout iout σout σout σout σout σout σout

→ → → →

σout Sout boolean boolean

→

τout nebo ıout

Pravidla jsou aplikována pˇresnˇe v takovém poˇrad´ı, jak jdou za sebou. Je potˇreba si uvˇedomit, zˇ e provád´ıme kompilaci, ne vyhodnocován´ı. To znamená, zˇ e vypoˇ ´ cet teprve pˇripravujeme, ale neprovád´ıme. 3.3.1

Kompilace elementárn´ıch konstrukc´ı

Poloˇzka Opout = Scalar[a] a ⇒ Opout Vysledkem kompilace je vˇzdy strom operátoru. ´ ˚ Jak jiˇz bylo uvedeno, v tomto stromu se nikdy ani na stranˇe závislych, ani na stranˇe nezávislych ´ ´ operátoru˚ nevyskytuje skalárn´ı hodnota. Jakoukoli skalárn´ı hodnotu je potˇreba nejprve zkonstruovat operátorem Scalar, kterému skuteˇcnou poˇzadovanou hodnotu pˇredáme jako staticky´ parametr. Promˇenná Opout = Var[v] $v ⇒ Opout Pˇr´ıstup k promˇenné v jednoduˇse kompilujeme na operátor Var[v]. Jak bude ale pozdˇeji vysvˇetleno, prakticky se bude tento operátor vˇzdy nahrazovat pˇr´ıstupem k v sloˇzce kontextové n-tice. Sekvence

Opout

expr1 ⇒ Op1 .. . exprn ⇒ Opn = Sequence(Op1 , . . . , Opn )

(expr1 , . . . , exprn ) ⇒ Opout Jednotlivé vyrazy expr1 , . . . , exprn nemus´ı ve vysledku dávat pouze poloˇzky. Vˇsechny d´ılˇc´ı ´ ´ sekvence spoj´ı operátor Sequence do jedné vysledn´ e (viz obrázek 3). Znamená to, zˇ e napˇr´ıklad ´ zápis (1,(2,3),(4,(5,6))) znamená totézˇ co (1,2,3,4,5,6). Datovy´ model neumoˇznuje, ˇ aby poloˇzka obsahovala vnoˇrenou sekvenci. Funkce

Opout

arg1 ⇒ Op1 .. . argn ⇒ Opn = Call[ f ](Op1 , . . . , Opn )

f (arg1 , . . . , argn ) ⇒ Opout Pˇri kompilaci pˇrecház´ı volán´ı funkce pˇrirozenˇe na operátor Call. Tento operátor má statickym ´ parametrem urˇcen název funkce f a obecnˇe n nezávislych ´ vstupu˚ urˇcuje hodnoty argumentu. ˚

15

(1, 2, 3, 4, 5, 6)

ܵ݁‫݁ܿ݊݁ݑݍ‬ଵ

݈ܵܿܽܽ‫ݎ‬ሾ1ሿ

(2, 3)

ܵ݁‫݁ܿ݊݁ݑݍ‬ଶ


ܵ݁‫݁ܿ݊݁ݑݍ‬ଷ



(4, 5, 6)

ܵ݁‫݁ܿ݊݁ݑݍ‬ସ


(5, 6)


Obrázek 3: Kompilace sekvence Aritmetické vyrazy ´ Do této chv´ıle moˇzná nemus´ı byt e jasné, kam se vlastnˇe podˇely aritmetické operátory. V ta´ uplnˇ ´ bulce 1 byly nadefinovány nejruznˇ ˚ ejˇs´ı speciáln´ı operátory, ale zˇ a´ dné z nich nepˇripom´ınaj´ı napˇr. operátor souˇctu, rozd´ılu atd. Urˇcitˇe to nen´ı t´ım, zˇ e by snad XQuery takové vyrazy nepodporoval. ´ Maly´ trik spoˇc´ıvá v tom, zˇ e lze veˇskeré tyto operace nahradit volán´ım vestavˇenych ´ funkc´ı. Pˇri kompilaci souˇctu, rozd´ılu, souˇcinu, pod´ılu nebo operace modulo se tedy jednoduˇse zavolaj´ı dvouparametrové funkce add, sub, mul, div nebo mod. O nahrazen´ı aritmetickych ´ operátoru˚ volán´ım vestavˇenych ´ funkc´ı se bˇezˇ nˇe stará normalizace (viz kapitola 2.3.3) – XQuery Core skuteˇcnˇe aritmetické vyrazy nepodporuje. ´ Konkrétnˇe napˇr. pro operaci souˇctu bude pˇreklad vypadat takto:

Opout

expra ⇒ Opa exprb ⇒ Opb = Call[add](Opa , Opb )

expra + exprb ⇒ Opout Levá i pravá strana souˇctu bude pˇreloˇzena na pomocné operátory Opa a Opb , které pak nastav´ıme na vstup operátoru Call se staticky danym ´ názvem funkce add. Unárn´ı minus lze jednoduˇse zkompilovat stejnˇe jako binárn´ı variantu s t´ım, zˇ e na levé stranˇe bude 0 (po kompilaci na operátor Scalar). Vyrazy porovnáván´ı ´ XQuery jazyk rozliˇsuje celkem 4 typy porovnáván´ı – obecné porovnán´ı, hodnotové porovnán´ı, porovnán´ı Xml uzlu a porovnán´ı poˇrad´ı Xml uzlu. Nejˇcastˇeji je moˇzné setkat se s obecnym ´ porovnán´ım, kde srovnáváme obsah dvou sekvenc´ı S1 a S2 . Jde o standardn´ı zápis symbolu˚ =, !=, <, >, <= a >=, které se pˇri kompilaci pˇreloˇz´ı na volán´ı dvouargumentovych ´ funkc´ı eq, neq, lt, gt, le a ge. Tyto funkce vracej´ı pravdivou booleovskou hodnotu za pˇredpokladu, zˇ e zadaná rovnost nebo nerovnost vyhov´ı pro alesponˇ jednu dvojici poloˇzek i1 ∈ S1 a i2 ∈ S2 . Ve vˇetˇsinˇe pˇr´ıpadu˚ pouˇzit´ı jsou S1 a S2 jednoprvkové. Druhym e ´ typem porovnán´ı je tzv. hodnotové, kdy nesrovnáváme dvˇe sekvence, ale vyhradnˇ ´ 16

dvˇe poloˇzky. Pro tato porovnán´ı má XQuery speciáln´ı kl´ıcˇ ová slova eq, neq, lt, gt, le a ge, které se pouˇz´ıvaj´ı naprosto stejnˇe jako standardn´ı symboly u obecného porovnán´ı. Pˇri kompilaci se hodnotové porovnán´ı pˇreloˇz´ı na volán´ı funkc´ı veq, vneq, vlt, vgt, vle a vge. Dalˇs´ı dva uvedené typy porovnán´ı nejsou v této práci implementovány, avˇsak jejich pˇreklad by probˇehl velice podobnˇe opˇet na volán´ı funkc´ı. Logické vyrazy ´ Logické operace (logicky´ souˇcin a souˇcet) by sice bylo moˇzné podobnym pˇrepsat na ´ zpusobem ˚ funkce and a or, nicménˇe pˇriˇsli bychom tak o podstatnou vyhodu moˇznosti l´ıného vyhodno´ cován´ı. Pˇri zpracováván´ı operátoru Call se chtˇe nechtˇe nejprve mus´ı vyhodnotit vˇsechny vstupy, coˇz je u logickych u˚ obvykle zbyteˇcné. Proto zde pˇreci jen pouˇzijeme speciáln´ı operátory ´ vyraz ´ Or a And, které jednotlivé vstupy vyhodnocuj´ı postupnˇe. Jakmile logicky´ souˇcet naraz´ı na ,,true“ nebo logicky´ souˇcin na ,,false“, dojde k okamˇzitému navrácen´ı vysledku. ´

Opout

arg1 ⇒ Op1 .. . argn ⇒ Opn = And{Op1 , . . . , Opn }()

Opout

arg1 and . . . and argn ⇒ Opout

arg1 ⇒ Op1 .. . argn ⇒ Opn = Or{Op1 , . . . , Opn }()

arg1 or . . . or argn ⇒ Opout

XML konstruktory Jak bylo v kapitole 2.3.2 uvedeno, v dotazech XQuery muˇ ˚ zeme pomoc´ı pˇr´ımych ´ nebo nepˇr´ımych ´ konstruktoru˚ vytvárˇ et vlastn´ı XML uzly. Na obrázek 4 lze pohl´ızˇ et dvˇema zpusoby – bud’ jako na sestaven´ı stromu operátoru˚ podle ˚ vstupn´ıho dotazu nebo jako na vysledek vyhodnocen´ı uvedeného stromu. Jelikoˇz v dotazu nejsou ´ pouˇzité zˇ a´ dné charakteristické konstrukce pro XQuery, bude vyhodnocován´ı spoˇc´ıvat pouze v parsován´ı XML na DOM a zpˇetné serializaci DOM na textovy´ rˇ etˇezec. Ukázkový XML Text

Odpovídající strom operátorů

𝐸𝑙𝑒𝑚𝑒𝑛𝑡[a]

𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒

𝐴𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒[id]

𝑆𝑐𝑎𝑙𝑎𝑟[1]

𝐶𝑜𝑚𝑚𝑒𝑛𝑡

𝐸𝑙𝑒𝑚𝑒𝑛𝑡[b]

𝑆𝑐𝑎𝑙𝑎𝑟[Komentář]





Obrázek 4: Kompilace XML

17

𝐸𝑙𝑒𝑚𝑒𝑛𝑡[b]

𝑇𝑒𝑥𝑡

𝑆𝑐𝑎𝑙𝑎𝑟[Text]

3.3.2

FLWOR vyrazy ´

Kompilaˇcn´ı pravidla budou aplikována postupnˇe pˇresnˇe v takovém poˇrad´ı, v jakém jdou za sebou jednotlivé klauzule. Gramatika XQuery umoˇznuje nˇekolikrát zopakovat klauzuli for a ˇ let v libovolném poˇrad´ı, následuje nepovinná omezuj´ıc´ı podm´ınka where, nepovinné setˇr´ızen´ı order by a povinná klauzule return. Cely´ FLWOR vyraz bude zpracováván pomoc´ı operátoru˚ ´ pracuj´ıc´ıch nad tabulkami, pouze v pˇr´ıpadˇe vstupn´ıho vyrazu nebo vypoˇ potˇrebovat ´ ´ ctu vysledku ´ ony tzv. hybridn´ı operátory. Pravidla pro pˇreklad jsou s malymi upravami pˇrevzata z [16]. ´ ´ for Bude iterována promˇenná x pˇres vstupn´ı sekvenci poloˇzek danou vyrazem expr. Vstupn´ı sekvence ´ poloˇzek muˇ vnoˇreného XPath ˚ ze byt ´ staticky zadána nebo muˇ ˚ ze vycházet napˇr´ıklad z vysledku ´ nebo FLWOR vyrazu. ´ expr ⇒ Op1 Jas TKOp1 ⇒ Op1 Op2 = MapFromItem{Tuple[x](IN)}(Op1 ) Op2 = MapIndex[pos](Op2 ) Op3 = MapConcat{Op2 }(Op0 ) JclausesKOp3 ⇒ Opout

Jfor $x [as T] [at $pos] in expr clausesKOp0 ⇒ Opout V prvn´ım kroku je zkompilován vyraz expr na pomocny´ operátor Op1 . Nejedná se samozˇrejmˇe ´ o jeden operátor, ale o cely´ podstrom s koˇrenem Op1 . Druhy´ krok je nepovinny. ´ Provád´ı se v pˇr´ıpadˇe nutnosti oˇsetˇren´ı datového typu vstupn´ı sekvence. Klauzuli as tato implementace kvuli ˚ zjednoduˇsenému typovému systému nepodporuje (viz kapitola 4.4.1). Ve tˇret´ım kroku je proveden pˇrechod od sekvence poloˇzek k jednoatributové tabulce, tzn. ˇ k tabulce obsahuj´ıc´ı n-tice s jedinou sloˇzkou x. Ctvrt y´ krok je opˇet nepovinny. ´ Záleˇz´ı na tom, zda hodláme vyuˇz´ıt moˇznosti poziˇcn´ı promˇenné at $pos. Pokud ano, pak operátorem MapIndex do vznikaj´ıc´ı tabulky jednoduˇse pˇridáme sloˇzku pos s celoˇc´ıselnou hodnotou v rozmez´ı {1..|expr|}, tzn. zajist´ıme oˇc´ıslován´ı jednotlivych ´ n-tic. V zápise kompilaˇcn´ıho pravidla je v tomto kroku pˇr´ıpadnˇe pˇrepsán pomocny´ operátor Op2 . Páty´ krok vyuˇz´ıvá operátor MapConcat. Ten zajist´ı, zˇ e prozat´ım pˇripraveny´ vypoˇ ´ cet v operátoru Op2 bude proveden pro kaˇzdou n-tici z vysledku operátoru, ktery´ vznikl kompi´ lac´ı pˇredchoz´ı for nebo let klauzule. Princip cˇ innosti MapConcat je vysvˇetlen n´ızˇ e. Posledn´ı krok pˇrekladu for nepˇredstavuje nic jiného, neˇz zpracován´ı zbytku FLWOR vyrazu ´ s t´ım, zˇ e operátor Op3 bude dalˇs´ımu kroku pˇredán jako kontextovy. ´ Je zde jedna drobná komplikace, na kterou nesm´ıme zapomenout. Ve zpracován´ı zbytku FLWOR vyrazu mus´ı byt ´ ´ jakykoli ´ pˇr´ıstup k promˇenné x kompilován ne na operátor Var[x], ale na TupleAccess[x](IN), tj. pˇr´ıstup ke sloˇzce x kontextové n-tice. Stejné pravidlo bude pˇr´ıpadnˇe platit také pro poziˇcn´ı promˇennou pos. Substituce prob´ıhá z toho duvodu, zˇ e ve skuteˇcnosti neexistuje zˇ a´ dná pamˇet’ová struktura, která ˚ by si pamatovala hodnoty promˇennych ´ samostatnˇe. Vˇsechny hodnoty jsou obsaˇzeny ve vznikaj´ıc´ı tabulce n-tic. Operátor MapConcat muˇ ˚ ze byt ´ obt´ızˇ nˇejˇs´ı na správné pochopen´ı. Na obrázku 5 je znázornˇen princip jeho cˇ innosti. Tento operátor pˇreb´ırá nezávislym ´ vstupem tabulku. Pro kaˇzdou n-tici ze 18

vstupn´ı tabulky vyhodnot´ı závisly´ operátor, ktery´ v tomto pˇr´ıpadˇe produkuje dalˇs´ı tabulku o 2 ntic´ıch. N-tice ze vstupn´ı tabulky je ve vypoˇ ´ ctu závislého suboperátoru dostupná v kontextu. Zápis #a je zkrácen´ım pˇr´ıstupu ke sloˇzce a kontextové n-tice. Z ukázky je patrné, zˇ e cˇ innost MapConcat je velmi podobná kartézskému souˇcinu (operátor Product), obsah pravé pˇripojované tabulky vˇsak závis´ı na obsahu levé nezávislé tabulky. 𝐚 1 1 2 2 3 3

𝐛 4 4 5 5 6 6

𝐜 5 4 7 10 9 18

𝑀𝑎𝑝𝐶𝑜𝑛𝑐𝑎𝑡

𝐜 #𝑎 + #𝑏 #𝑎 ∙ #𝑏

𝐚 1 2 3

𝐛 4 5 6

ˇ Obrázek 5: Cinnost operátoru MapConcat

let ´ Klauzule let zavád´ı do FLWOR vyrazu závislou promˇennou y. Ukolem operátoru˚ je v tomto ´ pˇr´ıpadˇe pˇridat do vznikaj´ıc´ı tabulky sloˇzku y s hodnotou vypoˇctenou podle expr. expr ⇒ Op1 Jas TKOp1 ⇒ Op1 Op2 = MapConcat{Tuple[y](Op1 )}(Op0 ) JclausesKOp3 ⇒ Opout

Jlet $y [as T] := expr clausesKOp0 ⇒ Opout V prvn´ım kroku je pˇreloˇzen vyraz expr do operátoru Op1 . Druhy´ krok opˇet pˇredstavuje oˇsetˇren´ı ´ datového typu, kterym nebudeme. Pomoc´ı MapConcat dojde k pˇripojen´ı jednosloˇzkové ´ se zabyvat ´ n-tice [y : expr] k tabulce vzniklé vyhodnocen´ım kontextového operátoru Op0 , tzn. tabulce, která je vysledkem vˇsech pˇredchoz´ıch klauzul´ı for a let pˇrekládaného FLWOR vyrazu. Nakonec opˇet ´ ´ pokraˇcujeme zpracován´ım zbytku, kde stejnˇe jako v pˇr´ıpadˇe for budeme nahrazovat jakykoli ´ vyskyt promˇenné y pˇr´ıstupem ke sloˇzce y kontextové n-tice. ´ V cˇ em se tedy zásadnˇe liˇs´ı zpracován´ı klauzul´ı for a let? Rozd´ıl je ve zpracován´ı vstupn´ıho vyrazu expr. Zat´ımco u for pˇrevád´ıme sekvenci danou expr na tabulku s n-ticemi obsahuj´ıc´ımi ´ jednotlivé d´ılˇc´ı poloˇzky sekvence, u klauzule let necháváme sekvenci v celku a tvoˇr´ıme jedinou n-tici se sloˇzkou y, která tuto sekvenci obsahuje. Z klauzule let je patrné, proˇc datovy´ model umoˇznuje sloˇzkám n-tic obsahovat celé sekvence. ˇ 19

where Zat´ımco pˇredchoz´ı for a let slouˇzily k vytvoˇren´ı tabulky, where bude vzniklou tabulku podle dané podm´ınky pouze redukovat. Základem zpracován´ı této klauzule je vˇseobecnˇe známy´ operátor relaˇcn´ı algebry Select. expr ⇒ Op1 Op2 = Select{Op1 }(Op0 ) JclausesKOp2 ⇒ Opout

Jwhere expr clausesKOp0 ⇒ Opout Vyraz expr je tedy zkompilován na pomocny´ operátor Op1 . Kontextovy´ operátor Op0 , cˇ ili ten, ´ ktery´ produkuje tabulku podle pˇredchoz´ıch let a for, bude slouˇzit jako nezávisly´ vstup do operátoru Select, závislym ´ vstupem selekce bude podm´ınka zkompilovaná v Op1 . Pokraˇcujeme dalˇs´ı klauzul´ı a jelikoˇz nedoˇslo k zˇ a´ dnému zavádˇen´ı promˇenné, nen´ı potˇreba oˇsetˇrovat substituci. order by expr1 ⇒ Op1 .. . exprn ⇒ Opn Op0 = MapConcat{Tuple[o1 , . . . , on ](Op1 , . . . , Opn )}(Op0 ) Op0 = OrderBy[o1 , . . . , on , modi f ier1 , . . . , modi f iern ](Op0 ) JclausesKOp0 ⇒ Opout

Jorder by expr1 modi f ier1 , . . . , exprn modi f iern KOp0 ⇒ Opout

Nejprve budou zkompilovány vˇsechny vyrazy expr1 . . . exprn , podle kterych ´ ´ budeme provádˇet tˇr´ıdˇen´ı, na operátory Op1 . . . Opn . Poté dojde k pˇripojen´ı n-tic se sloˇzkami jednotlivych ´ vypoˇctenych ´ vyraz u˚ k vysledku Op0 . Teprve pak je moˇzné aplikovat operátor OrderBy, kterému staticky ´ ´ nadefinujeme, podle kterych sloˇzek n-tic v tabulce má tˇr´ıdit a jakym zpusobem, tzn. vze´ ´ ˚ stupnˇe (ascending), sestupnˇe (descending), popˇr. jak má byt ´ tˇr´ıdˇena prázdná sekvence (empty least nebo empty greatest). Opˇet pokraˇcujeme zpracováván´ım zbytku FLWOR vyrazu, kterym ´ ´ je v tuto chv´ıli jistˇe pouze klauzule return. Drobnou komplikac´ı je pouze to, zˇ e zde do tabulky mapujeme sloˇzky n-tic o1 , . . . , on , o které si sám uˇzivatel neˇza´ dal. Je potˇreba dát pozor, abychom se nevhodnou volbou pojmenován´ı sloˇzky n-tice, nedostali do konfliktu s nˇejakou uˇzivatelem definovanou promˇennou. return expr ⇒ Op1 Opout = MapToItem{Op1 }(Op0 ) Jreturn exprKOp0 ⇒ Opout Posledn´ı krok pˇrekladu FLWOR je v celku jednoduchy. ´ Nejprve dojde ke kompilaci vyrazu, ´ ktery´ pˇredstavuje vypoˇ Pomoc´ı operátoru MapToItem je zajiˇstˇeno, ´ cet jedné d´ılˇc´ı poloˇzky vysledku. ´ zˇ e tento vyraz bude vyhodnocen pro kaˇzdou n-tici z vysledku kontextového operátoru Op0 . ´ ´ Vˇsechny d´ılˇc´ı vysledky nakonec utvoˇr´ı vyslednou sekvenci. ´ ´

20

Na obrázku 6 je v blokovém schématu shrnuto, jakym prob´ıhá pˇreklad jednotlivych ´ zpusobem ˚ ´ klauzul´ı podle vyˇ pravidel. Pro zjednoduˇsen´ı je vynechána klauzule order by. ´ se uvedenych ´ Bˇehem celé kompilace FLWOR se pracuje s promˇennou kontextového operátoru. Kaˇzdá klauzule tuto promˇennou zaobal´ı jinym ´ operátorem nebo v´ıce operátory. let

for MapConcat { MapFromItem { CreateTuple[var](IN) } ( expandExpr výrazu ) } (

where

MapConcat { CreateTuple[var] ( expandExpr výrazu ) } (

return

Select { expandExpr výrazu } (

MapToItem { expandExpr výrazu } (

)

)

)

IN() )

Obrázek 6: Blokové schéma kompilace FLWOR Následuje souhrnná ukázka, která demonstruje vysledek vˇetˇsiny vyˇ ´ ´ se nadefinovanych ´ kompilaˇcn´ıch pravidel.

Pˇr´ıklad 2: Souhrnný pˇr´ıklad kompilace Pokusme se nyn´ı pˇreloˇzit následuj´ıc´ı vyraz: ´ for $i in 1 to 10 let $j := $i * 2 where $j > 10 return $i

Bˇehem pˇrekladu bude postupnˇe vytvárˇ en strom na obrázku 7 n´ızˇ e. V tabulce 2 jsou uvedeny mezivysledky pˇri vykonáván´ı dotazu, které se vztahuj´ı k vyznaˇcenym ´ ´ m´ıstum ˚ ve stromu operátoru. ˚ Pˇreklad for a rozsahového vyrazu ´ Pˇreklad celého vyrazu je zahájen kompilac´ı for. Nejprve je pˇreloˇzen vyraz 1 to 10 na volán´ı ´ ´ dvouparametrové funkce range(low, high). Jedná se o jednoduché kompilaˇcn´ı pravidlo pro pˇreklad rozsahu hodnot, které zde dosud nebylo uvedeno. Funkce range vrac´ı sekvenci celych ´ cˇ ´ısel od definované spodn´ı hodnoty podle parametru low po horn´ı hodnotu high s krokem 1. Mezivysledek po vyhodnocen´ı Call[range] je moˇzné vidˇet v tabulce 2 jako result2 . Operátor ´ MapFromItem v kombinaci s Tuple[i] zajist´ı, zˇ e bude vzniklá sekvence transformována na tabulku s n-ticemi o jedné sloˇzce i. Vysledek po MapFromItem je oznaˇcen jako result3 . ´ Cely´ dosavadn´ı mezivysledek byl poˇc´ıtán v rámci vyhodnocen´ı závislé cˇ a´ sti operátoru ´ MapConcat pro kaˇzdou n-tici z jeho nezávislého vstupu, ktery´ je momentálnˇe tvoˇren IN. Tento IN se nevztahuje k zˇ a´ dnému závislému vstupu jiného operátoru, ale k programové funkci, která 21

celé vyhodnocován´ı zahájila (viz kapitola 3.2.3). Pro zjednoduˇsen´ı muˇ ˚ zeme pˇredpokládat, zˇ e tato funkce nastavila kontextovou n-tici jako prázdnou (result1 ). Vysledek operátoru MapConcat, ´ resp. celé klauzule for je uveden v result4 .

result7


překlad return 𝑇𝑢𝑝𝑙𝑒[𝑖]

𝐼𝑁

result6

𝑆𝑒𝑙𝑒𝑐𝑡[𝑖]

překlad where

𝐶𝑎𝑙𝑙[𝑔𝑡] result5


𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠[𝑗]


překlad let 𝐼𝑁

result4

𝑀𝑎𝑝𝐶𝑜𝑛𝑐𝑎𝑡 𝑇𝑢𝑝𝑙𝑒[𝑗] result3

result1

𝐼𝑁


𝐶𝑎𝑙𝑙[mul]

𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠[𝑖]

result2

𝐶𝑎𝑙𝑙[𝑟𝑎𝑛𝑔𝑒]


𝑇𝑢𝑝𝑙𝑒[𝑖] 𝐼𝑁



𝐼𝑁

překlad for

Odkaz na závislý suboperátor Odkaz na nezávislý suboperátor

Obrázek 7: Kompilace FLWOR result1 = [] i 1 result3 = 2 .. . 10

result2 = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) i

i

1 result4 = 2 .. . 10

1 result5 = 2 .. . 10

j 1 4 .. . 20

result7 = (6, 7, 8, 9, 10) Tabulka 2: Mezivysledky vyhodnocován´ı ´

22

i 6 7 result6 = 8 9 10

j 12 14 16 18 20

Pˇreklad let a aritmetického vyrazu ´ Následuje pˇreklad klauzule let. Nejprve je pˇreloˇzen d´ılˇc´ı vyraz $i * 2. Podle pravidla ´ pro kompilaci aritmetického vyrazu násoben´ı v kapitole 3.3.1 se tento vyraz pˇrekládá na ´ ´ volán´ı funkce mul. Prvn´ı cˇ initel je dán promˇennou i, m´ısto operátoru pro pˇr´ıstup k promˇenné Var[i] se d´ıky substituci uplatn´ı operátor TupleAccess[i] nad kontextovou n-tic´ı. Druhy´ cˇ initel tvoˇr´ı operátor generuj´ıc´ı skalárn´ı hodnotu Scalar[2]. Operátor MapConcat zajist´ı, zˇ e je tento pˇripraveny´ vypoˇ ´ cet spuˇstˇen nad kaˇzdou n-tic´ı z jeho nezávislého vstupu, ktery´ je tvoˇren vystupn´ ım operátorem z pˇrekladu pˇredchoz´ı klauzule for. Mezivysledek po vyhodnocen´ı ´ ´ MapConcat, cˇ ili celé klauzule let ukazuje opˇet tabulka 2, promˇenná result5 . Pˇreklad where s vyrazem pro porovnáván´ı ´ Porovnán´ı > se podle odstavce 3.3.1 pˇrekládá na volán´ı funkce gt. Nezávisly´ vstup selekce tvoˇr´ı vystup pˇredchoz´ı klauzule let. Vysledek po selekci ukazuje v tabulce mezivysledk u˚ promˇenná ´ ´ ´ result6 . return Posledn´ı klauzul´ı je return. Nejprve je zkompilován vyraz pro vypoˇ ´ ´ cet jedné d´ılˇc´ı poloˇzky. Jedná se pouze o pˇr´ıstup k promˇenné, ktery´ se vzhledem k substituci pˇrevád´ı na pˇr´ıstup do pˇr´ısluˇsné sloˇzky kontextové n-tice. MapConcat tento vypoˇ ´ cet spust´ı nad kaˇzdou n-tic´ı z tabulky vzniklé pˇredchoz´ı klauzul´ı where. Vˇsechny vysledn´ e poloˇzky utvoˇr´ı sekvenci, která je vystupem ´ ´ celého dotazu, viz promˇenná result7 .

3.3.3

XPath vyrazy ´

Pokud by algebra pracovala pouze s XQuery core, pak by se kompilace XPath vyraz u˚ omezila ´ jen na zpracován´ı axis kroku, lze normalizac´ı pˇrevést na FLWOR. ˚ jelikoˇz predikáty a filter vyrazy ´ Plán dotazu lze ale sestavit rovnou z XPath v puvodn´ ı podobˇe. ˚ Gramatika povoluje pouˇz´ıván´ı zkratkovych ´ zápisu˚ (viz kapitola 2.3.1). Zkrácené zápisy lze ale jednoduˇse rozepsat na plny´ tvar, takˇze se jim dále vˇenovat nebudeme. Podrobnˇejˇs´ı informace lze nalézt v [4]. Na obrázku 8 je pˇr´ıklad XPath vyrazu s pouˇzit´ım zkratkovych ´ ´ zápisu˚ a po rozepsán´ı. Obrázek dále zachycuje rozklad vyrazu na jednotlivé kroky a predikáty. ´ /library//book[@id = "10"]/author/(first/text() + last/text()) /child::library/descendant-or-self::node()/child::book[attribute::id = "10"]/child::author/ (child::first/child::text() + child::last/child::text())

axis krok child::library

axis krok

axis krok

descendant-or-self::node()

child::book

predikát attribute::id = “10“

axis krok child::author

Obrázek 8: Struktura XPath vyrazu ´

23

filter výraz child::first/child::text() + child::last/child::text()

Stejnˇe jako v pˇr´ıpadˇe FLWOR prob´ıhá kompilace XPath po cˇ a´ stech za pouˇzit´ı kontextového operátoru. Zahájen´ı pˇrekladu 1. V pˇr´ıpadˇe, zˇ e se na zaˇca´ tku vyrazu nacház´ı rovnou axis step, je kontextovy´ operátor inicia´ lizován na pˇr´ıstup k promˇenné Var[dot]. 2. Pokud je vyraz uvozen jednoduchym ´ ´ lom´ıtkem, zaˇc´ıná vyhodnocován´ı od koˇrene XML dokumentu. Koˇren muˇ ˚ zeme snadno obdrˇzet volán´ım vestavˇené funkce Call[root](). 3. Jestliˇze se na zaˇca´ tku nacház´ı dvojité lom´ıtko, je potˇreba naˇc´ıst XML dokument a rovnou z nˇej vybrat vˇsechny potomky pomoc´ı TreeJoin[descendant-or-self, node()](Call[root]()). Axis kroky Opout = TreeJoin[axis, nodetest](Op0 ) Jaxis :: nodetestKOp0 ⇒ Opout Kompilace axis step je pˇr´ımoˇcará. Staˇc´ı pouze aplikovat operátor TreeJoin, ktery´ je pro tento uˇ ´ cel v podstatˇe urˇceny. ´ Operátor TreeJoin pracuje tak, zˇ e pro kaˇzdy´ XML uzel ze vstupn´ı sekvence provede poˇzadovany´ pohyb po dané ose (axis), cˇ ´ımˇz vznikne mezivysledek obsa´ huj´ıc´ı mnoˇzinu XML uzlu. jsou nakumulovány do celkové vysledn´ e ˚ Vˇsechny mezivysledky ´ ´ (uspoˇra´ dané) mnoˇziny, pˇriˇcemˇz poˇrad´ı uzlu˚ mus´ı byt ım dokumentu ´ takové, jako bylo v puvodn´ ˚ a mus´ı byt Eliminace duplicit je nutná z duvodu v´ıce následuj´ıc´ıch ´ eliminovány duplicitn´ı vyskyty. ´ ˚ axis kroku, e mnoˇzinˇe ˚ kdy by mohlo doj´ıt k situaci, zˇ e se jeden konkrétn´ı uzel vyskytne ve vysledn´ ´ dvakrát. Kromˇe toho je provedena filtrace vystupn´ ı mnoˇziny na základˇe daného testu uzlu (staticky´ ´ argument operátoru – nodetest). Jedná se nejˇcastˇeji o jmenny´ test elementu. Existuje ale celá rˇ ada testu˚ – testy na atributy, textové uzly, komentárˇ e, na libovolny´ uzel a dalˇs´ı. ˇ Cinnost operátoru TreeJoin byv´ ´ a nazyv´ ´ ana jako navigace. Filter vyrazy ´ f ilterExpr ⇒ Op1 Op2 = MapFromItem{Tuple[dot](IN)}(Op0 ) Op3 = MapConcat{Op2 }(IN) Opo ut = MapToItem{Op1 }(Op3 ) J f ilterExprKOp0 ⇒ Opout Nejprve je zkompilován samotny´ filter vyraz na pomocny´ operátor Op1 . Poté je zajiˇstˇeno ´ pˇreveden´ı vstupn´ı sekvence reprezentované operátorem Op0 pomoc´ı MapFromItem na tabulku, která je následnˇe pˇrimapována pomoc´ı MapConcat k aktuáln´ı kontextové n-tici. Kontextová ntice totiˇz muˇ FLWOR. Nakonec je ˚ ze obsahovat nˇejaké platné promˇenné napˇr. vnˇejˇs´ıho vyrazu ´ aplikován operátor MapToItem. Ten postupnˇe nad n-ticemi v tabulce jednak provede samotny´ vypoˇ ktery´ je v tuto chv´ıli zkompilovany´ v Op1 , a jednak provede pˇreveden´ı zpˇet ´ cet filter vyrazu, ´ na sekvenci poloˇzek.

24

Predikáty ´ V pˇr´ıpadˇe kompilace predikátu˚ algebra opˇet vyuˇzije operátory pracuj´ıc´ı v prostoru n-tic. Uplnˇ e stejnˇe jako u filter vyraz u˚ bude i zde potˇreba zajistit dostupnost kontextového uzlu a vˇsech ´ aktuálnˇe platnych ´ promˇennych ´ dvojic´ı operátoru˚ MapFromItem a MapConcat. Poté jednoduˇse vybereme vyhovuj´ıc´ı záznamy operátorem Select a provedeme pˇrechod zpˇet od tabulky k sekvenci. Jedinou vyraznˇ ejˇs´ı komplikac´ı je, zˇ e se v predikátu nemus´ı nutnˇe nacházet ´ pouze logicky´ vyraz. Specifikace XPath totiˇz umoˇznuje, aby typ vnitˇrn´ıho vysledku predikátu byl ´ ˇ ´ kromˇe logického vyrazu také celé cˇ ´ıslo nebo sekvence. ´ Je-li vnitˇrn´ım mezivysledkem celé cˇ ´ıslo, pak toto cˇ ´ıslo pˇredstavuje poˇrad´ı jediného uzlu ze ´ vstupn´ı sekvence, ktery´ bude propuˇstˇen dále. Jinak rozhodne tzv. efektivn´ı booleovská hodnota sekvence, pro jej´ızˇ vypoˇ ´ cet plat´ı následuj´ıc´ı pravidla: 1. Obsahuje-li sekvence jedinou poloˇzku typu boolean, pak efektivn´ı booleovská hodnota je dána hodnotou této poloˇzky. 2. Obsahuje-li sekvence jedinou poloˇzku typu integer nebo double, nabyv´ ´ a efektivn´ı booleovská hodnota pravdy právˇe kdyˇz dané cˇ ´ıslo nen´ı nulové. 3. Obsahuje-li sekvence jedinou poloˇzku typu string, je efektivn´ı booleovská hodnota pravdivá v pˇr´ıpadˇe neprázdného rˇ etˇezce. 4. V pˇr´ıpadˇe jakékoli obecné sekvence rozhodne o efektivn´ı booleovské hodnotˇe jej´ı neprázdnost. Normalizace pˇrevád´ı predikáty XPath na where klauzule FLWOR vyraz u, ´ ˚ pˇriˇcemˇz pro alternativu dle datovych je vˇsak relativnˇe ´ typu˚ vyuˇz´ıvá konstrukci typeswitch. Tenhle zpusob ˚ komplikovany´ a pˇridává do celého vyrazu zbyteˇcnˇe mnoho operátoru˚ nav´ıc. Pro celou logiku ´ vyhodnocen´ı pravdivostn´ı hodnoty pro mezivysledek predikátu byla vytvoˇrena jednoduchá ve´ stavˇená funkce predicate. predicateExpr ⇒ Op1 Op2 = MapFromItem{Tuple[dot](IN)}(Op0 ) Op3 = MapConcat{Op2 }(IN) Op4 = Select{Call[predicate](Op1 )}(Op3 ) Opout = MapToItem{TupleAccess[dot](IN)}(Op4 ) JpredicateExprKOp0 ⇒ Opout Kompilace tedy probˇehne z hlediska pˇrevodu mezi n-ticemi a poloˇzkami stejnˇe jako u filter vyraz u, ´ ˚ pouze dojde k omezen´ı tabulky operátorem Select, kde jeho závislá cˇ a´ st nevyhodnocuje operátor podm´ınky pˇr´ımo, ale aˇz na základˇe vysledku funkce predicate. ´

Pˇr´ıklad 3: Pˇreklad XPath výrazu Nadefinovaná kompilaˇcn´ı pravidla budou prezentována na pˇr´ıkladu z obrázku 8 vyˇ y´ ´ se. Vysledn ´ strom operátoru˚ na obrázku 9 n´ızˇ e se vyznaˇcenymi m´ısty odkazuje na obrázek 10, kde jsou ´ schématicky znázornˇeny mezivysledky vybranych ´ ´ duleˇ ˚ zitych ´ operátoru. ˚ 25

/library//book[@id = “10“]/author/( first/text() +last/text()) result7


result6

𝐶𝑎𝑙𝑙[add]


𝐼𝑁

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[child, text()]

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[child, text()]

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[child, first]

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[child, last]

𝑇𝑢𝑝𝑙𝑒[dot]

𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠[dot]


𝐼𝑁

𝐼𝑁

𝐼𝑁


first/text() +last/text() result5

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛 child; author /library//book[@id = “10“]/author


/library//book[@id = “10“]

result4

𝑆𝑒𝑙𝑒𝑐𝑡 𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠[dot] result3

𝑀𝑎𝑝𝐶𝑜𝑛𝑐𝑎𝑡 𝐼𝑁 result2

𝐼𝑁


𝐶𝑎𝑙𝑙[predicate] 𝑇𝑢𝑝𝑙𝑒[dot]

𝐶𝑎𝑙𝑙[eq]

𝐼𝑁 𝑆𝑐𝑎𝑙𝑎𝑟["10"]

result1

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[child; book] 𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛 attribute; id 𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[descendant-or-self; node()] 𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠[dot] 𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛[child, library] 𝐼𝑁 𝐶𝑎𝑙𝑙[root]

.

/

@id

/library /library//book

Obrázek 9: Pˇreklad ukázkového XPath vyrazu ´ 26

XML dokument

library section

section

book id = “7“

book id = “10“

author

book id = “15“

author

author

first

last

first

last

first

last

John

Smith

Peter

Black

Adam

White

result1

book id = “7“

book id = “10“

author

book id = “15“

author

first

last

first

last

first

last

John

Smith

Peter

Black

Adam

White

result2

result3

dot

result4

a

dot

book id = “7“

id = “7“

author

2

last

John

Smith

book

dot book id = “10“

author first

last

John

Smith

2

author first

last

Peter

Black

book id = “10“

author

2

first

last

Peter

Black

book id = “15“

a

book

first

id = “10“

author

result5

author first

last

Peter

Black

author first

last

Peter

Black

book id = “15“

author

2

first

last

Adam

White

result6

author first

last

Adam

White

result7

a

dot

(Peter Black)

author

2

first

last

Peter

Black

Značení XML elementu Značení XML atributu

Obrázek 10: Mezivysledky ukázkového pˇrekladu XPath ´

27

/child::library/descendant-or-self::node()/child::book[attribute::id = "10"] /child::author/(child::first/child::text() + child::last/child::text())

Vyraz je uvozen jednoduchym ´ ´ lom´ıtkem, takˇze je potˇreba zajistit naˇcten´ı vstupn´ıho XML dokumentu volán´ım funkce root. Prvn´ım krokem je navigace na vˇsechny pˇr´ımé potomky s názvem ,,library“. Jedná se o axis step, takˇze pouˇzijeme operátor TreeJoin. Následuje zápis /descendant-or-self:node()/child:book (po rozepsán´ı ze zkratkového //book). Jde tedy o dvojity´ axis step, takˇze dvakrát pouˇzijeme TreeJoin. Pˇri vyhodnocován´ı v tuto chv´ıli obdrˇz´ıme mezivysledek oznaˇceny´ jako result1 . ´ Dalˇs´ı cˇ a´ st´ı dotazu je predikát. Vznikaj´ıc´ı sekvenci poloˇzek je tedy nutné pˇrevést na tabulku s n-ticemi o jedné sloˇzce dot. O toto pˇreveden´ı se stará operátor MapFromItem s konstruktorem n-tice (operátorem Tuple) v závislé cˇ a´ sti (viz mezivysledek result2 ). To vˇse probˇehne v rámci ´ závislé vˇetve operátoru MapConcat, ktery´ zajist´ı, zˇ e v podm´ınce selekce budou dostupné kromˇe kontextového uzlu také vˇsechny promˇenné, které nastavil napˇr. vnˇejˇs´ı vyraz FLWOR. Muˇ ´ ˚ zeme pˇredpokládat, zˇ e vnˇejˇs´ı kontextová n-tice obsahuje napˇr´ıklad sloˇzku a s hodnotou 2. Následuje proveden´ı selekce (result4 ) a návrat k toku datovych ´ poloˇzek operátorem MapToItem. Dalˇs´ım krokem je jiˇz nˇekolikrát pˇrekládany´ axis step se jmennym ´ testem na název uzlu ,,author“ a navigaci na osu child, takˇze opˇet jednoduˇse pouˇzijeme operátor TreeJoin. Posledn´ım krokem je filter vyraz. Zde je moˇzné opˇet pozorovat pˇrechod od sekvence poloˇzek ´ k tabulce pomoc´ı operátoru˚ MapFromItem, Tuple a MapConcat na stejném principu jako pˇri kompilaci predikátu. Pro kaˇzdou n-tici pak probˇehne vypoˇ o coˇz se postará ´ cet filter vyrazu, ´ závislá vˇetev operátoru MapToItem. Vysledek dotazu je oznaˇceny´ jako result7 . Je zde pro zjed´ noduˇsen´ı drobná nepˇresnost. Pˇri spojován´ı kˇrestn´ıho jména a pˇr´ıjmen´ı by se mezi obˇema cˇ a´ stmi samozˇrejmˇe mˇela nacházet mezera.

3.3.4

Kompilace dalˇs´ıch konstrukc´ı

Byl popsán pˇreklad nejpouˇz´ıvanˇejˇs´ıch konstrukc´ı XQuery. Mezi dalˇs´ı ménˇe známé konstrukce paˇr´ı napˇr. jiˇz zminovan y´ typeswitch, ktery´ provád´ı vˇetven´ı na základˇe datového typu. Dále ˇ pak klasická alternativa, tzn. vˇetven´ı na základˇe booleovské hodnoty, vˇseobecné kvantifikátory every, existenˇcn´ı kvantifikátory some a dalˇs´ı. Kompilaˇcn´ı pravidla jsou pro tyto konstrukce vˇetˇsinou pˇr´ımoˇcará a vyuˇz´ıvaj´ı operátory pracuj´ıc´ı na n-ticemi. Jejich podrobny´ popis by byl pro uˇ ´ cely této práce zbyteˇcnˇe zdlouhavy. ´

3.4

Optimalizace

Vyˇ ´ se popsaná pravidla pro kompilaci sice sestav´ı strom operátoru˚ tak, abychom po jeho evaluaci obdrˇzeli správny´ vysledek, nicménˇe ne vˇzdy je vypoˇ ´ ´ cet efektivn´ı. Existuje celá rˇ ada pravidel, jak operátory pˇreskládat, aby vysledek zustal zachován, ale vypoˇ ´ ˚ ´ cet probˇehl rychleji. Bude popsáno celkem 5 pravidel, z nichˇz prvn´ı dvˇe jsou specifická pro tuto práci.

28

3.4.1

Odstranˇen´ı MapConcat

Tato optimalizace se tyk´ ´ a pˇredevˇs´ım cˇ a´ st´ı operátorového stromu, které vznikly kompilac´ı XPath vyraz u. napˇr. konstanta, pˇredstavuje z hlediska ´ ˚ Problémem je, zˇ e kaˇzdy´ byt’ elementárn´ı vyraz, ´ gramatiky jednoduchy´ XPath s jedn´ım filter vyrazem. Z toho vyplyv´ ´ ´ a nutnost namapovat vysledek ´ z pˇredchoz´ıho nebo poˇca´ teˇcn´ıho kroku na promˇennou dot. Na obrázku 11 je zachycen strom operátoru˚ pro vyraz ,,1“. Jedná se o prakticky nepouˇzitelny´ ´ dotaz, nicménˇe z hlediska gramatiky XQuery je vˇse naprosto v poˇra´ dku. Uˇz na prvn´ı pohled je zˇrejmé, zˇ e kompilaˇcn´ı pravidla byla v tuto chv´ıli zbyteˇcnˇe dusledn´ a a vygenerovala velké ˚ mnoˇzstv´ı pˇrebyteˇcnych ´ operátoru. ˚ Prvn´ı optimalizaˇcn´ı pravidlo, které by nás v tuto chv´ıli mohlo napadnout je odstranit cely´ MapToItem a zanechat pouze Scalar[1], jelikoˇz skalárn´ı operátor nepˇristupuje ke kontextové n-tici, tzn. nezávisly´ vstup vubec nepotˇrebuje. Tato uvaha ale nen´ı v poˇra´ dku, protoˇze kdyby nezávislá ˚ ´ cˇ a´ st vyprodukovala v´ıce neˇz jednu n-tici, pak by vysledek nebyl správny. ´ ´ Závislá cˇ a´ st se mus´ı provést pˇresnˇe tolikrát, jaky´ je poˇcet n-tic z nezávislého operátoru. 𝑀𝑎𝑝𝑇𝑜𝐼𝑡𝑒𝑚


𝐼𝑁



𝑇𝑢𝑝𝑙𝑒𝐴𝑐𝑐𝑒𝑠𝑠 dot

𝑇𝑢𝑝𝑙𝑒 dot

𝐼𝑁

𝐼𝑁

Obrázek 11: Kompilace skalárn´ı hodnoty bez optimalizace Zkusme se nejprve zamˇerˇ it na cˇ innost suboperátoru MapFromItem. V nezávislém suboperátoru pouze pˇristoup´ıme k nˇejaké sloˇzce dot kontextové n-tice, obdrˇz´ıme tedy poloˇzku, kterou pˇredáme závislému vstupu, ktery´ z n´ı vytvoˇr´ı novou jednoprvkovou n-tici. Situace je ilustrována na tabulce 3. Nalevo je obsah kontextové n-tice, ke které pˇristupoval TupleAccess, napravo vysledek MapFromItem. ´ a

b

dot

1

2

−→

dot

Tabulka 3: Mezivysledek MapFromItem ´ N-tici, ke které pˇristupoval TupleAccess nastavil jako kontextovou operátor MapConcat. Jej´ı obsah mus´ı byt ´ shodny´ s obsahem nˇejaké vnˇejˇs´ı kontextové n-tice, která shodou okolnost´ı utvoˇrila vstup tohoto operátoru. Vysledek MapConcat je uveden v tabulce 4. ´ 29

a

b

dot

dot

1

2

Tabulka 4: Mezivysledek MapConcat ´ Názvy sloˇzek n-tic se sice dle definice nesm´ı opakovat, nicménˇe procesor si s duplicitn´ımi vyskyty porad´ı tak, zˇ e pˇristupuje vˇzdy k posledn´ımu z atributu˚ v poˇrad´ı pˇridáván´ı. V tuto chv´ıli ´ je ale jasné, zˇ e doˇslo k pouhému zkop´ırován´ı jedné sloˇzky a to je z hlediska dalˇs´ıho vyhodnocován´ı zbyteˇcné. Pokud by nˇektery´ z operátoru˚ pozdˇeji potˇreboval pˇristoupit k dot, nebude záleˇzet na tom, kterou kopii skuteˇcnˇe pouˇzije. Optimalizaˇcn´ı pravidlo tedy funguje tak, zˇ e je li nalezen MapConcat s nezávislym ´ vstupem IN a závislym ´ vstupem tvoˇrenym ´ MapFromItem, kde docház´ı pouze k pˇr´ıstupu ke sloˇzce q a konstrukci jednoprvkové n-tice se sloˇzkou q, muˇ ˚ ze byt ´ tento MapConcat rovnou nahrazen operátorem n-tic´ı IN. MapConcat{MapFromItem{Tuple[q](IN)}}(TupleAccess[q](IN))}(IN) → IN Po aplikaci tohoto optimalizaˇcn´ıho pravidla na strom operátoru z obr. 11, obdrˇz´ıme novy´ strom na obr. 12. ‫݉݁ݐܫ݋ܶ݌ܽܯ‬

‫ܰܫ‬

݈ܵܿܽܽ‫[ݎ‬1]

Obrázek 12: Kompilace skalárn´ı hodnoty po optimalizaci odstranˇen´ım MapConcat

3.4.2

Odstranˇen´ı MapToItem

Vrat’me se nyn´ı k puvodn´ ı uvaze odstranit MapToItem, pokud jeho závislá cˇ a´ st nepouˇz´ıvá kontex˚ ´ tovou n-tici IN. Bylo rˇ eˇceno, pokud by vyhodnocen´ım nezávislého suboperátoru vznikla tabulka s jinym po odstranˇen´ı MapToItem korektn´ı, jelikoˇz vysledek ´ poˇctem n-tic neˇz 1, nebyl by vysledek ´ ´ nen´ı ovlivnˇen jen obsahem, ale také délkou tabulky. Jenˇze v tuto chv´ıli délku tabulky známe – jedná se pˇresnˇe o jednu n-tici (kontextovou), takˇze vysledek odstranˇen´ı operátoru MapToItem neutrp´ı zˇ a´ dnou ujmu. Pˇri dalˇs´ım zamyˇslen´ı je moˇzné ´ ´ MapToItem odstranit i v pˇr´ıpadˇe, zˇ e závisly´ vstup IN vyuˇz´ıvá. Za pˇredpokladu, zˇ e nezávislym ´ vstupem je IN, provád´ı MapToItem pouze zkop´ırován´ı této kontextové n-tice opˇet do svého závislého vstupu. MapToItem{Op1 }(IN) → Op1 Pokud tedy na strom z obrázku 12 uplatn´ıme toto optimalizaˇcn´ı pravidlo, zustane pouze ˚ operátor Scalar[1]. Závˇereˇcná cˇ a´ st této práce (kap. 5.2) ukazuje cˇ asová srovnán´ı pro bˇeh dotazu bez a s optimalizacemi odstranˇen´ım MapConcat a MapToItem. 30

3.4.3

Vloˇzen´ı Product

ˇ Principem je nahrazen´ı operátoru MapConcat kartézskym tˇechto dvou ´ souˇcinem Product. Cinnost operátoru˚ se liˇs´ı pouze t´ım, zˇ e MapConcat provád´ı pˇripojen´ı pravé tabulky ke kaˇzdému záznamu levé tabulky, pˇriˇcemˇz obsah pravé závis´ı na obsahu záznamu˚ z levé. U operátoru Product jsou obˇe tabulky nezávislé. MapConcat{Op2 }(Op1 ) → Product(Op1 , Op2 ), za pˇredpokladu, zˇ e Op2 je nezávisly´ na kontextu. Pokud tedy v závislém suboperátoru Op2 nepouˇzijeme pˇr´ıstup k mezivysledku nezávislého ´ Op1 , muˇ ˚ zeme nahradit MapConcat operátorem Product. 3.4.4

Vloˇzen´ı Join

Pˇredchoz´ı optimalizace tvoˇr´ı v podstatˇe pouze mezikrok, ktery´ umoˇzn´ı pouˇzit´ı operátoru Join dobˇre známého z relaˇcn´ı algebry. Pokud se nad kartézskym ´ souˇcinem Product nacház´ı operátor Select, je moˇzné tuto dvojici nahradit operátorem Join. Vyhoda tohoto nahrazen´ı spoˇc´ıvá v tom, zˇ e ´ lze v závislosti na tvaru spojovac´ı podm´ınky pro evaluaci Join pouˇz´ıt ruzn´ ˚ e efektivn´ı algoritmy, napˇr. spojen´ı hashován´ım (hash-join). Optimalizace vloˇzen´ım Product a Join jsou pˇrevzaty z [16]. Select{Op1 }(Product(Op2 , Op3 )) → Join{Op1 }(Op2 , Op3 ) 3.4.5

Spojen´ı kroku˚ XPath

Posledn´ı zde popsaná a pozdˇeji implementovaná optimalizace souvis´ı s pouˇz´ıván´ım zkratkového zápisu osy descendant-or-self pomoc´ı //. Jednoduchy´ XPath a//b je rozepisován na a/descendant-or-self::node()/child::b. Na obrázku 13 je sestaveny´ plán dotazu pro vyhodnocen´ı takového vyrazu, pro snazˇs´ı orientaci jsou jednotlivé operátory TreeJoin rozliˇseny ´ spodn´ım indexem. 𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛3 [child, b]

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛2 [descendant-or-self, node()]

𝑇𝑟𝑒𝑒𝐽𝑜𝑖𝑛1 [child, a]


𝐼𝑁

Obrázek 13: Plán dotazu a//b Optimalizaˇcn´ı pravidlo jednoduˇse transformuje dva po sobˇe jdouc´ı operátory TreeJoin – prvn´ı s osou descendant-or-self a testem na libovolny´ XML uzel (mimo atribut), druhy´ s osou child a testem q, na jeden TreeJoin s osou descendant a testem q.

31

TreeJoin[descendant-or-self, node()](TreeJoin[child, q](Op)) → TreeJoin[descendant, q](Op)

𝐴0

𝐴1

𝐴2

𝐴3

𝐴4

𝐴5

Obrázek 14: Rozbor optimalizace

Dukaz ˚ Na obrázku 14 je znázornˇen podstrom nˇejaké cˇ a´ sti XML dokumentu. Pro odvozen´ı tohoto pˇrepisu bude potˇreba formálnˇe nadefinovat nˇekolik pomocnych ´ funkc´ı. Funkce c(a) pˇriˇrazuje kaˇzdému uzlu a mnoˇzinu jeho pˇr´ımych ´ potomku˚ A. Funkce child(A) pˇredchoz´ı zobrazen´ı pouze zobecnuje ˇ pro moˇznost pouˇzit´ı nad celou mnoˇzinou podle vztahu (1). Jedná se tedy o popis cˇ innosti operátoru TreeJoin[child, node()](A) child(A) =



c(a)

(1)

a∈A

Pohledem na obrázek 14 by mˇelo byt zobrazen´ı child pro kaˇzdou urove nˇ ´ jasné, zˇ e vysledkem ´ ´ je urove nˇ následuj´ıc´ı (2). ´ Ai+1 = child(Ai )

(2)

Dále je potˇreba formálnˇe zaznaˇcit cˇ innost TreeJoin pˇri navigaci na osy descendant-or-self a descen´ dant (funkce dos(A) a desc(A)). Urove nˇ 0 bude povaˇzována jako referenˇcn´ı, ke které budeme jednotlivé navigace vztahovat. dos(A0 ) =

n 

Ai

(3)

i=0

desc(A0 ) =

n  i=1

32

Ai

(4)

Kaˇzdy´ XML dokument je samozˇrejmˇe koneˇcny, ´ coˇz znamená, zˇ e mus´ı existovat nˇejaká urove nˇ n, pro kterou plat´ı (5). ´ An = ∅ (5) Je tedy potˇreba dokázat (6), tzn., zˇ e proveden´ı navigace na osu descendant-or-self následované navigac´ı na child je ekvivalentn´ı k proveden´ı jedné navigace descendant. child(dos(A0 )) = desc(A0 ) Na levou i pravou stranu vztahu (3) aplikujeme navigaci child a obdrˇz´ıme vztah (9).  n     child (dos(A0 )) = child  Ai 

(6)

(7)

i=0

Následuje kl´ıcˇ ovy´ bod, kdy se s funkc´ı pro navigaci na child zanoˇr´ıme do mnoˇzinového sjednocen´ı. Nezáleˇz´ı na tom, zda navigaci na child provedeme nad celou mnoˇzinou po sjednocen´ı jednotlivych ı nebo provedeme navigaci nad kaˇzdou urovn´ ı zvlásˇ t’ a sjednocen´ı provedeme ´ urovn´ ´ ´ aˇz pak. child (dos(A0 )) =

n 

child (Ai )

(8)

i=0

Za pouˇzit´ı vztahu (2) provedeme jednoduchou upravu na tvar (9) a (10). ´ child (dos(A0 )) =

n 

Ai+1

(9)

i=0

child (dos(A0 )) =

n+1 

Ai

(10)

i=1

Horn´ı hranici pro mnoˇzinové sjednocen´ı n + 1 je moˇzné sn´ızˇ it na n, jelikoˇz uˇz mnoˇzina An je prázdná, takˇze An+1 mus´ı byt ´ prázdná také. Potom pravá strana odpov´ıdá podle vztahu (4) navigaci na osu descendant a je tedy odvozen vztah (6). V závˇeru této práce jsou opˇet v kapitole 5.2 srovnány cˇ asy vyhodnocován´ı dotazu bez a s touto optimalizac´ı. 3.4.6

Dalˇs´ı moˇznosti optimalizace

Dalˇs´ı moˇznosti optimalizace, které v této práci nejsou implementovány, spoˇc´ıvaj´ı v pˇresunu nˇekterych ´ operátoru˚ v plánu dotazu smˇerem ke koˇrenovému operátoru nebo smˇerem k listum. ˚ V cˇ lánku [16] je popsán princip tzv. unnesting pˇrepisu, ˚ jejichˇz uˇ ´ celem je pokud moˇzno eliminovat vykonáván´ı zanoˇrenych smyˇcek pˇri vyhodnocován´ı dotazu, coˇz se tyk´ ´ ´ a pˇredevˇs´ım cˇ innosti operátoru˚ MapConcat. Toho je doc´ıleno zaveden´ım speciáln´ıho operátoru GroupBy a nˇekolika optimalizaˇcn´ıch pravidel, které napˇr. umoˇzn´ı pˇresun GroupBy ze závislého suboperátoru MapConcat nad tento MapConcat. Efektivnˇejˇs´ıho vyhodnocen´ı by bylo moˇzné dosáhnout také zaveden´ım operátoru TupleTreePattern [14], ktery´ je schopen v jednom kroku efektivnˇe vyhodnotit v´ıce za sebou

33

následuj´ıc´ıch axis steps a predikátu˚ napˇr. za pouˇzit´ı indexované XML databáze. Operátor TupleTreePattern pracuje na základˇe tzv. TPQ (Tree Pattern Query), coˇz je zjednoduˇsená podoba XPath vyraz u. ´ ˚ Princip optimalizace tedy spoˇc´ıvá v nalezen´ı co nejvˇetˇs´ıch moˇznych ´ cˇ a´ st´ı v plánu dotazu, které lze pˇrepsat na TupleTreePattern, jemuˇz je statickym ´ atributem nadefinován TPQ.

34

4

Implementace XQuery procesoru

Tato kapitola se vˇenuje postupu implementace XQuery procesoru, ktery´ je souˇca´ st´ı pˇr´ılohy diplomové práce. Zjednoduˇsená bloková funkce celého procesoru je zachycena na následuj´ıc´ım schématu. XQuery

Dotaz ve formě textového řetezce

Parser Syntaktický strom

Kompiler Plán dotazu

Optimalizátor Optimalizovaný plán dotazu XML dokument

DOM reprezentace dokumentu

Procesor

Objekty datového modelu

Výsledek

Obrázek 15: Bloková struktura procesoru Na vstupu vˇzdy stoj´ı zadany´ XQuery dotaz, ktery´ je v prvn´ım kroku pˇreveden parserem na syntakticky´ strom. Ze syntaktického stromu dále kompiler sestav´ı plán vykonáván´ı dotazu, ktery´ je pˇr´ıpadnˇe poupraven optimalizátorem. V posledn´ı fázi vstupuje do hry procesor, ktery´ strom operátoru˚ vyhodnot´ı, pˇriˇcemˇz muˇ ˚ ze, ale také nemus´ı, vyuˇz´ıvat koˇrenovy´ XML dokument. Kapitola se bude postupnˇe zamˇerˇ ovat na detailnˇejˇs´ı jednotlivych ´ bloku˚ z hlediska implementace.

4.1

Standard W3C a zjednoduˇsen´ı

Tato implementace standard jazyka XQuery z velké cˇ a´ sti dodrˇzuje, nicménˇe objevuje se zde nˇekolik uprav a zjednoduˇsen´ı. ´ 4.1.1

Podporované konstrukce

1. FLWOR vyrazy ´ FLWOR vyrazy jsou podporovány v celém rozsahu. Jedinym omezen´ım je ´ ´ chybˇej´ıc´ı moˇznost stanoven´ı datového typu promˇenné pomoc´ı kl´ıcˇ ového slova as. Toto omezen´ı vycház´ı ze zjednoduˇseného typového systému, ktery´ bude popsán pozdˇeji v kapitole 4.4. 2. XPath vyrazy ´ XPath vyrazy jsou podporovány vˇcetnˇe vˇsech definovanych XML os a zkrat´ ´ kovych zápisu. ´ ˚ Jsou podporovány jmenné testy a v omezené m´ırˇ e také tzv.

35

kind tests (tj. testy na typ uzlu), konkrétnˇe comment(), node(), text() a attribute(attribName) 3. Aritmetické a relaˇcn´ı vyrazy ´ Jsou podporovány standardn´ı aritmetické vyrazy nad cˇ ´ıselnymi ´ ´ poloˇzkami – operace sˇc´ıtán´ı, odˇc´ıtán´ı, násoben´ı, dˇelen´ı (celoˇc´ıselné i desetinné) a modulo. Dále standardn´ı vyrazy porovnáván´ı – ostré a neostré uspoˇra´ dán´ı, rovnost a nerovnost ´ poloˇzek. Vzhledem k tomu, zˇ e implementace nen´ı omezena pouze na XQuery core, pˇri pouˇz´ıván´ı nen´ı nutné pˇrepisovat aritmetické nebo relaˇcn´ı operátory na vestavˇené funkce. Tato implementace je oproti standardu m´ırnˇe nároˇcnˇejˇs´ı na dodrˇzován´ı typovych vyrazy je ´ konvenc´ı. Zejména pˇri práci s aritmetickymi ´ ´ potˇreba provádˇet explicitn´ı pˇretypován´ı hodnot zadanych rˇ etˇezci nebo ´ textovymi ´ XML uzly na celé nebo desetinné cˇ ´ıslo. 4. Logické vyrazy ´ Podporovány jsou základn´ı logické operace – logicky´ souˇcet or a souˇcin and. Operace negace je v XQuery standardnˇe realizována vestavˇenou funkc´ı not. 5. Alternativa Implementace podporuje vˇetven´ı if a vˇetven´ı podle datového typu typeswitch. 6. Pˇretypován´ı V rámci vydefinovaného zjednoduˇseného typového systému, je podporována i operace pˇretypován´ı. Kompletn´ı popis kompatibility a pˇretypovatelnosti jednotlivych ´ typu˚ je moˇzné nalézt v pˇr´ıloze B. 7. Kvantifikované vyrazy ´ Podporovány jsou také vˇseobecné a existenˇcn´ı kvantifikované vyrazy every a ´ some. 8. XML konstruktory Implementace podporuje konstruktory XML uzlu˚ a to jak konstruktory pˇr´ımé, tak konstruktory vypoˇctené (viz kapitola 2.3.2). 9. Vestavˇené funkce Kompletn´ı seznam podporovanych vestavˇenych funkc´ı je uveden v tabulce 5. ´ ´ Jejich popis vˇcetnˇe typu˚ argumentu˚ lze nalézt v pˇr´ıloze A. Vyznam funkc´ı ´ neodpov´ıdá pˇresnˇe standardu a je upraven pro potˇreby této práce. Je velmi pravdˇepodobné, zˇ e bude tento seznam v budoucnu rozˇsiˇrován.

36

add lt vle predicate empty

sub gt vge boolean not

mul le abs range

div ge count distinct

idiv veq position avg

mod vne last sum

eq vlt doc min

ne vgt root max

Tabulka 5: Podporované vestavˇené funkce

4.1.2

Nepodporované nebo cˇ a´ steˇcnˇe podporované konstrukce

• Vytvárˇ en´ı funkc´ı a modulu˚ • Specifikace uˇzivatelem definovanych ´ typu˚ • Jmenné prostory • Ordered a unordered vyrazy ´ • Procesn´ı instrukce, entity a sekce CDATA • Porovnáván´ı poˇrad´ı XML elementu˚

4.2

Implementaˇcn´ı prostˇred´ı

Cely´ XQuery procesor byl naimplementován v jazyce C++. Bylo vyuˇzito vyvojov´ e prostˇred´ı ´ Microsoft Visual Studio (v prubˇ ve verz´ıch 2010 a 2005). Jazyk C++ byl zvolen zejména ˚ ehu vyvoje ´ z duvodu rychlosti bˇehu vysledn´ eho programu a moˇznosti efektivn´ıho nakládán´ı s pamˇet´ı. Im˚ ´ plementace by pravdˇepodobnˇe byla pohodlnˇejˇs´ı v nˇekterém z vyˇssˇ´ıch programovac´ıch jazyku˚ C# nebo Java, avˇsak za cenu ztráty zde velmi zˇ a´ dané rychlosti. Kromˇe základn´ıch datovych ´ typu˚ a funkc´ı, které C++ nab´ız´ı, byl vyuˇz´ıván jmenny´ prostor std pˇredevˇs´ım pro práci s textovymi rˇ etˇezci. Pozdˇeji byla vyuˇzita i extern´ı knihovna Xerces Parser ´ pro naˇc´ıtán´ı vstupn´ıch XML dokumentu. ˚

4.3

Univerzáln´ı datové struktury

Na zaˇca´ tku i bˇehem vyvoje procesoru vzniklo nˇekolik univerzáln´ıch datovych ´ ´ typu˚ pˇredevˇs´ım pro zjednoduˇsen´ı práce s polem. Pozdˇeji se bude text na tyto vzniklé typy cˇ asto odvolávat, proto tedy alesponˇ struˇcny´ popis. 4.3.1

MyList

Jedná se o sˇ ablonu zapouzdˇruj´ıc´ı práci s dynamickym ´ polem pomoc´ı metod jako add(T item), removeAt(int index), T getItem(int index) a setItem(int index, T item). Pˇri pˇridáván´ı prvku˚ se MyList v pˇr´ıpadˇe nutnosti sám stará o správné pˇrealokován´ı intern´ıho pole. Z hlediska efektivity pˇrealokován´ı neprob´ıhá vˇzdy pˇri pˇridáván´ı prvku. Pokud souˇcasná kapacita nestaˇc´ı, dojde k alokaci nového pole o dvojnásobném rozmˇeru. Experimentálnˇe se ukázalo, zˇ e nejvhodnˇejˇs´ı vychoz´ ı velikost je 1. Pˇri vytvárˇ en´ı instance vˇsak lze poˇca´ teˇcn´ı kapacitu urˇcit ´ argumentem konstruktoru. 37

4.3.2

MyStack

Vyznam této sˇ ablony je evidentn´ı z názvu. Jedná se o zásobn´ık implementovany´ dvˇema ´ zpusoby – spojovym ˚ ´ seznamem a polem. Konkrétn´ı implementaci je moˇzno zvolit pˇri kompilaci zdrojovych ´ kod ´ u˚ procesoru. Jsou podporovány standardn´ı metody push(T item), T pop(), T getPeak() a bool empty(). Jejich vyznam ne tˇreba vysvˇetlovat. Pro realizaci seznamu bylo ´ nutné vytvoˇrit tˇr´ıdu MyLinkNode reprezentuj´ıc´ı jeden uzel jednosmˇerného spojového zenamu, ktery´ zapouzdˇruje skuteˇcnˇe nesenou hodnotu a pˇridává k n´ı odkaz na následuj´ıc´ı prvek. 4.3.3

MyQueue

Opˇet velmi dobˇre známá datová struktura – fronta s podporou metod enqueue(T item), T dequeue(), T getHead(), T getTail() a bool empty(). Implementaci vnitˇrnˇe zajiˇst’uje spojovy´ seznam pomoc´ı tˇr´ıdy MyLinkNode popsané v pˇredchoz´ım odstavci. 4.3.4

MyHashSet

Jedná se o implementaci mnoˇziny s metodami add(T item) a bool contains(T item). Z názvu vyplyv´ ´ a, zˇ e MyHashSet pro realizaci mnoˇziny vnitˇrnˇe vyuˇz´ıvá hash tabulku. Pro rˇ eˇsen´ı koliz´ı je zde vyuˇz´ıvána metoda dvojitého hashován´ı s funkcemi h1 (k) = k mod m a h2 (k) = 1 + (k mod (m − 1)), kde k pˇredstavuje celoˇc´ıselnou hodnotu identifikuj´ıc´ı prvek a m velikost tabulky. Tabulka má ve vychoz´ ım stavu 11 volnych pozic. K pˇrealokován´ı dojde vˇzdy po dosaˇzen´ı ´ ´ poloviˇcn´ıho zaplnˇen´ı. V rámci tˇr´ıdy je k dispozici seznam 30-ti pˇreddefinovanych ´ prvoˇc´ısel, podle kterych ´ se v pˇr´ıpadˇe potˇreby urˇc´ı nová velikost. Prvoˇc´ısla jsou po sobˇe zvolena tak, aby kaˇzdé bylo pˇribliˇznˇe 2 krát vˇetˇs´ı, viz tabulka 6. 11 397 12853 411527 13169977 421439783

23 797 25717 823117 26339969 842879579

47 1597 51437 1646237 52679969 1685759167

97 3203 102877 3292489 105359939 3371518343

197 6421 205759 6584983 210719881 2448069391

Tabulka 6: Prvoˇc´ısla pro volbu velikosti tabulky hash Identifikaci prvku v mnoˇzinˇe zajiˇst’uje pomocná sˇ ablona MyEqComparer, která abstraktnˇe definuje metody pro detekci shodnosti a zjiˇstˇen´ı hodnoty hash. Vzhledem k tomu, zˇ e se prvky obvykle identifikuj´ı svou adresou, je souˇca´ st´ı univerzáln´ıch struktur také implementace ReferenceEqComparer. MyHashSet bylo nutné naimplementovat primárnˇe pro efektivn´ı práci operátoru TreeJoin, ktery´ v posledn´ım kroku vyhodnocován´ı eliminuje duplicity. 4.3.5

MyIterator

Jedná se o abstraktn´ı tˇr´ıdu, která zajiˇst’uje pruchod polem, spojovym ˚ ´ seznamem nebo jinym ´ typem pˇredstavuj´ıc´ım seznam hodnot pomoc´ı metod reset(), T getNext() a bool hasNext(). 38

Tato abstraktn´ı tˇr´ıda byla implementována pro MyList jako MyListIterator a pro MyQueue jako MyQueueIterator. Iterátory umoˇznily pˇredevˇs´ım v operátorech XQuery algebry oddˇelit procházen´ı seznamu (napˇr. sekvence poloˇzek nebo tabulky) od jeho fyzické implementace.

4.4

Datovy´ model

Datovy´ model popisuje systém navzájem propojenych ´ tˇr´ıd, které zapouzdˇruj´ı práci s jednotlivymi ´ typy hodnot XQuery. <> DataValue

<<enum>> DataType

DataType getType() string toString() void initialize()

<> DataItemEnumerable SequenceIterator getIterator() int count() void initialize()

<> DataItem

*

int itemIndex

<> DataTupleEnumerable

XML_ATTRIBUTE XML_COMMENT XML_NODE XML_TEXT XML_DOCUMENT UNKNOWN

TableIterator getIterator() int count() void initialize()

DataSequence void addItem(DataItem value) void initialize()

SEQUENCE TABLE TUPLE BOOLEAN INTEGER STRING DOUBLE

DataTable

DataTuple void add(string name, DataItemEnumerable value) DataItemEnumerable getValue(string name) void initialize()

*

void addTuple(DataTuple tuple) void initialize()

Obrázek 16: Tˇr´ıdn´ı diagram datového modelu Z tˇr´ıdn´ıho diagramu na obrázku 16 je patrné, zˇ e jakákoli hodnota muˇ ˚ ze byt ´ na nejvyˇssˇ´ı urovni abstrakce interpretována jako DataValue. Dalˇs´ı urove nˇ dˇediˇcnosti spoˇc´ıvá v rozdˇelen´ı ´ ´ na DataTupleEnumerable a DataItemEnumerable. V základu jde o duáln´ı struktury – jedna pro práci s n-ticemi, druhá pro práci s poloˇzkami. Vyznam tˇr´ıd *Enumerable spoˇc´ıvá v moˇznosti iterován´ı pomoc´ı TableIterator nebo ´ SequenceIterator. Docház´ı tak k zakryt´ı rozd´ılu, ˚ zda pracujeme s n-tic´ı DataTuple nebo tabulkou DataTable a na druhé stranˇe s poloˇzkou DataItem nebo sekvenc´ı DataSequence. Tˇr´ıdn´ı diagram datového modelu poˇc´ınaje DataItem pokraˇcuje na obrázku 17. Uvedené tˇr´ıdy na obrázc´ıch 16 a 17 slouˇz´ı jako pevny´ základ, u kterého nejsou pˇredpokládány pravidelné zmˇeny nebo rozˇsiˇrován´ı. Z toho vycház´ı také filosofie názvoslov´ı a organizace nˇekterych ´ metod. 4.4.1

Typovy´ systém

Z pohledu dotazu, ktery´ procesor vykonává je pro kaˇzdy´ datovy´ objekt duleˇ ˚ zity´ jeho typ dany´ vyˇ ´ ctem DataType. Zde docház´ı ke zjednoduˇsen´ı oproti standardu W3C, ktery´ definuje moˇznost tvorby uˇzivatelskych ´ typu. ˚ V této implementaci dotazy pracuj´ı pouze s fixn´ı mnoˇzinou datovych ´ typu, ˚ jejichˇz kompatibilita je popsána v pˇr´ıloze B. Z tohoto zjednoduˇsen´ı vyplyvaj´ ´ ı nˇekterá dalˇs´ı

39

<> DataItem int itemIndex

BooleanItem

*

<> XmlNode XmlElement parent

StringItem

<> NumericItem

bool value

string value

void initialize(bool v)

void initialize(string v)

void initialize() IntegerItem

void navigate(TreeAxis axis, XmlElementFilter filter, MyList<XmlNode> result)

XmlElement

double value

void initialize(int v)

void initialize(double v)

XmlAttribute

XmlText

string name string value

string name void initialize() void addChild(XmlNode node) int childCount() XmlNode getChild(int index)

DoubleItem

int value

void initialize(string name, string value)

XmlComment

string text

string comment

void initialize(string s)

void initialize(string s)

XmlDocument void initialize()

Obrázek 17: Tˇr´ıdn´ı diagram datové poloˇzky omezen´ı, napˇr. nepodporovaná klauzule as ve vyrazech FLWOR, kde uˇzivatel sám specifikuje ´ typ sekvence poloˇzek. Jazyk XQuery je relativnˇe silnˇe typovany, ´ coˇz znamená, zˇ e operace jako sˇc´ıtán´ı cˇ ´ısla s rˇ etˇezcem reprezentuj´ıc´ım cˇ ´ıslo jsou obvykle neplatné a je nutné vyuˇz´ıt nˇejakého mechanismu pˇretypován´ı. Bylo nutné vyˇreˇsit konverzi mezi typy jak na implementaˇcn´ı urovni, tak na urovni procesoru ´ ´ z uˇzivatelského hlediska. Pˇretypován´ı v rámci implementace Vzhledem k tomu, zˇ e pˇri pouˇz´ıván´ı datového modelu docház´ı k pˇretypován´ı velmi cˇ asto, byl naimplementován relativnˇe jednoduchy´ systém pomocnych metod is* a as*. Pro kaˇzdy´ typ ´ modelu (vˇcetnˇe tˇech abstraktn´ıch) je ve tˇr´ıdˇe DataValue abstraktnˇe definována metoda as* (napˇr. asDataItem()), která provede pˇretypován´ı bez nutnosti pouˇzit´ı standardn´ı závorkové syntaxe. Pro otestován´ı, zda je pˇretypován´ı vubec moˇzné slouˇz´ı odpov´ıdaj´ıc´ı abstraktn´ı metoda is* (tzn. ˚ napˇr. isDataItem()). Vyznam ovˇsem nen´ı pouze v usnadnˇen´ı a zpˇrehlednˇen´ı zápisu. Uvedené metody totiˇz ´ neprovád´ı pˇretypován´ı vˇzdy pouze ve smyslu klasického polymorfismu, ale napˇr´ıklad pro StringItem je moˇzné zavolat asDataSequence(), pˇrestoˇze se DataSequence a StringItem nacház´ı v hierarchii dˇediˇcnosti na jiné vˇetvi. Návratová hodnota is* nav´ıc nemus´ı byt ´ pro dva dané typy vˇzdy stejná. Pokud napˇr. zavoláme isDataItem() na DataSequence, muˇ ˚ zeme obdrˇzet hodnotu ,,pravda“ v závislosti na tom, zda sekvence obsahuje jedinou poloˇzku.

40

Pˇretypován´ı z hlediska procesoru Na druhé stranˇe je nutné rˇ eˇsit pˇretypován´ı na urovni XQuery procesoru. Vˇsechny tˇr´ıdy modelu im´ plementuj´ı metody implicitlyCastable(DataType type), a castAs(DataType type), které tvoˇr´ı základ operátoru˚ Cast a Castable. Procesor tedy podporuje konstrukce castable a cast as, pˇriˇcemˇz je moˇzné pouˇz´ıvat typy uvedené v tab. 7. Ve srovnán´ı s vyˇ ´ ctem DataType (tˇr´ıdn´ı diagram na obr. 16) zde chyb´ı typ pro tabulku a n-tici. Duvodem je, zˇ e tyto dva typy hodnot slouˇz´ı vyhradnˇ e pro mezivysledky ˚ ´ ´ procesoru a nejsou tak pˇr´ıstupné uˇzivateli, ktery´ spouˇst´ı dotaz. Vyˇ ´ cet nav´ıc obsahuje pomocnou konstantu UNKNOWN. sequence boolean integer string double xml-attribute xml-comment xml-node xml-text xml-document

Sekvence poloˇzek Hodnota ,,true“ / ,,false“ Celé cˇ ´ıslo Textovy´ rˇ etˇezec Desetinné cˇ ´ıslo Xml atribut Xml komentárˇ Xml element Xml textovy´ uzel Xml dokument

Tabulka 7: Datové typy procesoru

4.4.2

Správa datovych ´ objektu˚

O vytvárˇ en´ı instanc´ı datovych ´ objektu˚ se stará tˇr´ıda DataModelManager, která pro kaˇzdy´ (neabstraktn´ı) datovy´ typ obsahuje metodu create* (viz tˇr´ıdn´ı diagram na obr. 18). Kaˇzdá nová hodnota si nav´ıc zapamatuje odkaz na DataModelManager, ktery´ ji vytvoˇril, aby mohla pˇr´ıpadnˇe sama zakládat dalˇs´ı hodnoty pro vysledky vypoˇ by mohlo ´ ´ ctu˚ napˇr. aritmetickych ´ operac´ı. V uvahu ´ pˇripadat také singleton rˇ eˇsen´ı, ale z duvodu napˇr. testován´ı se muˇ ˚ ˚ ze hodit vytvoˇrit dva oddˇelené správce. Samotné konstruktory datovych ´ typu˚ zde nemaj´ı zˇ a´ dné argumenty, o veˇskerou inicializaci se staraj´ı metody initialize(args). Inicializace jedné instance totiˇz muˇ ˚ ze probˇehnout v´ıcekrát. Argumenty této metody se liˇs´ı u fináln´ıch tˇr´ıd, napˇr. pro BooleanItem je inicializaˇcn´ı metodˇe pˇredávána skuteˇcná hodnota typu bool, pro XmlAttribute dvˇe hodnoty typu string (name a key) atd. V rámci hierarchie dˇediˇcnosti je zajiˇstˇeno, zˇ e pˇri volán´ı initialize na nˇejaky´ konkrétn´ı fináln´ı typ budou zavolány také inicializaˇcn´ı metody vˇsech pˇredku˚ podobnˇe jako se tomu dˇeje pˇri volán´ı konstruktoru. Recyklace instanc´ı Vyznam DataModelManager nespoˇc´ıvá pouze v evidenci referenc´ı na vzniklé objekty, aby je ´ nakonec bylo moˇzné rˇ a´ dnˇe zlikvidovat. DataModelManager um´ı existuj´ıc´ı objekty za urˇcitych ´ okolnost´ı znova vyuˇz´ıt. 41

DataModelManager

<> DataValue

MyList boolItems MyStack boolItemsCountStack int boolItemsCount MyList integerItems MyStack intItemsCountStack int intItemsCount … BooleanItem createBool(bool value) IntegerItem createInt(int value) …

Obrázek 18: Tˇr´ıdn´ı diagram správy datovych ´ objektu˚ Ke vˇsem neabstraktn´ım typum ˚ datového modelu je pˇridruˇzeno jednak zvlásˇ tn´ı pole, resp. pole zapouzdˇrené tˇr´ıdou MyList, a jednak index posledn´ı platné instance. Pˇri poˇzadavku na novou instanci dojde k inkrementaci indexu a zjiˇstˇen´ı, zda nebyla pˇrekroˇcena velikost pˇr´ısluˇsného pole. Pokud ano, pak skuteˇcnˇe dojde k vytvoˇren´ı a vloˇzen´ı do pole, jinak se vyuˇzije jiˇz existuj´ıc´ı objekt, ktery´ je na daném indexu zrovna k dispozici. Podle popisu v pˇredchoz´ım odstavci by ale promˇenná ukazovala pokaˇzdé na posledn´ı pozici a nová instance by byla vytvárˇ ena vˇzdy. To sice plat´ı, ale pouze do té doby, neˇz je na DataModelManager zavolána metoda clear. Ta jednoduˇse vˇsechny indexy vynuluje a vzniklé objekty je moˇzné zaˇc´ıt vyuˇz´ıvat znova. Tento zpusob má ale relativnˇe velkou nevyhodu. Zavolán´ım clear oznaˇc´ıme jako neplatné ˚ ´ vˇsechny vzniklé datové objekty a t´ım pádem jedinym ´ bodem, kde je moˇzné recyklaci vyuˇz´ıt, je zpracován´ı v´ıce XQuery dotazu˚ za sebou. Vyˇciˇstˇen´ım nav´ıc pˇrijdeme napˇr. také o hodnoty, které vznikly zpracován´ım vstupn´ıho XML, takˇze pˇred kaˇzdym ´ dotazem je nutné vstupn´ı XML naˇc´ıtat znova. Pˇredchoz´ı myˇslenka byla upravena tak, zˇ e je s kaˇzdym ´ poˇc´ıtadlem asociován nav´ıc jeˇstˇe jednoduchy´ zásobn´ık (implementovany´ tˇr´ıdou MyStack) a metoda clear je nahrazena dvojic´ı metod pushInstanceCounters a popInstanceCounters. Pomoc´ı zásobn´ıku tak nedocház´ı k upln´ emu vynulován´ı, ale pouze k obnoven´ı nˇejakého pˇredchoz´ıho stavu. ´ Nejen, zˇ e je t´ımto zpusobem odpadá nutnost znovu naˇc´ıtat vstupn´ı XML, recyklaci lze nav´ıc ˚ relativnˇe snadno vyuˇz´ıt i pˇr´ımo bˇehem vykonáván´ı dotazu, ˚ coˇz bude podrobnˇeji ukázáno na vyhodnocován´ı operátoru Select v kapitole 4.8.2. 4.4.3

Implementace DataSequence a DataTable

U implementace DataSequence a DataTable bylo potˇreba zvázˇ it, jakou organizaci zvolit pro reprezentaci seznamu poloˇzek nebo n-tic. V uvahu pˇripadaly dvˇe – pole zapouzdˇrené pomoc´ı ´ MyList a fronta zapouzdˇrená v MyQueue. Implementovány byly nakonec obˇe. Testován´ım se ukázalo, zˇ e z hlediska rychlosti vyhodnocen´ı na tom jsou obˇe pˇribliˇznˇe stejnˇe. Efektivita spojového seznamu, kterym ´ je fronta realizována, pravdˇepodobnˇe nebyla zcela vyuˇzita t´ım, zˇ e je pro kaˇzdy´ uzel nutné instanciovat zaobaluj´ıc´ı tˇr´ıdu. Seznam nen´ı moˇzné reprezentovat pomocnymi ´ promˇennymi pˇr´ımo v poloˇzce nebo n-tici, jelikoˇz v rámci v´ıce rozpoˇc´ıtanych u˚ muˇ ´ ´ mezivysledk ´ ˚ ze byt ´ poloˇzka nebo n-tice v jednu chv´ıli souˇca´ st´ı v´ıce sekvenc´ı nebo tabulek.

42

4.4.4

DOM

Z hlediska manipulace s XML je nejvyhodnˇ ejˇs´ı jeho reprezentace ve formˇe DOM (Document ´ Object Model). DOM tvoˇr´ı ned´ılnou souˇca´ st datového modelu poˇc´ınaje tˇr´ıdou XmlNode (viz tˇr´ıdn´ı diagram na obrázku 17). Souˇca´ st´ı jsou dále tˇr´ıdy XmlDocument, XmlAttribute, XmlText a XmlComment, jejichˇz vyznam by mˇel byt ´ ´ zˇrejmy. ´ Tˇr´ıda XmlNode pˇredstavuj´ıc´ı abstraktn´ı urove nˇ pro kaˇzdy´ XML uzel poskytuje metodu ´ navigate, která podle argumentu osy volá jednu z vnitˇrn´ıch metod pro navigaci. Samotná tˇr´ıda XmlNode implementuje metody pro navigaci na osy ancestor, ancestor-or-self, descendant-or-self, following, following-sibling, preceding a preceding-sibling. Navigace na attribute, child a descendant je záleˇzitost´ı aˇz tˇr´ıdy XmlElement, jelikoˇz pro vyhodnocen´ı tˇechto os je potˇreba pracovat s pˇr´ımymi ´ 1 nebo nepˇr´ımymi potomky . ´ 4.4.5

Symbolické názvy promˇennych ´

V kapitole 3.3.2, kde byl popisován pˇreklad FLWOR vyrazu, byla nadefinována nutnost substituce ´ pˇr´ıstupu k promˇennym ´ pomoc´ı operátoru Var na pˇr´ıstup do pˇr´ısluˇsné sloˇzky kontextové ntice operátorem TupleAccess. Jednou z posledn´ıch uprav procesoru bylo zaveden´ı symbolickych ´ ´ názvu˚ promˇennych, resp. symbolickych ´ ´ oznaˇcen´ı sloˇzek n-tic. N-tic se totiˇz v pˇr´ıpadˇe sloˇzitˇejˇs´ıch dotazu˚ muˇ ˚ ze vygenerovat obrovské mnoˇzstv´ı (ve sloˇzitych ´ dotazech rˇ a´ dovˇe miliony) a z hlediska definice si kaˇzdá mus´ı nést oznaˇcen´ı svych ´ ´ sloˇzek. Oznaˇcen´ı ve formˇe textového rˇ etˇezce je sice pˇrirozené, ale také zbyteˇcnˇe prostorovˇe nároˇcné. Nav´ıc operátor Tuple, ktery´ n-tice generuje a pˇriˇrazuje jim názvy sloˇzek mus´ı pro kaˇzdou novou n-tici název kop´ırovat, coˇz zhorˇsuje vykonnost procesoru. ´ Proto byla do tˇr´ıdy DataModelManager zaimplementována jednoduchá tabulka s dvojicemi kl´ıcˇ = symbolický název a metoda int getSymbolicKey(string key), která pro zadany´ kl´ıcˇ ve formˇe textového rˇ etˇezce vrát´ı odpov´ıdaj´ıc´ı symbolicky´ název v podobˇe celoˇc´ıselné hodnoty. Jestliˇze je metoda pro urˇcity´ kl´ıcˇ volána poprvé, postará se o vytvoˇren´ı nového symbolického názvu a zaveden´ı záznamu do tabulky, jinak vrát´ı odpov´ıdaj´ıc´ı existuj´ıc´ı symbolicky´ název. Názvy sloˇzek n-tic jsou tedy tvoˇreny celymi ´ cˇ ´ısly. V plánu vykonáván´ı dotazu se v operátorech Tuple a TupleAccess skuteˇcné názvy pˇreloˇz´ı na symbolické bˇehem statického vyhodnocován´ı (viz pozdˇeji v kapitole 4.8.1).

4.5

Parser

Implementace parseru vycházela z gramatiky definované standardem W3C ve formˇe EBNF [5]. Jedinym ´ omezen´ım je to, zˇ e v souˇcasné dobˇe implementace nepracuje s unicode. Pˇrestoˇze procesor nˇekteré konstrukce XQuery nepodporuje, parsován´ı vstupn´ıho dotazu je aˇz na zminovan y´ unicode ˇ kompletn´ı. Existuj´ı v zásadˇe dvˇe moˇznosti, jak pˇristoupit k vytvoˇren´ı parseru. Prvn´ı a jednoduˇssˇ´ı moˇznost je vyuˇzit´ı generátoru, ktery´ na vstupu obdrˇz´ı gramatiku a vygeneruje zdrojovy´ kod. ´ Druhou moˇznost´ı je ruˇcn´ı implementace. Vzhledem k obt´ızˇ né dostupnosti generátoru, ktery´ by byl schopen vytvoˇrit XQuery parser v jazyce C++, byla nakonec vyuˇzita druhá moˇznost, cˇ ili ruˇcn´ı im1 Navigace na descendant-or-self je implementov´ ana ve tˇr´ıdˇe XmlNode pˇrestoˇze obecny´ uzel potomky m´ıt nemus´ı. Tato navigace ale vyuˇz´ıvá navigaci na descendant, která je skuteˇcnˇe implementovaná aˇz v XmlElement, pouze k n´ı pˇridává vlastn´ı uzel.

43

plementace. Jak ale bude pozdˇeji popsáno, byla vytvoˇrena speciáln´ı utilita, která základn´ı skelet parseru vygenerovala. Parsován´ı se obvykle skládá ze dvou nezávislych ´ kroku˚ – lexikáln´ı a syntaktické analyzy. ´ Lexikální analýza

XQuery

Další token

Syntaktická analýza

Obrázek 19: Lexikáln´ı a syntaktická analyza ´ (viz [8]) Bˇehem lexikáln´ı analyzy je vstupn´ı soubor pˇreveden na posloupnost tokenu, ´ ˚ na základˇe kterych syntaktická analyza vytvoˇr´ı strom. Nen´ı nutné, aby tyto dva kroky prob´ıhaly zcela ´ ´ oddˇelenˇe, tzn. nejprve vytvoˇren´ı pole tokenu˚ a aˇz poté proveden´ı analyzy. Syntaktická analyza ´ ´ si postupnˇe sama zˇ a´ dá o dalˇs´ı a dalˇs´ı tokeny. Blok provádˇej´ıc´ı lexikáln´ı analyzu ´ se obvykle oznaˇcuje jako tzv. scanner. V pˇr´ıpadˇe XQuery je situace o nˇeco málo komplikovanˇejˇs´ı a to pˇredevˇs´ım kvuli ˚ pˇr´ımym ´ konstruktorum. ˚ Prakticky to znamená, zˇ e se v XQuery m´ıs´ı samotná konstrukce dotazu s jazykem XML. Zásadn´ı rozd´ıl je jednak v pˇr´ıstupu k tzv. b´ılym ´ znakum ˚ a jednak v pohledu na kl´ıcˇ ová slova. 4.5.1

Termináln´ı symboly

Je nutné rozliˇsovat termináln´ı symbol a typ termináln´ıho symbolu. Z ukázky v tabulce 8 vyplyv´ ´ a, zˇ e v urˇcitych ´ pˇr´ıpadech bude obsah termináln´ıho symbolu rovnou dán jeho typem a v urˇcitych ´ pˇr´ıpadech bude potˇreba konkrétn´ı obsah upˇresnit konkrétn´ı hodnotou. Termináln´ı symboly bez obsahu

Termináln´ı symboly s obsahem

TT_DOLLAR TT_NOT_EQUAL TT_DOT TT_COMMA TT_LEFT_BRACKET

TT_STRING_LITERAL TT_INTEGER_LITERAL TT_NCNAME TT_DECIMAL_LITERAL

Tabulka 8: Pˇr´ıklady termináln´ıch symbolu˚ bez obsahu a s obsahem

Termináln´ı symboly se dˇel´ı na dvˇe skupiny (vyplyv´ ´ a ze standardu W3C). Prvn´ı skupinu tvoˇr´ı tzv. delimiting terminal symbols, cˇ esky oddˇeluj´ıc´ı terminály. To jsou takové termináln´ı symboly, které mohou následovat bezprostˇrednˇe za sebou bez jakéhokoli oddˇelovaˇce. Jedná se napˇr. o pomlˇcku, závorku, znaménko plus, ukonˇcovac´ı znaˇcku tagu a dalˇs´ı. Kompletn´ı seznam je moˇzné nalézt ve specifikaci standardu XQuery [5]. Pro lepˇs´ı pochopen´ı nen´ı sloˇzité pˇredstavit si jednoduchy´ aritmeticky´ vyraz, kde za levou závorkou následuje ihned unárn´ı minus, tzn. pomlˇcka. ´ Druhou skupinou jsou tzv. non-delimiting terminal symbols, neboli nedˇel´ıc´ı terminály. To jsou pˇredevˇs´ım kl´ıcˇ ová slova a identifikátory. Ty mus´ı byt ´ mezi sebou oddˇeleny b´ılou mezerou nebo nˇejakym je celkem zˇrejmy. ´ jinym ´ oddˇeluj´ıc´ım terminálem. Duvod ˚ ´ Staˇc´ı si pˇredstavit dvˇe kl´ıcˇ ová slova bez jakéhokoli oddˇelen´ı. V takovém pˇr´ıpadˇe by samozˇrejmˇe nebylo moˇzné urˇcit, zda se 44

jedná o dvˇe kl´ıcˇ ová slova nebo jeden dlouhy´ identifikátor. Kompletn´ı seznam tˇechto symbolu˚ je opˇet souˇca´ st´ı pˇr´ılohy. Nejednoznaˇcnost terminálu˚ Gramatika XQuery nedefinuje termináln´ı symboly uplnˇ e jednoznaˇcnˇe. To znamená, zˇ e urˇcity´ ´ textovy´ rˇ etˇezec muˇ ˚ ze byt ´ za ruzn ˚ ych ´ okolnost´ı identifikován jako ruzn ˚ y´ termináln´ı symbol. Jako pˇr´ıklad muˇ ˚ zeme uvést QName a NCName, viz ukázka 10. Oba symboly jsou v gramatice definovány jako termináln´ı. Jak se má scanner zachovat, jestliˇze následuj´ıc´ım rˇ etˇezcem na vstupu bude ,,aaa:bbb“? V tuto chv´ıli nelze s urˇcitost´ı rˇ´ıct, zda scanner pˇri poˇzadavku na dalˇs´ı terminál vrát´ı ,,aaa“ jako NCName nebo ,,aaa:bbb“ jako cely´ QName. QName PrefixedName UnprefixedName Prefix LocalPart NCName Name

::= ::= ::= ::= ::= ::= ::=

PrefixedName | UnprefixedName Prefix ’:’ LocalPart LocalPart NCName NCName Name - (Char* ’:’ Char*) NameStartChar (NameChar)*

Ukázka 10: Problematické termináln´ı symboly ˇ sen´ı problému spoˇc´ıvá v tom, zˇ e si blok syntaktické analyzy Reˇ podle parsovaného grama´ tického pravidla sám urˇc´ı mnoˇzinu termináln´ıch symbolu, ˚ kterou bude v danou chv´ıli ochoten akceptovat. To znamená, zˇ e syntaktická analyza ´ postupnˇe dotazuje scanner na termináln´ı symboly, jejichˇz vyskyt je v danou chv´ıli oˇcekáván a scanner pouze odpov´ıdá logickou hodnotou, zda ´ dany´ termináln´ı symbol aktuálnˇe je cˇ i nen´ı na vstupu. 4.5.2

Syntakticky´ strom

Obvykle prob´ıhá pˇreklad formáln´ıho jazyka na operátory nebo jiná elementárn´ı volán´ı (napˇr. instrukce assembleru) rovnou bˇehem fáze parsován´ı. V této implementaci jsou vˇsak obˇe fáze striktnˇe oddˇeleny a samotny´ pˇreklad prob´ıhá aˇz na základˇe pamˇet’ové konstrukce syntaktického stromu. Syntakticky´ strom je tvoˇren gramatickymi ´ pravidly pouˇzitymi ´ ve vstupn´ım dotazu, kde vnitˇrn´ı uzly tvoˇr´ı netermináln´ı symboly (gramatická pravidla) a listové uzly tvoˇr´ı terminály. Koˇrenovym ´ pravidlem je vˇzdy pravidlo Module (viz [5], pˇr´ıloha A.1). Striktn´ı oddˇelen´ı fáze parsován´ı a pˇrekladu má nˇekolik vyhod: ´ 1. Oba bloky je moˇzné nezávisle upravovat nebo v pˇr´ıpadˇe potˇreby uplnˇ e vymˇenit. ´ 2. Reprezentace ve formˇe syntaktického stromu umoˇznuje provést urˇcitou transformaci ˇ vstupn´ıho dotazu. Pokud by se práce dále rozˇsiˇrovala a z hlediska efektivity by se ukázalo, zˇ e normalizace vstupn´ıho dotazu bude nutná, muˇ syntaktického ˚ ze se provést právˇe na urovni ´ stromu. V práci [9] je syntakticky´ strom pouˇz´ıván jako model dotazu.

45

3. V souvislosti s pˇr´ıpadnym ´ propojen´ım procesoru s indexovanou XML databáz´ı a vyhledáván´ım TPQ (Tree Pattern Query) ve stromu operátoru˚ bude pravdˇepodobnˇe nutné provést transformaci na tzv. TPNF [14]. 4.5.3

Scanner <<struct>> Token

<<enum>> TokenType

string value

Typy terminálních symbolů

Scanner string text int position

bool lookup(TokenType[] t, int length) Token readToken(TokenType t) char getCurrent() char readChar()

Obrázek 20: Tˇr´ıdn´ı diagram scanneru Funkci scanneru, cˇ ili lexikáln´ı analyzy, zajiˇst’uje tˇr´ıda Scanner. Kl´ıcˇ ovymi metodami jsou ´ ´ readToken, lookup, readChar a getCurrent. Implementace scanneru Scanner (viz tˇr´ıdn´ı diagram na obr. 20) je instanciován vˇzdy na základˇe nˇejakého vstupn´ıho textového rˇ etˇezce text a pamatuje si pozici aktuálnˇe cˇ teného znaku v promˇenné position. Poziˇcn´ı promˇenná je inicializována na nulovou hodnotu. Metodou lookup je moˇzné dotazovat scanner, zda od aktuáln´ı pozice pˇreˇc´ıst danou lze sekvenci typu˚ termináln´ıch symbolu. ˚ Pˇri tomto nahl´ızˇ en´ı se z hlediska uˇzivatele scanneru nesm´ı nic zmˇenit. Scanner sice bˇehem lookup s poziˇcn´ı promˇennou pracuje, avˇsak pˇred navrácen´ım vysledku dojde k obnoven´ı jej´ıho puvodn´ ıho stavu. ´ ˚ Nahl´ızˇ en´ı je duleˇ ˚ zité proto, zˇ e ne vˇzdy je moˇzné rozhodnout o následuj´ıc´ım gramatickém pravidle na základˇe prvn´ıho pˇreˇcteného terminálu. Gramatika tedy nen´ı typu LL1. Napˇr´ıklad v pˇr´ıpadˇe deklarac´ı se konkrétn´ı syntaktické pravidlo urˇc´ı aˇz t´ım, co následuje za kl´ıcˇ ovym ´ slovem declare (viz pravidla na ukázce 11). [7] Setter

[11] BoundarySpaceDecl

::= BoundarySpaceDecl | DefaultCollationDecl | BaseURIDecl | ConstructionDecl | OrderingModeDecl | EmptyOrderDecl | CopyNamespacesDecl ::= "declare" "boundary-space" ("preserve" | "strip")

46

[12] DefaultNamespaceDecl [13] OptionDecl [14] OrderingModeDecl [15] EmptyOrderDecl [16] CopyNamespacesDecl

::= "declare" "default" ("element" | "function") "namespace" URILiteral ::= "declare" "option" QName StringLiteral ::= "declare" "ordering" ("ordered" | "unordered") ::= "declare" "default" "order" "empty" ("greatest" | "least") ::= "declare" "copy-namespaces" PreserveMode "," InheritMode

Ukázka 11: Gramatická pravidla nerozhodnutelná na základˇe prvn´ıho terminálu

Metoda readToken funguje podobnˇe jako lookup, avˇsak jej´ı cˇ innost konˇc´ı navrácen´ım obsahu jednoho typu termináln´ıho symbolu (pˇredaného argumentem) a upravou position. Par´ ser obvykle pomoc´ı lookup nejprve vyzkouˇs´ı nˇekolik moˇznost´ı a aˇz poté se rozhodne, jakym ´ zpusobem se zanoˇr´ı. ˚ Velmi duleˇ ˚ zité veˇrejné metody jsou také getCurrent a readChar. Obˇe metody vrac´ı znak vstupn´ıho rˇ etˇezce na aktuáln´ı pozici position. Metoda readChar nav´ıc pˇred navrácen´ım vysledku poziˇcn´ı promˇennou inkrementuje. Je zde moˇzné nalézt analogii s metodami lookup ´ a readToken. 4.5.4

Syntaktická analyza ´

Syntaktická analyza ´ se provád´ı pomoc´ı rekurzivn´ıho sestupu dle dané gramatiky. Z tˇr´ıdn´ıho diagramu na obrázku 21 je patrné, zˇ e pro implementaci syntaktického stromu byl vyuˇzit návrhovy´ vzor kompozit. Termináln´ı uzel (SyntaxTerminalNode) se vˇzdy odkazuje na konkrétn´ı termináln´ı symbol (Token – viz tˇr´ıdn´ı diagram na obr. 20). Netermináln´ı uzel byl vytvoˇren vˇzdy podle nˇejakého gramatického pravidla a odkazuje se tedy na jeden z prvku˚ vyˇ ´ ctu RuleType. Parser *

Scanner scanner

SyntaxNode SyntaxNode SyntaxNode … SyntaxNode

<> SyntaxNode

*

vytvořené instance

void print() string toString()

parseRule1() parseRule2() parseRule3() parseToken(TokenType t)

SyntaxTerminalNode

void print() string toString()

SyntaxNonterminalNode MyList<SyntaxNode> childNodes void addChild(SyntaxNode node) SyntaxNode getChild(int index) int count() string toString()

<<struct>> Token

Obrázek 21: Tˇr´ıdn´ı diagram parseru

47

<<enum>> RuleType

Generován´ı parseru V uvodu podkapitoly 4.5 bylo naznaˇceno, zˇ e implementace parseru probˇehla cˇ a´ steˇcnˇe auto´ matizovanˇe. Vubec prvn´ı krok, jeˇstˇe pˇred zahájen´ım práce na procesoru, spoˇc´ıval ve vytvoˇren´ı ˚ jednoduchého generátoru, ktery´ z dané gramatiky v EBNF základ parseru XQuery v jazyce C++ vytvoˇril. Jen pro ilustraci - metod parse* se ve tˇr´ıdˇe Parser nacház´ı v´ıce neˇz 100. Bez tohoto zjednoduˇsen´ı by bylo manuáln´ı kodov´ an´ı cˇ asovˇe velmi nároˇcné. ´ Tento jednoduchy´ generátor si poradil se základn´ımi konstrukcemi samotné gramatiky – sekvencemi, alternativami, iteracemi symbolu˚ s povinnym vyˇ ´ nebo nepovinnym ´ vyskytem, ´ ´ cty znaku˚ atd. Komplikované bylo pˇredevˇs´ım sestaven´ı kodu pro analyzu ´ ´ alternativy právˇe z duvodu ˚ nejednoznaˇcnosti terminálu. ˚ Vysledkem byl kod, ´ ´ jenˇz obsahoval metody parse*, které se za pomoc´ı nahl´ızˇ en´ı navzájem volaly. Generátor velmi dobˇre poslouˇzil pro vytvoˇren´ı kodu analyzuj´ıc´ıho XQuery dotazy bez ´ pˇr´ımych ´ XML konstruktoru. ˚ Jejich parsován´ı bylo nutné doimplementovat manuálnˇe. Ne vˇzdy generátor sestavil kod e správnˇe tak, aby parser ,,nezabloudil“. Do´ u alternativ uplnˇ ´ dateˇcné upravy byly v principu jednoduché, avˇsak vzhledem k mnoˇzstv´ı gramatickych ´ ´ pravidel cˇ asovˇe dosti nároˇcné. V mnoha pˇr´ıpadech bylo nutné upravit poˇrad´ı podm´ınek tak, aby napˇr. bylo upˇrednostnˇeno kl´ıcˇ ové slovo oproti identifikátoru. Oˇsetˇren´ı chyb a správa pamˇeti Lexikáln´ı i syntaktická analyza skonˇcit ´ muˇ ˚ ze v pˇr´ıpadˇe nekorektnˇe zadaného XQuery vyrazu ´ chybou. Muˇ ˚ ze se jednat napˇr. o neoˇcekávany´ token, neuzavˇrenou závorku, neukonˇceny´ tag a dalˇs´ı. Jestliˇze parser naraz´ı na chybu, vygeneruje se vyjimka s pˇr´ısluˇsnym ´ ´ chybovym ´ kodem. ´ Souˇca´ st´ı tˇr´ıdy Parser (viz tˇr´ıdn´ı diagram na obr. 21) je datová struktura, která postupnˇe shromaˇzd’uje reference na vzniklé uzly syntaktického stromu. Tato struktura je v souˇcasné verzi rˇ eˇsena pomoc´ı MyList<SyntaxNode>. Vˇzdy pˇri instanciován´ı termináln´ıho nebo netermináln´ıho uzlu se do struktury okamˇzitˇe pˇridá vzniklá reference. Vˇsechny vzniklé instance je tak moˇzné i v pˇr´ıpadˇe chyby a následnˇe generované vyjimky rˇ a´ dnˇe odalokovat. ´ Parsován´ı XML Vypoˇctené konstruktory jsou z hlediska parsován´ı rutinn´ı záleˇzitost. Menˇs´ı komplikace nastanou pˇri pouˇz´ıván´ı konstruktoru˚ pˇr´ımych. Jakmile parser naraz´ı na pravidlo DirectConstructor, neˇza´ dá ´ scanner dále o tokeny, ale cˇ te vstupn´ı soubor po znac´ıch pomoc´ı metod readChar a getCurrent, které jsou souˇca´ st´ı scanneru (viz obr. 20). Bˇehem parsován´ı XML je potˇreba sledovat zaˇca´ tky a konce elementu, ˚ komentárˇ u˚ nebo procesn´ıch instrukc´ı. V hlaviˇckách uzlu˚ se mohou samozˇrejmˇe objevit také atributy. Kromˇe toho je potˇreba poˇc´ıtat s pˇreddefinovanymi entitami napˇr. pro zápis znaku ,,<“ nebo ,,>“, tzn. < nebo ´ >. Nakonec se v obsahu elementu, ˚ atributu˚ nebo komentárˇ u˚ muˇ ˚ ze objevit i zanoˇreny´ vyraz ´ ve sloˇzenych z´ a vork´ a ch. ´ Byl vytvoˇren speciáln´ı typ tokenu TT_EXTRA, ktery´ slouˇz´ı právˇe pro uˇ ´ cely, kdy se tokeny nevytvárˇ´ı bˇehem lexikáln´ı, ale aˇz bˇehem syntaktické analyzy. Na obrázku 22 je naznaˇceno parsován´ı ´ krátkého konstruktoru XML elementu a. Celkem zaj´ımavou vlastnost´ı jazyka XQuery je, zˇ e na cely´ XQuery procesor lze svym ´ zpusobem ˚ pohl´ızˇ et také jako na parser XML. Pokud se v XML vyhneme nˇekterym ´ speciáln´ım konstrukc´ım, 48

vysledek = x < y + { $i }

:SyntaxTerminalNode

:SyntaxTerminalNode

:SyntaxNonterminalNode

token.tokenType = TT_EXTRA token.value = “vysledek = x“

token.tokenType = TT_EXTRA token.value = “y + “

ruleType = RT_ENCLOSED_EXPR

:SyntaxNonterminalNode ruleType = RT_COMMON_CONTENT

Obrázek 22: Princip parsován´ı XML elementu které jsou charakteristické pro XQuery, pak ono XML samo o sobˇe pˇredstavuje platny´ XQuery dotaz. Tento ,,dotaz“ se pˇreloˇz´ı na operátory tak, zˇ e vysledkem vyhodnocen´ı je DOM. Aby bylo ´ jednoznaˇcnˇe rozliˇseno, co je skuteˇcnˇe XML a co je XQuery dotaz, gramatika XQuery zakazuje, aby se v hlaviˇcce dotazu nacházela procesn´ı instrukce . Pˇri testován´ı procesoru bˇehem vyvoje byla uvedená vlastnost uplatnˇena ve vestavˇené funkci ´ pro naˇc´ıtán´ı vstupn´ıch XML dokumentu. ˚ Pozdˇeji byla funkce z hlediska efektivity upravena tak, aby pro parsován´ı XML dokumentu vyuˇz´ıvala Xerces Parser.

4.6

Kompiler

Jakmile máme pˇripraveny´ syntakticky´ strom, potˇrebujeme z nˇej vytvoˇrit plán vykonáván´ı dotazu. O tuto transformaci se stará kompiler neboli pˇrekladaˇc implementovany´ tˇr´ıdou Compiler. Tˇr´ıdn´ı diagram základn´ıch typu˚ pˇrekladaˇce se nacház´ı na obr. 23. Ze stejnych u, ´ duvod ˚ ˚ jako u syntaktické analyzy, ´ je pˇri vytvárˇ en´ı instanc´ı konkrétn´ıch operátoru˚ nutné peˇclivˇe udrˇzovat seznam vzniklych ´ referenc´ı. O jejich evidenci se v tomto pˇr´ıpadˇe nestará sama tˇr´ıda Compiler, ale oddˇelená tˇr´ıda OperatorManager. K tomuto rozdˇelen´ı doˇslo proto, zˇ e kompiler nen´ı jediné m´ısto, kde mohou objekty operátoru˚ vznikat. Na diagramu jsou dále zachyceny abstraktn´ı tˇr´ıdy Operator a StaticOpType pro reprezentaci operátoru a statické sloˇzky operátoru. 4.6.1

Kompilace

V tomto kroku muˇ ˚ zeme pˇredpokládat, zˇ e byl syntakticky´ strom vytvoˇren pomoc´ı parseru a je tedy v souladu s gramatikou XQuery. Souˇca´ st´ı kompileru je mnoˇzstv´ı metod expand*, které na základˇe nˇejaké konstrukce XQuery, tzn. syntaktického uzlu, sestav´ı operátor, resp. opˇet cely´ strom operátoru. ˚

49

Závislé a nezávislé suboperátory *

OperatorManager

vytvořené instance *

Operator createAnd() Operator createSelect() Operator createJoin() …

<> Operator DataModelManager dataModelManager Enviroment enviroment MyList getDependent() MyList getIndependent() MyList<StaticOpType> getStatic()

int saveSubstState() void restoreSubstState()

string toString() DataValue evaluate(DataValue input) void evaluateStatic() void evaluateStaticCore()

Compiler DataModelManager dataModelManager

Statické atributy operátorů *

Operator expandXQuery(SyntaxNonterminalNode root) *

Operator expandExpr(SyntaxNonterminalNode rule) Operator expandFLWOR(SyntaxNonterminalNode rule) … StaticOpType expandKindTest(SyntaxNonterminalNode rule) …

vytvořené instance

<> StaticOpType DataModelManager dataModelManager string toString() DataValue evaluate(DataValue input)

Obrázek 23: Tˇr´ıdn´ı diagram pˇrekladaˇce Metoda expandExpr Tato metoda tˇr´ıdy Compiler pˇredstavuje univerzáln´ı vychoz´ ı bod pro kompilaci jakéhokoli ´ gramatického pravidla, tzn. neterminálu. Na základˇe typu vstupn´ıho netermináln´ıho uzlu se metoda rozhodne, zda je pravidlo natolik jednoduché, zˇ e se o pˇreklad postará sama nebo pro zpracován´ı zavolá jinou konkrétn´ı metodu expand*.

Pˇr´ıklad 4: Kompilace vˇetven´ı Algoritmus 1 demonstruje kompilaci jednoduchého pravidla vˇetven´ı IfExpr podle gramatického pravidla na ukázce 12. Zde je gramatikou pˇresnˇe urˇceno, na jakych ´ pozic´ıch se poduzly pˇredstavuj´ıc´ı podm´ınku, kladnou a zápornou vˇetev nacházej´ı. [45] IfExpr ::= "if" "(" Expr ")" "then" ExprSingle "else" ExprSingle

Ukázka 12: Gramatické pravidlo pro vˇetven´ı

V tomto pˇr´ıpadˇe je vytvoˇrena instance operátoru Cond. Instance nen´ı zaloˇzena standardnˇe kl´ıcˇ ovym slovem new, ale metodou createCond (objektu správce operátoru˚ ´ OperatorManager), která podle argumentu˚ rovnou nastav´ı v poˇrad´ı operátor pro vypoˇ ´ cet kladné vˇetve, operátor pro vypoˇ ´ cet záporné vˇetve a operátor pro vypoˇ ´ cet podm´ınky. Z gramatiky v´ıme, zˇ e se netermináln´ı symbol pro logicky´ vyraz rozhoduj´ıc´ı podm´ınku nacház´ı v rámci ´ pravidla IfExpr pevnˇe na indexu 2, pravidlo pro kladnou vˇetev na indexu 5 a pravidlo pro zápornou vˇetev na indexu 7. Pro kompilaci tˇechto pravidel se rekurzivnˇe opˇet zavolá metoda expandExpr.

50

ˇ ast metody expandExpr pro pˇreklad podm´ınky Algoritmus 1: C´ if pˇrekládaným pravidlem je IfExpr then return operatorManager.createCond( expandExpr(potomek syntaktického uzlu na indexu 5), expandExpr(potomek syntaktického uzlu na indexu 7), expandExpr(potomek syntaktického uzlu na indexu 2)); end

Volán´ı jiné metody pro pˇreklad Jestliˇze univerzáln´ı metoda expandExpr zjist´ı, zˇ e pˇrekládá napˇr. pravidlo AndExpr nebo OrExpr, nen´ı uˇz kompilace tak pˇr´ımoˇcará jako v pˇredchoz´ım pˇr´ıpadˇe a zavolá se jednouˇ ´ celová metoda expandAndExpr nebo expandOrExpr. Kompilaci by sice v tomto pˇr´ıpadˇe jeˇstˇe bylo moˇzné vyˇreˇsit rovnou v tˇele expandExpr, avˇsak vysledn y´ kod ´ ´ by se takto pomalu stal velmi nepˇrehlednym. ´ Propadáván´ı pravidel Existuje mnoho pˇr´ıpadu, ˚ kdy se neterminál pouze alternativnˇe pˇrepisuje na jeden jiny´ neterminál. NumericLiteral := IntegerLiteral | DecimalLiteral | DoubleLiteral

Ukázka 13: Propadaj´ıc´ı pravidlo

Z hlediska parsován´ı jsou takovéto pˇrepisy duleˇ ˚ zité, ale z hlediska kompilace tato pravidla svym propadávaj´ı a nedocház´ı k vytvárˇ en´ı zˇ a´ dného operátoru. Jestliˇze se tedy kompi´ zpusobem ˚ luje napˇr. pravidlo NumericLiteral z ukázky 13, pak metoda expandSyntax rovnou zavolá sama sebe s nultym ´ potomkem netermináln´ıho uzlu, ktery´ právˇe zpracovává. V tomto pˇr´ıpadˇe to bude vˇzdy jedeno z pravidel IntegerLiteral, DecimalLiteral nebo DoubleLiteral. Teprve tato pravidla budou zkompilována na operátor Scalar. Substistuce promˇennych ´ O substituci promˇennych se stará jiˇz zminovan´ a tˇr´ıda OperatorManager, která primárnˇe ´ ˇ slouˇz´ı pro správu pamˇeti. Vyuˇz´ıvá se zde toho, zˇ e jedinym ´ moˇznym ´ m´ıstem v programu, kde muˇ ˚ ze vzniknout operátor Var pro pˇr´ıstup k promˇenné, je metoda createVar právˇe ve tˇr´ıdˇe OperatorManager. V této metodˇe lze proj´ıt tabulku aktuálnˇe substituovanych promˇennych ´ ´ a v pˇr´ıpadˇe nalezen´ı shody vrátit m´ısto instance Var instanci operátoru TupeAccess s pˇr´ıstupem do kontextové n-tice IN. Kdy se substituce provád´ı a jaky´ je jej´ı vyznam popisuje kapitola 3.3.2. ´ Z hlediska kompileru, cˇ ili tˇr´ıdy Compiler a nˇekteré z metod expand* (viz tˇr´ıdn´ı diagram na obr. 23), lze pouˇz´ıván´ı substituc´ı pˇripodobnit zásobn´ıku (proto také název metody pushSubst). Jestliˇze byla v poˇrad´ı aktivována nejprve substituce promˇenné var1 a aˇz poté var2 , mus´ı doj´ıt ke zruˇsen´ı substituce v opaˇcném poˇrad´ı, tzn. var2 , poté var1 . Duálnˇe k metodˇe pushSubst by tedy mˇela existovat také nˇejaká metoda popSubst.

51

Ve skuteˇcnosti je tomu ale trochu jinak. Zat´ımco aktivován´ı substituc´ı prob´ıhá obvykle postupnˇe napˇr. v urˇcitych zruˇsen´ı substituc´ı se provád´ı najednou. Z toho ´ fáz´ıch kompilace FLWOR vyrazu, ´ duvodu je v yhodnˇ e jˇ s ı celkov y stav substituc´ ı nejprve nˇejakym uloˇzit, poté pokraˇcovat ˚ ´ ´ ´ ´ zpusobem ˚ v kompilaci, podle potˇreby substituce jednotlivych ´ promˇennych ´ postupnˇe aktivovat a nakonec se k uloˇzenému stavu opˇet vrátit. Uloˇzen´ı a obnoven´ı substituˇcn´ıho stavu se provád´ı metodami getSubstState a restoreSubstState. Uložení stavu substituce

Aktivace substituce

Obnovení stavu

i dot

k j i dot

k j i dot

int state = saveSubstState(); // state = 1

pushSubst(“j“); pushSubst(“k“);

restoreSubstState(state);

Obrázek 24: Princip substituce promˇennych ´ Z ukázky na obrázku 24 je patrné, zˇ e pˇri obnoven´ı stavu substituce zust´ ˚ avaj´ı v tabulce názvy promˇennych. To samozˇrejmˇe niˇcemu nevad´ı, protoˇze pˇri testu na substituci prob´ıhá vyhledáván´ı ´ pouze po aktuáln´ı index. 4.6.2

Kompilace sloˇzitˇejˇs´ıch konstrukc´ı

Mezi komplikovanˇejˇs´ı konstrukce XQuery na kompilaci patˇr´ı FLWOR a XPath vyrazy. V obou ´ pˇr´ıpadech se vˇsak jedná pouze o opatrnou manipulaci s gramatickymi pravidly a vytvárˇ en´ı ´ operátoru˚ podle pouˇzité algebry, tzn pravidel nadefinovanych ´ v kapitolách 3.3.2 a 3.3.3. Z hlediska implementace je obt´ızˇ ná zejména správná lokalizace kl´ıcˇ ovych ´ gramatickych ´ pravidel v syntaktickém stromu. Tato uloha by byla pravdˇepodobnˇe snazˇs´ı, kdyby pˇreklad prob´ıhal ´ rovnou bˇehem parsován´ı. Pˇriˇsli bychom ale o urˇcité vyhody (viz kapitola 4.5.2). Pro ilustraci jsou ´ základn´ı gramatická pravidla pro FLWOR a XPath vyrazy uvedena v ukázkách 14 a 15. ´ [33]

FLWORExpr

[34]

ForClause

[35] [36]

PositionalVar LetClause

[37]

WhereClause

::= (ForClause | LetClause)+ WhereClause? OrderByClause? "return" ExprSingle ::= "for" "$" VarName TypeDeclaration? PositionalVar? "in" ExprSingle ("," "$" VarName TypeDeclaration? PositionalVar? "in" ExprSingle)* ::= "at" "$" VarName ::= "let" "$" VarName TypeDeclaration? ":=" ExprSingle ("," "$" VarName TypeDeclaration? ":=" ExprSingle)* ::= "where" ExprSingle

Ukázka 14: Koˇrenové neterminály FLWOR

52

[68]

PathExpr

RelativePathExpr

::= | | ::=

("/" RelativePathExpr?) ("//" RelativePathExpr) RelativePathExpr StepExpr (("/" | "//") StepExpr)*

[69] [70] [71] [72] [75] [82]

StepExpr AxisStep ForwardStep ReverseStep PredicateList

::= ::= ::= ::= ::=

FilterExpr | (ReverseStep (ForwardAxis (ReverseAxis Predicate*

AxisStep | ForwardStep) PredicateList NodeTest) | AbbrevForwardStep NodeTest) | AbbrevReverseStep

Ukázka 15: Koˇrenové neterminály pro XPath

4.7

Optimalizace

Samotná optimalizace se skádá z postupného uplatnˇen´ı nˇekolika optimalizaˇcn´ıch pravidel, která byla nadefinována v kapitole 3.4. Aplikace kaˇzdého z nich je nepovinná, resp. vysledek vyhod´ nocen´ı dotazu mus´ı s optimalizac´ı i bez n´ı stejny. ´ Optimalizátor funguje na modulárn´ım principu a je tedy moˇzné snadno urˇcovat, jaká pravidla se skuteˇcnˇe uplatn´ı a v jakém poˇrad´ı. <> OperatorTransformation

<> Operator

Operator transform(Operator input)

... Operator transform(OperatorTransformation transform) ...

<> OptimizerTransformation OperatorManager operatorManager Operator transform(Operator input)

RemoveMapToItemTransformation

RemoveMapConcatTransformation

InsertProductTransformation




...

Obrázek 25: Tˇr´ıdn´ı diagram optimalizace Tˇr´ıda OperatorTransformation z tˇr´ıdn´ıho diagramu na obr. 25 obecnˇe popisuje nˇejakou transformaci operátoru metodou transform bez návaznosti na optimalizátor. Konkrétn´ı implementace této metody muˇ ˚ ze zajistit nahrazen´ı jednoho operátoru nebo kombinace jinym ´ operátorem nebo kombinac´ı. Abstraktn´ı tˇr´ıda OptimizerTransformation popisuje transformaci urˇcenou vyhradnˇ e pro ´ optimalizátor. Tyto dvˇe urovnˇ e abstrakce vznikly proto, aby byl cely´ systém schopen s mi´ nimáln´ımi upravami fungovat i v teoretickém pˇr´ıpadˇe odebrán´ı vˇseho, co se optimalizac´ı tyˇ ´ ´ ce. Vzhledem k tomu, zˇ e optimalizac´ı vznikaj´ı nové operátory, je potˇreba transformac´ım optimizéru pˇredat také instanci OperatorManager. 53

Aby bylo moˇzné transformaci propagovat na cely´ strom, doˇslo k rozˇs´ırˇ en´ı tˇr´ıdy Operator z tˇr´ıdn´ıho diagramu na obrázku 23 o abstraktn´ı metodu transform. Kaˇzdá konkrétn´ı implementace operátoru mus´ı v této metodˇe na základˇe argumentem pˇredané transformace upravit nejprve vˇsechny své suboperátory a poté vrátit transformovanou podobu sama sebe (this). Na algoritmu 2 je zachycena transformace operátoru Select. Identifikátor op pˇredstavuje operátor pro vypoˇ – podm´ınky ´ cet nezávislého vstupu, boolean je operátor pro vypoˇ ´ cet mezivysledku ´ selekece. Algoritmus 2: Transformace operátoru Select input : transformace t ve formˇe instance OperatorTransformation output: transformovaná podoba operátoru Select op ← op.transform(t); boolean ← boolean.transform(t); return t.transform(this);

Pˇr´ıklad 5: Transformace vloˇzen´ı Product Pro ukázku zde bude na algoritmu 3 popsáno nahrazen´ı operátoru MapConcat operátorem Product, tzn. kartézskym ´ souˇcinem. Proˇc je toto moˇzné a za jakych ´ okolnost´ı, popisuje kapitola 3.4.3. Logiku transformace zajiˇst’uje metoda tˇr´ıdy InsertProductTransform, která dˇed´ı z OptimizerTransformation na tˇr´ıdn´ım diagramu (obr. 25). Transformace se uplatn´ı pouze tehdy, jestliˇze zpracovává operátor MapConcat, jinak metoda vrát´ı vstupn´ı operátor beze zmˇeny. Pˇri uplatnˇen´ı transformace je potˇreba zjistit, zda se v závislém podoperátoru nenacház´ı reference na kontextovou n-tici, resp. operátor IN. Prohledat se mus´ı cely´ podstrom, pˇriˇcemˇz v podstromu se prohledávaj´ı pouze nezávislé suboperátory. Pˇri pˇrechodu na závisly´ suboperátor by se pˇr´ıpadnˇe nalezeny´ IN nevztahoval k MapConcat, pro ktery´ IN hledáme (viz kapitola 3.2.3). Jednou z moˇznost´ı, jak tuto detekci provést je pro pruchod stromem at’ uˇz do hloubky nebo ˚ do sˇ´ırˇ ky pouˇz´ıt rekurzi. Rekurzivn´ı procházen´ı operátoru˚ je nahrazeno zásobn´ıkem, na jehoˇz vrchol je ze zaˇca´ tku um´ıstˇen nezávisly´ podoperátor právˇe zpracovávaného mapConcat. V pˇr´ıpadˇe, zˇ e má doj´ıt k nahrazen´ı, je m´ısto puvodn´ ıho mapConcat navrácena nová instance ˚ Product s pˇrebranym ´ závislym ´ i nezávislym ´ podoperátorem.

4.8

Vyhodnocován´ı

Posledn´ı fáze spoˇc´ıvá ve vyhodnocen´ı pˇripraveného plánu dotazu. V blokovém schématu na obrázku 15 je sice naznaˇceno, zˇ e se o vyhodnocen´ı stará procesor. Ve skuteˇcnosti je principem vyhodnocen´ı volán´ı metody operátoru evaluate, která argumentem pˇreb´ırá kontextovou hodnotu. V dalˇs´ı cˇ a´ sti textu budou popsány pouze nˇekteré sloˇzitˇejˇs´ı operátory. Vˇetˇsina operátoru˚ provád´ı triviáln´ı operace, jejichˇz popis by zde postrádal smysl.

54

Algoritmus 3: Transformace vloˇzen´ı Product input : operátor op – koˇren transformovaného podstromu output: transformovaná podoba if transformovaný operátor je MapConcat then inicializuj prázdny´ zásobn´ık ; mapConcat ← pˇretypuj op na MapConcat ; vloˇz do zásobn´ıku závisly´ operátor z mapConcat ; while zásobn´ık nen´ı prázdný do oppom ← vyjmi prvek ze zásobn´ıku ; if oppom je operátor IN then byl nalezen závisly´ IN ; ukonˇci cyklus ; else vloˇz do zásobn´ıku vˇsechny nezávislé operátory z oppom ; end end if byl nalezen závislý IN then return instanciuj Product s puvodn´ ˚ ım nezávislým a závislým vstupem z mapConcat ; end end return vstupn´ı operátor op beze zmˇeny ;

4.8.1

Vyhodnocen´ı statickych ´ sloˇzek operátoru˚

V pˇr´ıpadˇe nˇekterych ´ operátoru˚ je pˇred spuˇstˇen´ım vykonáván´ı plánu potˇreba nejprve inicializovat nˇejaké vnitˇrn´ı promˇenné na základˇe statickych ´ sloˇzek. Jedná se napˇr. o pˇreklad názvu˚ sloˇzek n-tic na symbolické názvy (viz kapitola 4.4.5). O statické vyhodnocen´ı se staraj´ı metody evaluateStatic a evaluateStaticCore (viz tˇr´ıdn´ı diagram na obr. 23). Prvn´ı metoda pouze zajiˇst’uje rekurzivn´ı volán´ı sama sebe na závislé i nezávislé operátory a volán´ı evaluateStaticCore. Ve druhé uvedené metodˇe je moˇzné podle potˇreby provést inicializaci, která závis´ı na statickych ´ sloˇzkách a sloˇzen´ı závislych ´ nebo nezávislych suboperátoru. ´ ˚ Volán´ım evaluateStatic na koˇrenovy´ operátor celého stromu jeˇstˇe pˇred zaˇca´ tkem vyhodnocován´ı dotazu tak muˇ ˚ zeme pˇrednastavit nˇekteré vnitˇrn´ı vlastnosti operátoru, ˚ které jsou bˇehem vyhodnocován´ı nemˇenné. 4.8.2

Operátor Select

ˇ Cinnost algoritmu 4 pro vyhodnocen´ı Select nen´ı sama o sobˇe nijak zaj´ımavá, c´ılem ukázky pseudokodu 4 je prezentace vˇsech pˇredem pˇripravenych ´ ´ vlastnost´ı datového modelu. Nejprve je vyhodnocen nezávisly´ podoperátor op nad stejnym ´ kontextem, s jakym ´ byl volán právˇe zpracovávany´ Select. Jedná se o operátor vracej´ıc´ı vstupn´ı tabulku n-tic. Dále si lze vˇsimnout jednak praktického vyuˇzit´ı metody pro pˇretypován´ı asDataTupleEnumerable a jednak toho, zˇ e na vyhodnoceny´ vstup nen´ı pohl´ızˇ eno jako na tabulku, ale jako na DataTupleEnumerable. Nezáleˇz´ı na tom, zda je vstupem celá tabulka, nebo jedna n-tice. 55

Algoritmus 4: Vyhodnocen´ı operátoru Select input : kontextová hodnota in output: tabulka n-tic po proveden´ı selekce DataValue inputValue ← op.evaluate(in) ; DataTupleEnumerable inputEnumerable ← inputValue.asDataTupleEnumerable() ; DataTable outputTable ← dataModelManager.createDataTable() ; TableIterator iterator ← inputEnumerable.getIterator() ; while iterator.hasNext() do DataTuple tuple ← iterator.getNext() ; dataModelManager.pushInstanceCounters() ; DataValue value ← boolean.evaluate(tuple) ; dataModelManager.popInstanceCounters() ; BooleanItem boolItem ← value.asBooleanItem() ; if boolItem.value = true then pˇridej n-tici tuple do vystupn´ ı tabulky outputTable ; ´ end end return outputTable;

Pomoc´ı dataModelManager je vytvoˇrena instance vystupn´ ı tabulky a muˇ ´ ˚ ze se zahájit iterace pˇres vstup. Pro kaˇzdou zpracovávanou n-tici je vyhodnocen závisly´ boolean, ktery´ vyhodnocuje podm´ınku selekce. Pˇred resp. po vyhodnocen´ı boolean jsou volány metody pushInstanceCounters a popInstanceCounters, které zajist´ı moˇznost recyklace instanc´ı promˇennych. Ze vˇsech hod´ not, které potenciálnˇe vzniknou bˇehem zpracován´ı boolean nás totiˇz zaj´ımá pouze vystupn´ ı ´ BooleanItem a i tu je moˇzné po pˇreˇcten´ı skuteˇcné logické hodnoty okamˇzitˇe zahodit. Ostatn´ı hodnoty, musely vzniknout z duvodu nˇejakého mezivysledku, ktery´ nás uˇz dále nezaj´ımá. Problém by ˚ ´ mohl vzniknout jen v pˇr´ıpadˇe pouˇz´ıván´ı globáln´ıch promˇennych, které ale zat´ım implementovány ´ nejsou. Pokud by bˇehem vypoˇ doˇslo k vytvoˇren´ı obsahu globáln´ı promˇenné, ´ ctu mezivysledku ´ nesmˇel by byt ´ tento obsah zahozen. 4.8.3

Operátor TreeJoin

Operátor TreeJoin je jedn´ım z tˇech, které operuj´ı pouze nad sekvencemi poloˇzek. Nejsloˇzitˇejˇs´ı cˇ a´ st cˇ innosti operátoru je navigace v XML stromu, kterou neˇreˇs´ı sám operátor, ale tˇr´ıda XmlNode. Navigace na osu descendant Nejen, zˇ e je navigace na vˇsechny pˇr´ımé nebo nepˇr´ımé potomky cˇ asto vyuˇz´ıvaná pˇr´ımo v XQuery dotazu, pomoc´ı této navigace lze také rozepsat nˇekteré dalˇs´ı – preceding, following nebo descendant-or-self. Algoritmus pro zjiˇstˇen´ı vˇsech potomku˚ v DOM reprezentaci je sám o sobˇe velmi jednoduchy. ´ Staˇc´ı rekurzivnˇe proj´ıt cely´ podstrom pro dany´ XML element. Je pouze potˇreba zachovat poˇrad´ı

56

uzlu, ˚ coˇz je zajiˇstˇeno procházen´ım do hloubky. Byly otestovány celkem cˇ tyˇri moˇznosti implementace této metody – jednoduchá rekurze, pˇrepis na nerekurzivn´ı podobu pomoc´ı zásobn´ıku realizovaného spojovym ´ seznamem, pˇrepis na nerekurzivn´ı podobu pomoc´ı zásobn´ıku realizovaného polem a pruchod pˇredpˇripravenym ˚ ´ spojovym ´ seznamem, ktery´ byl konstruován bˇehem vytvárˇ en´ı DOM (viz n´ızˇ e). Posledn´ı zminovan y´ zpusob se experimentálnˇe ukázal jako nejefektivnˇejˇs´ı, nicménˇe neˇ ˚ dodrˇzuje puvodn´ ı poˇrad´ı uzlu˚ podle dokumentu. Druhym ˚ ´ nejrychlejˇs´ım se ukázala klasická rekurze, o nˇeco pomalejˇs´ı byla nerekurzivn´ı varianta se zásobn´ıkem realizovanym ´ pomoc´ı MyList a nejhuˇ ˚ re dopadla nerekurzivn´ı varianta se zásobn´ıkem realizovanym ´ spojovym ´ seznamem. Vˇse bylo testováno na na XML dokumentu o velikosti 18 MB s cca 300 tis´ıci XML uzly (viz popis v kapitole 5) a jednoduchém XPath dotazu //item[@id="item4016"]. Prumˇ ˚ erné cˇ asy vyhodnocován´ı jsou uvedeny v tabulce 9. Pruchod spojovym ˚ ´ seznamem Pouˇzit´ı rekurze Nerekurzivn´ı varianta pomoc´ı pole Nerekurzivn´ı varianta pomoc´ı spojového seznamu

110 ms 120 ms 135 ms 210 ms

Tabulka 9: Srovnán´ı algoritmu˚ pro navigaci na osu descendant

Efektivitu rekurze lze v tomto pˇr´ıpadˇe zduvodnit t´ım, zˇ e se v tˇele metody fyzicky pouˇz´ıvaj´ı ˚ pouze dvˇe lokáln´ı promˇenné. Argumenty metody jsou oznaˇceny jako const, takˇze pˇri rekurzivn´ım volán´ı by nemˇelo docházet ani k vytvárˇ en´ı lokáln´ıch kopi´ı. Nav´ıc u bˇezˇ nych XML se ´ urove nˇ zanoˇren´ı pohybuje maximálnˇe v rˇ a´ du jednotek aˇz des´ıtek. ´ Neefektivitu zásobn´ıku realizovaného spojovym ´ seznamem lze vysvˇetlit t´ım, zˇ e pro kaˇzdou poloˇzku je nutné vytvoˇrit novou instanci zaobaluj´ıc´ıho uzlu.

Postorder seznam Relativnˇe zaj´ımavá experimentáln´ı metoda podávaj´ıc´ı m´ırnˇe lepˇs´ı vysledky neˇz rekurze je pouˇzit´ı ´ pˇredpˇripraveného spojového seznamu, ktery´ lze velmi jednoduˇse konstruovat pˇri vytvárˇ en´ı DOM a reprezentovat nˇekolika pomocnymi promˇennymi pˇr´ımo ve tˇr´ıdˇe XmlNode. Seznam je postupnˇe ´ ´ vytvárˇ en tak, aby pruchodem vznikl postorder zápis. Kaˇzdy´ novˇe pˇridany´ uzel je zaˇrazen bez˚ prostˇrednˇe pˇred svého rodiˇce. Procházen´ı vˇsech potomku˚ zaˇc´ıná nalezen´ım nejlevˇejˇs´ıho uzlu celé vˇetve. Poté je seznam procházen tak dlouho, neˇz je nalezen pro danou vˇetev koˇrenovy´ uzel. Pruchod sice nevrac´ı uzly podle puvodn´ ıho uspoˇra´ dán´ı v dokumentu, coˇz ale nevad´ı, pokud ˚ ˚ bude procesor ve vychoz´ ım stavu pracovat v tzv. unordered reˇzimu (viz [5]). Pˇredpokladem je, zˇ e ´ procesor nikdy nekonstruuje DOM tak, zˇ e by uzly napˇr. vkládal na urˇcity´ index – uzel je vloˇzen do svého rodiˇce vˇzdy jako posledn´ı. Vkládán´ı do stromu s postorder zápisem (viz obr. 26) prob´ıhá jednoduˇse tak, zˇ e pˇreruˇs´ıme ,,pˇr´ıchoz´ı“ vazbu rodiˇce a protáhneme ji pˇres novˇe vloˇzeny´ uzel. Pro seznam to znamená, zˇ e novˇe vloˇzeny´ uzel bude zaˇrazen pˇred svého rodiˇce. Aby bylo moˇzné z uzlu j okamˇzitˇe nalézt uzel i, kde je potˇreba vazbu pˇreruˇsit, je seznam ve skuteˇcnosti implementován jako obousmˇerny. ´

57

a

b

c

e

f

d

g

i

h

j

k

l

x m

n

Obrázek 26: Postorder seznam Vytvoˇren´ı takového seznamu, ktery´ by pruchodem dával klasicky´ preorder zápis a t´ım vra˚ cel uzly podle poˇrad´ı v dokumentu, moˇzné je. Vyhledáván´ı pak prob´ıhá s rozd´ılem, zˇ e uzly navˇstˇevujeme v poˇrad´ı od koˇrene aˇz po nejpravˇejˇs´ıho potomka dané vˇetve. Problém je ale v prubˇ ˚ ezˇ né konstrukci takového seznamu. Na obrázku 27 jsou znázornˇeny tˇri rozd´ılné situace pˇri vkládán´ı uzlu x do vznikaj´ıc´ı stromové DOM reprezentace. Aby zustal zachován preorder zápis, mus´ı byt ˚ ´ ve vˇsech tˇrech pˇr´ıpadech (A, B, C) pˇreruˇsena vazba mezi uzly g a a. V pˇr´ıpadˇe A by se mohlo zdát, zˇ e jde o tu vazbu, která je ,,pˇr´ıchoz´ı“ do rodiˇcovského uzlu, kam se x vkládá. Naopak pˇr´ıpad C by mohl naznaˇcovat na pouhé pˇresmˇerován´ı z posledn´ıho pˇr´ımého potomka rodiˇcovského uzlu. Obecnˇe by mechanizmus musel pracovat tak, zˇ e se nejprve nalezne nejpravˇejˇs´ı potomek ve vˇetvi toho elementu, kam se x vkládá, a tam se provede pˇresmˇerován´ı. To, co bychom tedy z´ıskali pˇri provádˇen´ı navigace na descendant, bychom pak ztratili pouˇz´ıván´ım konstruktoru˚ XML elementu, ˚ jelikoˇz kaˇzdym ´ novym ´ vloˇzen´ım uzlu do vznikaj´ıc´ıho stromu by muselo probˇehnout vyhledán´ı nejpravˇejˇs´ıho potomka. A

B

a

C

a

c

b

x

d

c

b

e

f

a

d

g

c

b

e

f

x

g

Obrázek 27: Preorder seznam

58

d

e

f

g

x

Sloˇzitost vˇsech uvedenych ´ algoritmu˚ se pohybuje v θ(n), kde n pˇredstavuje poˇcet uzlu, ˚ které mus´ı algoritmus navˇst´ıvit. Nejnákladnˇejˇs´ı operac´ı je v tomto pˇr´ıpadˇe test uzlu (test na jméno, test na atribut a dalˇs´ı). Efektivita jednotlivych ´ algoritmu˚ souvis´ı s reˇzi´ı kolem datovych ´ struktur, na základˇe kterych ´ algoritmus pracuje. TreeJoin Vrat’me se tedy k cˇ innosti samotného operátoru TreeJoin, která znázornˇena algoritmem 5. Algoritmus 5: Implementace TreeJoin input : kontextová hodnota in output: sekvence s uzly po proveden´ı navigace DataValue inputValue ← independentOp.evaluate(in) ; DataItemEnumerable enumerable ← inputValue.asDataItemEnumerable() ; SequenceIterator iterator := enumerable.getIterator(); inicializuj prázdny´ seznam MyList⟨XmlElement⟩ items; while iterator.hasNext() do XmlNode node ← iterator.getNext() ; node.navigate(axis, nodeTest, items) ; end DataSequence outputSequence ← dataModelManager.createDataSequence() ; // Eliminace duplicit inicializuj prázdny´ MyHashSet⟨XmlElement⟩ hashSet ; for vˇsechny poloˇzky item v items do if hashSet neobsahuje poloˇzku item then pˇridej poloˇzku item do vystupn´ ı sekvence outputSequence ; ´ pˇridej poloˇzku item do hash tabulky hashSet. end end return outputSequence ; Nejprve je potˇreba vyhodnotit nezávisly´ vstup independentOp, ktery´ je následnˇe pˇretypován na DataItemEnumerable. Opˇet tedy zakryt´ı rozd´ılu mezi sekvenc´ı a poloˇzkou. Iterátorem jsou procházeny vˇsechny poloˇzky vstupn´ı sekvence a metodou navigate postupnˇe nashromázˇ dˇeny do seznamu items. V podstatˇe jedinym samotného TreeJoin je eliminace duplicit. Nejjed´ sloˇzitˇejˇs´ım ukolem ´ noduˇssˇ´ı implementac´ı by bylo pouˇzit´ı zanoˇrené smyˇcky, coˇz ale z hlediska efektivity urˇcitˇe nen´ı nejlepˇs´ı rˇ eˇsen´ı. Právˇe z toho duvodu byla implementována mnoˇzina MyHash, která je souˇca´ st´ı ˚ univerzáln´ıch struktur popsanych ´ vyˇ ´ se v kapitole 4.3.

59

4.8.4

Operátor IN

Z hlediska správného pochopen´ı, jak funguje pˇredáván´ı hodnoty kontextu je vhodné vysvˇetlit ´ skuteˇcnou funkci operátoru IN. Ukolem tohoto operátoru nen´ı nic jiného, neˇz navrácen´ı kontextu, se kterym ´ bylo voláno jeho vyhodnocen´ı. Triviáln´ı postup je uveden na algoritmu 6. Ve vˇetˇsinˇe pˇr´ıpadu˚ je obsahem IN n-tice, pouze v pˇr´ıpadˇe závislého vstupu operátoru MapFromItem jde o poloˇzku. Algoritmus 6: Implementace IN input : kontextová hodnota in output: kontextová hodnota in return in ;

4.8.5

Operátor Call

Relativnˇe zaj´ımavy´ operátor z hlediska implementace pˇredstavuje Call, cˇ ili volán´ı funkce. Vyˇ ´ cet vˇsech základn´ıch vestavˇenych ´ funkc´ı byl uveden v tabulce 5. Pro uˇ ´ cely testován´ı fungovala prvn´ı verze vyhodnocován´ı v principu velmi jednoduˇse formou jedné globáln´ı statické metody, viz algoritmus 7. Algoritmus 7: Puvodn´ ı implementace Call ˚ input : název funkce, obsah kontextu IN, pole argumentu˚ funkce output: vysledek funkce ´ if název funkce je ,,add“ then zpracován´ı funkce add else if název funkce je ,,sub“ then zpracován´ı funkce sub else if název funkce je ,,mul“ then zpracován´ı funkce mul end ··· Toto naivn´ı rˇ eˇsen´ı s sebou neslo nˇekolik vyznamn ych ´ ´ nevyhod: ´ • nutnost zásahu do operátoru Call vˇzdy pˇri implementaci dalˇs´ı funkce, • ad-hoc rˇ eˇsen´ı – chybˇej´ıc´ı modulárn´ı stavba, • nutnost nˇekolikanásobného porovnáván´ı rˇ etˇezce názvu funkce pˇri kaˇzdém poˇzadavku na vyhodnocen´ı. Prostˇred´ı Novy´ princip modulárn´ı stavby funkc´ı je znázornˇen na obrázku 28. Tˇr´ıda Enviroment slouˇz´ı pro popis prostˇred´ı, ve kterém bude XQuery dotaz vykonáván. Prostˇred´ım se rozum´ı to, jaké funkce 60

Enviroment

<> Function

MyList XmlNode rootContextNode

* DataModelManager dataModelManager Enviroment enviroment

loadRootDocument(string filename) getFunction(string name, int argsCount) registerFunction(Function function) registerBuiltInFunctions()

string getName() int argsCount() DataValue evaluate( DataValue contextItem, DataValue[] args)

FAdd

FSub



...

Obrázek 28: Tˇr´ıdn´ı diagram modulárn´ı stavby funkc´ı budou k dispozici, co je koˇrenovy´ uzel a vyhledovˇ e také jaké jsou napˇr. globáln´ı promˇenné nebo ´ konstanty. Dle specifikace W3C by se dalo rˇ´ıct, zˇ e právˇe tato tˇr´ıda popisuje tzv. statický kontext. Z diagramu by mˇelo byt modulárn´ı rˇ eˇsen´ı funguje. Pro funkci ´ evidentn´ı, jakym ´ zpusobem ˚ je vytvoˇrena abstraktn´ı tˇr´ıda Function, kaˇzdá konkrétn´ı funkce pak mus´ı umˇet vrátit svou signaturu, tzn. název a poˇcet vstupn´ıch argumentu. ˚ Do budoucna by souˇca´ st´ı signatury mohly byt ´ také jejich datové typy. Pˇred samotnym ´ pouˇz´ıván´ım funkce mus´ı probˇehnout jej´ı registrace do prostˇred´ı metodou registerFunction. Bˇehem vyhodnocován´ı statickych sloˇzek operátoru Call (kap. 4.8.1) je dáno, jaky´ bude m´ıt ´ volaná funkce název, a poˇctem podoperátoru˚ dáno, kolik argumentu˚ bude funkce potˇrebovat. Z prostˇred´ı je tedy moˇzné jednoduˇse z´ıskat odkaz na potˇrebnou funkci vˇcetnˇe jej´ı implementace jeˇstˇe pˇred zahájen´ım vyhodnocován´ı. Dojde tedy k ,,prolinkován´ı“ mezi konkrétn´ım operátorem Call a algoritmem samotné funkce. Zaveden´ım modulárn´ı stavby funkc´ı skuteˇcnˇe doˇslo ke zrychlen´ı vykonáván´ı dotazu na ukázce 16. Na zkuˇsebn´ım XML dokumentu (viz n´ızˇ e kap. 5) doˇslo ke zlepˇsen´ı z pˇribliˇznˇe 330 na 290 ms d´ıky efektivnˇejˇs´ımu volán´ı funkce eq pro porovnáván´ı. for $i in //item where some $t in $i//listitem/text() satisfies $t = "Test" return $i

Ukázka 16: Testovac´ı dotaz

4.8.6

Dalˇs´ı operátory

Mezi dalˇs´ı m´ırnˇe komplikovanˇejˇs´ı operátory patˇr´ı napˇr. MapConcat, Join nebo Product. U tˇechto velmi podobnych ´ operátoru˚ snad stoj´ı za zm´ınku akorát to, zˇ e spojován´ı n-tic se provád´ı na rela61

tivnˇe n´ızké urovni. M´ısto postupného pˇrekop´ırován´ı názvu˚ a hodnot z jedné n-tice do druhé se ´ pouˇz´ıvá n´ızkourov nov´ ´ ˇ a kopie bloku pamˇeti. Sloˇzitˇejˇs´ım operátorem byl dále OrderBy pˇredevˇs´ım kvuli ˚ nutnosti implementace QuickSort jako efektivn´ıho algoritmu tˇr´ıdˇen´ı. Ten byl nakonec implementován mimo tˇr´ıdu samotného operátoru OrderBy pro moˇznost opakovaného vyuˇzit´ı tˇr´ızen´ı MyList. Kromˇe vˇsech vyˇ ´ se popsanych ´ principiálnˇe duleˇ ˚ zitych ´ tˇr´ıd se ve skuteˇcné implementaci objevuje velké mnoˇzstv´ı dalˇs´ıch pomocnych konverzn´ıch funkc´ı atd. ´ struktur, metod, promˇennych, ´ Ty ale nejsou z hlediska popisu funkˇcnosti procesoru uplnˇ e podstatné. V pˇr´ıpadˇe, zˇ e by se práce ´ dále rozˇsiˇrovala, bylo by potˇreba vytvoˇrit kompletn´ı programátorskou dokumentaci. V tuto chv´ıli je samotny´ zdrojovy´ kod ´ relativnˇe detailnˇe okomentován a názvy vˇsech identifikátoru˚ by do urˇcité m´ıry mˇely byt ´ samopopisné. K udrˇzován´ı programátorské dokumentace by bylo moˇzné vyuˇz´ıt napˇr. nástroje Doxygen, ktery´ umoˇznuje automatické generován´ı systému HTML stránek ˇ na základˇe komentárˇ u˚ a samotného kodu. ´

62

5

Experimentáln´ı vyhodnocován´ı

Tato kapitola demonstruje na ukázkovych ´ XQuery dotazech naimplementovany´ algebraicky´ procesor. Vˇsechny testy probˇehly na PC s konfigurac´ı uvedené v tabulce 10. CPU Operaˇcn´ı pamˇet’ Operaˇcn´ı systém

Intel Core 2 Duo E7300, 2.66 GHz 4 GB Microsoft Windows 7 Proffesional 64-bit

Tabulka 10: Konfigurace testovac´ıho PC Testovac´ı XML dokument je zjednoduˇsen´ım dokumentu z testu˚ XMark [17]. Základn´ı parametry jsou uvedeny tabulce 11. Dokument je souˇca´ st´ı CD pˇr´ılohy této práce. Velikost souboru Poˇcet XML uzlu˚ Poˇcet elementu˚ Maximáln´ı zanoˇren´ı XML

18 247 kB 313 296 271 848 12 urovn´ ı ´

Tabulka 11: Parametry testovac´ıho XML dokumentu

5.1

Srovnán´ı jinych ´ implementac´ı

Následuje celkem 13 testu, ˚ jejichˇz uˇ ´ celem je jednak prezentace vˇetˇsiny implementovanych ´ konstrukc´ı jazyka XQuery a jednak porovnán´ı délek bˇehu s jinymi dostupnymi procesory. ´ ´ Pro srovnán´ı byly vybrány implementace Saxon [10] a Xml Prime [2]. Oba tyto procesory jsou volnˇe dostupné pro nekomerˇcn´ı pouˇzit´ı. Kaˇzdy´ dotaz byl na vˇsech implementac´ıch spuˇstˇen celkem ˇ 5 krát, aby nedoˇslo k zavádˇej´ıc´ım vysledk um byly mˇerˇ ené ve ´ ˚ kvuli ˚ náhodnym ´ odchylkám. Casy vˇsech pˇr´ıpadech pouze na vykonáván´ı dotazu, tzn. bez parsován´ı vstupn´ıho XML a bez parsován´ı, kompilace a optimalizace dotazu. Ukázalo se, zˇ e Xml Prime vyhodnocuje nˇekteré cˇ a´ sti dotazu aˇz bˇehem iterován´ı pˇres vyslednou sekvenci. Do cˇ asu je tedy zahrnuta jedna prázdná iterace pˇres ´ vysledek. ´ Souˇca´ st´ı kaˇzdého testu je vstupn´ı dotaz a dvˇe tabulky. Prvn´ı vˇzdy udává vysledn´ e cˇ asy v mili´ ˇ sekundách. Rádek Procesor pˇrestavuje cˇ asy pro násˇ implementovany´ procesor. Byly mˇerˇ eny cˇ asy prvn´ıho a druhého bˇehu dotazu. U vˇsech procesoru˚ je pˇri druhém bˇehu evidentn´ı vyuˇz´ıván´ı pˇredalokovanych ´ objektu˚ z bˇehu prvn´ıho. Jsou uvedeny vˇzdy nejmenˇs´ı zjiˇstˇené cˇ asy. Druhá tabulka se vázˇ e k naˇsemu procesoru a slouˇz´ı jako pˇrehled poˇctu vytvoˇrenych ´ instanc´ı pro jednotlivé typy datového modelu v prvn´ım bˇehu. Sloupec Req pˇredstavuje poˇcet poˇzadavku˚ na vytvoˇren´ı objektu daného typu, sloupec New udává, kolik instanc´ı bylo skuteˇcnˇe vytvoˇreno (viz recyklace instanc´ı v kap. 4.4.2). Vstupn´ı dotaz je uveden v takovém tvaru, aby vyhovˇel naˇsemu procesoru. Pˇri spouˇstˇen´ı dotazu˚ na procesorech podle standardu W3C je potˇreba v nˇekterych ´ pˇr´ıpadech upravit názvy funkc´ı – obvykle m´ısto distinct pouˇz´ıt fn:distinct-values.

63

Test 1: Test generován´ı XML ulzu˚ for $ i in 1 to 100000 return { $ i }

Procesor Saxon Xml Prime

1. bˇeh 324 ms 375 ms 906 ms

2. bˇeh 84 ms 297 ms 687 ms

Req 400 002 200 000 2 100 000 0 0

sekvence n-tice tabulka integer double string

New 400 002 200 000 2 100 000 0 0

boolean Xml element Xml atribut Xml text Xml dokument Xml komentárˇ

Req 0 100 000 0 100 000 0 0

New 0 100 000 0 100 000 0 0

Tento test je zamˇerˇ eny´ pˇredevˇs´ım na generován´ı vˇetˇs´ıho mnoˇzstv´ı DOM objektu, ˚ v tomto pˇr´ıpadˇe XML elementu. ˚ Bˇehem vyhodnocován´ı musel násˇ procesor pˇrevést relativnˇe velké mnoˇzstv´ı celoˇc´ıselnych ´ poloˇzek na n-tice a vytvoˇrit mnoho d´ılˇc´ıch sekvenc´ı pro sestaven´ı obsahu vysledn ych ´ ´ elementu. ˚ Test 2: Generován´ı prvoˇc´ısel for $ i in 2 to 1000 where every $x in (2 to $ i − 1) s a t i s f i e s ( $ i mod $x != 0) return $ i


1. bˇeh 115 ms 63 ms 187 ms

2. bˇeh 112 ms 15 ms 47 ms


Req 500 669 999 000 2 000 57 8521 0 0

New 1 999 3 994 4 1 999 0 0


Req 79 021 0 0 0 0 0

New 1 0 0 0 0 0

V tomto pˇr´ıpadˇe byl testován zanoˇreny´ kvantifikovany´ vyraz. Ve druhém bˇehu procesory Saxon ´ a Xml Prime pravdˇepodobnˇe lépe vyuˇzily pˇredalokované pamˇeti. Test 3: Jednoduchý XPath se jmenným testem a navigac´ı na descendant-or-self / / item


1. bˇeh 21 ms 47 ms 109 ms

2. bˇeh 20 ms 0 ms 0 ms


Req 1 0 0 0 0 0

New 1 0 0 0 0 0


Req 0 0 0 0 0 0

New 0 0 0 0 0 0

Z tabulky vzniklych ı) sekvence. Vˇsechny ´ instanc´ı je vidˇet, zˇ e bylo potˇreba pouze jediné (vystupn´ ´ XML uzly byly vytvoˇreny bˇehem parsován´ı XML. Uzlu˚ item je v dokumentu celkem 6 586.

64

Test 4: Iterován´ı sekvenc´ı poloˇzek for $item in / / item return $item


1. bˇeh 30 ms 47 ms 109 ms



Req 6 588 13 172 2 0 0 0

New 6 588 13 172 2 0 0 0


Req 0 0 0 0 0 0

New 0 0 0 0 0 0

Jedná se o podobny´ dotaz jako v pˇredchoz´ım pˇr´ıpadˇe. Zde je ovˇsem rozd´ıl v tom, zˇ e procesor mus´ı poloˇzky ze vstupn´ı sekvence z duvodu FLWOR vyrazu pˇrevést na n-tice. Pˇredchoz´ı dotaz ˚ ´ byl v procesorech Saxon a Xml Prime pravdˇepodobnˇe normalizován, takˇze XPath musel byt ´ pˇreveden na FLWOR. To by mohlo vysvˇetlovat, proˇc jsou vysledky u Saxonu a Xml Prime ´ v porovnán´ı s pˇredchoz´ım testem velmi podobné, zat´ımco u naˇseho procesor je pozorovatelná malá zmˇena.

Test 5: FLWOR v kombinaci s XPath for $item in / / item where $item / @id = ”item1853” return $item


1. bˇeh 31 ms 109 ms 156 ms



Req 6 589 13 172 2 0 0 0

New 3 13 172 2 0 0 0


Req 6 586 0 0 0 0 0

New 1 0 0 0 0 0

Tento test ukazuje na rychlostn´ı pˇrevahu naˇseho procesoru pˇri prvn´ım bˇehu a naopak ztrátu pˇri druhém bˇehu. Saxon a Xml Prime zˇrejmˇe dokázˇ ´ı vyuˇz´ıt nˇejakych ´ informac´ı z pˇredchoz´ıho bˇehu dotazu.

65

Test 6: Dotaz s kvantifikovaným výrazem for $item in / / item [ location = ”United S t a t e s ”] where some $cat in $item / incategory / @category s a t i s f i e s $cat = ”category418” return $item


1. bˇeh 69 ms 125 ms 187 ms


Req 21 284 59 394 9 791 0 0 0


New 4 912 22 978 7 0 0 0


Req 29 653 0 0 0 0 0

New 1 0 0 0 0 0

Testovac´ı dotaz 6 prezentuje moˇznosti kvantifikovanych u. ´ vyraz ´ ˚ Prvn´ı bˇeh byl pˇribliˇznˇe dvakrát kratˇs´ı oproti Saxonu a XmlPrime, ve druhém bˇehu ale byla ztráta.

Test 7: Ukázka pouˇzit´ı pˇr´ımých konstruktoru˚ distinct ( for $item in / / item [ location = ”United S t a t e s ”] l e t $location := $item / location / t e x t ( ) l e t $quantity := $item / quantity / t e x t ( ) c a s t as double order by $quantity return Location : { $location } , Price : { $quantity ∗ 24.57 } )


1. bˇeh 194 ms 359 ms 375 ms

2. bˇeh 110 ms 140 ms 78 ms

sekvence n-tice tabulky integer double string

Req 193 209 52 316 7 0 9 786 0

New 186 623 52 316 7 0 9 786 0


Req 6 586 4 893 0 19 572 0 0

New 1 4 893 0 19 572 0 0

Dotaz ukazuje pouˇzit´ı pˇr´ımych konstruktoru˚ prokládanych vnoˇrenymi vypoˇ ´ ´ ´ ´ cty. Jedná se o vypoˇ ´ cet ceny poloˇzky na základˇe jednotkové ceny a mnoˇzstv´ı.

66

Test 8: Ukázka poˇc´ıtán´ı souhrnu˚ for $region in / s i t e / regions for $item in $region / / item l e t $count := count ( $item / / incategory ) order by $count return


1. bˇeh 168 ms 218 ms 421 ms

2. bˇeh 82 ms 78 ms 125 ms

Req 245 840 39 518 6 6 586 0 0


New 219 496 39 518 6 6 586 0 0


Req 0 6 586 13 172 0 0 0

New 0 6 586 13 172 0 0 0

Tento dotaz ukazuje jednak pouˇzit´ı dvou klauzul´ı for a jednak praktické poˇc´ıtán´ı souhrnu˚ pomoc´ı funkce count.

Test 9: Poˇc´ıtán´ı souhrnu˚ s generován´ım XML <summary> { for $location in d i s t i n c t ( / / location / t e x t ( ) ) l e t $count := count ( / / item [ location = $location ] ) return { $location } {$count } }


1. bˇeh 9 565 ms 1 687 ms 343 ms

2. bˇeh 8 094 ms 1 531 ms 79 ms


Req 1 537 562 3 056 832 467 232 0 0

New 9 610 3 056 832 467 232 0 0


Req 1 527 952 697 0 930 0 0

New 1 697 0 930 0 0

V tomto testu se bohuˇzel násˇ procesor ukázal jako neefektivn´ı v porovnán´ı se Saxonem a Xml Prime. Sp´ısˇ e neˇz na sˇ patnou implementaci toto ukazuje na chybˇej´ıc´ı optimalizaci. Ke zlepˇsen´ı by mˇelo vést zaveden´ı operátoru GroupBy (kapitola 3.4.6). Srovnán´ı s procesorem Xml Prime ale nemus´ı byt e korektn´ı, jelikoˇz testován´ım se ukazuje, zˇ e Xml Prime provád´ı skuteˇcné ´ uplnˇ ´ vyhodnocen´ı nˇekterych eho XML stromu dotazu aˇz pˇri fyzickém cˇ ten´ı ´ zanoˇrenych ´ cˇ a´ st´ı vysledn´ ´ hodnot. Obsahy uzlu˚ location a count zustaly pravdˇepodobnˇe nevypoˇctené. ˚

67

Test 10: Ukázka podm´ınˇených výrazu˚ for $item in / / item l e t $info := i f ( $item / location = ”United S t a t e s ”) then $item / payment else $item / quantity l e t $name := $item /name return


1. bˇeh 116 ms 187 ms 390 ms

2. bˇeh 79 ms 62 ms 109 ms

Req 59 276 39 516 4 0 0 0


New 39 518 39 516 4 0 0 0


Req 6 586 6 586 13 172 0 0 0

New 1 6 586 13 172 0 0 0

Ukázka má sp´ısˇ e prezentovat moˇznost pouˇzit´ı podm´ınˇenych u. ´ vyraz ´ ˚

Test 11: Pouˇzit´ı konstrukce typeswitch for $item in ( 1 , ”a ” , 2 . 7 8 , ” true ” c a s t as boolean , 10) l e t $typeInfo := typeswitch ( $item ) case s t r i n g return ” s t r i n g ” case integer return ” integer ” case double return ”double ” case boolean return ”boolean ” default return ”undefined ” return $typeInfo





Req 17 30 3 0 0 0

New 17 30 3 0 0 0


Req 13 0 0 0 0 0

New 2 0 0 0 0 0

Jedná se o velmi jednoduchy´ dotaz, ktery´ sp´ısˇ e demonstruje pouˇzit´ı konstrukce typeswitch. V naˇsem procesoru je testován´ı datovych ´ typu˚ podporováno pouze cˇ a´ steˇcnˇe – je moˇzné testovat poloˇzky na typ skalárn´ı hodnoty. Relativnˇe zaj´ımavé je cˇ asové srovnán´ı, které ukazuje na reˇzijn´ı záleˇzitosti ohlednˇe kaˇzdého dotazu.

68

Test 12: Ukázka generován´ı pˇrehledového XML for $location in d i s t i n c t ( / / location / t e x t ( ) ) return { $location } { for $item in / / item [ location = $location ] return }


1. bˇeh 9 905 ms 1 750 ms 734 ms

2. bˇeh 8 140 ms 1 547 ms 344 ms


Req 1 570 952 3 069 540 930 0 0 0

New 29 828 3 069 540 930 0 0 0


Req 1 527 952 7 282 6 586 1 160 0 0

New 1 7 282 6 586 1 160 0 0

Jedná se podobnˇe problematicky´ dotaz jako v testu 9. Zde je opˇet patrná vysoká ztráta na Saxon a Xml Prime. Dotaz ukazuje moˇznost generován´ı sloˇzitˇejˇs´ıho souhrnového XML.

Test 13: Pouˇzit´ı tˇr´ızen´ı ve FLWOR výrazu for $item in / / item l e t $name := $item /name/ t e x t ( ) order by $name return $item


1. bˇeh 87 ms 203 ms 219 ms



Req 19 760 39 516 4 0 0 0

New 19 760 39 516 4 0 0 0


Req 0 0 0 0 0 0

New 0 0 0 0 0 0

Posledn´ım testem je ukázka tˇr´ızen´ı poloˇzek ve FLWOR vyrazu. V souˇcasné implementaci se ´ pro tˇr´ızen´ı pouˇz´ıvá algoritmus Quick sort. Pro lexikografické tˇr´ızen´ı by minimálnˇe stály za vyzkouˇsen´ı i jiné algoritmy, napˇr. Radix sort.

69

5.1.1

Shrnut´ı cˇ asovych ´ srovnán´ı

Testován´ım se ukázalo, zˇ e násˇ procesor ve vˇetˇsinˇe pˇr´ıpadu˚ podává srovnatelné nebo dokonce lepˇs´ı vysledky neˇz existuj´ıc´ı implementace. Grafické porovnán´ı vysledk u˚ je znázornˇeno na obr. 29. Na ´ ´ druhou stranu byly i dotazy (9 a 12), kde byla evidentn´ı velká ztráta. Tato ztráta ale sp´ısˇ e neˇz na moˇznost sˇ patné implementace datovych ´ struktur ukazuje na chybˇej´ıc´ı optimalizaci spojuj´ıc´ı vnitˇrn´ı zanoˇreny´ FLWOR s vnˇejˇs´ım FLWOR nebo XPath. U procesoru˚ Saxon a Xml Prime je potˇreba zohlednit jejich dlouholety´ vyvoj (Xml Prime od roku 2009, Saxon od r. 1998) a spolupráci vˇetˇs´ıho ´ mnoˇzstv´ı lid´ı nejen na samotné implementaci, ale také na testován´ı. Tato implementace minimálnˇe otev´ırá moˇznosti k dalˇs´ım optimalizac´ım. Dalˇs´ı moˇznosti zlepˇsen´ı efektivity se skryvaj´ ´ ı napˇr´ıklad v pouˇz´ıván´ı sofistikovanˇejˇs´ıch metod pro evaluaci XPath vyraz u, ´ ˚ kdy jednotlivé cˇ a´ sti nejsou zpracovávány postupnˇe, ale na XPath je pohl´ızˇ eno jako na celek (kap. 3.4.6). Zaj´ımavou moˇznost´ı by mohl byt ´ napˇr. dalˇs´ı pˇreklad z plánu vykonáván´ı pˇr´ımo do strojového kodu. ´

[ms]

[ms]

1000

12000

900 10000

800

700

8000

600

500

6000

400 4000

300 200

2000

100 0

0 Test 1

Test 2

Test 3

Procesor 1

Test 4

Procesor 2

Test 5

Saxon 1

Test 6

Test 7

Saxon 2

Test 8

Xml Prime 1

Test 10

Test 11

Test 13

Xml Prime 2

Test 9

Test 12

Problematické dotazy

Obrázek 29: Srovnán´ı cˇ asu˚ jednotlivych ´ procesoru˚

5.2

Vliv optimalizac´ı na délku bˇehu

Následuj´ıc´ı dva testy jsou zamˇerˇ eny na vliv optimalizac´ı nadefinovanych ´ v kapitole 3.4 na dobu vyhodnocován´ı.

70

Test 14: Optimalizace spojen´ım kroku˚ XPath Tento test ukazuje srovnán´ı doby vykonáván´ı bez a s optimalizac´ı spojen´ım kroku˚ XPath (kap. 3.4.5). Jako ukázkovy´ dotaz slouˇz´ı dotaz z testu 8.

for $region in / s i t e / regions for $item in $region / / item l e t $count := count ( $item / / incategory ) order by $count return

Bez optimalizace S optimalizac´ı

1. bˇeh 298 ms 168 ms

2. bˇeh 192 ms 82 ms

Z vysledk u˚ je viditelny´ podstatny´ rozd´ıl, zejména pˇri druhém bˇehu dotazu. ´

Test 15: Optimalizace odstranˇen´ım MapConcat a MapToItem V tomto testu je srovnána doba vykonáván´ı bez a s optimalizac´ı odstranˇen´ım MapConcat a MapToItem (kap. 3.4.1 a 3.4.2). Jako ukázkovy´ dotaz je vyuˇzit dotaz z testu 2.

for $ i in 2 to 1000 where every $x in (2 to $ i − 1) s a t i s f i e s ( $ i mod $x != 0) return $ i

Bez optimalizace S optimalizac´ı

1. bˇeh 258 ms 115 ms

2. bˇeh 255 ms 112 ms

Z vysledk u˚ je pozorovatelné témˇerˇ dvojnásobné zlepˇsen´ı vykonu procesoru. ´ ´

71

6

Závˇer

Vysledkem práce je funkˇcn´ı algebraicky´ XQuery procesor, ktery´ vycház´ı ze specifikace W3C, ´ podporuje základn´ı konstrukce jazyka XQuery od aritmetickych operac´ı pˇres logické operace, ´ práci se sekvencemi pomoc´ı FLWOR a XPath vyraz u˚ aˇz po konstrukce jako alternativy a vˇetven´ı ´ dle datového typu.

6.1

Vlastn´ı pˇr´ınos a moˇznosti rozˇs´ırˇen´ı

Vlastn´ım pˇr´ınosem této práce je pˇredevˇs´ım modulárnˇe navrˇzeny´ systém, jehoˇz cˇ a´ sti mohou byt ´ v budoucnu dále rozˇsiˇrovány vˇetˇs´ım tymem lid´ı. Naimplementovany´ procesor pˇristupuje ke ´ kompilaci XQuery dotazu˚ bez pˇredchoz´ı normalizace, coˇz muˇ ˚ ze usnadnit napˇr. vyhledáván´ı stromovych ´ vzoru˚ pro efektivn´ı vykonáván´ı na indexovanych ´ databáz´ıch. Dále se zde objevuj´ı specifické optimalizace (kapitola 3.4) a návrhy algoritmu˚ na rˇ eˇsen´ı navigac´ı v XML dokumentech (kapitola 4.8.3). Tato práce otev´ırá velké moˇznosti pro vyvoj a testován´ı ruzn optimalizaˇcn´ıch postupu˚ ´ ˚ ych ´ a fyzickych algoritmu˚ rˇ eˇs´ıc´ıch funkˇcnost jednotlivych operátoru. ´ ´ ˚ Reálnym ´ c´ılem je vyuˇz´ıván´ı TPQ pro vyhodnocován´ı vyraz u˚ FLWOR podle [14]. Pˇr´ınosem je také samotny´ naimplementovany´ ´ procesor, ktery´ je pro bˇezˇ né uˇ ´ cely prakticky pouˇzitelny. ´

6.2

Osobn´ı zhodnocen´ı

Jelikoˇz se jiˇz delˇs´ı dobu prakticky pohybuji v oblasti vyvoje informaˇcn´ıch systému˚ (bakalárˇ ská ´ práce [12]) od návrhu a tvorby databáz´ı, pˇres implementaci GUI, aˇz po komunikaci s koncovymi ´ zákazn´ıky, bylo mym vybrat si takové téma, které by mi umoˇznilo nahlédnout do pozad´ı ´ umyslem ´ technologi´ı, které v´ıce nebo ménˇe pouˇz´ıvám. Puvodn´ ım zámˇerem bylo vytvoˇrit funkˇcn´ı procesor ˚ SQL, avˇsak vzhledem k relativn´ı nasycenosti trhu standardn´ımi relaˇcn´ımi databázovymi stroji ´ byla volba XQuery minimálnˇe z hlediska studia zaj´ımavˇejˇs´ı. Nejsloˇzitˇejˇs´ım ukolem na celé práci bylo zorientovat se ve velkém mnoˇzstv´ı informac´ı ohlednˇe ´ XML technologi´ı. Jak bylo v kapitole 2.3.4 uvedeno, XQuery uzce souvis´ı s jinymi dotazovac´ımi ´ ´ jazyky, takˇze krom studia standardu XQuery bylo potˇreba nahl´ızˇ et také do specifikac´ı XPath a XML. Podrobné detailn´ı zkoumán´ı vˇsech tˇechto standardu˚ by vyˇzadovalo mnohem delˇs´ı dobu a spolupráci vˇetˇs´ıho mnoˇzstv´ı lid´ı. To je duvodem, proˇc se tento procesor muˇ ˚ ˚ ze od specifikace liˇsit.

72

Reference [1] W3C. W3Schools [online].

1999-2012

[cit.

2012-02-05].

Dostupné

z:

[2] CLINICAL & BIOMEDICAL COMPUTING LTD. XML Prime [online]. 2009-2012 [cit. 201204-09]. Dostupné z: [3] W3C. Extensible Markup Language (XML) 1.1 (Second Edition) [online]. 2006 [cit. 2012-01-24]. Dostupné z: [4] W3C. XML Path Language (XPath) 2.0 (Second Edition) [online]. 2010 [cit. 2012-02-10]. Dostupné z: [5] W3C. XQuery 1.0: An XML Query Language (Second Edition) [online]. 2010 [cit. 2012-02-03]. Dostupné z: [6] W3C. XQuery 1.0 and XPath 2.0 Data Model (XDM) (Second Edition) [online]. 2010 [cit. 201203-20]. Dostupné z: [7] W3C. XQuery 1.0 and XPath 2.0 Formal Semantics (Second Edition) [online]. 2010 [cit. 201203-20]. Dostupné z: [8] WIKIPEDIE. Lexikáln´ı analýza [online]. 2011

[cit.

2012-01-27].

Dostupné

z:

ˇ ˇ – Technická [9] BRUSKA, Filip. Normalizace XQuery dotazu. ˚ Ostrava, 2010. Diplomová práce. VSB univerzita Ostrava. [10] KAY, Michael H. SAXON: The XSLT and XQuery Processor [online]. 2011 [cit. 2012-02-05]. Dostupné z: [11] A simple proof for the turing-completeness of xslt and xquery [online]. 2006 [cit. 2012-04-11]. Dostupné z: ´ S, ˇ Petr. Absolvován´ı individuáln´ı odborné praxe [online]. Ostrava, 2010 [cit. 2012-04-11]. [12] LUKA ˇ – Technická univerzita Ostrava. Bakalárˇ ská práce. VSB [13] MANOLESCU, Ioana, PAPAKONSTANTINOU a Vasilis VASSALOS. Xml tuple algebra [online]. 2009 [cit. 2012-04-11]. Dostupné z: ˇ A ˇ ´ [14] MICHIELS, Philippe, George A. MIHAIL a Jérom SIMEON. Put ˆ tree pattern in your algebra [online]. 2007 [cit. 2012-04-11]. Dostupné

a z:

[15] ROBIE, Jonathan, Don CHAMBERLIN a Daniela FLORESCU. Quilt: An xml query language [online]. 2000 [cit. 2012-04-11]. Dostupné z:

73

´ Christopher, Jérom ´ ´ [16] RE, SIMEON a Mary FERNANDEZ. A complete and effiˆ cient algebraic compiler for xquery [online]. 2006 [cit. 2012-04-11]. Dostupné z: [17] XMark-An XML Benchmark Project

[online].

74

[cit.

2012-04-25].

Dostupné

z:

A

Vestavˇené funkce

add Dvouparametrová funkce pro sˇc´ıtán´ı cˇ ´ıselnych ´ poloˇzek nebo spojován´ı textovych ´ rˇ etˇezcu. ˚ add(a, b) → c a

b

c

integer

integer

integer

souˇcet cˇ ´ısel

integer

double

double


double

integer

double


double

integer

double


string

sequence

string

zˇretˇezen´ı po serializaci sekvence

string

string

string

zˇretˇezen´ı

sub Dvouparametrová funkce pro odˇc´ıtán´ı cˇ ´ıselnych ´ poloˇzek. sub(a, b) → c a

b

c

integer

integer

integer

rozd´ıl cˇ ´ısel

integer

double

double


double

integer

double


double

integer

double


mul Dvouparametrová funkce pro násoben´ı cˇ ´ıselnych ´ poloˇzek. mul(a, b) → c a

b

c

integer

integer

integer

souˇcin cˇ ´ısel

integer

double

double


double

integer

double


double

integer

double


div Dvouparametrová funkce pro desetinné dˇelen´ı cˇ ´ıselnych ´ poloˇzek. div(a, b) → c

75

a

b

c

integer

integer

double

pod´ıl cˇ ´ısel

integer

double

double


double

integer

double


double

integer

double


idiv Dvouparametrová funkce pro celoˇc´ıselné dˇelen´ı cˇ ´ıselnych ´ poloˇzek. idiv(a, b) → c a

b

c

integer

integer

integer

pod´ıl cˇ ´ısel bez desetinné cˇ a´ sti

mod Dvouparametrová funkce pro zbytek po celoˇc´ıselném dˇelen´ı. mod(a, b) → c a

b

c

integer

integer

integer

zbytek po celoˇc´ıselném dˇelen´ı

veq, vneq Dvouparametrové funkce pro hodnotové porovnáván´ı. Funkce vneq vrac´ı vˇzdy negovany´ vysledek veq. ´ veq(a, b) → c, vneq(a, b) → c

76

a

b

c

integer

integer

boolean

porovnán´ı celych ´ cˇ ´ısel

integer

double

boolean

porovnán´ı celého a desetinného cˇ ´ısla

integer

boolean

boolean

porovnán´ı celého cˇ ´ısla a booleovské hodnoty pˇrevedené na 1 nebo 0

double

integer

boolean

porovnán´ı desetinného a celého cˇ ´ısla

double

double

boolean

porovnán´ı dvou desetinnych ´ cˇ ´ısel

string

string

boolean

porovnán´ı celych ´ cˇ ´ısel

string

xml-attribute

boolean

porovnán´ı textového rˇ etˇezce a hodnoty atributu

string

xml-element

boolean

porovnán´ı textového rˇ etˇezce s textovym ´ obsahem elementu

string

xml-text

boolean

porovnán´ı textového rˇ etˇezce s obsahem textového uzlu

string

xml-comment

boolean

porovnán´ı textového rˇ etˇezce s komentárˇ em

xml-attribute

xml-attribute

boolean

porovnán´ı hodnot dvou atributu˚

xml-attribute

string

boolean

porovnán´ı hodnoty atributu a textového rˇ etˇezce

xml-attribute

xml-element

boolean

porovnán´ı hodnoty atributu s textovym ´ obsahem elementu

xml-attribute

xml-text

boolean

porovnán´ı hodnoty atributu s obsahem textového uzlu

xml-attribute

xml-comment

boolean

porovnán´ı hodnoty atributu s komentárˇ em

xml-element

xml-element

boolean

porovnán´ı struktury celych ´ elemtnu˚ vˇcetnˇe obsahu

xml-element

xml-attribute

boolean

porovnán´ı textového obsahu elementu s hodnotou atributu

xml-element

string

boolean

porovnán´ı textového obsahu elementu s textovym ´ rˇ etˇezcem

xml-element

xml-text

boolean

porovnán´ı textového obsahu elementu s obsahem textového uzlu

xml-element

xml-comment

boolean

porovnán´ı textového obsahu elementu s komentárˇ em

xml-text

xml-text

boolean

porovnán´ı textu˚ dvou textovych ´ uzlu˚

xml-text

xml-element

boolean

porovnán´ı obsahu textového uzlu s textovym ´ obsahem elementu

xml-text

xml-attribute

boolean

porovnán´ı obsahu textového uzlu s hodnotou atributu

xml-text

string

boolean

porovnán´ı obsahu textového uzlu s textovym ´ rˇ etˇezcem

xml-text

xml-comment

boolean

porovnán´ı textového obsahu textového uzlu s komentárˇ em

xml-comment

xml-comment

boolean

porovnán´ı dvou komentárˇ u˚

xml-comment

xml-text

boolean

porovnán´ı komentárˇ e a obsahu textového uzlu

xml-comment

xml-element

boolean

porovnán´ı komentárˇ e s textovym ´ obsahem elementu

xml-comment

xml-attribute

boolean

porovnán´ı komentárˇ e s hodnotou atributu

xml-comment

string

boolean

porovnán´ı komentárˇ e s textovym ´ rˇ etˇezcem

vlt, vgt, vle, vge Dvouparametrové funkce pro hodnotové uspoˇra´ dán´ı datovych ´ poloˇzek. Funkce vgt odpov´ıdá <, vlt odpov´ıdá >, vge odpov´ıdá ≥, vle odpov´ıdá ≤. vlt(a, b) → c, vgt(a, b) → c, vle(a, b) → c, vge(a, b) → c

77

a

b

c

integer

integer

boolean

uspoˇra´ dán´ı celych ´ cˇ ´ısel

integer

double

boolean

uspoˇra´ dán´ı celého a desetinného cˇ ´ısla

integer

boolean

boolean

uspoˇra´ dán´ı celého cˇ ´ısla a booleovské hodnoty pˇrevedené na 1 nebo 0

double

integer

boolean

uspoˇra´ dán´ı desetinného a celého cˇ ´ısla

double

double

boolean

uspoˇra´ dán´ı dvou desetinnych ´ cˇ ´ısel

string

string

boolean

uspoˇra´ dán´ı celych ´ cˇ ´ısel

string

xml-attribute

boolean

lexikografické uspoˇra´ dán´ı textového rˇ etˇezce a hodnoty atributu

string

xml-element

boolean

lexikografické uspoˇra´ dán´ı textového rˇ etˇezce s textovym ´ obsahem elementu

string

xml-text

boolean

lexikografické uspoˇra´ dán´ı textového rˇ etˇezce s obsahem textového uzlu

string

xml-comment

boolean

lexikografické uspoˇra´ dán´ı textového rˇ etˇezce s komentárˇ em

xml-attribute

xml-attribute

boolean

lexikografické uspoˇra´ dán´ı hodnot dvou atributu˚

xml-attribute

string

boolean

lexikografické uspoˇra´ dán´ı hodnoty atributu a textového rˇ etˇezce

xml-attribute

xml-element

boolean

lexikografické uspoˇra´ dán´ı hodnoty atributu s textovym ´ obsahem elementu

xml-attribute

xml-text

boolean

lexikografické uspoˇra´ dán´ı hodnoty atributu s obsahem textového uzlu

xml-attribute

xml-comment

boolean

lexikografické uspoˇra´ dán´ı hodnoty atributu s komentárˇ em

xml-element

xml-element

boolean

lexikografické uspoˇra´ dán´ı textového obsahu dvou elementu˚

xml-element

xml-attribute

boolean

lexikografické uspoˇra´ dán´ı textového obsahu elementu s hodnotou atributu

xml-element

string

boolean

lexikografické uspoˇra´ dán´ı textového obsahu elementu s textovym ´ rˇ etˇezcem

xml-element

xml-text

boolean

lexikografické uspoˇra´ dán´ı textového obsahu elementu s obsahem textového uzlu

xml-element

xml-comment

boolean

lexikografické uspoˇra´ dán´ı textového obsahu elementu s komentárˇ em

xml-text

xml-text

boolean

lexikografické uspoˇra´ dán´ı textu˚ dvou textovych ´ uzlu˚

xml-text

xml-element

boolean

lexikografické uspoˇra´ dán´ı obsahu textového uzlu s textovym ´ obsahem elementu

xml-text

xml-attribute

boolean

lexikografické uspoˇra´ dán´ı obsahu textového uzlu s hodnotou atributu

xml-text

string

boolean

lexikografické uspoˇra´ dán´ı obsahu textového uzlu s textovym ´ rˇ etˇezcem

xml-text

xml-comment

boolean

lexikografické uspoˇra´ dán´ı textového obsahu textového uzlu s komentárˇ em

xml-comment

xml-comment

boolean

lexikografické uspoˇra´ dán´ı dvou komentárˇ u˚

xml-comment

xml-text

boolean

lexikografické uspoˇra´ dán´ı komentárˇ e a obsahu textového uzlu

xml-comment

xml-element

boolean

lexikografické uspoˇra´ dán´ı komentárˇ e s textovym ´ obsahem elementu

xml-comment

xml-attribute

boolean

lexikografické uspoˇra´ dán´ı komentárˇ e s hodnotou atributu

xml-comment

string

boolean

lexikografické uspoˇra´ dán´ı komentárˇ e s textovym ´ rˇ etˇezcem

eq, eq Dvouparametrové funkce pro obecné porovnáván´ı. Pro jednoprvkové sekvence pracuj´ı funkce stejnˇe jako veq a vneq, pro v´ıceprvkové sekvence vrac´ı funkce pravdivou hodnotu, pokud porovnán´ı vyhov´ı alesponˇ jedné dvojici poloˇzek z obou sekvenc´ı. eq(a, b) → c, neq(a, b) → c a

b

c

sequence

sequence

boolean

obecné porovnán´ı sekvenc´ı

78

lt, gt, le, ge Dvouparametrové funkce pro obecné porovnáván´ı. Pro jednoprvkové sekvence pracuj´ı funkce stejnˇe jako vlt, vgt, vle a vge, pro v´ıceprvkové sekvence vrac´ı funkce pravdivou hodnotu, pokud porovnán´ı vyhov´ı alesponˇ jedné dvojici poloˇzek z obou sekvenc´ı. lt(a, b) → c, gt(a, b) → c, le(a, b) → c, ge(a, b) → c a

b

c

sequence

sequence

boolean

obecné porovnán´ı sekvenc´ı

abs Absolutn´ı hodnota cˇ ´ıselné poloˇzky. abs(a) → b a

b

integer

integer

absolutn´ı hodnota celého cˇ ´ısla

double

double

absolutn´ı hodnota desetinného cˇ ´ısla

count Poˇcet poloˇzek v sekvenci. count(a) → b a

b

sequence

integer

poˇcet poloˇzek v sekvenci

position Pozice kontextového uzlu v rámci sekvence poloˇzek, ke které náleˇz´ı (ˇc´ıslováno od 1). position() → a a integer

pozice kontextového uzlu

position Délka sekvence, které náleˇz´ı kontextovy´ uzel. last() → a

79

a integer

pozice kontextového uzlu

doc Naˇcten´ı extern´ıho XML dokumentu. Pro cˇ ten´ı XML a pˇrevod na DOM je vyuˇzit Xerces Parser. Funkce argumentem pˇreb´ırá textovy´ rˇ etˇezec reprezentuj´ıc´ı cestu k souboru. doc( f ileName) → a f ileName

a

string

xml-document

naˇcteny´ XML dokument

root Funkce vrac´ı vstupn´ı XML dokument, ktery´ je naˇcten a zpracován jeˇstˇe pˇred zaˇca´ tkem vyhodnocován´ı dotazu. root() → a a xml-document

vstupn´ı XML dokument

predicate Funkce slouˇz´ı pro vyhodnocen´ı predikátu˚ XPath vyraz u˚ (viz 3.3.3). ´ predicate(a) → b a

b

sequence

boolean

efektivn´ı booleovská hodnota

integer

boolean

booleovská hodnota informuj´ıc´ı, zda pozice kontextového uzlu odpov´ıdá cˇ ´ıslu a

boolean Funkce vrac´ı tzv. efektivn´ı booleovskou hodnotu (viz 3.3.3). boolean(a) → b a

b

sequence

boolean

efektivn´ı booleovská hodnota

range Funkce utvoˇr´ı sekvenci cˇ ´ısel od a do b s krokem 1.

80

range(a, b) → c a

b

c

integer

integer

sequence

sekvence cˇ ´ısel od a do b

distinct Funkce na základˇe porovnán´ı (funkce eq) provád´ı odstranˇen´ı duplicit ze sekvence. Doˇslo k rozˇs´ırˇ en´ı vˇsech tˇr´ıd datového modelu o metodu vracej´ıc´ı hash kl´ıcˇ , coˇz umoˇznuje relativnˇe ˇ efektivn´ı cˇ innost eliminace duplicitn´ıch hodnot podobnˇe jako v operátoru TreeJoin. distinct(a) → b a

b

sequence

sequence

vystupn´ ı sekvence bez duplicitn´ıh hodnot ´

avg Funkce vrac´ı prumˇ ˚ ernou hodnotu ze sekvence, jej´ızˇ poloˇzky mus´ı byt ´ explicitnˇe pˇretypovatelné na desetinné cˇ ´ıslo. avg(a) → b a

b

sequence

double

prumˇ ˚ erˇ ná hodnota

sum Funkce vrac´ı souˇcet hodnot ze sekvence, jej´ızˇ poloˇzky mus´ı byt ´ explicitnˇe pˇretypovatelné na desetinné cˇ ´ıslo. sum(a) → b a

b

sequence

double

Souˇcet

min Funkce vrac´ı minimáln´ı hodnotu ze sekvence. Podm´ınkou je, aby byly prvky v sekvenci navzájem porovnatelné. min(a) → b a

b

sequence

item

minimáln´ı hodnota

81

min Funkce vrac´ı maximáln´ı hodnotu ze sekvence. Podm´ınkou je, aby byly prvky v sekvenci navzájem porovnatelné. max(a) → b a

b

sequence

item

maximáln´ı hodnota

empty Funkce vrac´ı pravdivou booleovskou hodnotu, jestliˇze je sekvence pˇredaná argumentem prázdná.

empty(a) → b a

b

sequence

boolean

prázdnost sekvence

not Jednoduchá funkce pro zjiˇstˇen´ı negované booleovské hodnoty. not(a) → b a

b

boolean

boolean

negovaná hodnota

82

B

Kompatibilita datovych ´ typu˚

I – implicitn´ı a explicitn´ı pˇretypován´ı t1 na t2

I1

I1

I1

I1

xml-document

I1 E E E4 I E4 E4 E4 E4

xml-text

I1 E E I E I I I I

xml-node

I1 E I E3 E E3 E3 E3 E3

xml-comment

I1 I E E2 E E2 E2 E2 E2

xml-attribute

double

I I I I I I I I I I

string

sequence boolean integer string double xml-attribute xml-comment xml-node xml-text xml-document

integer

↓ t1 , t2 →

boolean

sequence

E – explicitn´ı pˇretypován´ı t1 na t2

I I I I I

I

Tabulka 12: Kompatibilita datovych ´ typu˚ 1

– Za pˇredpokladu, zˇ e sekvence obsahuje jedinou poloˇzku.

2

– Za pˇredpokladu, zˇ e textovy´ rˇ etˇezec, hodnota atributu, komentárˇ e, textového uzlu nebo textového obsahu elementu je “0”, “1”, “true” nebo “false”.

3

– Za pˇredpokladu, zˇ e textovy´ rˇ etˇezec, hodnota atributu, komentárˇ e, textového uzlu nebo textového obsahu elementu reprezentuje celé cˇ ´ıslo.

4

– Za pˇredpokladu, zˇ e textovy´ rˇ etˇezec, hodnota atributu, komentárˇ e, textového uzlu nebo textového obsahu elementu reprezentuje desetinné cˇ ´ıslo.

83

C

Spustitelny´ procesor

Samostatnˇe spustitelny´ procesor je moˇzné nalézt na pˇriloˇzeném CD k této práci. Jeho obsluha je snadná: XQueryProcessor.exe <soubor XML> <souboru s dotazem> []

Specifikace vystupn´ ıho souboru je nepovinná, v pˇr´ıpadˇe, zˇ e vystup nen´ı definován, vyp´ısˇ e se ´ ´ vysledek dotazu pˇr´ımo na monitor. ´ Spustitelny´ soubor pouze demonstruje jedno z vyuˇzit´ı procesoru. Souˇca´ st´ı pˇriloˇzeného CD jsou zdrojové soubory s projektem pro Microsoft Visual Studio 2005. Praktické uplatnˇen´ı spoˇc´ıvá ve vyuˇzit´ı techto zdrojovych souboru˚ jako komponenty pro implementaci jinych rozsáhlejˇs´ıch ´ ´ projektu˚ vyuˇz´ıvaj´ıc´ıch moˇznosti vyhledáván´ı v XML. Obsah CD je bl´ızˇ e specifikován souborem ,,Obsah.pdf“, ktery´ je um´ıstˇen v koˇrenovém adresárˇ i.

84

XQuery algebra XQuery Algebra

Recommend Documents