………l………l……l………l…………‖ll…………‖川‖lll…………l………l刷Il……………ll……l……………l……ll……ll………………‖l……l……lll…………l州Il…………l川l川l……lll州Il…………l洲‖川Il……冊l

XML用木パターン言語ⅩPath解説
田島 敬史
本稿では，ⅩML用の簡単な検索言語とみなせるⅩPathについて解説する．まず，ⅩPathの言語概要について説明
し，次に，XPathに関する近年の研究の中から，ⅩPathの評価の計算量に関する研究，ⅩPathの様々な部分言語の表
現力に関する研究，および，ⅩPathの様々な部分言語の集合演算に対する閉包性に関する研究について簡単に解説する．

キーワード：ⅩML，XPath，計算量，部分言語，表現九 閉包性…………………………ll州l………l‖…………ll州Il……ll……………l…………ll……………l州‖ll州l…………‖……………ll………………………l州Il……………凧‖l…………lll州l州‖l…………ll……l州l………州／0

1．はじめに

1bookl

本特集中の文献［1］でも触れられていたように，

ⅩMLデータ中の一部を指定するための言語として
ⅩPath［2］が広く使われており，これは簡単なⅩML／／↑＼＼1

用検索言語ともみなせる．そこで本稿では，ⅩPath

9
e
r

f

1

J

‖﹁−−⊥▼の概要と，関連するいくつかの研究について解説する．

』i。。8

g

なお，ここでの言語の定義の仕方は，文献［2］とは若干異なるが，問合せ式の意味は変わらない．
図1ⅩPathでのデータモデル

2．XPath言語概要
文献［1］で述べられていたように，ⅩMLデータは

このデー

タに対するⅩPath問合せの例を次に示す．

木構造で表現でき，例えば，次に示すⅩMLデータは，／child：：book／child：：Chapter［descendant：：figure］

図1に示すような木とみなせる．図中の数字は本文中

この式のように，XPathによる問合せ式は，「／」でで各要素を参照するために便宜上ふった物である．

区切られたロケーションステップと呼ばれるものの並〈？Ⅹmlversion＝ 1．0 ？〉びである．そのうち，「／」で始まるものを絶対ロケー〈book〉

ションパス，ロケーションステップで始まるものを相くforeword〉．．．．．．〈／foreword〉

対ロケーションパスと呼ぶ．この二つ以外の場合もあくchapter〉

りうるが，ここでは省略する．各ロケーションステッ
プは，〈section〉．．．くfigure〉．．．く／figure〉…

軸：：ノードテスト［ⅩPath表現］…［ⅩPath表現］

く／section〉という形をしている．［…］の部分は述語と呼ばれ，各くSeCtion〉…く／section〉

ステップは，0個以上，任意個の述語を持つ．

く／chapter〉

ロケーションステップは，ある「文脈ノード」のもくchapter〉とで評価されて，ノードの集合を返す．軸は，文脈ノ

くSeCtion〉．．．く／section〉

ードから見て木構造中でどのような位置関係にあるノ

くSeCtion〉．．．く／section〉

ードを選択するかを指定するもので，主なところではく／chapter〉〈／b00k〉

たじま けいし北陸先端科学技術大学院大学情報科学研究科〒923−1292能美市旭台ト1
2005年6月号

次のものが指定できる．

Self，Child，Parent，descendant，anCeStOr，descendant−Or−Self，anCeStOr−Or−Self，fotlowlng−

Sib＝ng，PreCeding−Sibfing

各軸の意味は，順に，文脈ノード自身，子供，親，子© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（11）3丁3￣ ￣ ￣「￣ ￣descendant‥＝figure（9）＝true−descendant：：figure（）＝払1se一−酔（0）⊂hild：：bookChild：：Chapter

叫

1

ト（3）

＿ ＿ ＿ ＿」

図2 ⅩPathの実行の流れ

孫，祖先，自身または子孫，自身または祖先，後方のはノード1のみ）を文脈ノードとして続くchik】：：

兄弟，前方の兄弟である．

Chapterを評価すると，ここまでで，根からbook，

また，ノードテストはノードの種類や名前を指定するもので，主なところでは次のものが指定できる．

Chapterとたどって得られるすべてのchapter要素の集合が返される．

述語内も同様の手順で評価され，descendant：：

名前 −その名前を持つノード−（上記の軸の場合は）任意の要素ノード＊

figureは，／book／chapterまでで得られる各要素につtext（）一文字列ノード

いて，その要素の子孫でfigureという要素名を持つ

