論文

Journal of the DBSJ Vol.7, No.1

XML 文書のアクセス制御におけるているアクセス制御ルール集合は，ルール生成時のアクセス権限

ロール階層を考慮したルール簡略化とルール変更操作の局所化

設定情報を保持し参照されるだけではなく，アクセス権限設定情Simplifying Access Control Rules and Localizing Impact of Updates for XML Documents and Role Hierarchyて重要な意味を持ってくる．そのためルールの冗長性を削減する

報の変更に伴い適切に変更される必要がある．このようにルール
集合を効率の良い形式で管理することは，管理コスト全体からみとともに，ルール集合への更新操作に必要なコストを抑えることが可能な手法を提案する．
以下，本稿は 2 章において関連研究について述べ，3 章で DR
領域とアクセス制御ルールとしてのアクセス制御ラベルとその牛場 祐貴 ♥
吉川 正俊 ♠

岩井原 瑞穂 ♦Yuki USHIBA
Masatoshi YOSHIKAWA

Mizuho IWAIHARA

集合の簡略化について述べる．4 章において権限判定の方法と更新の方法について述べた後，コストを評価する．5 章で同一のア
クセス権限設定情報から既存手法，提案手法によって作成されたXML のアクセス制御において，ロールベースドアクセス制御を行う際に，XML 文書の木構造だけでなくロール間の関係から構成されるロール階層の構造も利用したルールの削減を行う手法
を提案する．提案手法では，XML 文書内の部分木の包含関係とロール階層内の到達可能集合の包含関係を利用し，求めるアクセス制御情報を実現するために必要なアクセス制限ルール数を削減する．また提案手法によって更新の範囲を局所的に押さえた結果，更新コストを削減できることがわかった．

We adopt Role-Based Access Control(RBAC) inorder to use instead of user group and use role hierarchy as relation of roles. Role hierarchy as wellas XML Document tree is useful for reducing redundant rules. We deﬁne and use DR-Region to reduce
the space for rules and to localize impact of updates.

ルール集合に対し更新操作を行い定量的評価をする．6 章はまとめと今後の課題である．

2.

関連研究

2.1

XML 文書におけるアクセス制御

XML 文書は開始タグと終了タグで囲まれた入れ子構造を持ち，要素をノードとする木構造として文書を表現できる (図 1)．
さらに XML 文書が置かれているディレクトリ構造や URI を含めた木構造と考えることができるため，これ以降はそのように木構造をなしている XML 文書集合をアクセス制御対象としても考えることにする．
きめ細かいアクセス制御は XML 文書が存在するディレクトリ
や URI を含めた XML 文書の構造・内容に応じて直接的にアクセスの制約をかけるため，アクセス制御ルールは XML 文書の構造・内容に深くかかわってくる．文献 [1] では XML 文書におけるアクセス権限設定が親子間で同じアクセス権限設定を持つ傾向にあるという構造的な局所性に注目し，アクセス権限設定がXML 文書の階層構造によく一致するとき，より少ないラベル数でアクセス制御情報を表現できる特徴を持つ手法が示されている．また文献 [2] では文献 [1] で使用されるラベルを統合することにより，総ラベル数を削減を行う手法が示されている．

1.

はじめに

顧客情報など秘匿性の高い文書を XML 文書形式で保存することが多くなり，XML 文書や XML 文書が存在するディレクトリ
や URI に対するアクセス権限を適切に管理するアクセス制御は情報保護において重要となりつつある．
大きな企業では数万を越すユーザが存在するとことがあり，またアクセス制御対象オブジェクトの文書も数千万を越え，管理コ
スト以外にも情報保護や内部統制の面からこのような大規模なアクセス制御の効率化を行う必要がある．また生成され，蓄積され♥♦♠京 都 大 学 大 学 院 情 報 学 研 究 科

y.ushiba@db.soc.i.kyoto-u.ac.jp
正 会 員

京 都 大 学 大 学 院 情 報 学 研 究 科

iwaihara@i.kyoto-u.ac.jp
正 会 員

京 都 大 学 大 学 院 情 報 学 研 究 科

ロールベースドアクセス制御

