一般論文

DBSJ Journal, Vol. 7, No. 3
December 2008

Web コンテンツ管理のための一貫性制約発見手法

この問題に対し，我々は，DB 等をバックエンドに持たない Web
コンテンツの一貫性管理の支援を目的としたシステムの研究開発を行ってきた [2, 4, 5, 6]．このシステムは，Web コンテンツ間に成立すべき制約 (例えば，研究室 Web サイトにおける学生の論文リストは，研究室の論文リストのサブセットである，等) を与える
ことにより，既存の Web コンテンツに対して後付けでコンテンツの一貫性管理が行えるようにするものである．本システムを利用すれば，既存の Web サイトを，DB をバックエンドにした Web サ
イトに再構築しなくとも，このような一貫性管理が可能になる．
しかし，既存の Web コンテンツに対する制約は人手で与えなくてはならないため，膨大な Web コンテンツを対象とした場合には既存 Web コンテンツからの制約発見支援が必須である．
本論文で扱う問題と関連研究. 本論文では，Web コンテンツ間の制約を，Web ページの HTML や XML 要素間 (以下 Web ページ要素) の包含従属性 (inclusion dependency)[3] に限定し，システムを用いてその発見を支援するための手法を提案する．例えば，「学生の論文リストを表すコンテンツ X が研究室の論文リスト Y のサ
ブセットでなければならない」という制約を X ⊆IN D Y と記述する．この制約の発見を支援するために，既存の Web コンテンツにおいて X ⊆ Y の包含関係が存在するか否かを決定するのが本論文で扱う問題である．包含関係の存在は包含従属性を示すための根拠となる．
情報統合の分野において，包含関係の発見に関する研究は行われてきた．[7] では，リレーション (群) のインスタンスが与えられたとき，これらのリレーションの属性間に包含関係が成立するかの判定を行う効率よいアルゴリズムを提案している．そこでは，与えられたリレーションインスタンスに対して，属性 X の値の集合と属性 Y の値の集合に包含関係が存在するとき，X ⊆ Y を出力する (図 1(上))．
それに対し，我々の問題では次の 2 点が異なる．

A Method for Integrity Constraint Discovery for
the Management of Web Contents

高橋 公海 ♥
杉本 重雄 ♦

森嶋 厚行 ♦
北川 博之 ♠

松本 亜季子 ♣Masami TAKAHASHI
Atsuyuki MORISHIMA
Akiko MATSUMOTO
Shigeo SUGIMOTO
Hiroyuki KITAGAWA
近年，Web サイトを通じた情報発信が広く普及し，管理しなくてはならない Web コンテンツの量が増加している．我々はこれまで，コンテンツ制約を入力とすることによって，DB 等をバックエンドに持たない非定型 Web コンテンツの一貫性管理の支援を行うシステムの研究開発を行ってきた．本稿では，既存の Web コン
テンツからコンテンツ制約を発見するためのアルゴリズムと出力される大量の制約をランキングする手法について提案する．

Today, publishing information from Web sites are common, andthe size of the Web contents that need to be managed is increasing.
So far, we have been developing a system to support the content integrity of Web sites without back-end DBs, which tries to satisfy given
constraints on the contents. This paper proposes algorithms to automatically discover such constraints from existing Web content, and amethod for ranking the large amount of discovered constraints.

1. Web ページのコンテンツには間違いも多く含まれるため，厳密な包含関係の判定ではうまくいかない．すなわち，一文字異なるだけで包含関係の可能性を除去してしまうと，包含従属性の発見率が低下する．

1. はじめに

2. Web ページ要素はリレーション属性と異なり階層構造を成している (図 1(下))．したがって，4 章で詳述するように，出力される包含関係に重要なものとそうでないものが含まれる．
例えば，X ⊆ Y が得られたとき，階層構造での Y の上位要
素 Z(図 1(下)) に関して X ⊆ Z が得られることは自明であり，制約としての重要性は低いと考えられる．