node（）一任意のノード

ものの場合を返す．ただし，述語の評価結果がノード

また，述語は，軸，ノードテスト，および自分より集合となった場合は，空集合であればfalse，そうで左にある述語によって絞り込まれた中間結果のノード

なければtrueとすることになっているので，この場集合をさらに絞り込むためのもので，述語中にはロケ

合，そのようなfigure要素が存在するchapter要素ーションパス（絶対，相対），定数（数値，文字列），に対しては述語がtrueとなり，最終結果の集合に含組込み関数，これらを演算子（or，and，＝，＞等）でつまれることになる．

ないだもの等が書ける．これらは，中間結果集合中の各ノードを文脈ノードとして評価され，この結果がまた，ⅩPathでは，様々な省略記法が用意されている．これらのうち，主なものを次に示す．

trueになる文脈ノpドだけからなる集合が返される．

●「軸：：」を省略した場合はchild軸が使用される

この時，文脈ノードに加えて，中間結果集合の大きさ●／／…／descendant−Or−SeJf：：nOde（）／（文脈サイズ），中間結果集合中で文脈ノードが何番目●．…Self：：nOde（）／であるか（文脈ノード位置，詳細は省略）も文脈とし●．．…Parent：：nOde（）／て参照できる．また，評価結果が真偽値型ではない場

最後に，省略記法を用いて記述した問合せ式の例を合は，いくつかと，それらの意味を示す．

●ノード集合型は，空集合でなければtrue●数値型は，文脈ノード位置と等しければtrue●／book／chapter［2］／section［3］：根の下のbook
ノpドの子供のchatperノードの中で2番目のものの，その子供のsectionノードの中で3番目の等の規則によって，真偽値型に変換される．
ロケーションパスでは，左側のロケーションステッ

ノード．

プが返したノード集合中の各要素を文脈ノードとして，●／book／chapter［figure［10］］［3］：bookの下の次のロケーションステップを評価し，これらの各文脈

Chapterノpドのうち，その子供にfigureノード

ノードに対する結果の集合すべての和集合を返す．こが10以上あるものの中で数えて，3番目のもの．

れを，右端のステップまで繰り返していく．

●／book／chapter［3］［figure［10］］：bookの下の

例えば，上述の問合せ式を図1のデータに対して評

Chapterノ，ドのうちの3番目のものが，その子価した場合の実行の様子は図2のようになる．図2中供にfigureノードを10以上持てば，その要素のの番号は，図1中でノードに付けられていた番号，実みの集合，そうでなければ，空集合．

線四角が軸とノードテストによる集合から集合へのマップ，破線四角が述語によるフィルタ操作である．
まず先頭の「／」は特別な意味を持ち，対象となる●／／figure［1］：／descendant−Or−SeJf：：nOde（）／figure［1］と等価で，任意の深さにあるfjgureの
うち，兄弟の中で最初のfigureノードであるよ

ⅩML文書のトップレベル全体を表すノードを返す．

うなもの（任意の探さにあるfigure要素で，最次に，このノードを文脈ノードとしてchild：：book

初のものを返す／descendant：：figure［1］とは意味を評価すると，このトップレベルにあるbook要素をが異なる）．

元とする集合を返す．この集合中の各ノード（実際に3丁4（12）

オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

合，まず／a／bの中間解として（b．，…，bn）を求め，こ3．XPath評価の計算量の各要素をコンテキストノードとして次のステップ

次に，本節では，XPathの評価の問題の計算量にfollowing−Sib［ing：：bを実行していくと，まず，blについて概観する．一般に，聞合せ処理の計算量を考え対して（b2，…，b乃）が求まり，これらの各要素をコンテる場合，聞合せ式が固定でデータベースのサイズのみ

キストノードとして次のステップを実行していくと，を考える場合（datacomplexity），データベースが固まず，b2に対して（b。，…，b乃）が求まり，…というよう定で問合せ式のサイズのみを考える場合（queryに，ロケーションステップを評価する関数への再帰的

complexity），双方を問題の人力とし，両方のサイズな呼び出しの回数が，ロケーションステップ数の指数を考える場合（combinedcomplexity）があるが，こオーダになる．実際，文献［4］によると，当時，存在

こでは最後のcombinedcomplexityについて考える．

した主な実装で実験を行ったところ，このような指数

また，ⅩMLデータがどのようなデータ構造で与えオーダの計算時間が観測されたそうである．

られるかも問合せ評価の計算量に影響する．XMLデ