アクセス制御の主体であるユーザ集合を特定の役割に応じてロールとしてまとめ，ロール間の継承関係を組織構造等に基づいてロール階層を構築することができる．アクセス制御対象のオブジェクトとユーザの間のマッピングにロール階層をはさむことにより，オブジェクトとロールのマッピングおよびロールとユーザのマッピングに分割できる．これにより，アクセス制御ルールの管理コストを削減することができるロールベースドアクセス制御(RBAC)[4] は標準化が行われ普及が進んでいる．

3.
学 生 会 員yoshikawa@i.kyoto-u.ac.jp

1

2.2

提案手法

XML 文書におけるアクセス制御ルールの簡略化に関する既存手法はロール階層に適用することは以下の理由から困難である．

• XML 文書のみに適用することを想定しているか [1]，または操作など固定された構造に対して適用することを想定して

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

論文

Journal of the DBSJ Vol.7, No.1
存在することは同値．すなわち次の式が成り立つ．

r0n2 ∈ DoS(n1 ) ⇔ DoS(n2 ) ⊆ DoS(n1 )

d0

(1)

証明 1 n1 から n2 への有向路が存在するとき，n2 からの有向路
r1

d1

d2

r2

r3

が存在する任意のノード n3 に対して，n1 からも n2 を通り n3へ至るような有向路が存在するため，DoS(n1 ) は DoS(n2 ) のd3

要素全てを含む．逆に DoS(n1 ) と DoS(n2 ) が包含関係にある
とき，DoS(n2 ) の要素である n2 は DoS(n1 ) の要素でもある．
r4

図 1 XML 文書木すなわち DoS の定義から n1 から n2 への有向路が存在することを示している．

図 2 ロール階層

補題 2 (有向路の存在と AoS の包含関係) n2 から n1 への有向路が存在することと AoS(n1 ) と AoS(n2 ) の間には包含関係がおり [2]，ロール数が数千に及ぶようなロール階層にはその存在することは同値．

まま適用できず，またロール階層での継承等が考慮されていない．

証明 2 DoS と同様である．

• 制約条件があることにより，ロール階層にそのまま適用することはできない．

定義 2 (cas(cascade)) 非巡回有向グラフ G(V, E) とノード

そこで XML 文書の木構造とロール階層構造を考慮した新たなラベル設定を提案する．
以下では，まずラベルを設定する DR 領域の定義を行った後に，DR 領域の包含関係により構成される DR 束について述べる．そしてアクセス権限情報設定の手法であるラベル付けアル
ゴリズム，簡略化の手法である冗長なラベルの除去について述
べる．

3.1

n ∈ V に対して，{‘u‘, ‘d‘} の 2 値で設定され，それぞれ ‘u‘ はAoS(n),‘d‘ は DoS(n) を用いることを意味する．
定義 3 (DR 領域) XML 文書内の文書ノード d の DoS(d) とロール階層内のロール r からの cas に基づく DoS(r)/AoS(r)にそれぞれ所属する任意の文書ノードとロールの対の集合を DR領域と呼ぶ．またこの基点となる d と r の対を代表対と呼び，代表対と cas の組から DR 領域への関数を以下の式で定義する．

DR 領域