近年，Web サイトを通じた情報発信が広く普及し，コンテンツの量も増加している．Web の特徴の一つは分散管理であるが，一方で，その特徴がコンテンツ一貫性の維持を困難とする一因となっている．例えば，大学の研究室の Web サイトでは，各構成員が自分のホームページ上で研究論文リストを公開することが多いが，これらの論文リストの間には矛盾が多く見られる等といった問題がある．一般に，コンテンツの一貫性を管理するためには，バッ
クエンドに DB システムを配置し，DB に格納されているデータ
から Web ページを作成するアプローチがとられる．しかし，筑波大学の Web サイトを対象とした我々の予備調査 [2] では，バックエンド DB 等をもたずに手作業で管理されている Web サイトも，数多く存在する．また，ある学部の Web サイトとその学部に属する学科の Web サイトが同じ内容を含むにも関わらず，管理者が別であるために統一的に管理されていないということもよくあることである [1]．このような場合，例えばある学科 HP の入試説明会
情報に変更があった場合，学群の HP でも同様の変更を行わなければならないが，確実な変更を保証することは多大な努力を要す
るものである．

そこで，本研究では，(1) に対しては許容率という概念を導入し，どれだけの許容率でどの包含関係が存在するかをもれなく計算することを提案する．また，(2) に対しては，スコア付けルール
によって，より重要と考えられる包含関係に上位スコアをつける
ような手法を提案する．
これらを実現するために，本手法の出力は単なる X ⊆ Y ではなく，組 (X ⊆ Y, p, s) の集合とする．ここで X, Y は Web ペー
ジ要素，p は許容率 (0 ≤ p ≤ 1)，s は重要度スコア (0 ≤ s ≤ 1)である．ここで，X に含まれるデータのうち割合 p を除去すれば
X ⊆ Y が成立するとき，X ⊆ Y は許容率 p で成立する，と呼ぶ．例えば，図 2 の Web ページ要素の組を考える．ここで，要素 A の a,b,c,d は要素 B に含まれているため，要素 A が a,b,c,d のみであれば A ⊆ B と判定できる．しかし，要素 A に x が追加された場合には，要素 B に x が含まれていないため，厳密な判定では包含関係は存在しない．しかし，1/5 個のデータを除去すれば
A ⊆ B が成立するため，これは許容率 0.2 で成立する．後述する
方法で重要度スコアが 0.5 と与えられたと仮定すると，本手法では (A ⊆ B, 0.2, 0.5) を出力する．
本論文の構成は次の通りである．2 章で，我々が開発中の Web
サイトコンテンツ一貫性管理システムについて説明する．3 章で，許容率を導入した包含関係の発見アルゴリズムを提案する．まず，♥ 学生会員

筑波大学大学院 図書館情報メディア研究科
mtaka@slis.tsukuba.ac.jp♦ 正会員
筑波大学大学院 図書館情報メディア研究科{mori,sugimoto}@slis.tsukuba.ac.jp♣ 学生会員
筑波大学 図書館情報専門学群
s0512261@ipe.tsukuba.ac.jp♠ 正会員
筑波大学大学院 システム情報工学研究科
kitagawa@cs.tsukuba.ac.jp1

日本データベース学会論文誌 Vol. 7, No. 3

2008 年 12 月

一般論文

DBSJ Journal, Vol. 7, No. 3
December 2008

図 3 コンテンツ一貫性制約を用いた Web サイト管理
Fig. 3 Web Site Management Using Content Integerity Constraints

Input: refValues, depValues
Output: 許容率 for depValues ⊆ refValues
1 C = |depValues|; // 含まれない値があるたびにカウントダウン
2 while depValues has next value do
3currentDep := depValues.next();
4
if refValues is empty then return 1-(C-a/depValues.size);
5
while true do
6currentRef := refValues.next() ;7
if currentDep = currentRef then break;8else if currentDep < currentRef then9
C := C - 1;
10
if C == 0 then return 1;
11
if depValues has next then12currentDep := depValues.next();
13
currentRef := refValues.prev();
14
else break;15
else if refValues has no next value thenreturn 1-(C-a/depValues.size);
16 return 1-(C/depValues.size);