しかし，上述のような単純な再起呼出しによる実行

ータの表現形式としては，ポインタによる木構造としには無駄がある．例えば，a→bl→b3→b。というパて与えられる場合や，ⅩMLの記述形式の文字列としスでb。が解として求まる計算過程と，a→b2→b3→て与えられる場合，また，関係データベースやネイテ

b4というパスでb。が解として求まる計算過程とでは，

ィブデータベースの中に，関係や専用のデータ構造にb3→b。の部分は同じ計算を重複して行っている．

よって格納されている場合等がある．このうち，デー

文献［4］では，これに対して，XPathの評価を多項

タベースに格納されている場合については文献［1］に式時間，多項式領域で行うアルゴリズムが示されてい譲り，ここでは，ポインタによる木構造と文字列を考る．このアルゴリズムの要点は，次の二点である．まえる．しかし，両者は対数領域で互いに変換可能［3］ず，あるノード集合Sと軸ズが与えられた場合，なので，Lより上の計算量の処理を考える場合には，

ズ（5）＝（∬′lJ∈S，∬ズJ′）（ここで，Jズ∬′は∬から区別する必要はない．よって，ここではポインタによJ′が軸ヱ′で到達できることを表す）は，入力データ

る木構造のみを考え，各ノードに対して，最初の子供

木の大きさをEDlとして，0（lDl）で，firstChild，へのポイ ンタ（子供がない場合はnull）である

nextsibIing，firstChildrl，neXtSibling−1から計算ゼ

firstChild，次の兄弟へのポイ ンタ（ない場合はきる．

null）であるnextSibling，およびこれらの逆である，

第二に，上述のような重複した計算を行わないため

firstChild￣1，neXtSibling￣1が与えられるものとする．

に，左のステップが返すノード集合の各ノードを文脈

3．1時間計算量として次のステップを順に実行していくのではなく，

まず，ⅩPathの評価の時間計算量について考える．

各ステップについて，COnteXtrValue tableという物

XPath評価の最も単純で分かりやすいアルゴ））ズムを計算していく．これは，何を文脈としてそのステッの一つとして，文脈とロケーションステップを受け取プを実行したら，何が解になるかを表す，文脈と解のって結果となるノード集合を返す関数を定義し，この対の集合である．例えば，上述の問合せ中のステップ

関数を根ノードと最初のロケーションステップに適用

fo［lowing−Sibling：：bについては，次の集合となる．

してノード集合を生成し，その各要素を文脈ノードと（（bl，b2），…，（bl，bn），（b2，b3），…，（b2，bn），

して次のロケーションステップを評価する関数を再帰（b3，b4），…，（b3，bn），…，（bn＿1，bn））

的に呼び出し，以降これを繰り返していくようなアル

正確には，文脈は，文脈ノード，文脈サイズ，文脈ノ

ゴリズムが考えられる．しかし，この方法は，問合せ

ード位置の三つ組なので，COnteXt−Value tableはこの大きさに対して指数時間の計算量となる．例えば，の三つと解の計四つ組の集合である．上では，文脈サ／a／b／fo［lowing−Sibling：：b／fo［［owing−Sibling：：b

イズと文脈ノード位置は解に影響しないので省略した．

という問合せを，根の下のaの子供に乃個のbがある，次のようなデータに対して実行したとする．

これを結合することによって，ボトムアップに上位の

a ／づタ、モ・−＼

部分式についてのcontext−Value tableを求めて行き，

b b・・・b b

ダ番目の兄弟のbをbゴと書くことにすると，この場
2005年6月号

このようなcontextrvalue tableを，問合せ式を木構造で表した際の葉に当たる部分式についてまず求め，最終的に根に当たる式，すなわち問合せ式全体に対す© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（13）3丁5るcontext−Value tableを求める．この手法によって，に還元可能な問題のクラスであり，次のことが知られ聞合せ式の大きさをl似，データ木の大きさを雷βlとている．

して，0（l功5＊】￠l2）の時間計算量と0（lβl4＊l￠l2）の領域計算量でⅩPathを評価することができる．
実際には，このアルゴリズムは多項式計算量ではあNCl⊂L⊂NL⊂LOGCFL⊂NC2⊂P
NCiは，0（が）台の計算機によって0（logf乃）の計算
時間によって解ける問題のクラスである．つまり，

るものの，中間結果として不要なcontext−Valueの四

LOGCFLは，NL（対数領域で非決定的に解ける問

つ組を大量に生成して非効率的なので，同文献では，

