一般論文

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

履歴追跡型データモデルの評価

野ではログを用いて人や物を追跡することが求められてい

Evaluation of History Traceable Data
Modelによるログ管理では，項目によって構成された表を単位としる．しかしながら従来のRDBMSに代表されるデータベースてログを管理し，項目間および表間の関係を管理するものであるため，列間または表間の関係性にもとづくログ解析には

平井 規郎 ♥
郡 光則 ♠

森山 令子 ♦

Norio HIRAI Ryoko MORIYAMA
Mitsunori KORI

優れているが，前後関係などの行間に存在する関係性を必要とする追跡などのログ解析は困難であった．そこでログを用いて対象を追跡するためにはログに含まれる関係性を管理するのに適したデータモデルを定義する必要がある．本報告では，上記データモデル（以下履歴追跡型データモデル）の定義について述べるとともに，本定義モデルを実装し評価した結果を示す．

近年多種多様な形式をもつ膨大なログがシステムから収集蓄積されるようになり，これらのログをただ蓄積するだけでなく，活2. 先行研究用することが要求されている．従来ログの活用方法としては集収集・蓄積されるログの量が増大するにつれてログの処理計などのように全体の傾向に着目するマクロな視点にもとづい時間も膨大になり，その結果ログは蓄積するのみで利活用がた方法が提案されてきた．しかしこの方法では追跡のようにすすまないという状況があった．これに対して我々は，多様個々の人や物の動きに着目したミクロな視点での活用が困難でなログへの対応，高速蓄積・検索，ストレージ容量削減を目あった．本報告では，ログに含まれる対象の前後関係を整理し的として，大規模ログデータベースの開発をおこなってきたて管理することにより追跡を可能にする履歴追跡型データモデ（文献[1],[2]）．その結果処理性能の向上により，従来困ルを提案する．また提案手法を実装し，履歴追跡型データモデ難であった大量のログに対する集計・検索処理が可能になっルの有効性および追跡効率を評価した結果について報告する．

た．一方ビル管理，製造およびセキュリティなどの分野では，従来の集計処理以外に，個々の人や物などを対象とする追跡In late years , enormous log with various forms comes toなどの分析ニーズが高まってきた．そこで我々は大規模ログ

be collected and accumulated by various systems, andデータベースを基盤として追跡を可能にするデータベース

what we utilize these log is demanded. Previouslyの研究に取り組んでいる．たとえば操作ログによる人の行動

various methods have been suggested those command

履歴の分析では，ユーザが操作したアプリケーションの時刻

total tendency based on the macro viewpoint. However,と位置情報を分類してユーザ操作をモデル化して分析する

these methods were inappropriate to utilize logs basedなどの研究があるが（文献[3]），全体としての人の行動傾

on the micro viewpoint such as trace of history for each

向を把握するものであって，個々の動きを対象とした分析でperson or object. In this paper, we propose a History

はない．トレーサビリティの観点では情報変化過程のトレー

Traceable Data Model to enable a trace by managing the

サビリティに関するデータモデルの研究（文献[4]）がある．

context of objects included in logs. And we report to

この方法は情報の時系列変化を情報の変化差分に着目してevaluate effectiveness and efficiency of this data model.

モデル化したものであり，機器情報のトレースに有効である．
しかし，一般的なログではなく数値データを対象としている

1. はじめに点で課題がある．また分散する複数のデータソースにまたが近年ストレージコストの低価格化および容量の増大を背って保持されるデータに対してトレーサビリティを実現す景として，収集蓄積されるログの爆発的な増加や多様化に伴るシステムに関する研究（文献[5]）では，統一的な検索手い，これらのログから有用な情報を抽出し，現象の分析や原段を基盤とするトレーサビリティシステムの手法が提案さ因の特定に活用することが求められている．特に，セキュリれているが，データモデルの一般化に課題がある．

ティ，ビル／設備管理および製造トレーサビリティなどの分

3. 履歴追跡型データモデル提案♥