図 1 RDB における包含関係の発見 (上) と我々の扱う問題 (下)Fig. 1 Discovery of Inclusion Relationships in RDBs (top) and Our Problem(bottom)

図 4 Brute Force アルゴリズム
Fig. 4 Brute Force Algorithm
図 2 許容率導入例
Fig. 2 Introduction of Acceptance Rate : An Example

含関係が成立するか計算する．本章では重要度スコアの計算については扱わない．これについては次の章で説明する．
本手法では，Web ページのコンテンツが，Web ページ要素の階層構造になっていると仮定する (実際の Web ページそのものでな
く，ラッピング結果でもよい)．また，Web ページ要素 x, y が表
す集合 X,Y に次の関係が成立すると仮定する．
Web ページ要素が表す集合が満たすべき性質: x が y の下位要素
であれば，X ⊆ Y である．
この性質を満たすような集合としては，各 Web ページ要素に含まれる文字列を N-gram 等で単純に分割したものや，形態素解析で分割したものが考えられる．提案手法はその集合の作成方法とは独立しているため，この性質を満たしていればいずれも適用可能である．
以降で提案するアルゴリズムは厳密な包含関係を発見するための[7] でのアルゴリズムを拡張し，許容率を導入したものである．いずれも，Web ページ要素 dep と ref に対応する集合 depV alues と
ref V alues に対して，depV alues ⊆ ref V alues かどれだけの許容率で成立するかを判定する．最初に説明する Brute Force アルゴ
リズムは，一組の (depV alues, ref V alues) が与えられたときに，この判定を行うアルゴリズムである．このアルゴリズムの問題は，
Web 要素の個数が n であるとき，n C2 回の実行 (とディスクスキャン) が必要であることである．二番目に説明する single pass アルゴ
リズムは，一度に複数の depV aluesi ∈ D と ref V aluesj ∈ R が与えられた時，これらの全ての組合せ depV aluesi ∈ ref V aluesj
がどれだけの許容率で成立するかを，いずれの Web ページ要素も一度のディスクスキャンで計算するものである．

最も単純なアルゴリズムを説明し，次に I/O コストを削減するた
めに複数の Web ページ要素を並列に処理する single pass アルゴリ
ズムを提案する．4 章で，ルールを用いた重要度スコアの計算方法を提案する．5 章で実験結果を説明する．6 章はまとめと今後の課題である．

2. コンテンツ一貫性制約を用いた Web サイト
管理手法
図 3 は我々が提案している明示的な一貫性制約を用いた Web コ
ンテンツ管理システム [4][5] の概要である．以下にその利用手順を述べる．(1) まず，利用者がコンテンツ一貫性制約を登録する．
(2) 制約が登録されると，システムは定期的もしくは Web サイトの更新が行われた際などに Web サイトのチェックを行い，先に登録しておいた制約と照らし合わせ，制約が破られていないかどうかを調べる．(3) その際，もし制約違反を発見したら，Web サイト
管理者に報告もしくは自動修正を行う．
本システムを利用するためには，Web コンテンツに関する制約をあらかじめ与える必要がある．しかし，Web コンテンツを構成するページ数が増えると，手作業で一つずつ発見することは現実的ではない．そこで，その発見支援のための仕組みが重要となる．
本論文は，その制約の一つである包含従属性の発見支援に関するものである．

3. 1 Brute Force アルゴリズム

3. Web コンテンツ間の包含従属性発見支援

アルゴリズムを図 4 に示す．これは，二つの集合 depV alues と
ref V alues が与えられたとき，包含関係 depV alues ⊆ ref V aluesが成立するかどうか判定する．

提案手法では，Web コンテンツに関する包含従属性の発見を支援するために，既存の Web サイトに含まれる全ての Web ページに含まれる全ての要素の組合せに対して，どれだけの許容率で包2

日本データベース学会論文誌 Vol. 7, No. 3

2008 年 12 月

一般論文

DBSJ Journal, Vol. 7, No. 3
December 2008