題のクラス）とPの間にあるクラスで，また，NC2

同様の計算を問合せ木の根からトップダウンに行う，に含まれるので，0（乃2）台の計算機を使った並列計算

より無駄の少ないアルゴリズムも示している．また，

で0（log2乃）の計算時間で解けることになる．なお，

文献［5］では，上の計算量を0（lβl4＊l￠l2）時間，LOGCFL⊂DSPACE（log2）0（lβl2＊l￠l2）領域に改善したアルゴリズムが示されとなることも知られている（DSPACE（log2）はlog2ている．

領域で決定的に解ける問題のクラス）ため，この部分

また，文献［4］では，より小さい時間計算量で解けるⅩPathの部分言語として，Core XPathが示されている．CoreXPathは，ⅩPathから算術演算に関す言語は，メモリ量が限られる環境においても解くことができるということも分かる［3］．

文献［6］では，pOSitive Core XPathより大きい部

る機能と，文字列演算に関する機能を取り除いて，木分言語でLOGCFいこ属する物として，pWFが示さ

構造のパターンマッチの機能のみに制限したものであれている．pWFは，pOSitive Core XPathに，文脈る．このようなCoreXPathの評価は，単純な集合演

ノード位置と文脈サイズを返す関数position（），last

算，前述の各軸に対応する二項関係ズ，あるラベルJ（）と，基本的な算術演算子，等号・不等号演算，数値を持つ全ノードの集合を求めるT（ハから構成される

リテラルを加え，逆に次の制限を加えた物である．

大きさ悼lの代数式に変換することができ，ズもr（ハも0（β）で計算できることから，全体として0（l￠l＊l劫），すなわち問合せの大きさに対してもデータ木の大きさに対しても線形時間で計算できる．

●♪［el】…［e乃］のような複数の述語の並びを含むステップは許さない●算術演算の入れ子は許さない
これらの制限は，COre XPathでは意味がないことに

3．2 並列化可能性注意されたい．後者についてはcore XPathは算術演

逐次計算による計算量に関しては，前節のように多算を含まないことから明らかであり，前者については，

項式時間，多項式領域による計算アルゴリズムが示さ

coreXPathにおいて次が成り立つことによる．

れているが，では，並列計算によって，効率良く

b［el］．．．［en］…b［eland．．．anden］

ⅩPathの評価を行うことは可能であろうか．これに上の式が成り立たないのは， わ中にpoisition（）やついては，ⅩPathの部分言語である前述のCore

Iast（）が現れる場合のみである．以上から，pWFはXPathでさえP困難であることが文献［6］に示されてpositiveCoreXPathを含む言語となる．

いる．一般に，P困難な問題は本質的に逐次的な計算

このpWFまで拡張してもLOGCFL内にとどまるを含んでおり，並列化によって効率良く解くことはで

理由は，上のような制限を加えた場合，評価の中間結きないと考えられているので，Core XPath，あるい

果となるノード集合を明示的にに求める必要がないたはより大きなⅩPath部分言語の評価は，並列化によめである．逆に，上の制限がないと，例えばって効率良く解くことはできないと考えられる．
しかし，同じ文献［6］および文献［3］では，それぞれ，CoreXPathから論理否定演算子を取り除いた部
分言語positive Core XPathの評価の問題が，LOG−／a／b［position（）＝…］［position（）＝…］…

のような聞合せでは，順にノード集合を求めていかな
いと，述語内の条件の計算ができない．

文献［6］では，完全なXPathに対しても，pWFとCFLに属することを（文献［6］では，さらにLOGC−

同様の制限に加えて，一部の組込み関数を禁じるなどFL完全であることも）示し，pOSitive Core XPath

して，LOGCFL内に押えたpXPathを定義しているの評価が並列化によって効率良く計算可能であることが，ここでは詳細は省略する．

が示されている．LOGCFLとは，対数領域（L）で3．3 領域計算王

文脈自由文法（contextfreelanguage，CFL）の問題

次に，領域計算量については，文献［3］に，その評3丁6（14）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

佃問題がL（対数領域で決定的に解ける問題のクラのpositiveCoreXPathの軸をchild，Parent，Self−Or−ス）に属する二つの部分言語Core XPathlとCore

descendant，Self−Or−anCeStOrに制限し，一方で和演

XPath十＊が示されている．Core XPathlは，軸を距

算∪を加えた言語1と，その七つの部分言語の計8個

