Tyzoh.jp

非常に大雑把にいうと、The Third Manifestoで規定される関係モデルとは、次のようになると理解しました。

• 型は「値の集合に名前をつけたもの」とする。ある型の値とは、その型によって名前をつけられた集合の要素とする。
• 型にはスカラ、タプルおよび関係という３つの種類とする。タプルおよび関係は、それぞれタプル型生成子および関係型生成子によって生成される。
• タプル型生成子によって生成される型（これをタプル型と呼ぶことにします。タプル型は型の名前ではなく、タプル型生成子によって生成される型の総称です。）は、型T_i(i=0,1,...n-1)に対して、これらの型によって名前をつけられた値の集合の直積につけた名前とする。（実際には、この直積集合の各成分に一意な名前がつく。）
• 関係型生成子によって生成される型（これを関係型と呼ぶことにします。関係型は型の名前ではなく、関係型生成子によって生成される型の総称です。）は、型T_i(i=0,1,...n-1)に対して、これらの型によって名前をつけられた値の集合の直積のべき集合につけた名前とする。（実際には、この直積集合の各成分に一意な名前がつく。）
• それぞれの型には演算子が定義されていて、演算の結果もまた別の型となる。

つまり、それまでに生成した型（によって名前をつけられた値の集合）の直積集合およびそのべき集合を用いて新しい型を生成していくところに、モデルに対する制約があるとみることができます。 いいかえれば、関係型の値の要素はタプル型の値で、その値はどれも同じ数の直積成分をもっており、それぞれの直積成分はそれにつけられた名前によって参照することができます。このことによって、複数の対象（データ）の構成要素を統一した方法でアクセスすることができることになります。

これに対して、ここで定式化しようとしている半構造化データモデルは、 タプル型や関係型がないデータモデルだということができます。 前回までは、属性名の全体集合Pを考えて、そこからの部分関数を使って定式化することを試みましたが、次のようにしたほうがより簡潔な記述となります。

対象を一意に識別するための識別子の集合をIとする。 Iのそれぞれの要素iには、それがもつ属性名の集合P_iおよび P_iを定義域とする関数f_iが定められているものと します。つまり、管理する対象全体は
{(i, f_i) | i∈I }
となります。P_i=domain(f_i)です。 また、iにf_iを割り当てる関数をFとします。 つまりf_i=F(i)です。

この記法に従えば、前回までの属性名の全体集合Pは次のようにあらわせます。
P=∪P_i
ここで∪は、I全体にわたってとることにします。

このモデルに対する操作は次のようになります。

• (識別子の追加)新たな識別子i∉Iに対して I:=I∪{i}
• f=F(i)とp∉domain(f)に対して、新たな関数gでdomain(g)=domain(f)∪{p}∧∀q∈domain(f) g(q)=f(q)なるｇをA(i)の値とする。
• f=A(i)とp∈domain(f)に対して、新たな関数gで domain(g)=domain(f)∖{p}∧∀q∈domain(g) g(q)=f(q)なるｇをA(i)の値とする。
• 与えられた述語Cと、Pの部分集合Qに対して、
  {(i, g) | i∈I∧C(i)∧g=A(i)|_Q}
  を計算する。ここでg=A(i)|_Qは、次のように定義します。
  f=F(i)としたときgは次を満たす関数です。
  domain(g)=domain(f)∩Q∧∀p∈domain(f)∩Q g(p)=f(p)

Pを属性名全体の集合、Vを属性値全体の集合として、 管理対象全体は、idの集合Iおよび Iから「PからVへの部分関数」への写像Aです。 つまり id∈Iに対して、A(id)はPからVへの部分関数となり、 domain(A(id))⊆Pが成り立っています。

これに対して、問合せとは、指定された述語CおよびPの部分集合Sに対して、 Cを満たすIの部分集合Jと、 すべてのid∈J に対してA(id)の定義域をSに制限したものを得る操作とします。 述語とは、Iから{true, false}への写像をいいます。

ここでPからVへの部分関数fと、Pの部分集合Sに対して、 fの定義域をSに制限するとは、SからVへの部分関数gで

domain(g)=S∩domain(f)∧∀p∈domain(g) g(p)=f(p)

すると問合せの結果は、

{ (id, g) | id∈I∧C(id)∧g=A(id)|S }

まず、どのような問題を解きたかったのかをもう一度整理しておきます。

現実世界においては、モデル化の対象は、それが持つ属性 （ここで「属性」とは「属性名」とその値の対のこととします。） の集合の同一性によってのみ識別されることになりますが、 本モデル化においては、その属性の集合とは別に、それらをモデル上で 識別するための識別子を付与することにします。