具体的には，まず図 4 の 1 行目で，depV alues 中の値のうち
ref V alues に含まれないものがあるたびに 1 ずつ減算するカウン
タ C の初期値を計算する．C = 0 になるということは，depV aluesのいずれの値も ref V alues に含まれていなかったということである．それ以降では，depV alues に含まれる各値が ref V alues に含まれているかどうかを順に判定していき，含まれていない値を見つけるたびに C を 1 つ減じる．そして，C が 0 になれば，許容率 p = 1 で depV alues ⊆ ref V alues が成立するため，1 を出力する (10 行目)．
テストが終わった段階 (16 行目) で C > 0 の場合には，許容率 p = 1 − (C/depV alues.size) を返す．depV alue が最後の値までテストされていないにも関わらず，ref V alue の次の値が無くなってしまった場合 (4 行目，15 行目) には，許容率 p = 1 − (C −a/depV alues.size) を返す．ここで，a は depV alue の残りの要素数である．
もし depV alue 中の現在の値が ref V alue 中の現在の値と等しい (7 行目) ならば，同じものが含まれているため，depV aluesと ref V alues を次の値に進める．もし depV alue 中の現在の値が ref V alue 中の現在の値よりも小さい (8 行目) ならば，その値は ref V alue 中に含まれないと判定できる．このようにして，
depV alues の値が ref V alues に含まれるかの判定を行う．

は ref の値が渡されたら図 8 のアルゴリズムを起動する．このアルゴリズムは現在のキューの状態に応じて適切に図 6 のプログラ
ムを呼び出すものである．

図 5 Single-Pass アルゴリズムの概要
Fig. 5 Overview of the Single Pass Algorithm

Input: referencedObject, referencedValue,dependentValue
Output: satisfied IND or null,
1 if dependentValue = referencedValue then2
if 3 next dependent value then3
if 3 referencedObject.wantNextValue(this) then4
nextWaiting :=nextWaiting ∪ referencedObject;
5else
6return 1-(C-a/depValues.size);7else
8
C := 1-(C-a/depValues.size);
9
return this ⊆ referencedObject, C;
10 else if dependentValue > referencedValue then11
if referencedObject.wantNextValue(this) then12currentWaiting :=currentWaiting ∪ referencedObject;
13
else
14
return 1-(C-a/depValues.size);
15
else
16
C = C -1;
17
if(C < 0){18
C := 1; return C;
19}else{
20
if 3 next dependent value then21
next :=
next ∪ referencedObject;
22
else
23
C := 1-(C-a/depValues.size);
24
return this ⊆ referencedObject, C;
25}
26 return null;

3. 2 Single-Pass アルゴリズム
Single-Pass アルゴリズムは，Brute Force アルゴリズムと同じ作業を行うが，一つの組ごとではなく，複数の組合せの処理を同時に行う．具体的には，D = {depV alues1 , . . . , depV aluesm }, R ={ref V alues1 , . . . , ref V aluesn } の時，包含関係 depV aluesi ∈ref V aluesj がどれだけの許容率で成立するかの判定を並行して行う．
図 5 は本アルゴリムの考え方を図示したものである．具体的には，各 depV aluesi と ref V aluesj を処理するためのオブジェク
トを生成し，これらが値をやり取りしながらカーソルを進めていく．このとき，あらかじめ depV aluesi と ref V aluesj 中の値はソートしておく．このアルゴリズムでは，集合中の値は 1 度だけ読まれ，包含関係を満たす可能性のある全ての候補のペアは並行してテストされるため，I/O の量を最小化することができる．各集合はオブジェクトによって管理される．
基本的なアイデアは次の通りである．すなわち，各 dep オブジェ
クトは，現在指しているカーソルの値が関係する全ての ref オブジェクトの値との比較が終わった時に初めて，自身のカーソルを次に進める．同様に，各 ref オブジェクトは，現在指しているカーソ
ルの値が関係する全ての dep オブジェクトの値との比較が終わったときに初めて，自身のカーソルを次に進める．
実際の動作は，各 dep オブジェクトが主体となって行う．すな
わち，dep オブジェクトのカーソルを移動する決定は dep オブジェ
クト自身が行う．ref オブジェクトのカーソルを移動する決定は，後述する monitor オブジェクトが dep オブジェクトからの ref の値の要求状況を見て判断する．
図 6 は，各 dep オブジェクトが実行するアルゴリズムの一部である．その dep オブジェクトのカーソルが現在指す値と，ref オブジェクトの現在の値を入力として比較し，dep のカーソルを動かすかどうかを判定する部分である．また，条件がそろえば，包含関係と許容率の組を出力する．
dep オブジェクトが ref オブジェクトの値を要求する (カーソルを動かして欲しい) ときには，currentWaiting および nextWaiting というキューにその ref オブジェクトの参照を代入することによって行う．
Monitor オブジェクトは，そのキューの内容をみて，ref オブジェ
クトのカーソルを進める．図 7 にそのコードを示す．具体的には，ある ref オブジェクトと関係する全ての dep がその ref オブジェク
トに要求を出したとき，その ref オブジェクトのカーソルを進め，次の値をそれらの dep オブジェクトに渡す．各 dep オブジェクト