離1のノードにしか進まないもの，すなわち，Self，について調べている．これらの八つの部分言語は，Child，Parent，PreVious−Sibling，neXt−Siblingのみに制限したもので，ⅩPath十＊は，軸を前方の任意の●後方軸，すなわちparentとself−Or−anCeStOrを含むかどうか．（†）

距離のノードに進むもの，すなわち，Self，descen−●任意長に対応する軸，すなわちself−Or−descen・

dant，descendant−Or−SeLfのみに制限したものであdantとself−Or−anCeStOrを含むかどうか．（r）

る．

●述語を含むかどうか．（［］）

文献［3］には，これらの部分言語の対数領域での評の3点の組合せの2＊2＊2＝8通りである．これら

価アルゴリズムが示されている．このアルゴリズムは，各々を上に示した記号を使って表すことにして，八つ問合せ木とデータ木を並行して探さ優先探索していき，の部分言語を例えばズ‡＝レと†を含み［］を含まな問合せ木中の次のステップに進む度に，データ木中でい言語」のように書くことにする．

も，現在見ているノードから，そのステップにマッチ

4．1表現力の部分言語間の関係するパスで到達できるノードへと進んで行く．そして，

まず，これら八つの部分言語間の関係について，次そのようなノードがない場合は，バックトラックを行が示せる2．

う．通常のⅩPathの評価をこのようなアルゴリズム

ズ⊆ズー＝ズ【］＝ズ【1⊆ズエ ⊆ズr【】＝ズ‡【】で行う場合は，このバックトラックを可能にするためズ⊆

ズr⊆ズ‡⊆ズr【1＝ズ‡【】に，これまでのステップにマッチしたノードをスタッ

ここでは，要点についてのみ簡単に例を使って説明す

クに積んで覚えておく必要がある．

る．まず，ズ†＝ズ【】については，直感的には，両者

しかし，軸をⅩPathlのように制限した場合，現在の間で，次のような書き換えが可能なことによる．

見ているノードから，一つ前のステップにマッチして／a［b［c／d］［e］］／f＝／a／b／c／d／ ／．．／e／‖／Jf

いたノードへは，対応するステップの軸を逆にたどれズ∴からズ【】へも同様の書き換えで†を取り除くこと

ばいつでも戻れるので，各ステップにマッチしたノーができる．また，ズr【】＝ズ‡【】については，文献［7］でドをすべて覚えてし−く必要はない．同様に，ⅩPath＋＊

は，これらのいずれもが，ある木パターン言語に等しでは，データ木中の各パス上でのノードの並び順だけい事を使って証明しているが，具体的な書き換えとしが重要である．よって，例えば，／／a／／b／／cという問ては，例えば次のような書き換えを行えばよい．

合せを評価する時に，現在，あるaノードの下の，／／a／／b／ancestor：：d＝／／d［．／／a／／b］∪／／a／／d［．／／b］

あるbノードにいて，その子孫にcノードが見つか

文献［8］では，より大きなXPath言語について，与えらなかったためバックトラックする場合，今見ているられたⅩPath式から後方軸を除去する書換え方法がbノードの位置さえ記憶しておけば，aノードの位置示されている．また，ズ‡⊆ズr【】が等号でないというは記憶しておかなくても，bノードから遡って最も根点については，次のような問合せを考えればよい．

に近いaノードを探し，そのaノードの子孫で，位／／a／／a［ノ／b］

置を記憶している現在のbノードよりも先に現れる

これを，／a／a［b］＝／a／a／b／‥と書き換えられたことの次のbノードへと進めば良い．よって，これらの部

類推から／／a／／a／／b／ancestor：：aと書き換えても，分言語では，これらの定数個のポインタを格納するた等価にならない．／／a／／a／／b／ancestor：：a／ancestor：：め（およびその他の計算を行うため）に必要な対数領

a／／aも，やはり等価でない（各自で確認されたい）．

域のみで評価が可能となる．

1正確には，parentやancestorに対するノードテストを

4．様々な部分言語とその性質

述語の形でしか書けないところが異なる．
2文献［7］では，言語表現力に関して，二種類の等価性を

前節では，ⅩPathの様々な部分言語が登場した．

そこで，本節では，ⅩPathのいくつかの部分言語について，それらの関係と性質について調べた文献［7］の内容の一部を簡単に紹介する．この文献では，前述2005年6月号

考えているが，ここでは文献［7］で言うところのroot
equivalenceについてのみ考える．また，前述のように，ここで考える言語は，文献［7］の言語とはノードテストの扱いが少し異なるので，ここで示している関係も，文献［7］で示されている物とは多少異なる．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（15）3TT

