DEIM Forum 2019 H4-3

シーケンス OLAP のための複数行パターンマッチング問合せ処理
那須 勇弥†

中挾 晃介††

北川博之†††† 筑波大学大学院システム情報工学研究科 〒 305–8573 茨城県つくば市天王台 1-1-1†† 公益財団法人鉄道総合技術研究所 〒 185–8540 東京都国分寺市光町 2-8-38††† 筑波大学計算科学研究センター 〒 305–8573 茨城県つくば市天王台 1-1-1
E-mail: †yuuya.n@kde.cs.tsukuba.ac.jp, ††nakabasami.kosuke.39@rtri.or.jp, †††kitagawa@cs.tsukuba.ac.jp
あらまし

シーケンス OLAP は，シーケンスデータ上の特定のパターンの出現箇所 (パターンオカレンス) を抽出

し，集約次元の粒度を切換える drill-down・roll-up などの OLAP 演算や，パターンを切換える pattern-drill-down・

pattern-roll-up などの OLAP-Pattern 演算を使用して多次元集約を実行する集約分析技術である．最も汎用的な DBの 1 つである RDB 上でシーケンス OLAP の OLAP-Pattern 演算を効率的に処理するためには，異なる複数のパターンについての行パターンマッチング結果をあらかじめ抽出しておく必要がある．一般に，このような複数パターンの
行パターンマッチングはそれぞれ個別に実行されるが，それらのパターン同士が共通部分を持つ場合に冗長な処理が発生する．そこで，RDB 上でシーケンス OLAP の OLAP-Pattern 演算をサポートするために，複数行パターンマッ
チングとパターンオカレンスの親子関係検出を効率的に処理するパターン階層モデルと問合せ処理手法を提案する．
さらに，RDB の UDF として提案手法を実装し，人工データを用いた実験で提案手法の性能の検証を行う．
キーワード 時系列データ処理，SQL/RPR，OLAP

1 はじめにンマッチング問合せ処理手法を提案する．提案手法では，拡張
前のパターンを親，拡張後のパターンを子とするパターンの階

近年，IoT やソーシャルメディアの普及に伴い，多種多様な層構造を定義し，複数パターンを統合した NFA によって複数データが生成されデータベースに蓄積されている．特に，RFID

パターンの行パターンマッチングを実行する．さらに，パターによる移動ログデータや株取引データなど，特定の順序に従っ

ンオカレンス抽出時に逐次的にパターンオカレンス間の親子関て生成されるデータをシーケンスデータと呼ぶ．そのような係を検出する．提案手法によって，複数パターンの行パターン

シーケンスデータに対して，データの並びのパターンを照合し，マッチングとパターンオカレンス間の親子関係検出を効率的に特定パターンの発生箇所 (パターンオカレンス) を抽出・集約す

実行することができる．本研究では，RDB の UDF(ユーザー

る分析技術が求められている．

定義関数) として提案手法を実装し，人工データを用いた実験

データベースに蓄積されたシーケンスデータに対するパターで提案手法の性能の検証を行う．

ンオカレンスの集約分析手法としてシーケンス OLAP が知られている．シーケンス OLAP はシーケンスデータからパターンオカレンスを抽出し，データの次元の階層構造に基づい

2 シーケンス OLAPて集約条件を変更する drill-down や roll-up などの OLAP 演

シーケンス OLAP はデータベースに蓄積されたシーケンス

算を実行することで多次元集約分析を行うことができる．まデータに対するパターンオカレンスの集約分析手法である．本た，シーケンス OLAP 分析では集約結果を取得後，現在のパ研究では，最も汎用的なデータベースの 1 つである RDB に蓄積

ターンとは異なるパターンの集約結果を確認したいという要

されたシーケンスデータを処理対象として考える．シーケンス

求がある．このような要求に対して，シーケンス OLAP では

OLAP はシーケンスデータからパターンオカレンスを抽出し，pattern-drill-down や pattern-roll-up などの集約対象パターン

データの次元の階層構造に基づいて集約条件を変更する OLAP

を切換える OLAP-Pattern 演算を実行することで，異なるパ演算を活用して多次元集約分析を実行する．シーケンス OLAP

ターンの集約結果を取得することができる．OLAP-Pattern 演に関わる表の例を図 1 に示す．シーケンス表には，パーソン

算を実行するためには，複数のパターンについてパターンマッ

トリップデータとして sid(シーケンス ID)，city，venue，time

チングを行い，それらのパターンオカレンス間の親子関係を検を持つタプルが格納されている．シーケンス OLAP ではまず，出する必要がある．一般に，このような複数パターンのパター

シーケンスデータに対してパターンを指定して行パターンマッ

ンマッチングはそれぞれ個別に実行されるが，それらのパター

チングを行い，パターンオカレンスを抽出する。パターンは (X

ン同士が共通部分を持つ場合に冗長な処理が発生する．

Y) などのいくつかの変数 (パターン変数と呼ぶ) の並びで表現