図 6 dep オブジェクトでの値の比較とカーソル移動
Fig. 6 Value Comparison and Cursor Movement by a Dep Object

4. スコアリング
これまで，我々は Web ページ要素間の包含関係 X ⊆ Y に関す
る出力 (X ⊆ Y, p, s) のうち，p を計算する方法を説明してきた．
ここでは，重要度スコア s の計算方法について議論する．
重要度スコアを計算する動機は次の通りである．すなわち，ページに含まれる全ての要素の組み合わせの包含関係を計算する場合，自明なルールとそうでないルールが混在し，価値の高い包含関係が埋もれてしまうことである．これは，Web ページ要素間に階層関係が存在することに主に起因する (図 1)．
そこで，我々は出力される包含関係に対して重要度スコア (0 ≤s ≤ 1) を計算するための 3 つのルールを定義し，これを用いて自明でない包含関係の発見を支援することを提案する．
以下の各ルールの説明においては，x，y をそれぞれ Web ペー
ジ要素とし，X ，Y をそれぞれの要素が含む単語の集合とする．

3

日本データベース学会論文誌 Vol. 7, No. 3

2008 年 12 月

一般論文

DBSJ Journal, Vol. 7, No. 3
December 2008

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
30
31
32
33
34
35
36
37

デフォルトの重要度スコアとして，あらかじめ全ての包含関係に 1 が与えられているとするすなわち，全ての包含関係に対して(X ⊆ Y, p, 1) がデフォルトの状態であるとする．そして，ルールを適用することによって重要度のスコアを変更する．

//モニタが値を渡す Ref を入れておくキュー
Queue monitor queue;
while(true){//終了判定for each dep in D{
if(dep.refobjectlist.isEmpty) D.dep.remove;}for each ref in R{
if(ref.depobjectlist.isEmpty) R.ref.remove;}if(D.isEmpty || R.isEmpty)
break;

4. 1 スコアリングルール 1
これは，他のルールから演繹できる自明な関係の重要度を下げる
ルールである (図 9)．

//キューに追加
for each ref in R{
boolean flag = true;for each dep in ref.depobjectlist{
if(!contains(dep.currentWaiting, ref)&& !contains(dep.nextWaiting, ref)){
flag = false;
break;}}
if(flag) monitor queue.add(ref);}if(monitor queue.isEmpty)
break;

図 9 スコアリングルール 1
Fig. 9 Scoring Rule 1

ルール 1：r1 : A ⊆ B ，r2 : C ⊆ D が成立すると仮定する．ルール 1 を適用する前の r2 の重要度スコアを scoreold (r2 ) とする．もし，C が A の下位要素であり，かつ，D が B の上位要素である
時，ある c < 1 を用いて score(r2 ) = scoreold (r2 ) × c とする．