正会員 （株）三菱電機 情報技術総合研究
所 Hirai.Norio@dx.MitsubishiElectric.co.jp♦
正会員 （株）三菱電機 情報技術総合研究
所Moriyama.Ryoko@dr.MitsubishiElectric.co.jp♠
非会員 （株）三菱電機 情報技術総合研究
所 Kori.Mitsunori@ab.MitsubishiElectric.co.jp

本章では，まず本研究において使用する用語を定義し，次に我々が提案する履歴追跡型データモデル（文献[6],[7]）の定義について述べる．

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

一般論文

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

3.1 用語の定義ればならない．図 1 では「入室」，「退室」がイベントに該

図1はあるユーザ（識別ID=A）の入退室管理装置に記録さ当する．

れたログを関係データモデルおよび履歴追跡型データモデ
ルで管理した場合のイメージ図である．図1をもとにそれぞれの用語について定義する．

3.2 履歴追跡型データモデル定義
履歴追跡型データモデルとはイベントの発生前後における追跡対象の状態変化を対象ごとに整理して管理するためのデータモデルである．我々は追跡対象とイベントの関係構

関係データモデル
日付時刻

ユーザ

イベント

扉

7/31 08:05

A

入室

扉1

7/31 08:07

A

入室

扉2

7/31 11:00

A

退室

扉2

7/31 11:05

A

退室

扉1

造を検討した結果，データモデルを定義する上で必要な関係構造は 3 つに分類できると考える．以下に履歴追跡型データモデルの定義に必要な 3 つの関係構造について説明する．

3.2.1 順序関係構造
順序関係構造とは１つの追跡対象の状態をイベントによって関係付ける１対１の写像関係である．この写像関係はイ履歴追跡型データモデル

ベントの発生前後の状態を関係付ける写像関係であり，イベントの発生によって状態は遷移する．この状態とイベントのユーザクラス

写像関係はグラフで表現することが可能である．図 2 におい

A入室

入室

退室

退室て x0，x1，x2 はインスタンス X の状態を表す．f1 は状態 x0を x1 に遷移させるイベント，f2 は状態 x1 を x2 に遷移させるイベントである．図 2 の上図は写像関係で表現したもので下扉クラス

図はグラフで表現したものである．

扉1退室

入室

3.2.2 階層関係構造
階層関係構造とはあるクラスに属するインスタンスが同

扉2
入室

退室

じクラスに属する異なるインスタンスを生成するようなイベントによって関係付けられる１対多または多対１の親子関係である．たとえばファイルをコピーした場合は１つのフ

図1
Fig.1

用語定義

Term Definition

3.1.1 クラス

ァイルから複数のファイルが生成され，親子関係が発生する．
またメールをリプライした場合はリプライによって元のメールとの間に親子関係が発生する．このように親子関係を発生させるイベントによって関係付けられる状態間の写像関追跡対象が属するカテゴリを表し，関係データモデルにお係を階層関係と定義する．なお，異なるクラスに属するインける項目に対応する．個々のクラスは全体において一意に識スタンスを生成するイベントは考慮しないものとする．図 3

別可能なクラス ID をもつ．図 1 では「ユーザ」および「扉」

において x0，x1 はインスタンス X の状態，y1 はインスタンスY の状態である．X,Y はともに同一クラスに属するインスタンスである．またイベント f1 は X が Y を生成する階層関係のイベントであり，このイベントにより x0 から x1 および y1がクラスに該当する．

3.1.2 インスタンス
追跡対象の実体を表し，クラス内で一意に識別可能な IDに同時に遷移する．

をもつ．したがって，クラスの ID とインスタンス ID で追跡対象は全体において一意に識別できなければならない．図
1 では「A」「扉 1」「扉 2」がインスタンスに該当する．

3.2.3 クラス間関係構造
クラス間関係構造とは，異なるクラスに属するインスタンス間を関係付ける写像関係である．たとえばある時刻に記録

3.1.3 イベントされた 1 つの入退室ログにはユーザが扉を通過したことが記

入室，退室，ログインなど人や物の動作を表し，全体にお録されている．この場合，履歴追跡型データモデルではユーいて一意に識別可能なイベント ID をもつ．インスタンスはザと扉の間の関係をクラス間関係構造として定義する．クライベントの前後で状態が遷移する．イベントは特殊なクラス