そこで本研究では，最も汎用的なデータベースの 1 つであされる．また，パターンで指定されている各パターン変数に対る RDB(関係データベース) 上でのシーケンス OLAP におけして条件を指定することができる．例えば，X.venue=Airport，

る OLAP-Pattern 演算をサポートするために，複数行パター

Y.venue=Airport の条件を指定したパターン (X Y) は Airport

図 1: シーケンス OLAP で用いる表から Airport への移動パターンを表す．このパターンについて

W Y) → (X Y) のように子パターンから親パターンに切換える

行パターンマッチングが実行されると図 1 のパターンオカレン

演算を pattern-roll-up と呼ぶ．

ス表が出力される．

さらに，シーケンス OLAP ではパターンを切換えるだけで次に，出力されたパターンオカレンス表に対して集約処理がはなく，特定のパターンオカレンスについて異なるパターンに実行される． シーケンス OLAP の集約分析の結果は，図 2 における詳細な分析を行いたいという要求がある．例えば，図 3

示すようなデータキューブで表現することができる．図 2 のに示すようにパターン (X Y) について集約結果を確認した後左のキューブは (X city，Y city，travel hour) の属性値によるに，New York の Airport から New York の Airport へ移動しカウントのクロス集計結果を示している．このような集約結

たパターンオカレンスについて，その間に通過した会場 W を分果に対して，次元表を結合することによって集約の粒度を変更

析するというシナリオを考える．このような要求に応えるためする OLAP 演算 (roll-up，drill-down) を実行することが可能には，パターン (X W Y) のパターンオカレンスの中から条件となる． 例えば，図 1 のパターンオカレンス表の X city と次に合致するもの ({X city, Y city}=New York) のみを抽出する

元表の city を結合することで，同じ region の属性値を持つ集必要がある．図 3 の右側の表からは，New York の Airport か

約結果をまとめることができる．このような集約の粒度を粗ら New York の Airport へ移動する間に，Hotel と Restaurant

くする演算を roll-up と呼び，反対に，集約の粒度を細くするの両方を通過したシーケンス (sid=1)，どこも通過していない演算を drill-down と呼ぶ．図 2 では，左のデータキューブをシーケンス (sid=2)，Cafe を通過したシーケンス (sid=3) が存