提案手法は CAM のようにアクセス権限設定が XML 文書の階層構造だけでなく，ロール階層の改造構造にもよく一致すると{
DR(d, r, cas) =DoS(d) × DoS(r), (cas = ‘d‘)DoS(d) × AoS(r), (cas = ‘u‘)

きに，より少ないルール数でアクセス制御情報を表現できる特徴を持つ．まず階層構造における適用範囲を定める関数 DoS/AoS

定理 1 (有向路の存在と DR 領域の包含関係) 文 書 ノ ー ドを定義したのち，アクセス制御ラベルを設定する DR 領域の定義を行う．

d1 , d2 と ロ ー ル r1 , r2 に 関 し て ，d1 と d2 の 間 に 有 向 路 が
存 在 し r1 と r2 の 間 に 有 向 路 が 存 在 す る こ と と DR 領 域
DR(d1 , r1 , cas), DR(d2 , r2 , cas) の間に包含関係が成り立つこ定義 1 (DoS(descendant or self )/AoS(ancestor or self ))とは同値である．すなわち以下の式が成り立つ．

非巡回有向グラフ G(V, E) が与えられたとき, それぞれ以下のよ
うに定義される関数である．DoS(n) は n からの有向枝の向きに沿った有向路が存在するノードの集合を返す．以下の式で定義

d1 ∈ DoS(d2 ) ∧ r1 ∈ DoS(r2 )⇔ DR(d1 , r1 , ‘d‘) ⊆ DR(d2 , r2 , ‘d‘)(2)

d1 ∈ DoS(d2 ) ∧ r1 ∈ AoS(r2 )される．

DoS(n) = {n} ∪∪DoS(c)c∈V ∧(n,c)∈Eの集合を返す．以下の式で定義される．

∪(3)

証明 3 XML 文書木とロール階層それぞれに関する補題 1 から

AoS(n) は n への有向枝の向きに沿った有向路が存在するノード

AoS(n) = {n} ∪⇔ DR(d1 , r1 , ‘u‘) ⊆ DR(d2 , r2 , ‘u‘)AoS(p)p∈V ∧(p,n)∈E(2) が導出される．同様に XML 文書に関する補題 1 とロール階層に関する補題 2 から (3) が導出される．逆に例えば互いに包含関係を持たない 2 つの文書ノード d1 ，d2 と同一のあるロールを代表対とする DR 領域を考えると，互いに含まれていない文書
ノードとロールの対が存在するため包含関係は存在しない．ゆえ補題 1 (有向路の存在と DoS の包含関係) n1 から n2 への有向に DR 領域において包含関係が存在するのは (2) または (3) を路が存在することと DoS(n1 ) と DoS(n2 ) の間には包含関係が満たすときのみである．

2

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

論文

Journal of the DBSJ Vol.7, No.1

定理 2 DR 領域の集合は半順序をなす．すなわち以下の式が成が positive/negative/neutral であるとき d 部にそれぞれ +/-/

り立つ．

親のラベルと同じものを設定する．

(反射律)
DR(d1 , r1 , cas) ⊆ DR(d1 , r1 , cas)
(推移律)
(DR(d1 , r1 , cas) ⊆ DR(d2 , r2 , cas))∧(DR(d2 , r2 , cas) ⊆ DR(d3 , r3 , cas))⇒ DR(d1 , r1 , cas) ⊆ DR(d3 , r3 , cas)
(反対称律)(DR(d1 , r1 , cas) ⊆ DR(d2 , r2 , cas))∧(DR(d2 , r2 , cas) ⊆ DR(d1 , r1 , cas))⇒ DR(d1 , r1 , cas) = DR(d2 , r2 , cas)

定義 5 (positive/negative/neutral) DR 領 域 が posi-tive(negative) と は そ の DR 領 域 が ア ク セ ス 許 可 (ア ク セ ス
拒 否) の 葉 で あ る か ，positive(negative) の 子 の 数 が ，negative(positive) の子の数より多いこととする．neutral とは positive の子の数と negative の子の数が等しいこととする．
■文書構造における冗長なラベル

文書構造における冗長なラベ

ルとは同じロールを代表対に持つ DR 束内の他の DR 領域から包摂されるラベルであり，以下で定義される．DR 束を親から順に冗長なラベルであるか判定し，もし冗長なラベルであれば自身に印をつける．

証明 4 cas が ‘d‘ の場合を示す．
定義 6 (文書構造における subsumed label) DR 束内におい(反射律)て自身のラベルが自身と同じロールを代表対に持ち，かつラベ同一の文書ノード間に有向路が存在すると考えられ，同一のロール間にも有向路が存在すると考えられる．よって定理 1
により式は成り立つ．

(推移律)

ルを持つ他の DR 領域集合から導出可能であるときに subsumed

label であるとし，導出は自身のラベルが存在しない場合に以下の導出アルゴリズム 1 により行われる．

前件より d2 から d1 への有向路が存在し，かつ d3 から d2

アルゴリズム 1 (導出アルゴリズム 1) 自身が代表対である DR

への有向路が存在する．すなわち d3 から d1 への有向路が領域にラベル付けされていれば，そのラベルの s 部に示されてい存在する．また r2 から r1 への有向路が存在し，かつ r3 かるアクセス権限判定を返せばよい．そのようなラベルが存在しな

ら r2 への有向路が存在する．すなわち r3 から r1 への有向

いとき，自身と同じロールを代表対に持ち，かつラベルを持つ最路が存在する．よって定理 1 により式は成り立つ．

も近い先祖 DR 領域のラベルによって以下のように導出する．

(反対称律)
前件より d2 から d1 への有向路が存在し，かつ d1 からd2 への有向路が存在する．また r2 から r1 への有向路が存在し，かつ r1 から r2 への有向路が存在する．よってDoS(d1 ) = DoS(d2 ) かつ DoS(r1 ) = DoS(r2 ) が成り立
つ．ゆえに DR 領域の定義より 2 つの DR 領域は等しい．

(+, +) のとき (+, +) が導出される．
(−, −) のとき (−, −) が導出される．
(+, −) のとき 自身と同じロールを代表対に持ち，かつラベルを持つ最も近い子孫 DR 領域集合のラベルに marker でな
い (+, ∗) が存在すれば，(+, −) が導出される．そのようなラベルが存在しなければ，(−, −) が導出される．

cas が ‘u‘ の場合も同様である．
■ラベルの追加設定 ある DR 領域に関して自身と同じ文書ノー
定義 4 (DR 束) 反射的包含関係，推移的包含関係を除いた包ドを代表対に持ち，かつ文書構造において冗長なラベルを持つ子含関係をもつ 2 つの DR 領域間に有向枝を張ることで構成する．

DR 領域を持つならば，自身のラベルの r 部に − を追加する．そうではないときに自身のラベルの r 部に + を追加する．

このとき有向枝の始点を親 DR 領域，終点を子 DR 領域という．

3.2

DR 束の構成と冗長性除去■ロール階層における冗長なラベル

ロール階層における冗長なラベルとは同じ文書ノードを代表対に持つ DR 束内の他の DR

次に DR 領域に対して以下の順でアクセス制御情報であるア領域から包摂されるラベルであり，以下で定義される．DR 束を

クセス制御ラベル (以下，単にラベルという) の設定と冗長なラ

親から順に冗長なラベルであるか判定し，もし冗長なラベルであベルの除去を行う．

れば除去する．

1. DR 領域に (s, d) という形式のラベルを設定する
2. 文書構造における冗長なラベルに印を付ける
3. ラベルに r 部を追加設定する．
4. ロール階層における冗長なラベルを除去する

定義 7 (ロール階層における subsumed label) DR 束内において自身のラベルがラベルを持つ親 DR 領域集合から導出可能
であるときに subsumed label であるとし，導出は自身のラベルが存在しないとして以下の導出アルゴリズム 2 により行われる．

■アクセス制御ラベルの設定

ラベルは (s, d) という形式で与え，設定方法は自身のアクセス制御情報がアクセス許可 (またはアルゴリズム 2 (導出アルゴリズム 2) 自身が代表対である DR

アクセス拒否) を与えられていれば s 部に +(-) を設定し，自身領域にラベル付けされていれば，そのラベルの s 部に示されてい3

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

論文

Journal of the DBSJ Vol.7, No.1

@
@ d0
@

d1

d2

d3

r0

×

○

○

×

r1

○

○

×

○

r2

×

×

○

×

r3

×

×

×

○

r4

×

×

×

×

¶XML 文書 (図 1) のロール階層 (図 2) における DR 束
s-d-

d0r0
s+d+

s+d+

d1r0
s+d+

d2r0

s-d-

s-d-

s-d-

s-d-

XML 文書木

RH

ロール階層

Lattice

DR 束

||

要素数

h

データ構造の高さ

s+d+

s-d-

d0r1

s+d+

d0r3

s-d-

s-d-

s-d-

d3r0

s+d+

s-d-

d1r4

s-d-

s+d+

s-d-

d2r4

d3r4

図 3 冗長性削除前
s-d-r+d0r0
s+d+r-

d1r0

s+d+r-

s+d+r-

s-d-r-

s+d+r-

d2r0 d0r1

s-d-r+

d0r2

s-d-r+

d0r3

s-d-r+

d2r1 d2r2
表2

s-d-

d0r2

d1r1 d1r2 d1r3 d2r1 d2r2 d2r3 d0r4 d3r1 d3r2 d3r3

表 1 Accessibility Map

DT

³

d0r4

s+d+r-

d3r3

コスト計算に使用する変数・関数
図 4 文書構造における冗長性削除後

s-d-r+るアクセス権限判定を返せばよい．そのようなラベルが存在しな

d0r0

いとき，自身と同じ文書ノードを代表対に持ち，かつラベルを持
つ親 DR 領域集合のうちラベルの r 部に + を持ち，かつ d 部に-

s+d+r-

d1r0を持つようなラベルが 1 つでも存在するとき，(−, −, +) を導出
し，そうではないとき (+, +, +) を導出する．

s+d+r-

s+d+r-

s+d+r-

d2r0 d0r1 d3r3

s+d+r-

d2r2

s-d-r-d2r1

例 1 (DR 束) XML 文書木 (図 1)，ロール階層 (図 2) に対して DR 束を構成する．アクセス権限設定が表 1 で与えられているときに，得られる DR 束が図 3 である．ここから文書構造に

図 5 冗長性削除後µ´

おいて冗長なラベルを削除しラベルに r 部を追加したものが図 4である．そこからさらにロール階層における冗長なラベルを削除したものが図 5 である．ここではラベルを持つ DR 領域のみを描いている．

4.

アクセス権限判定および更新における操作

アクセス権限判定および更新操作とその時間コストについて述べる．また考察する更新は以下に挙げた操作である．

(アクセス権限変更) 文書ノードとロールの対に設定されている
アクセス権限情報を変更する．

(文書ノード/ロールの追加) 新しく追加された文書ノード (ロール) におけるアクセス権限設定は追加先の祖先ノード (ロール) に設定されたアクセス権限判定ルールに従う．
(文書ノード/ロールの削除) 削除対象の文書ノード (ロール) がXML 文書木 (ロール階層) において子を持つ場合，子を文書ノード (ロール) の親の子として引き上げるような削除を
行う．

4.1

提案手法における各操作と時間コスト

アクセス権限判定は以下の権限判定アルゴリズムを用いて行う．
アルゴリズム 3 (権限判定アルゴリズム) (a) 自身が代表対である Dr 領域にラベルが設定されていれば，ラベルの s 部に設定されているアクセス制御情報を用いて判定する．(a) ではなく (b)同じ文書ノードを代表対に持つ親 DR 領域集合から導出アルゴリ
ズム 2 を用いてラベルを導出できれば，導出して判定する．(a)(b) のいずれでもなければ，同じロールを代表対に持つ親 DR 領域についてラベルが導出できるまで同様のことを繰り返す．導出されたラベルから導出アルゴリズム 1 を用いて自身のラベルを導出する．
定理 3 (提案手法における時間コスト) 提案における時間コストは表 3 で示される．
証明 5 提 案 手 法 に 関 し て 格 納 さ れ て い る ラ ベ ル の 数 は |また操作のコストを評価するために表 2 に用意した変数，関数をLattice | であるため，1 回の問い合わせにつき log(| Lattice |)用いる．また提案手法における要素数はラベル数とする．

の時間コストが生じる．

4

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

論文

Journal of the DBSJ Vol.7, No.1
時間コスト

24000

権限判定

O((h(DT ) × RH) × log(| Lattice |))22000

アクセス権限変更

O(log(| Lattice |))20000

文書ノード追加
文書ノード削除O(1)O(| RH | ×log(| Lattice |))

ロール追加

O(1)

ロール削除

O(| DT | ×log(| Lattice |))表3label count操作

existing
proposal

18000
16000
14000
12000
10000
8000
6000

提案手法における時間コスト0(権限判定) 権限判定アルゴリズムの適用に必要な親 DR 領域集

20
40
60
80
accessible node / all node [%]100

図 6 ランダムに設定した場合合を得るために，最悪の場合権限判定対象の文書ノードのXML 文書木における先祖集合とロールのロール階層における可達集合の直積集合の回数の問い合わせが生じるが，得られた段階で探索は終了する．

(アクセス権限変更) ラベルが存在すれば書き換え，存在しなければ追加するため問い合わせは 1 回生じる．
(文書ノード追加) ラベルに対する処理はない．
(文書ノード削除) 各ロールを順にラベルが存在するか参照していくためロールの数だけ問い合わせと削除が生じる．

5.3

アクセス権限情報の付与

文書ノードとロールの全ての対に対してアクセス権限情報を設
定を以下のように行う．まず局所性を持ちうる領域の指定としてXML 文書内の文書ノード d とロール階層内のロール r を乱数により選び，DoS(d) × DoS(r) に含まれる文書ノードとロールの対各々に対して次のように行う．確率 ps (選択確率とする) に(ロール追加) ラベルに対する処理はない．
(ロール削除) 各文書ノードを順にラベルが存在するか参照してよりアクセス制御情報の設定を文書ノードとロールの対ごとに独いくため文書ノードの数だけ問い合わせと削除が生じる．

るか決定する．文書ノードとロールの対ごとに独立に設定する場

立に設定するか，または親のアクセス制御情報を考慮して設定す合，確率 pr (許可確率とする) に従ってアクセス許可/アクセス拒

5.

更新操作の定量的評価

アクセス権限設定である Accessibility Map(AM)[1] とそれを圧縮した Compressed Accessibility Map(CAM)[1] と提案手法

否を設定する．また親のアクセス制御情報を考慮して設定する場
合，確率 pl (局所性確率とする) に従って親のアクセス権限情報を考慮してアクセス権限情報を設定する．これを全ての文書ノードとロールの対に対して設定されるまで繰り返す．

に関して XML 文書とロール階層を処理する計算機実験により，

今回選択確率を文書ノードとロールの対ごとに独立に設定する

各手法に基づいたルール簡略化後に権限判定および更新操作をそことを選択する確率とし，許可確率をランダムに設定する際にア

れぞれ 30 回ずつ行い，それぞれの処理時間の平均値を得た．実

クセス許可である確率とし，局所性確率を親のアクセス制御情報

験で用いた XML 文書の文書ノード数は 500 個，ロール数は 100と等しい確率として，それぞれの確率について 10%〜90% の 9個である．

段階となるように設定した．それゆえそれぞれの確率の大小によ5.1

り次のようになる．選択確率が小さいほど文書ノードとロールの実験環境

Pentium 4 CPU 3.20GHz, 3.21GHz, 2.00GB RAM のPC，OS は Microsoft Windows XP，実行プログラムは Java，DBMS は MySQL 5.0 を使用した．

対ごとに独立に設定し，大きいほど親のアクセス制御情報を考慮

5.2

アクセス制御情報と異なる設定をし，大きいほど親のアクセス制

実験用 XML 文書，ロール階層の生成

文書ノードとロール階層の対に対してアクセス権限情報を設定するために，文書ノードおよびロールを ID で管理できるように
データベースに格納する．XML 文書における木構造は，求めるして設定する．許可確率が小さいほどアクセス拒否を設定し，大きいほどアクセス許可を設定する．局所性確率が小さいほど親の御情報と等しい設定をする．

5.4

構成とルール削減数の評価

まず文書ノードとロールの対ごとに独立にアクセス制御情報をノード数に達するまで木に乱数で得られた ID を持つ文書ノード

設定した場合 (ps = 90%, pl = 50%) について行った結果が図 6の葉として次々と追加することで生成した．またロール階層におである．大きな差は見られないが，提案手法のほうが CAM からける非巡回有向グラフは求めるノード数で連結になるまで無向枝

さらに圧縮を行う手法のため常にラベル数を下回っている．

を追加し，乱数により source を定め，そこから枝をたどる際に一方，局所性を持たせてアクセス制御情報を設定した場合有向枝に変えることで生成した．このようにして生成した文書木(ps = 10%, pr = 50%) について行った結果が図 7 である．

の子の数は平均 12 個，ロール階層の子の数は平均 3 個となった．

5.5

XML 文書，ロール階層をともにグラフの隣接リストモデルを用
いてデータベースに格納した．

5

各操作の実行時間

各手法で構成されたものそれぞれに対して乱数により選んだ対象に更新操作を行い，その平均所要時間で比較する．また比較の日本データベース学会論文誌 Vol.7, No.1

論文

Journal of the DBSJ Vol.7, No.1
セス制御ルールであるアクセス制御ラベルを設定し冗長性の除去

22800
existing
proposal

22600を行った結果，ルール数削減効率と更新操作の効率に関して提案

label count22400

手法の優位性を実験により確認した．しかし，アクセス権限判定

22200にかかる時間が増大したために，それに伴ってアクセス権限変更

22000の効率は悪くなった点は改良の余地を残しているといえる．

21800
21600

今後の方針として提案手法を大規模な XML 文書木，大規模な

21400

ロール階層に適用した場合のスケーラビリティに関する調査を予21200定している．提案手法の優位性を顕著にし，また権限判定を高速

21000
0

20

40
60
local strength

80

100

たな探索アルゴリズムや格納方式の開発の予定である．

[謝辞]

図 7 局所性を持たせた場合

PP
手法
PP
AM
PP
操作
PP

本研究の一部は，平成１９年度科研費基盤研究 (B)(課題番号

CAM

提案手法

0.25

3.66

10.91

アクセス権限変更

0.02

0.58

0.66

文書ノードの追加

3.66

処理が不要

処理が不要

文書ノードの削除

29.83

12.58

11.91

ロールの追加547.16135.00452.83
51.58

処理が不要

表4

18300031), および科学技術振興機構 戦略的国際科学技術協力推進事業 「アイデンティティ連携におけるリスクを考慮した個人

アクセス権限判定

ロールの削除化するため，新たな冗長性削除ルールを開発し，それとともに新51.16

更新操作の所要時間 [ms]ために AM に対しても同様の更新操作を行った．表 4 がその結果である．

(アクセス権限判定) 提案手法は探索すべき範囲が CAM に比べて大きいため，差が生じている．

(アクセス権限判定) アクセス権限判定した後に変更を行うため，先ほど述べた判定に必要な時間の影響が強くなっている．

(文書ノードの追加) 圧縮を行う手法では共通して何も行わない
ので，所要時間は発生しない．

(文書ノードの削除) AM および CAM では参照すべきノード

情報共有方式」による．

[文献][1] T.Yu,D.Srivastava,
L.V.S.Lakshmanan,
and
H.V.Jagadish, ”A Compressed Accessibility Map
for XML”, ACM Transactions on Database Systems,
Vol. 29, No. 2, June 2004, Pages 1-38.
[2] M.Jiang and A.Wai-Chee Fu, ”Integration and Eﬃcient
Lookup of Compressed XML Accessibility Maps”, IEEE
Transactions on Knowledge and Data Engineering, Vol.
17, No. 7, July 2005.
[3] M.Iwaihara, B.Wang, and S.Chatvichienchai, ”Extracting Global Policies for Eﬃcient Acess Control of XML
Documents”, WISE 2005, LNCS 3806, pp. 161-174,2005[4] D.F.Ferraiolo, R.Sandhu, S.Gavrila, D.Richard Kuhn,
and R.Chandramouli,
Proposed NIST Standard forRole-Based Access Control , ACM Transactions on Information and System Security, Vol. 4, No. 3, August
2001, Pages 224-274.

数が多いため，処理にかかる時間が提案手法より必要となっ牛場 祐貴 Yuki USHIBAている．

京都大学大学院情報学研究科修士課程在学中．京都大学工学部情(ロールの追加) AM または CAM では新しくアクセス制御情報学科卒業．日本データベース学会学生会員

報を構成する必要があるのに対し，提案手法では処理を行わ

岩井原 瑞穂 Mizuho IWAIHARA

ないため差が生じている．

京都大学大学院情報学研究科准教授．1993 年九大工学研究科情(ロールの削除) AM および CAM では参照すべきノード数が多いため，処理にかかる時間が提案手法より必要となっている．

報学専攻博士後期課程修了．工学博士．日本データベース学会,
情報処理学会，電子情報通信学会，ACM, IEEE 各会員．

吉川 正俊 Masatoshi YOSHIKAWA
京都大学大学院情報学研究科教授．1985 年京都大学大学院工学

6.

おわりに

研究科博士後期課程修了．工学博士．電子情報通信学会．ACM，

IEEE Computer Society 各会員．日本データベース学会理事．

XML 文書のアクセス制御において，ロールベースドアクセス
制御を取り入れ，ロール階層を導入することで，DR 領域という文書ノードとロールの対の集合を定義し，DR 領域に対してアク6

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