ス間関係構造は RDBMS などで定義される項目間の関係とであり，履歴追跡型データモデルでは必ず定義されていなけ同等であり，1 つのログに複数のクラスが含まれる場合にそ

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

一般論文

DBSJ Journal, Vol.7, No.3
December 2008のクラスに属するインスタンス間はすべてクラス間関係構造によって関係付けられる． 図 4 において x0,x1,x2 はクラx0クラスⅠx1スⅠに属するインスタンス X の状態を表し，y0,y1,y2 はクラスⅡに属するインスタンス Y の状態を表す．イベント f1 はx0 と x1 の状態を関係づける写像関係であるとともに x0 と y1の状態を関係づける写像関係でもある．このような関係構造をもつ図 4 の鎖線で表した関係がクラス間関係構造である．

イベント発生前y1の状態

f1

x0

x0

x1

f2

x1

g2

y2

f1

x1

f2

y1 g2

図4

クラス間関係構造

x2
y2x2

f2x1x

図2

f1

y0 g1

Fig.4

Fig.2

y1

イベント発生後の状態

x0xx2

f2
g1

y0
クラスⅡx1

f1x2xClass Relation Structure

4. 実装
評価を目的として前章で定義した履歴追跡型デー
タモデルを実装した．

順序関係構造Ordered Relation Structure

4.1 履歴追跡型ログDBデータ構造
履歴追跡型ログDBは，ログから前章で定義した3つの関係構造を抽出し，対象ごとの関係を管理することにより効率的
イベント発生後の状態

イベント発生前の状態

x0x1

f1y1な追跡を可能にするためのインデックス（以下挙動インデックス）をメモリ上に生成する．挙動インデックスはログから3つの関係構造を抽出しグラフ構造として管理する．履歴追跡型データモデルを実現する挙動インデックスのデータ構
造図を図5に示す．挙動インデックスが管理する主なデータ構造としては，クラス情報構造体，インスタンス情報構造体，階層情報構造体，順序履歴情報構造体がある．クラス情報はインスタンス情報を管理する．階層情報および順序履歴情報

x0f1

x1y1は個々のインスタンスによって管理される．階層情報は階層関係を発生させたイベント，子のインスタンスおよび対応する順序履歴へのポインタを管理する（図5の点線）．順序履
歴は属するインスタンスで発生したイベントの発生順に格図3Fig.3

階層関係構造Hierarchical Relation Structure納され，前後関係のポインタとともに管理される．クラス間関係構造は異なるクラス間に属する順序履歴同士を関係づけるポインタとして管理される（図5の鎖線）．

4.2 履歴追跡型ログDBシステム構成
履歴追跡型ログDBは，履歴追跡型データモデルを実現する挙動インデックスを生成管理する管理部，追跡処理を実行する実行部および追跡結果をグラフ表現で表示する結果表示部から構成される．履歴追跡型ログDBとして実装したシステム構成図を図6に示す．図6の標準形式データとは挙動イ

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

一般論文

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

ンデックス生成のためにログを共通の形式に変換したデータである．
クラス情報

クラス
情報のデータに対して評価した結果について述べる．
①

シミュレーションデータ

②

メール送受信履歴

5.1.1 シミュレーションデータによる評価
定義した3つの関係構造をもつ単純な評価用シミュレーシ

インスタン
ス情報

インスタンス情報
情報

インスタンス情報情報ョンデータを生成し適用した．以下に生成したデータのデー
タモデル図を示す．なおクラスは2つあり，個々のクラスには2つのインスタンスが存在する．クラス1では階層関係イベントによってインスタンス1がインスタンス2を生成する．

階層順序

階層

図5
Fig.5

階層順序

順序

インスタンス 1
クラス 1

実装データ構造

インスタンス 2

Implement Data Structure
結果表示部
クラス 2

インスタンス A
インスタンス B

図7
管理部

Fig.7

実行部

評価用シミュレーションデータ
Simulation Data for Evaluation

追跡結果１
クラス1に属するインスタンス1を追跡した結果を図8に示
ログ

標準形式
データ