形式的には、全ての属性名の集合Pから属性値の集合Ｖへの部分関数fに よって対象を特徴づけることにします。 つまり、domain(f)⊆Pおよびrange(f)⊆Vということです。 この部分関数fと、対象を一意に識別する識別子idの対(id, f)が 取り扱う対象となります。いいかえれば、取り扱う対象の集合は 識別子の集合から上記の部分関数fの集合への写像Aとみなすことができます。 つまり、idを識別子として domain(A(id))⊆Pおよびrange(A(id))⊆Vとなります。

このモデルに要求される操作は次の通りです。

• 新しい識別子の割り当て
• 新しい属性名の割り当て
• 特定のidに対してf=u(id)のdomainを拡張すること。
  つまり特定の属性p∈P∖domain(f)に対してdomain(g)=domain(f)+{p}∧∀q∈domain(f) f(q)=g(q) なる部分関数gをu(id)の値とすること
• 特定のidに対してf=A(id)のdomainを制限すること。
  つまり特定の属性p∈domain(f)に対してdomain(g)=domain(f)∖{p}∧∀q∈domain(g) f(q)=g(q) なる部分関数gをA(id)の値とすること
• 特定のidに対してf=u(id)の値を変更すること。
  つまり、ある値v∈Ｖを用いて特定の属性p∈domain(f)に対して domain(g)=domain(f)∧∀q∈domain(f)∖{p} f(q)=g(q)∧g(p)=v なる部分関数gをA(id)の値とすること
• 対象全体の中から、指定した条件を満たす(id, f)の集合を取り出すこと。

このようなモデル化の方法は、対象がもつ属性値の集合の空でない部分集合を 主キーとみなす関係モデルよりも、属性値の並びが一致する場合にも それらを区別する識別子を陽に持つオブジェクトモデルと近い考え方です。 また、関係モデルでは、属性名に相当するものは、関係スキーマの一部として、 ナイーブな関係モデルには含まれませんが、本モデルにおいては、オブジェクトの メンバ（もしくはフィールド）と同じように、属性名を取り扱うことになります。

ただし、オブジェクトモデルにあるような、格納する対象に対する クラス（もしくは型）、すなわち同じ構造をもつ対象を一まとめにするような 概念は導入しないことにします。 しかし、実際にこのデータを用いたシステムを設計・実装する際には、 対象に含まれる情報のうち、その一部分を切り出してきて、 システムで想定する構造を持つものとして取り扱う必要があります。 そのためには、指定した条件に合致する対象を選び出すときに、 同じ構造を持つようにして切り出すことにします。 つまり、問合せ言語の提供により、その問合せを発行するシステムが 想定する構造を構築することにします。

いきなりですが、SPARQL問合せにおける空白ノードの扱いは、 RDFにおける空白ノードの扱いとずいぶん違います。 RDFにおいては、空白ノードは、そのノードが他のノードと識別できるような名前（URI)を持たないノード、いわゆる「名前無しノード」ですが、 SPARQL問合せのグラフパタン中に現れる空白ノードは、一種の変数のように扱われます。

つまりグラフパタンに対するパタン解を構成する際に、そのグラフパタン中の空白ノードは、検索対象のグラフ中のノードと「マッチ」します。 この点においては、グラフパタン中の変数と同じように振舞うのですが、 以前のSPARQL Puzzlerに書いたように、 空白ノードの名前の有効範囲が基本グラフパタン内であることなど、 いくつかの相違点が存在します。

また、SPARQL問合せの形式的定義において、パタン解は、変数からRDF項への写像であって、空白ノードは、パタン解の定義域に含まれていないこと、そして、この形式的定義においてSPARQL問合せの結果（正確には、ORDER BYやDISTINCTなどの処理を行う前）は、パタン解の順序付けされない並びであると規定している点です。このために、グラフパタン中の空白ノードが検索対象のグラフのどのノードと「マッチ」しているかは、検索結果であるパタン解の並び上は区別することができません。

同じことが、同じグラフパタンをUNION節でつなぎ合わせた場合の振る舞いにも 影響しています。

さて、今回のSPARQL問合せ

PREFIX dc: <http://purl.org/dc/elements/1.1/>
PREFIX ex: <http://www.tyzoh.jp/example/>
SELECT ?x ?z { ?x dc:creator _:y .
               _:y dc:title ?z . }

@prefix dc: <http://purl.org/dc/elements/1.1/> .
@prefix ex:  <http://www.tyzoh.jp/example/> .

ex:graph1 dc:creator _:a .
_:a dc:title "kawabe" .
ex:graph1 dc:creator _:b .
_:b dc:title "kawabe" .

{ ?x→ex:graph1, ?z→"kawabe" }

そして、先に述べたように、SPARQL問合せの結果は、「パタン解の 順序付けされない並び」と規定されており、この並びに同一のパタン解が複数含まれていてもよいように読めます。

ということで、この問題の答も3の実装依存になるというのが、私の理解です。