roll-up(X city → X region）して，右のデータキューブを取得

在することが分かる．このように，特定のパターンオカレンス

している．

について異なるパターンにおける詳細な集約結果を得る演算をpattern-occurrence-drill-down と呼ぶ．

図 3: pattern-occurrence-drill-down
図 2: シーケンス OLAP のデータキューブ

これらの機能を RDB 上で実現する方法について考察する．ま次に，シーケンス OLAP では集約の次元だけでなく，パター

ず，RDB における行パターンマッチングは SQL2016 [1] で標ンそのものを変更する機能も必要となる．例えば，Airport(X)

準化されている MATCH RECOGNIZE 句を用いた問合せで実から Airport(Y) への移動パターンを分析した後に，さらに，そ行することができる．また，drill-down，roll-up を含む OLAPの間に会場 W を通過したパターンを分析するというシナリオ

分析機能も RDB で提供されている機能で実現することができが考えられる．このような要求に応えるためには，パターン (Xる．次に，OLAP-Patten 演算について考える．OLAP-PattenY) とは別にパターン (X W Y) のパターンオカレンスを抽出し演算を実行するためには，親パターンと子パターンのそれぞておく必要がある．本研究では特に，2 つのパターンについて，

れについてパターンオカレンスを抽出する必要がある．この片方のパターンに新たなパターン変数を追加することで，もう時，MATCH RECOGNIZE 句は複数のパターンの問合せを片方のパターンが得られる場合に，元のパターンを親パターン，

実行することができないため，複数回の問合せを行う必要が新たなパターンを子パターンとする．このように，集約対象のある． 次に，pattern-occurrence-drill-down について考える．

パターンを異なるパターンに切換える演算を OLAP-Patternpattern-occurrence-drill-down を効率的に実行するためには，演算と呼ぶ．特に，(X Y) → (X W Y) のように親パターンか同一の発生箇所を示すパターンオカレンス同士を異なるパター

ら子パターンに切換える演算を pattern-drill-down と呼び，(Xンの間でリンクさせる必要がある．しかし，RDB はそのような参照を検出して保持する機能を持たない．そこで本研究では，ている Z や V などを用いたパターンである (X W Y Z) や (VRDB を用いてシーケンス OLAP における OLAP-Pattern 演

X W Y) などは定義することができない．

算をサポートするために，複数パターンの行パターンマッチン
グとパターンオカレンス間の親子関係検出を効率的に実行する手法を提案する．

3 パターン階層モデル
本章では，パターンの親子関係からなるパターン階層モデル

図 4: パターンの親子関係について定義する．我々は，あるパターン (例:(X Y)) とそれに
新しいパターン変数を追加した拡張パターン (例:(X W Y)) が

複数行パターンマッチングを実現するために，上記のパターある場合，拡張パターンのパターンオカレンスは元のパターン

ンおよびパターン階層の定義を行のシーケンスとして関係モデの条件も満たしているという性質に着目した．この性質から，

ルの表に適用する． さらに，複数行パターンマッチングに以下

元のパターンが親，拡張パターンが子となるような親子関係をの表現を用いる．

定義する．まず，パターンを構成するパターン要素を定義する．
［定義 1］ (パターン要素) パターン要素 p はパターン変数 v(1文字)，または，パターン要素からなる正規表現である．正規表
現は以下のものを考える．

•

パターン P にパターン変数 {v1 , . . . , vm } が出現する場

合，pattern variables(P ) = {v1 , v2 , . . . , vm } と表す.

•

パ タ ー ン 変 数 vi に 一 致 し た 行 の 集 合 Ri を Ri ={r1 , . . . , rk } と表す．

•

シーケンス (denoted by p1 . . . pn )•［定義 5］ (パ タ ー ン オ カ レ ン ス) pattern variables(P ) =クリーネ閉包 (denoted by p*)•

選択 (denoted by p1 |p2 ){v1 , . . . , vm } であるパターン P のパターンオカレンス oP を

ここで，p または pi パターン要素であり, 各パターン要素には

oP = {R1 , . . . , Rm } とする.

同じパターン変数が複数回出現することはない. 特に，シーケ［定義 6］ (パターンオカレンスの親子関係) 親パターン Pparent

ンスのパターン要素のことをシーケンスパターン要素と呼ぶ.

のパターンオカレンス oPparent と子パターン Pchild のパター

［定義 2］ (パターン) パターン P は 1 つのシーケンスパター
ン要素である．ここで，パターンを P = {p1 . . . pn } と表す.

ンオカレンス oPchild に対して，∀Ri , Ri ∈ oPparent ⇒ Ri ∈oPchild が成り立つ時，oPchild は oPparent の子パターンオカレ
ンスである.

［定義 3］ (パ タ ー ン の 親 子 関 係) も し ，パ タ ー ン Pchild［例 2］ (パターンオカレンスの親子関係) 図 4 に示されているが パ タ ー ン Pparent = {p1 , p2 , . . . , pn } に 対 し て ，新 た(X Y) のパターンオカレンスと (X W Y) のパターンオカレン= {pnew , p1 , p2 , . . . ,スは，いずれも図 1 のシーケンス表の 2 行目が X，5 行目が Y

な パ タ ー ン 要 素 pnew を 前 (Pchildpn })，間 (Pchild = {p1 , p2 , . . . , pnew , . . . , pn }) ，後 (Pchild =に一致しているため，それぞれ親子関係を持つ．

{p1 , p2 , . . . , pn , pnew }) に挿入するという処理を有限回繰り返
すことによって構築可能である場合，パターン Pchild は親パ

4 問合せ言語ターン Pparent の子パターンである.

本章では，複数行パターンマッチングを実行するための［定義 4］ (パターンの親子関係の分類) 親パターン Pparent と問 合 せ 言 語 に つ い て 説 明 す る ．SQL2016 で 標 準 化 さ れ て

その子パターン Pchild が存在するとき，Pparent と Pchild のいる MATCH RECOGNIZE 句では定義できるパターンが最後のパターン要素が一致する場合，その親子関係を suﬃx

1 つ に 限 ら れ て お り，複 数 パ タ ー ン の 行 パ タ ー ン マッチ ン

match case に分類する．また，一致しない場合，その親子関グを行うためには複数回の問合せが必要となる． そこで，係を prefix match case に分類する．

MATCH RECOGNIZE 句 を ベ ー ス と し て ，複 数 行 パ タ ー
ン マッチ ン グ と パ タ ー ン オ カ レ ン ス 間 の 親 子 関 係 検 出 が［例 1］ (パターンの親子関係) 図 4 は親パターン (X Y) に対実行可能な MULTI MATCH RECOGNIZE 句を提案する．

する子パターンと孫パターンの例を示す図である．各パターン

MULTI MATCH RECOGNIZE 句の構文を以下に示す．

を結ぶ線に付随する文字はそれぞれの親子関係の分類を示している．子パターンを新しく定義するときは，別の子パターンで

リスト 1: MULTI MATCH RECOGNIZE 句のシンタックス

すでに使用されているパターン変数を新しく追加するパターン

1

要素として使用することはできない．例えば，以下の (X W Y)

2の子パターンを定義する際に，すでに他のパターンで使用され

3
4

SELECT <select list>
FROM <table name>
MULTI MATCH RECOGNIZE (PARTITION BY <column names>

ORDER BY <column names>
MEASURES <measures list>
PATTERN SET <define patterns>
DEFINE <define pattern variables>
WINDOW <window param>

5
6
7
8
9
10

);

PARTITION BY 句ではシーケンスを形成するための識別子となる属性を指定する．ORDER BY ではシーケンス内での順序の基準となる属性を指定する．MEASURES 句では出力されるパターンオカレンスが持つ属性を定義する．PATTERNSET 句ではパターンを指定する．DEFINE ではそれぞれのパを示す属性)，pattern oid(各パターン内での id となる属性)
はデフォルトで出力される．
図 6 では，P1 に一致したパターンオカレンスの id が P1 oidとして出力される． 同様に，P2 と P3 のパターンオカレンス
では p2 oid と p3 oid が出力される．さらに，子パターンオカ
レンスは親パターンオカレンスの pattern oid を持つ．例えば，

6 行目の P2 のパターンオカレンス (oid = 6) は 5 行目の P1 のパターンオカレンス (oid = 5) を親パターンオカレンスとして持つ．従って，パターンオカレンス (oid = 6) は親パターンオ
カレンスの P1 oid として P 1 oid = 3 を持つ．

ターン変数の条件を指定する．WINDOW 句では抽出するパ
ターンオカレンスの最大長を指定する．また，図 1 のシーケン
ス表に対するクエリの例をリスト 2 に示す．
リスト 2: MULTI MATCH RECOGNIZE 句を用いたクエリ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SELECT ∗FROM sequence
MULTI MATCH RECOGNIZE (PARTITION BY sid
ORDER BY time
MEASURES X.rid AS (X rid; P1, P2, P3),
W.rid AS (W rid; P2),
Y.rid AS (Y rid; P1, P2, P3),
Z.rid AS (Z rid; P3),
X.city AS (X city; P1, P2, P3),
W.city AS (W city; P2),
Y.city AS (Y city; P1, P2, P3),
Z.city AS (Z city; P3)
PATTERN SET (P1; X Y (P2; X W Y) (P3; X Y
Z))DEFINE X AS (X.venue = ”Airport”),
W AS (W.city = Xcity),
Y AS (Y.venue = ”Airport”),
Z AS (Z.city = Y.city)
WINDOW [Rows 5]);

リスト 2 は親パターン (X Y) と 2 つの子パターン (X W Y)，(X Y Z) の複数行パターンマッチングを実行するためのクエリである．MEASURES 句では各属性に対して，その属性を出力するパターンを指定する．リスト 2 では，全てのパターンで X，Y に関連する属性が出力されるように指定されている．また，
P1 と P3 はパターン変数 W を持たないため，W に関連する属性は P2 のみ出力するように指定されている．WINDOW 句で指定されている [Rows 5] という記述は，最初に一致した行から 5 行未満の範囲に出現するパターンオカレンスのみを抽出する条件を表している．

MULTI MATCH RECOGNIZE 句の問合せ処理では，パ

図 5: MULTI MATCH RECOGNIZE 句の問合せ結果

5 問合せ処理
本章では，図 5 のようなパターンオカレンス表を生成するための問合せ処理方法を提案する．パターンオカレンス表を生成するためには，複数行パターンマッチングと親子関係検出を実行する必要がある．提案手法では，複数のパターンを統合的に扱う NFA(Nondeterministic Finite Automaton) [11] を用いて複数行パターンマッチングを行う．さらに，パターンオカレ
ンス抽出時に逐次的に親子関係検出を実行することで，効率的に問合せ処理を行う．

5. 1 データ構造
提 案 手 法 で は ，複 数 行 パ タ ー ン マッチ ン グ を 実 行 す る

NFA(MRPR-NFA) とパターン毎に抽出したパターンオカレン
スを管理する pattern occurrence buﬀer を組合せたデータ構造を用いる．MRPR-NFA と pattern occurrence buﬀer は共に

MULTI MATCH RECOGNIZE 句を用いたクエリをコンパイ
ルすることによって構築する．まずは，MRPR-NFA について説明する．

5. 1. 1 MRPR-NFA
MRPR-NFA は複数のパターンを統合的に扱い，複数行パ
ターンマッチングを実行するためのオートマトンである．基本的な考え方は SASE [2] [5] を参考にした．MRPR-NFA は以下のように定義される．

ターンオカレンスの親子関係検出を実行するために，複数行パ

A = (Q, E, q0 , F )ターンマッチング実行前に行番号として rid という属性を追加する．rid を追加したシーケンス表に対して複数行パターンマッ

ここで，Q は状態の集合，E はエッジの集合，q0 は初期状態，

チングと親子関係検出を実行すると，図 5 のパターンオカレン

F は受理状態の集合を示す．また，エッジは以下のように定義

ス表のような結果が得られる．パターンオカレンス表の oid(パされる．

ターンオカレンス表の主キーとなる属性)，sid(PARTITIONe = (qs , qd , action, name, condition)

BY 句で指定された属性)，pid(一致したパターンのパターン名

ここで，qs は遷移元の状態，qd は遷移先の状態を示す．action

は遷移時に実行される処理を示す．定義されている action に条件を反映させる．また，take action 実行時に遷移先が受理状ついては後述する．name は遷移条件の判定対象となるパター態であった場合，match buﬀer に格納されている行ポインタはン変数名を示す．condition は name で指定されたパターン変5.1.2 節で説明する pattern occurrence buﬀer へ出力される．

数における条件を示す.

MRPR-NFA の評価は初期状態から始まる．状態の遷移は次に，MRPR-NFA の構築アルゴリズムについて説明する．

MRPR-NFA は複数行パターンマッチングを効率的に実行する
ため，複数のパターンを統合的に扱うオートマトンを構築する．

Algorithm 1 MRPR-NFA 構築
Require: pattern set PS, conditions from DEFINE and WINDOW C, initial state q0
Q ← {q0 }, E ← ∅, F ← ∅MRPR-NFA 構築アルゴリズムの疑似コードを Algorithm1 に示す．このアルゴリズムでは複数のパターンでマッチングを共有する部分を検出するために prefix tree の挿入アルゴリズムをe ← newEdge(q0 , q0 , ”ignore”, N one, conditions)

ベースとした手法を用いる．まず，アルゴリズムの入力としてE.append(e)クエリの PATTERN SET 句，DEFINE 句，WINDOW 句を

rootN ode ← newN ode(q0 )コンパイルした情報を受け取る．次に，各パターンに対してパ

for all P ∈ P S do

ターン要素を元に状態とエッジを作成する．なお，Algorithm1

node ← rootN ode
for all p ∈ P do
if p not in node.children thennode.children[p] ← newN ode(p)では説明を簡略化するために，パターン要素は単一のパターン変数であると仮定している．この時，接頭語が共通しているパターンがあれば，その部分は状態を共有するために状態とエッQ.append(p)ジの作成をスキップする．また，接尾語が共通しているパターe ← newEdge(node.state, p, ”take”, p, conditions)

ンや途中のパターン要素が共通しているパターンについては共

E.append(e)有せずに別々の状態としてオートマトンを構築する．

if p is not P.last then

図 6 はリスト 2 のクエリから構築される MRPR-NFA の例を

e ← newEdge(p, p, ”ignore”, p, conditions)

示している．各状態を結ぶ線はエッジを表し，エッジの近くに

E.append(e)記述されている文字は，エッジに関連付けられている action，

end ifend ifnode ← node.children[p]name，condition を表している．リスト 2 のクエリでは (X
Y)，(X W Y)，(X Y Z) の 3 つのパターンが定義されている．

end for(X Y) と (X Y Z) は接頭語の”X Y”が共通しているため，X とF.append(p)Y の状態を共有している．また，(X Y) と (X W Y) は接頭語

end forの”X”が共通しているため，X の状態を共有している．

A ← newN F A(Q, E, p0 , F ) return A

行の入力によって引き起こされる．行の入力による遷移先が複数存在する場合，それぞれに遷移した状態を持つインスタンスが複製される．また，行の入力による遷移先が 1 つも無い場合
は，メモリスペースの節約のためにそのインスタンスは削除される．各インスタンスは行パターンマッチングの中間結果を保持する match buﬀer に関連付けられている．MRPR-NFA へ

図 6: MRPR-NFAの入力時に条件を満たした行へのポインタが対応する match

buﬀer へ格納される．match buﬀer への行ポインタの格納は後述する take action を実行することによって行われる．
エッジに関連付けられた action は状態 qs を持つインスタン
スに入力された行が condition の条件を満たし，状態遷移が発生した場合に実行される．MRPR-NFA では，take (conditionの条件を満たした行へのポインタを match buﬀer に格納する．
遷移先が受理状態であれば match buﬀer に格納された行ポインタを出力する) と ignore (condition の条件を満たした行をスキップする) の 2 つの action を用いる．

condition には MULTI MATCH RECOGNIZE 句の DEFINE 句で定義された条件を反映させる．また，遷移元の状

図 7: MRPR-NFA のインスタンス

態に初期状態を持つエッジを除く全てのエッジの condition にWINDOW 句で指定されたパターンオカレンスの最大長の制約

図 7 に MRPR-NFA のインスタンスの例を示す．各インスタ

ンスはそれぞれ現在の状態，親パターンの pattern oid，match

ンスタンスの遷移が終わり，次の行を参照する前に pattern

buﬀer に関連付けられている．親パターンの pattern oid につ

occurrence buﬀer に保持されているパターンオカレンス同士

いては子パターンを持つパターン全てを対象とする．この値

で親子関係検出を実行し，パターンオカレンス表へ結果を出力の取得方法については 5.2 節で説明する．また，図 7 は図 1する．また，パターンオカレンス表への結果出力後に patternのシーケンス表の 3 行目まで (r1 ∼ r3 ) が入力された時のイ

occurrence buﬀer に保持されているパターンオカレンスを全て

ンスタンスの様子を表している．例えば，インスタンス a1 は削除する．その後，次の行の入力を行う．

q0 → X → Y1 → Z のように遷移したインスタンスである．
5. 1. 2 pattern occurrence buﬀer
pattern occurrence buﬀer は各インスタンスの match buﬀer
から出力された行ポインタをパターンオカレンスとして管理するバッファである．図 8 に図 1 のシーケンス表の 5 行目まで (r1 ∼ r5 ) を入力した時の pattern occurrence buﬀer の様子

Algorithm 2 複数行パターンマッチング
Require: rows R, MRPR-NFA A, pattern occurrence buﬀer B
patternOccurrenceT able ← ∅, Automata ← ∅Automata.append(newInstance())
for all r ∈ R doを示す．各パターンに対応するバッファには抽出されたパター

newAutomata ← ∅ンオカレンス，そのパターンオカレンスを出力したインスタン

for all a ∈ Automata do

スへのポインタ，パターンオカレンスの累計の count が格納される．新たなパターンオカレンスが格納される時に count がedges ← A.getT ransitableEdges(a, r)
for all e ∈ edges doac ← a.copy()

加算され，さらにその値を pattern oid としてパターンオカレ

ac.state ← e.qd

ンスに付与する．また，子パターンのパターンオカレンスは検if e.action is ”take” then

出した親パターンオカレンスの pattern oid も保持する．さら

ac.matchBuf f er[e.name].append(r)に，子パターンを持つパターンの pattern oid はパターンオカ

if e.qd in A.F then

レンスに付与される時，効率的に親子関係検出を行うために対

ac.matchBuf f er.pushP atternOccurrence(B)end if

応するインスタンスへ同じ値が付与される．例えば，図 8 の

end if

P1 に格納されている (x1 , y2 ) は P 1 oid = 1 を取得している．
同様に，P 1 oid = 1 は a1 にも付与されるため，図 7 の a1 がnewAutomata.append(ac)end forP 1 oid = 1 の情報を保持している．また，pattern occurrence

end forbuﬀer は行パターンマッチング時に，新たな行が入力される前

B.detectP arentChildRelationships()に保持されているパターンオカレンスをパターンオカレンス表

B.pushP atternOccurrences(patternOccurrenceT able)

へ出力し，count 以外の中身を空にする．図 8 では 5 行目が入Automata ← newAutomata

力された時に，すでにパターンオカレンス表へ出力されている

end forものは背景を灰色にしている．

return patternOccurrenceT able

5. 2. 2 親子関係検出
次に，パターンオカレンスの親子関係検出アルゴリズムについて説明する．パターンオカレンスの親子関係検出はパターンの親子関係が prefix match case の場合と suﬃx match case の場合で異なる手法を用いる．
図 8: pattern occurrence buﬀer

まずは，パターンの親子関係が prefix match case の場合について説明する．パターンの親子関係が prefix match case の

5. 2 複数行パターンマッチングと親子関係検出場合，子パターンオカレンスは必ず，親パターンオカレンスより後に抽出されるという性質を持つ．また，MRPR-NFA にお5. 2. 1 複数行パターンマッチング
まずは，複数行パターンマッチングのアルゴリズムについて説明する．具体的なアルゴリズムを Algorithm 2 に示す．複
数行パターンマッチングでは称号対象の表のスキャンを行う．
その際に，参照した行を 1 行ずつ MRPR-NFA に入力し，各インスタンスの遷移を発生させる．あるインスタンスで takeaction を持つエッジによる遷移が発生した場合，入力行へのポ
インタをそのインスタンスの match buﬀer へ格納する．また，その際に，遷移先の状態が受理状態であれば対応する patternoccurrence buﬀer へパターンオカレンスの出力を行う．各イ

いて prefix match case の子パターンは親パターンの受理状態を共有している．従って，prefix match case の親パターンオカ
レンスを出力したインスタンスはその後に子パターンオカレン
スを出力する可能性がある．その場合，親パターンオカレンスの pattern oid はインスタンスが保持しているため，子パター
ンオカレンス出力時に共に親の pattern oid を出力することで親子関係検出を行うことができる．
次に，パターンの親子関係が suﬃx match case の場合について説明する．パターンの親子関係が suﬃx match case の場
合，最後のパターン要素が共通しているため子パターンオカレ

ンスは必ず，親パターンオカレンスと同じタイミングで抽出さrid が付与されたソート済みの表を作成する SQL を関数内部でれるという性質を持つ．この性質から，抽出されたタイミング

実行し，メモリに展開する．さらに，2 つ目から 5 つ目の引数で親子関係を持つ suﬃx match case のパターンオカレンスははそれぞれ対応する句で指定されている文字列を受け取る．

全て pattern occurrence buﬀer に格納されているということが言える．そこで，suﬃx match case の親子関係検出は対応する
パターンオカレンス同士の結合処理によって行う．結合の条件としてパターンオカレンスが保持している各行の rid を用いる．
親子で共通するパターン変数にマッチした行の rid を 2 つのパ
ターンオカレンスで比較し，全ての行の rid が一致したパター
ンオカレンス同士は親子関係を持つと判定する．ここで，子パ
ターンオカレンスの親パターンオカレンスは孫パターンオカレ
ンスの親パターンオカレンスも兼ねるという性質を考慮した
場合，初めに親子の結合処理を実行しておけば，孫子の結合処理実行時に親と孫の親子関係も検出できることがわかる．この図 9: MULTI MATCH RECOGNIZE 句の UDF

性質を利用して冗長な結合処理を削減するために PATTERNSET 句から親子関係検出計画を作成する．親子関係検出計画

図 10 に prefix match case でパターン数を変化させた実験

は結合処理を行う親子パターンのペアのリストである．親子結果を示す．グラフの x 軸はパターン数，左の y 軸はクエリ関係検出では各検出計画に対して対応するバッファの結合処理の処理時間，右の y 軸は出力されたパターンオカレンスの数を行う．また，親子関係検出ではパターンオカレンスの各行のを示している．さらに，CD は Collective Detection，MR はrid を用いた等価結合を実行するため，各行の rid をキーとしMATCH RECOGNIZE 句を示している．パターン数 5 におた Hash Join を用いて効率的に結合処理を実行する．

ける MR の処理時間は他と比べて非常に大きくなってしまったため，グラフからは除外している．実験結果から，どのパ

6 実験

ラメータでも提案手法が最も高速であることがわかる．特に，MATCH RECOGNIZE 句と比較すると 2 倍近く高速に実行で
本章では，提案手法の性能を評価するために行った実験につきている．これは，MATCH RECOGNIZE 句がパターンの数

いて記す．本実験では，提案手法の性能を評価するために RDB

だけ UDF を呼び出すことで，複数行パターンマッチングの処

上に擬似的に提案手法と比較手法を実装し，クエリの処理時

理時間が増加しているためである．また，Collective Detection

間を計測する．比較手法は，提案手法と同様に MRPR-NFAと比較すると提案手法は 10%程度高速に実行できていることがで複数行パターンマッチングを行い，パターンマッチング終

わかる．これは，親子関係が prefix match case の場合，親の了後にまとめて親子関係検出を行う Collective Detection とパ

pattern oid を MRPR-NFA のインスタンスで伝搬することで，ターン毎にパターンマッチングを実行し，SQL の結合処理で親結合処理を実行せずに親子関係を検出できるためである．

子関係検出を行う MATCH RECOGNIZE の 2 つである．実

さらに，図 11 に suﬃx match case での実験結果を示す．実験は全てで Ubuntu 16.04.3 LTS，Intel(R) Core(TM) i7-4790

験結果から，どのパラメータでも提案手法が最も高速であるこCPU @ 3.60GHz，32GB RAM で構成された PC 上で行った．

とがわかる．prefix match case と比べて全体的に処理時間が実験に用いる RDB はオープンソースの PostgreSQL 9.5 を選大きくなっているのは，suﬃx match case の方が MRPR NFA

択した．また，PostgreSQL の UDF(ユーザー定義関数) としの state，インスタンスの数が多く，複数行パターンマッチングて提案手法と比較手法を C 言語で実装した．さらに，本実験の処理時間が大きくなるためである．Collective Detection とではシーケンスデータやクエリの特徴をコントロールするた

比較した場合，こちらも 10%程度高速に実行できていることがめに人工データをデータセットとして用いる．人工データはわかる．これは，親子関係が suﬃx match case の場合，複数行

シーケンス数が 100，各シーケンスが 10,000 行を持つ，合計パターンマッチング中に逐次的に結合処理を実行することで，1,000,000 行の表である．提案手法を擬似的に実装した UDF

ある程度区切られた範囲内で結合処理を実行できるためである．

を図 9 に示す．PostgreSQL では表を出力として扱うことができる表関数を使用できる．表関数は FROM 句に記述することで，関数で作成した表を SQL のセマンティクス上で扱うことができる．MULTI MATCH RECOGNIZE 句はパターン
オカレンス表を出力するため，表関数として UDF を実装した．この UDF は 5 つの文字列を引数とする．1 つ目の引数は

MULTI MAT-CH RECOGNIZE 句を用いたクエリの FROM
句，PARTITION BY 句，ORDER BY 句の指定を変換した

SQL 文である．これらの 3 つの句の指定から，図 4 のような

図 10: prefix match case における処理時間

SKYSEA Client View のログ及び資産情報の処理の高速化・軽量化・高度化」の助成を受けたものである．
文

図 11: suﬃx match case における処理時間

7 関連研究過去にはシーケンスデータに対してパターンマッチングを実行する手法が数多く研究されている．その多くは SASE [13] [4]，Cayuga [3]，Zstream [9] などのストリームデータに対してリ
アルタイムにパターンマッチングを行う CEP(Complex Event

Processing) として提案されている．さらに，クエリワークロードとして登録された複数パターンのパターンマッチングを部分的に共有して効率的に問合せ処理を行う手法も提案されている [12] [14] [10]．しかし，これらの手法は抽出したパターンオ
カレンスに対して OLAP 分析を実行する機能を持たない．
シーケンスデータに対して OLAP 分析を実行する手法として S-OLAP [8] や E-Cube [6] [7] が知られている．さらに，

S-OLAP，E-Cubu は複数のパターンを効率的に処理する機能を持っている．しかし，S-OLAP，E-Cube はどちらも独自の言語とシステムの構築を必要とし，データベースなどに蓄積されたデータとの統合的な処理が困難であるという問題点が存在する．本研究では汎用的なデータ管理システムである RDB を用いることでこの問題を解決している．

8 おわりに
本研究では，RDB 上でのシーケンス OLAP をサポートする複数行パターンマッチングの問合せ処理手法を提案した．
まずは，パターンの親子関係を元にパターン階層モデルを定義した．また，複数行パターンマッチングを実行するためのSQL 拡張記述 MULTI MATCH RECOGNIZE 句を示した．
MULTI MATCH RECOGNIZE 句の問合せ処理として，提案
手法では複数パターンを統合的に扱う MRPR-NFA を用いて効率的に複数行パターンマッチングとパターンオカレンス間の親子関係検出を実行し，パターンオカレンス表を出力することができる．出力されたパターンオカレンス表でシーケン
ス OLAP の OLAP-Pattern 操作をサポートすることが可能となる．また，今後の課題として prefix match pattern，suﬃx

match pattern を組合せたパターン，クリーネ閉包を用いたパターンの実験，実データを用いたシーケンス OLAP 分析の実証実験や，シーケンス OLAP 用 GUI の開発があげられる．

謝

辞

本研究の一部は，平成 30 年度共同研究 (SKY 株式会社)（CPE30034)）「データエンジニアリングの知見の応用による

献[1] ISO/IEC 2016. Information technology ― database languages ― sql technical reports ― part 5:row pattern recognition in sql. Technical report, ISO copyright oﬃce, 2016.
[2] Jagrati Agrawal, Yanlei Diao, Daniel Gyllstrom, and Neil
Immerman. Eﬃcient pattern matching over event streams.
In Proceedings of the 2008 ACM SIGMOD international
conference on Management of data, pages 147–160. ACM,
2008.
[3] Alan J Demers, Johannes Gehrke, Biswanath Panda, Mirek
Riedewald, Varun Sharma, Walker M White, et al. Cayuga:
A general purpose event monitoring system. In CIDR, volume 7, pages 412–422, 2007.
[4] Daniel Gyllstrom, Jagrati Agrawal, Yanlei Diao, and Neil
Immerman.
On supporting kleene closure over event
streams. In Data Engineering, 2008. ICDE 2008. IEEE
24th International Conference on, pages 1391–1393. IEEE,2008.
[5] Ilya Kolchinsky, Izchak Sharfman, and Assaf Schuster. Lazyevaluation methods for detecting complex events. In Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems, pages 34–45. ACM, 2015.
[6] Mo Liu, Elke Rundensteiner, Kara Greenfield, Chetan
Gupta, Song Wang, Ismail Ari, and Abhay Mehta. E-cube:
Multi-dimensional event sequence processing using concept
and pattern hierarchies. In Data Engineering (ICDE), 2010
IEEE 26th International Conference on, pages 1097–1100.
IEEE, 2010.
[7] Mo Liu, Elke Rundensteiner, Kara Greenfield, Chetan
Gupta, Song Wang, Ismail Ari, and Abhay Mehta. Ecube: multi-dimensional event sequence analysis using hierarchical pattern query sharing. In Proceedings of the 2011
ACM SIGMOD International Conference on Managementof data, pages 889–900. ACM, 2011.
[8] Eric Lo, Ben Kao, Wai-Shing Ho, Sau Dan Lee, Chun Kit
Chui, and David W Cheung. Olap on sequence data. In
Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 649–660. ACM, 2008.
[9] Yuan Mei and Samuel Madden. Zstream: a cost-based query
processor for adaptively detecting composite events. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 193–206. ACM, 2009.
[10] Olga Poppe, Allison Rozet, Chuan Lei, Elke A Rundensteiner, and David Maier. Sharon: Shared online event sequence aggregation. In 2018 IEEE 34th International Conference on Data Engineering (ICDE), pages 737–748. IEEE,
2018.
[11] Michael O Rabin and Dana Scott. Finite automata andtheir decision problems. IBM journal of research and development, 3(2):114–125, 1959.
[12] Medhabi Ray, Chuan Lei, and Elke A Rundensteiner. Scalable pattern sharing on event streams. In Proceedings ofthe 2016 International Conference on Management of Data,
pages 495–510. ACM, 2016.
[13] Eugene Wu, Yanlei Diao, and Shariq Rizvi.
Highperformance complex event processing over streams. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 407–418. ACM, 2006.
[14] Shuhao Zhang, Hoang Tam Vo, Daniel Dahlmeier, andBingsheng He. Multi-query optimization for complex event
processing in sap esp. In 2017 IEEE 33rd International
Conference on Data Engineering (ICDE), pages 1213–1224.
IEEE, 2017.