挙動インデックス

す．図8よりクラス1の順序関係構造および階層関係構造を管理することにより追跡可能であることがわかる．

履歴追跡型ログ DB

図6
Fig.6

履歴追跡型ログ DB システム構成図

System Composition of Traceable LogDB

5. 評価実験
本研究の目的は定義した履歴追跡型データモデルがログ情報の追跡に有効であること，および一定の追跡性能を満たすことを確認することにある．プロトタイプであるため，必ずしもメモリ性能および処理性能は最適化されていないが，評価した結果について以下に述べる．

5.1 モデルの有効性評価
本研究で定義した履歴追跡型データモデルの有効性評価

図8Fig.8

階層関係追跡結果

Result of Trace for Hierarchical Relation

追跡結果2
クラス間関係構造を用いてクラス1に属するインスタンス1の動きと関係するクラス2のインスタンスを追跡した結果を図9に示す．図9よりクラス1に属するインスタンス1の関係をたどることによりクラス2に属するインスタンスAとインスタンスBの追跡が可能であることがわかる．の目的は3章で定義した順序関係構造，階層関係構造，クラス間関係構造から構成される履歴追跡型データモデルにもとづきログを管理することにより，すべての情報の追跡が可

図9

能であるかどうかを検証することにある．そこで，本研究では生成した実験データおよび実データを適用しモデルの有Fig.9

クラス間関係追跡結果

Result of Trace for Class Relation

効性評価を行った．本稿では適用したデータから以下の２つ

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

一般論文

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

5.1.2 メール送受信ログによる評価実験結果

実装したシステムに実際のメール送受信ログを適用してメール送受信ログとはメールのヘッダ情報である．メール追跡した結果，すべてのメールおよびユーザについて追跡が送受信ログ追跡ではヘッダ情報に含まれる時刻，送受信アド可能であることを確認した．図11にあるメールの配信経路をレス（From, To, Ccなど），メッセージID（メールを一意追跡した結果例を示す．に識別するID），In-Reply-To（返信の親メールのメッセージID）等の情報から関係構造をもつ挙動インデックスを生成管理する．メール送受信ログのデータモデルはユーザクラスとメッセージIDクラスの２つのクラスをもつ．メール送受信
ログ追跡では以下の追跡を行い評価した．
■

メール配信経路の追跡■

ユーザ送受信履歴の追跡

メール送受信ログにおけるデータモデル図の例を以下に簡単に示す．図10は，たとえば２人のユーザAおよびユーザBの間でのみ発生したメールのやりとりを履歴追跡型データモデルで表現したものである．

図 11

メールの配信経路の追跡を関係データモデルにより追跡

Fig.11する場合には，以下の①～⑤の処理を返信回数分繰り返す．
①

追跡対象メッセージIDを指定②

指定したメッセージの受信者を取得③

指定したメッセージIDを親に持つ子メッセージIDを取得④

子メッセージIDを受信したユーザを取得⑤

親メッセージID受信者と子メッセージID受信者の関係を生成

これに対して履歴追跡型データモデルでは，ユーザの履歴とメッセージIDの履歴の他にクラス間関係構造でメッセー

実メール送受信ログ追跡結果例
Result of Mail Trace

5.2 性能評価実験
本節では性能評価の結果について述べる．本報告における性能評価の目的は，我々が定義した履歴追跡型データモデルに実際のログを適用し，対象の追跡を実時間内に処理することが可能かどうかを確認することである．そこで実装したシステムに実際のメールヘッダ情報から生成したメール送受信ログを適用し，追跡性能を評価した．
本評価で用いた性能評価環境を表1に示す．

ジIDとユーザが図10のように関係付けられているため，追跡対象となるメッセージIDを1度指定すれば関係構造をたどることですべての配信経路を取得することが可能である．

メッセージ ID クラス

Table 1表 1 性能評価環境
Performance Evaluation Environment

OSMicrosoft(R) WindowsXP
Service Pack3

CPUメモリHDD

Intel(R) Core(TM)2
1.98GB RAM
149GB

性能評価結果実際のメール送受信ログを適用し，評価した結果について示す．