//dep オブジェクト起動
while(r=monitor queue.next() != null){//ref のカーソルを進める
for each ref in R {if(ref.cursor.hasNext)
ref.cursor++;}for each dep in r.depobjectlist{
dep.Algorithm3(r, r.value);}monitor queue.clear;}

4. 2 スコアリングルール 2
これは，Web ページ要素の集合間の包含関係と，それらの部分集
合間の包含関係が与えられたとき，後者の関係が前者から容易に推測できる場合に，後者の重要性を下げるルールである．
例えば，図 10 のような場合，論文リストの各論文同士の関係の重要度が下がることになる．具体的には，図中で要素 A と要素
B を ul タグの要素，論文 1〜5 を li タグの要素とする．また，要素 A と要素 B の関係以外に，論文 2・4・5 同士の関係が発見されているとする．このとき，論文 2・4・5 同士の関係の重要度が下げられる．

図 7 Monitor オブジェクトが実行するアルゴリズム
Fig. 7 Main Algorithm of the Monitor Object
Input: referencedObject, referencedValue
1 // compare with next dependent value
2 if referencedObject∈ nextWaiting then3
nextWaiting := nextWaiting\ referencedObject;4
next := next ∪ {(referencedObject, referencedValue)}5
return;6
7 // compare with current dependent value
8 currentWaiting := currentWaiting\ referencedObject;
9 processComparison(referencedObject, referencedValue);10
11 // Do we need current value any longer?
12 if currentWaiting = φ and(next != φ or nextWaiting != φ) then13
dependentValue := next dependent value;
14// update waiting lists
15
currentWaiting := nextWaiting;16
nextWaiting := φ17// test corresponding inclusion dependencies
18
do{
19
next old = next;
20
next = φ;21
for each otherReferencedObject in next old{22
processComparison(otherReferencedObject,value of otherReferencedObject);23}
24
boolean cond = (currentWaiting = φ) and next != φ then25
if(cond){26
dependentValue := next dependent value;
27// update waiting lists
28
currentWaiting := nextWaiting;29
nextWaiting := φ30}
31}while(currentWaiting = φ and next != φ);

図 10 スコアリングルール 2
Fig. 10 Scoring Rule 2

ルール 2：r0 : A ⊇ B ，r1 : C1 ⊇ D1 ，r2 : C2 ⊇ D2 ...rn : Cn ⊇Dn が許容率 p >> 0 で成立するとする．ルール 2 を適用する
前の ri の重要度スコアを scoreold (ri ) とする．|B| を B が表す
Web ページ要素のサイズとする．また，0 < α ≤ 1 とする．この時，以下の条件が全て成立する場合に，ある c < 1 を用いてscore(ri ) = scoreold (ri ) × c (ただし，i 6= 0) とする．

(1)
(2)
(3)

∀1≤i≤n (A ⊇ Ci )∀∪1≤i≤n (B ⊇ Di )
|

1≤i≤n

|B|

Di |

>α

ここで，α をカバー率と呼ぶ．カバー率とは，要素 B の部分要素のうち，どれぐらいの割合が要素 A の部分要素との間に包含関係があるかを表したものである．α = 1 の時には，全ての B の子要素に対して，A の子要素との間に包含関係が存在することは自図 8 dep オブジェクトのメインアルゴリズム
Fig. 8 Main Algorithm of a Dep Object

4

日本データベース学会論文誌 Vol. 7, No. 3

2008 年 12 月

一般論文

DBSJ Journal, Vol. 7, No. 3
December 2008

明であるため，これらの包含関係の重要性は低くなる．本ルール
では Web ページコンテンツの不完全さを考慮し，α が 1 よりやや小さい場合にも適用可能な余地を残している．

4. 3 スコアリングルール 3
これは，許容率をわずかにあげるだけで自明でない包含関係が得られるとき，前者の重要度を下げるためのルールである．
図 11 に例を示す．ここでは，C と B では「札幌」と「北海道」のように一部の語が異なっており，かつ「北海道」が C の外に存在するため，低い許容率では B ⊆ A しか発見できないが，少し許容率を上げるとより自明でない B ⊆ C が発見できる．つまり，許容率が低い時には body のような全体との関係になるが，少し許容率を上げるだけで，その度合い以上に，粒度のかなり小さな要素同士の組み合わせが発見できる場合に，body のような全体との関係を除去しようというものである．