さて、次回からはまた問題編の第3ラウンドがスタートします。

この問題も問７と同じように UNION節を構成する各グラフパタンに対するパタン解が同一である場合、 UNION節は、これらをどうあつかうのか、という点がポイントです。

ですから、この問の答も、問７と同じように ３の実装依存ということになります。

問７では、UNION節を構成する各グラフパタンに同一のパタン解が あった場合に、UNIONはそれを一つにまとめてしまうのか？、が問題でしたが、今度は、UNION節を構成する二つのグラフパタンに対するパタン解が同一か、が問題です。もし同一であれば、その後は、問７と同じ結果になります。

ここで、パタン解とは、変数からRDF項への写像でしたから、 説明を見やすくするために、 変数?xがあるRDF項Aに写像されるということを

?x→A

S={ ?x→A, ?y→B, ... }

そうするとUNIONの左側のグラフパタンに対するパタン解S1は

S1={ ?x→ex:graph1 }

S2={ ?x→ex:graph1, ?y→"kawabe" }

さて、このパタン解S1とS2が同一であるかどうかがポイントですが、 この二つのパタン解は、例えば次のようなSELECT問合せ

SELECT ?x ?y { ?z dc:creator ?x OPTIONAL { ?x dc:title ?y } }

ということで、2の結果セットの<result>…</result>が2個が答となります。

SPARQLの仕様によると、UNIONグラフパタンを構成するグラフパタンのいずれかが、（パタン）解SによってグラフGに適合するとき、このUNIONグラフパタンは、ここの解SによってグラフGに適合する、となっています。

今回の問題は、UNIONグラフパタンを構成する複数のグラフパタンに同一のパタン解Sが含まれていたとき、それは、最終的に2つのパタン解なのか、それとも同一なパタン解だから、一つなのか、という点です。 出題したSPARQL問合せでは、同一のグラフパタンをUNIONで連結していますから、必ず同一のパタン解が含まれることになります。

これをどのように扱うのか、SPARQLの仕様を何度も読み直してみましたが、ちゃんと規定されているように読めませんでした。

ということで、今回の答えは4の実装依存としたいと思います。 もし、仕様のここにかいてあるよ、といった情報がありましたら、 是非コメントとして書き込んでください。

最初にお詫びしなければなりません。 今回の問題の正解は、選択肢の中にありませんでした。 申し訳ありません。

これまでのSPARQL Puzzlerで説明してきたように、 SPARQL問い合わせの結果は、WHERE句に指定したトリプルパタンに対する パタン解の並びとなるのでした。 パタン解は、トリプルパタンに含まれる変数からRDF項に対する写像でした。 今回のSELECT問合せ

 SELECT * WHERE { FILTER ( $x =  1) }

ところで、これまでには説明してきませんでしたが、このパタン解で写像されるRDF項は検索対象のグラフ（正確には、そのグラフに含まれる空白ノードの名前付け替えをしたもの）に含まれていなければならないのです。

つまり、検索対象のグラフにリテラル'1'が含まれていれば、$xを1に写像するパタン解が、このSELECT問合せの結果になれます。しかし、検索対象のグラフに1が含まれていなければ、このSELECT問合せに対するパタン解はなしなのです。 リテラル1が検索対象のグラフに含まれるとすると、それは目的語の位置にしか現れることはできませんから、目的語が1のRDFステートメントが、このグラフにふくまれるかどうかによって、結果セットの<result>…</result>は1個であったり、0個であったりするということになります。

ということで、今回の問題の答えは、5(?)の「検索対象のグラフに依存する」でした。

@prefix dc: <http://purl.org/dc/elements/1.1/> .
@prefix ex:  <http://www.tyzoh.jp/example/> .

ex:graph1 dc:creator _:a .
_:a dc:title "kawabe" .
ex:graph1 dc:creator _:b .
_:b dc:title "kawabe" .

PREFIX dc: <http://purl.org/dc/elements/1.1/>
PREFIX ex: <http://www.tyzoh.jp/example/>
SELECT ?x ?z { ?x dc:creator _:y .
               _:y dc:title ?z . }

1. 結果セットの<result>…</result>が1個
2. 結果セットの<result>…</result>が2個
3. 実装依存
4. 構文エラー

@prefix dc: <http://purl.org/dc/elements/1.1/> .
@prefix ex:  <http://www.tyzoh.jp/example/> .

ex:graph1 dc:title "kawabe" .

PREFIX dc: <http://purl.org/dc/elements/1.1/>
PREFIX ex: <http://www.tyzoh.jp/example/>
SELECT * { { ex:graph1 dc:title ?x } UNION
           { ex:graph1 dc:title ?x  OPTIONAL { ?x dc:creator ?y } }

1. 結果セットの<result>…</result>が1個
2. 結果セットの<result>…</result>が2個
3. 実装依存
4. 構文エラー