ユーザクラス

モデルの有効性評価でも述べたように関係データモデル
によるメール配信経路の追跡では，返信が発生したかどうかを確認するために，すべてのメッセージについて親子関係があるかどうかを調べる必要があり，計算量が膨大である．さらに取得したメッセージIDをもとに関係する送受信者を取得し，関係を生成するなどの処理も含めると追跡処理には不

図 10

メール送受信ログデータモデル

Fig.10

Data Model of Mail Log

向きである．一方履歴追跡型データモデルではメッセージID間の親子関係，およびメッセージIDとユーザの関係をデータ

日本データベース学会論文誌 Vol.7, No.3
2008 年 12 月一般論文

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

モデルとして管理しているため，効率よく追跡することが可[文献］

能である．そこで入手可能なメールログを対象として測定し[1]竹内 丈志，山岸 義徳，中村 隆顕，郡 光則：“大規模ログデータベースの評価”，IPSJ68回全国大会講演論
文集，ID-1，2006．
[2]中村 隆顕，山岸 義徳，竹内 丈志，郡 光則：“大規模ログデータベースの実現”，IPSJ68回全国大会講演論
文集，ID-2，2006．
[3]松本 光弘，清原 良三，福井 秀徳，沼尾 正行，栗原 聡：“携帯端末による人物行動履歴の分析に関する一考察”，第21回人工知能学会全国大会講演論文集，2F3-3，2007．
[4]大木 康幸，有澤 博：“ユビキタス環境における情報変化過程のトレーサビリティのためのデータベースモデル”，DEWS2005．
[5]百合山 まどか，小金山 美賀，渡邊 裕治，北山 文彦，沼尾 雅之：“疎結合な関係にある企業間のトレーサビリティシステムの提案”，DEWS2006．
[6]平井 規郎，森山 令子，郡 光則：“履歴追跡に適応するデータモデルの検討”，IPSJ70回全国大会講演論文集，
3B-6，2007．
[7]森山 令子，郡 光則，平井 規郎：“履歴追跡結果の表示方式の検討”，IPSJ70回全国大会講演論文集,3B-7，2007．

た結果，メッセージ数またはユーザ数に依存することなく同等の測定結果が得られた．メール配信経路の取得について測定した結果を表2に示す．
表 2 メール配信経路取得時間
Table 2 Mail Trace Time
返信数

計測時間（ミリ秒）

23458102245556. 考察
モデルの有効性評価では，メール送受信ログをはじめとしていくつかの実データを適用し追跡した結果，我々の定義した3つの関係構造をもつ履歴追跡型データモデルによりすべての対象に対して追跡可能であることを確認した．また性能評価では表2からわかるように，従来のデータモデルでは非効率的な処理であったメール配信経路の取得を効率よく実時間内で処理することが可能であることを確認した．

7. まとめと今後の課題
本研究ではまず対象の追跡を可能にするためにログのもつ情報からイベントと対象の関係構造を定義し，これらの関係構造によって構成されるデータモデルを履歴追跡型データモデルとして定義した．次に定義した履歴追跡型データモ
デルを実装し，モデルの有効性および性能について評価を実施した．その結果以下の結論を得た．


順序履歴および階層履歴についてイベントの発生順または逆順に追跡することが可能

追跡対象と関係する異なるクラスの追跡が可能



従来は困難であった追跡処理を実時間内で処理するこ平井 規郎 Norio HIRAI
三菱電機株式会社 情報技術総合研究所勤務．1991 年東京工業大学大学院理工学研究科修士課程終了．データベースシステム等の研究・開発に従事．

森山 令子 Ryoko MORIYAMA
三菱電機株式会社 情報技術総合研究所勤務．1987 早稲田大学理工学部卒業．データベースシステム等の研究・開発に従事．

郡 光則 Mitsunori KORI
三菱電機株式会社 情報技術総合研究所勤務．1986 年東京大学大学院工学系研究科修士課程修了．並列処理，情報検索等の研究開発に従事．とが可能
今後は性能向上とともに，履歴追跡型ログDBにおける検索についてクエリ言語を含めた検索方式の検討をすすめていく．

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