図 12 包含関係の発見数の累積度数分布
Fig. 12 Cumulative Distribution of the Number of Discovered Inclusion
Relationships

図 12 に，許容率と成立した包含関係の累積度数分布を示す．ス
コアリングによって有用度の低い包含関係は 1 より低いスコアをつけられるため，重要と考えられる包含関係の以外の発見数を減らすことが出来ることが分かる．図 13 は，許容率と F 値の関係を示したものである，スコアリングルールを適用するに従って，再現率と適合率が共に上がる傾向にあることが分かる．

図 11 スコアリングルール 3
Fig. 11 Scoring Rule 3

5. 2 実験 2
実験 2 では，筑波大学情報学群の Web サイト，および情報学群に属する各学類 (情報科学類，知識情報図書館学類，情報メディア創成学類) の Web サイトを対象とし，どの部分に包含関係が見られるか調査した．
これらは同じような内容を含んでいるにも関わらず，管理者が違うために統一的に管理されていないサイトである．
図 14,15 に発見できた包含関係の例を示す．図 14 は情報学群への問合せ先として各学類の事務の住所・電話番号・メールアドレ
ス等が一覧で示されているページと，ある学類の Web サイトに含まれる事務の住所・電話番号・メールアドレスが書かれたページであり，包含関係を発見した．この包含関係は許容率 31.8%で成立した．図 15 は情報学群の公開講義に関する記述が情報学群とある学類の Web サイトに含まれていた事例であり，包含関係を発見した．この包含関係は許容率 1.1%で成立した．
一般に，図 14 で示したような連絡先に変更があった場合は，Web
サイト管理者も変更する可能性が高いかもしれない．しかし，図15 のような場合には，両方のサイトに同じ内容が含まれていることを忘れてしまい，コンテンツ一貫性が保たれないということも十分に考えられるため，そういった箇所も発見できたことは有用であった．

ルール 3：r1 : A ⊇ B が許容率 p1 で成立し，r2 : C ⊇ B が許容率 p2で成立するとする．また，p1 < p2 とする．ルール 3 を適用する前のr1 の重要度スコアを scoreold (r1 ) とする．この時，次の条件が全て成立する場合に，ある c < 1 を用いて score(r1 ) = scoreold (r1 )×cとする．
(1) A ⊇ C(2) |C|× pp21 < β|A|
ここで，β ≤ 1 である．β = 1 の時，許容率の変化と A から C
へのサイズの変化が等くなる．β の値が小さいほど，劇的に C のサイズが小さくなることが求められる．

5. 実験
本節では，提案手法の性質を調べるために行った実験について説明する．本実験では，Web コンテンツに含まれる各 Web ページ
要素 x の内容を形態素解析で分割したものを対応する集合 X とした．

5. 1 実験 1
実験 1 では，ある Web ページの組を対象に本アルゴリズムを適用した．対象としたページは，ある研究室の教員の Web ページと，同じ研究室に所属するある学生の Web ページである．正解となる
包含関係の集合を用意し、アルゴリズムの出力から重要度 1 の包含関係だけを選択し，適合率と再現率を計算した．実験は下記の
4 つの場合について行い，結果を比較した．今回の実験では，α を0.9，β を 0.35 とした．

6. まとめ
本稿では，既存の Web コンテンツを入力として，コンテンツ間の包含関係を計算するためのアルゴリズムの提案を行った．本アルゴリズムでは，Web コンテンツには誤りが多いこと，および Web
コンテンツが階層構造を持つことに着目し，下記の工夫を行った．
(1) 許容率の概念を導入し，この値と共に包含関係と共に出力する．(2) 自明でない包含関係を優先するために重要度スコアを導入
し，それを計算するためのルールを作成した．実験の結果，これらの手法が有効に働く可能性が高いことが分かった．今後の課題
としては，より効率よく包含関係の発見を行うための仕組みの開1. スコアリング無し (全ての重要度スコアが 1)
2. スコアリングルール 1 のみ適用
3. スコアリングルール 1，2 を適用
4. スコアリングルール 1，2，3 を適用