その他の，⊆の箇所については，容易に確認できる係があるかを判定する問題．XPath式の簡単化等にものと思う．

応用できる．

4．2 部分言語の集合演算に関する閉包性

最小ビュー間堰［11］：ⅩPath式の集合が与えられ次に，各部分言語が，集合演算（和，積，補集合）た時に，別のⅩPath式集合で，当初の各XPath式のの各々について閉じているかどうかを考える．ここで解をそれらの解から計算可能で，かつ，それらの解の考える各部分言語は明示的に∪演算を持っているので，総サイズが最小な物を求める問題．ネットワーク越し

和について閉じていることは明らかである．積についに問合せを行う場合の通信量の最適化等に応用できる．

ては，文献［7］で，ズ‡以外が閉じていることが示さ
参考文献

れている．まず，ズrr】が（よってズ‡r】も）が積に閉じていることについては，文献［7］では，この言語が，［1］天笠俊之，吉川正俊：「ⅩMLデータベース技術概説」，∃，＞，＜と二項関係cゐブタd，滋5Cβ乃ゐ乃J，からなる

オペレーションズ・リサーチ，第50巻，第6号，pp．365−

ある種の一階論理と等しいことを使って証明している

372，（2005）．

が，直感的には，例として次のような物を考えればよしヽ［2］）．Clark，S．DeRose（eds）： XAa nlth（肋′ゐ）1々柑わ乃了．0．附ヲC斤gco∽∽g乃（加わ乃， （1999）．

［3］L Segoufin： Typing and querying XML docu−／／a［b］／／dn／／a［c］／／＊［e］

ments：Some complexity bounds，＝／／a［b］／／a［c］／／d［e］∪

In PYVC．〆ACM

棚，pp．167−178，（2003）．

／／a［c］／／a［b］／／d［e］∪［4］G．Gottlob，C．Koch，RPichler： Efficientalgorith−msforprocessingxpathqueries，／／a［b］［c］／／d［e］

ズ【】について（よって，ズ↑およびズいこついても）や，ズ㌻，ズについても，同様に考えられる．しかし，InPnc．dl／℃DB，pp．95−106，（2002）．

［5］G．Gottlob，C．Koch，R．Pichler： XPath query

後方軸を除去できないズ；の場合は，積について閉じ

evaluation：Improvingtimeandspaceefficiency，ていないことは，次のような例を考えればよい．

P和C．〆應ニEgJCβg，pp．379−390，（2003）．

In［6］G．Gottlob，C．Koch，R．Pichler： Thecomplexityof／／a／／an／／b／ancestor：：a

この積は，／／a／／a［．／／b］で表せるが，前述のように，XPathqueryevaluation，InPnc．dACMPODS，pp．

179−190，（2003）．

これと等価な式はズ‡では表現できない．
また，同論文では，これらの部分言語はすべて，補集合演算について閉じていないことが示されている．

［7］M．Benedikt，W．Fan，G．M．Kuper：
propertiesofXPathfragments，

Structural

InPYVC．qflCDT，pp．

79−95，（2003）．

［8］D．01teanu，H．Meuss，T．Furche，F．Bry： ⅩPath：

5．結び

lookingforward， Inl穐戒sh坤On X〟エー励sed加ゎ
本稿では，ⅩPathの言語概要，その評佃の計算量，様々な部分言語の表現力や，集合演算に対する閉包性〟α乃喝ゼ∽g乃′，pp．109−127，（2002）．

［9］A．K．Gupta，D．Suciu： Stream processing ofについて簡単に解説した．XPathに関するその他のXPath querieswith predicates，

研究としては，次のような問題に関するものがある．

j汀G〟0∂，pp．419−430，（2003）．

XMLストリームデータに対する評価［9］：ネットワ

ーク上を流れるⅩMLストリームデー

タに対して

ⅩPathを評価する場合に，データを先頭から一度だ
け走査しながら評価を行うアルゴリズムに関する問題．

包含関係や等価性の判定［10］：与えられた二つのⅩPath式の解の間に，常に包含関係あるいは等価関

3丁8（16）［10］G．Miklau，D．Suciu：

In Pnc．〆ACM

Containment and equiva−

1ence for an XPath fragment，

In Proc．of ACM

PODS，pp．65−76，（2002）．
［11］K．Tajima，Y．Fukui：

AnsweringXPathqueries

OVernetWOrksbysendingminimalviews，
l／℃aβ，pp．48−59，（2004）．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

InP7VC．d