5

日本データベース学会論文誌 Vol. 7, No. 3

2008 年 12 月

一般論文

DBSJ Journal, Vol. 7, No. 3
December 2008

図 15 発見された包含関係の例 (2)Fig. 15 Discovered Inclusion Relationship : Example 2[6] 高橋公海，澤菜津美，森嶋厚行，杉本重雄，北川博之. Web
コンテンツ一貫性管理支援ツールの開発. 第 70 回情報処理学会全国大会講演論文集 (第 5 分冊), pp. 189-190, 2008 年 3 月．
[7] J. Bauckmann，U. Leser，F. Naumann．Efficiently Computing Inclusion Dependencies for Schema Discovery．InterDB’06(ICDE Workshop), 2006.

図 13 F 値
Fig. 13 F-measure

高橋 公海 Masami TAKAHASHI
筑波大学大学院 図書館情報メディア研究科博士前期課程在学中．
情報処理学会学生会員，日本データベース学会学生会員．

森嶋 厚行 Atsuyuki MORISHIMA
筑波大学大学院 図書館情報メディア研究科/知的コミュニティ基
盤研究センター准教授．筑波大学大学院 工学研究科修了．博士(工学)．ACM，IEEE-CS，情報処理学会，電子情報通信学会，日本データベース学会各正会員．

松本 亜季子 Akiko MATSUMOTO
筑波大学 図書館情報専門学群在学中．日本データベース学会学生会員．

杉本 重雄 Shigeo SUGIMOTO

図 14 発見された包含関係の例 (1)Fig. 14 Discovered Inclusion Relationship : Example 1

筑波大学大学院図書館情報メディア研究科/知的コミュニティ基盤
研究センター教授．京都大学大学院工学研究科情報工学専攻博士後期課程単位取得退学．京都大学工学博士．ACM, IEEE-CS, 情報処理学会, 日本データベース学会各正会員．

発，および発見した包含関係から具体的な制約を記述する手法の開発などが挙げられる．

北川博之 Hiroyuki KITAGAWA[謝辞]

筑波大学大学院システム情報工学研究科/計算科学研究センター教授．1980 年東京大学大学院理学系研究科修了．理学博士．日本
データベース学会理事，情報処理学会フェロー，電子情報通信学会フェロー，ACM，IEEE-CS，日本ソフトウェア科学会各正会員．

ゼミ等においてコメントいただきました，筑波大学大学院図書館情報メディア研究科 杉本重雄教授，阪口哲男准教授，永森光晴
講師に感謝いたします．本研究の一部は科学研究費補助金特定領域研究 (#19024006)，科学研究費補助金基盤研究 (B)(#19300081)，
科学研究費補助金若手研究 (B)(#20800076) による．

[文献][1] 筑波大学情報学群，”http://inf.tsukuba.ac.jp/”，(参照 2008-0822)[2] 澤菜津美，森嶋厚行，飯田敏成，杉本重雄，北川博之．コ
ンテンツ一貫性制約を用いた Web サイト管理手法の提案．
DEWS2007，7 pages，2007 年 3 月．
[3] Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of
Databases. Addison-Wesley 1995.
[4] Natsumi Sawa，Atsuyuki Morishima，Shigeo Sugimoto，Hiroyuki Kitagawa．Wraplet: Wrapping Your Web Contents witha Lightweight Language．Proc. IEEE SITIS’ 2007.
[5] 澤菜津美，森嶋厚行，杉本重雄，北川博之．情報統合利用を目的とした HTML ページのラッピング支援．DEWS2008, 2008
年 3 月．

6

日本データベース学会論文誌 Vol. 7, No. 3

2008 年 12 月