Allenの時区間関係を条件とする時区間データの効率的な結合演算手法

(1)

DEIM Forum 2016 D3-1

Allen の時区間関係を条件とする

時区間データの効率的な結合演算手法

山下夏奈

†

猪口明博

†

関西学院大学理工学部情報科学科

〒 669–1337 三田市学園 2 丁目 1 番地

E-mail:

†{

kana06,inokuchi

}

@kwansei.ac.jp

あらまし

Overlap Interval Partitioning (

OIP) は，交わりをもつ 2 つの時区間（タプル）の結合演算を効率良く解

くためのデータ構造である．しかしながら，このデータ構造を Allen の時区間関係の 1 つを満たす 2 つの時区間の結

合演算に用いると，結合の回数が増えたり，結合の必要のない 2 つのタプルに対して，条件節の真偽を確認する必要

があり，非効率である．そこで，本稿では 2 次配列型のデータ構造を持つ Partition Array を提案し，必要最低限の

結合を行い，効率的な結合演算を可能にする．提案手法 Partition Array と既存手法

OIP を実装し，実行時間の違い

について考察することにより，提案手法の有効性を評価・検証する．

キーワード

時制データベース，時区間データ，結合演算，索引，Allen の時区間関係

1. はじめに

近年，情報通信技術の発展により，様々なデータを半自動的

に収集できるようになった．例えば，スーパーマーケットやコ

ンビニエンスストアでは，店舗で商品を販売するごとに商品の

販売情報を記録する

POS

システムの導入により，商品名や価

格，数量などの購買データが蓄積される．また，インターネッ

トショピングを利用すると，商品の閲覧履歴や注文履歴，購入

日時などが記録される．多種多様なデータの中でも，市場の流

行や消費者の購買行動，購買意識の変化を調べるときには時区

間を持つデータの分析が重要である．ここで，時区間とは，始

点と終点を持つ時間領域のことである．先ほどの例では，顧客

の来店時間や商品の購入日時，注文日時などが時区間を持つ

データである．時区間を持つデータを分析することで，常に変

化し続ける市場を捉えることができ，顧客ごとのニーズに基づ

いた商品やサービスの提供が可能になる．

時区間データを持つ

2 つのリレーションがあるとき，データ

ベースから特定の時区間関係を持つデータを抽出して結合する

ために，全ての時区間の対の結合をとるのは効率が悪い．そこ

で本研究では，時区間を持つデータに対して時区間関係を取り

入れた演算手法を提案する．具体的には，

Allen

の

13 種の時

区間関係

[5]

をサポートするデータ構造を持つ演算手法を提案

する．これにより，時区間を持つデータの結合操作が効率的に

なる．

既存手法である

Overlap Interval Partitioning (

OIP)

では，

リレーションの時間範囲を

k

個の等しい長さの最少構成区間

に分割する．また，

1 つ以上の隣接した最少構成区間の集合で

パーティションを構成する．リレーションに格納されている各

タプルは，タプルの区間を完全に覆うパーティションの中で最

小のものに割り当てられる．そして，各パーティションを

Lazy

Partition List

と呼ばれる木構造で保持する．各パーティショ

ンを木構造で保持することで，抽出したいタプルが格納され

ている可能性があるパーティションを深さ優先探索して得るこ

とができ，効率的である．

OIP

では，

Allen

の時区間関係の

af ter(A, B)

，

bef ore(A, B)

以外の

11 個の時区間関係の論理

和をサポートできる．しかしながら，論理和でなく，各時区間

関係を条件とする結合演算に適しているとは言えない．そこで

本稿では，各時区間関係を条件とする結合演算に対して効率的

な結合演算を可能にするデータ構造と，それに対する探索手法

を提案する．

2. 区間の結合演算とその既存手法

2. 1

問題定義

本稿では，離散時間領域

Ω

T

は線形に並んだタイムポイント

の集合で構成されているものとする．区間

T

はタイムポイント

の対であり，

[T

S

, T

E

]

で表される．ここで，

T

S

と

T

E

はそれぞ

れ

T

の始点と終点である．タイムポイントと区間に対して，以

下に記す演算を用いる．

• タイムポイント

x

が区間

T

に含まれている，つまり

T

S

<

_{= x <}

_{= T}

E

ならば，

x

∈ T

と記す．

• 区間

Q

と

T

が交わっている，つまり

x

∈ Q ∧ x ∈ T

を

満たすタイムポイント

x

が存在するならば，

Q

∩ T |= ∅

と記す．

• 区間

T

が区間

U

に含まれている，つまり

∀x ∈ T ⇒ x ∈

U

を満たすタイムポイント

x

が存在するならば，

T

⊂

₌

U

と記す．

• T

E

− T

S

は

T

S

と

T

E

のタイムポイントの差を意味する．

• T

S

− x

は，タイムポイント

T

S

を

x

だけ過去にずらすこ

とを意味し，

T

E

− T

S

= x

⇒ T

S

+ x = T

E

が成り立つ．

• | T |= (T

E

− T

S

) + 1

は，区間

T

の存続時間を意味する．

時制リレーションスキーマを

R = (A

1 ,

· · · , A

m

, T )

と表す．

ここで，

1 <

_{= i <}

_{= m}

に対して，

A

i

は領域

Ω

i

に属し，区間

T

は

領域

Ω

T

_{× Ω}

T

_{に属する．スキーマ}

_R

_{における時制リレーショ}

ン

r

は，

R

におけるタプルの有限集合である．もし

r

のタプル

の中で最小の始点が

U

S

であり，

r

のタプルの中で最大の終点

が

U

E

であるならば，

r

の時間範囲は

U = [U

S

, U

E

]

である．

(2)

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

ϮϬϭϮͲϭ

ϮϬϭϮͲϮ

ϮϬϭϮͲϯ

ϮϬϭϮͲϰ

ϮϬϭϮͲϱ

ϮϬϭϮͲϲ

ϮϬϭϮͲϳ

ϮϬϭϮͲϴ

ϮϬϭϮͲϵ

ϮϬϭϮͲϭϬ

ϮϬϭϮͲϭϭ

ϮϬϭϮͲϭϮ

G

S

ϭ͕ϭ

V

ϱ

S

Ϯ͕Ϯ

S

ϯ͕ϯ

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

S

Ϭ͕Ϭ

S

Ϯ͕ϯ

S

ϭ͕Ϯ

S

Ϭ͕ϭ

S

Ϭ͕Ϯ

S

Ϭ͕ϯ

V

ϭ

_V

Ϯ

V

ϳ

V

ϯ

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

S

ϭ͕ϯ

V

ϰ

V

ϲ

4 図 1

_{OIP with Configuration (s, 4)}

文献

[1]

で対象とされた問題は，

2 つのリレーション

r

と

s

が

入力として与えられたとき，時区間が交わりをもつタプルのペ

アを求める結合演算

{r ◦ s | r ∈ r ∧ s ∈ s ∧ r.T ∩ s.T |= ∅}

を

効率良く求めることである

[2, 3, 4, 6]

．

2. 2

パーティション

本節では，上記の問題を解く既存手法として

_{OIP [1]}

を説明

する．

_OIP

ではリレーション

r

の時間範囲

U = [U

S

, U

E

]

は

k

個の等しい長さの最少構成区間に分割される．

［定義

2.1 ］

（

OIP Configuration

）

k

が与えられたとき，

r

の

OIP Configuration

は

(r, k)

で表される

（注 1）

_．

_■

パーティションは，

1 つ以上の隣接した最少構成区間の集合で

ある．各タプルは，タプルの区間を覆うパーティションの中で

最小のものに割り当てられる．

［定義

2.2 ］

（

OIP Partition

）

OIP Configuration (r, k)

が与

えられ，最少構成区間に対して，時間順に

0 から

k

− 1

の

ID

が振られているものとする．

_OIP

のパーティション

p

i,j

は

i

番目から

j

番目の最少構成区間に跨り，その区間は

[U

S

+ i

· d, U

S

+ (j + 1)

· d − 1]

である．ここで，

0 <

_{= i <}

_{= j < k}

，

d =

⌈

|U|

_k

⌉

である．タプル

r

∈ r

は，

i =

⌊

r.T

S

−U

S

d

⌋

かつ

j =

⌊

r.T

E

−U

S

d

⌋

であるとき，

p

i,j

に割り当てられる．

■

存在する

_OIP

のパーティションの数は，

k

2 +k

2 である．また，

c = p

i,j

のとき，

c.i

と

c.j

はそれぞれパーティションの始点の

ID

と終点の

ID

を表す．

［例

2.3 ］図

1 にあるリレーション

s

は

{s

1 ,

· · · , s

7 }

の

7 つ

のタプルを含み，時間範囲は

U = [2012-1, 2012-12]

であ

る．

k = 4

であるとき，

d =

⌈

|U|

_k

⌉ = ⌈

|12|

₄

⌉ = 3

であ

る．また，

p

0,1

の範囲は

[2012-1, 2012-6]

である．タプル

s

6 について，

i =

⌊

s

6 .T

S

−o

d

⌋ = ⌊

2012-6

−2012-1

3 ⌋ = ⌊

5

3 ⌋ = 1

，

j =

⌊

s

6 .T

E

−o

d

⌋ = ⌊

2012-10

−2012-1

3 ⌋ = ⌊

9

3 ⌋ = 3

であることよ

り，

s

6 はパーティション

p

1,3

に割り当てられる．

10 個のうち

5 個のパーティションは空である．

_□

［補題

2.4 ］

OIP Configuration (r, k)

とクエリ区間

q =

[q.T

S

, q.T

E

]

が与えられているとする．

q

と交わりをもつ可

能性があるタプル

_{{r | r ∈ r, r ∩ q |= ∅}}

は，

i <

_{= ⌊}

q.T

E

−U

S

d

⌋

か

つ

j >

_{= ⌊}

q.T

S

−U

S

d

⌋

を満たすパーティション

p

i,j

に存在する．

■

［例

2.5 ］図

1 に示す

_{OIP Configuration (s, 4)}

とクエリ区間

（注1）：文献 [1] では，

OIP Configuration は (k, d, U

S

) で表される．しか

し d や U

S

は k と r から導出できるので，本稿では (r, k) の表現を用いる．

S

M

L

4

4 D7ULDQJXODUULGUDSK

E/D]\3DUWLWLRQ/LVW

図 2 Management of

_{OIP Partitions}

ϮϬϭϮͲϭ

ϮϬϭϮͲϮ

ϮϬϭϮͲϯ

ϮϬϭϮͲϰ

ϮϬϭϮͲϱ

ϮϬϭϮͲϲ

ϮϬϭϮͲϳ

ϮϬϭϮͲϴ

ϮϬϭϮͲϵ

ϮϬϭϮͲϭϬ

ϮϬϭϮͲϭϭ

ϮϬϭϮͲϭϮ

G

S

Ϭ͕Ϭ

U

ϭ

U

Ϯ

S

ϭ͕ϯ

ƌ

ϯ

図 3

_{OIP with Configuration (r, 4)}

q = [2012-5, 2012-5]

が与えられているとする．クエリと交わり

をもつ可能性があるタプルは，

i <

_{= ⌊}

2012-5−2012-1

₃

⌋ = ⌊

4

3 ⌋ = 1

かつ

j >

_{= ⌊}

2012-5

−2012-1

₃

⌋ = ⌊

4 ₃

⌋ = 1

であるパーティション

p

i,j

にある．これを満たすパーティションは灰色に塗られている

p

0,3

, p

0,2

, p

0,1

, p

1,3

, p

1,2

, p

1,1

である．

□

2. 3

Lazy Partition List

図

2(a)

に，図

1 の

_OIP

のデータ構造を示す．このグラフ

は

Triangular Grid Graph

と呼ばれ，インメモリで管理され

る．クエリ区間と結合可能な全ての適切なパーティション

p

i,j

は

j >

_{= ⌊}

q.T

S

−U

S

d

⌋

かつ

i <

= ⌊

q.T

E

−U

S

d

⌋

を満たす．ここで

U

s

と

d

s

はそれぞれ

s

の時間範囲の始点とパーティションの最少構成

区間の長さである．これを満たすパーティションを見つけるた

めにグラフの左端最上部から探索を開始し，

j >

_{= ⌊}

q.T

S

−U

S

d

⌋

で

ある間，

j

が減少する方向に移動する．そして

p

0,j

であるノー

ドから，

i <

_{= min(j, ⌊}

q.T

E

−o

s

d

s

⌋)

である間，

i

が増加する方向に

移動する．例

2.5 に示したクエリ区間

q

と結合可能なパーティ

ションは，図

2(a)

の灰色で強調されている

6 個である．

一方，

Lazy Partition List

は，

Triangular Grid Graph

か

ら空のパーティションを除いたものであり，各節点は

right

と

down

の

2 つのリンクをもつ．図

2(b)

は図

1 の

Lazy Partition

List

を示している．この図に示されるように，クエリ区間と交

わりを持つタプルを含むパーティションは連結する部分グラフ

であり，必ず根を含む．したがって，根から探索することでこ

れらのパーティションに漏れなく，また無駄なく到達し，結合

演算を取ることができる．

2. 4

Lazy Partition List

を用いた

_OIP

の実行

リレーション

r

と

s

に対する

OIPJ

OIN

アルゴリズムを

Algo-rithm 1

に示す．

Lazy Partition List

L

r

がもつ各パーティショ

ンの区間

c

r

と交わりともつパーティションを

L

s

から探索する．

L

s

の根から探索をはじめ，

right

のリンクを優先に深さ優先探索

する．もし，

c

r

と交わりを持つパーティション

x

に到達したら，

2 つのパーティションの結合演算をとり，結果を

z

に追加する．一

方，

c

r

交わりを持たない節点に到達したら，それ以降に

c

r

と交

わりをもつパーティションは存在しないので，バックトラックす

る．これを図

1 の

s

と図

3 の

r

に対して適用することで最終的に

(3)

Algorithm 1:

OIPJ

OIN

Data: Lazy partition lists

L

r

and

L

s

,

OIP

Configurations (r, k

r

) and (s, k

s

)

Result: z =

{r ◦ s | r ∈ r ∧ s ∈ s ∧ r.T ∩ s.T |= ∅}

1 z :=

∅;

2 [U

_S

r

, U

_E

r

] := r

の有効区間

;

3 [U

_S

s

, U

_E

s

] := s

の有効区間

;

4 d

s

:=

⌈

U

_E

s

−U

_S

s

+1

k

s

⌉ ;

5 d

r

:=

⌈

U

r

E

−U

S

r

+1

k

r

⌉ ;

6 for node c

r

in

L

r

do

7 Q

S

:= U

S

r

+ c

r

.i

· d

r

;

8 Q

E

:= U

S

r

+ (c

r

.j + 1)

· d

r

− 1;

9 if Q

E

>

_{= U}

S

s

∧ Q

S

< U

S

s

+ k

· d

s

then

10 s :=

⌊

Q

S

−U

s

S

d

s

⌋;

11 e :=

⌊

Q

E

−U

s

S

d

s

⌋;

12 c

s

:=

L

s

.head;

13 while c

s

|= null ∧ c

s

.j >

_{= s do}

14 x := c

s

;

15 while x

|= null ∧ x.i <

_{= e do}

16 z := z

∪ { joined tuples from c

r

and x

};

17 x := x.right;

18 c

s

:= c

s

.down;

19 return z;

z =

{r

3 ◦s

4 , r

3 ◦s

6 , r

3 ◦s

7 , r

1 ◦s

3 , r

1 ◦s

4 , r

1 ◦s

5 , r

2 ◦s

4 , r

2 ◦s

6 }

が出力される．

3. OIP

の課題

OIPJ

OIN

のアルゴリズムは，

_L

r

の各パーティション

c

r

と

結合可能なパーティション

x

を

_L

s

から探しだす．そして，タ

プル

r

∈ c

r

と交わりを持つタプル

s

∈ x

があればそれらを結

合する．結合の条件が

2 つの区間

A

と

B

の交わりがあれば，

このアルゴリズムは，重複なく，かつ漏れなく結合可能なパー

ティションの対を探し探し出すことができるが，

Allen

の時区

間関係

[5]

の

1 つである

contains

を条件とする結合演算に適し

ているとは言えない．その具体例を次に示す．

［例

3.1 ］時区間関係

contains(A, B)

の条件を満たすタプル

A

と

B

の結合を取るときの例を示す．ここで

contains(A, B)

は

A.T

S

< B.T

S

∧ B.T

E

< A.T

E

を満たす場合に真を返す

1 階述語である．時間範囲

U = [2012-1, 2012-12]

であるリレー

ション

r

と

s

，および

k = 4

を入力とする．このときの

Lazy

Partition List

L

s

は図

2 となる．この時区間関係に関して

L

r

のパーティション

p

1,1

に含まれるタプルと結合可能なタプル

を含む

_L

s

のパーティションは

p

1,1

である．この節点は，

L

s

の根ではないので，

_L

s

を全探索する必要がある．したがって，

Algorithm 1

に示される既存手法では，非効率である．

□

このように，既存手法では各リレーションのパーティションを

木構造で保持しているため，必要最低限のパーティションのみ

ϮϬϭϮͲϭ

ϮϬϭϮͲϮ

ϮϬϭϮͲϯ

ϮϬϭϮͲϰ

ϮϬϭϮͲϱ

ϮϬϭϮͲϲ

ϮϬϭϮͲϳ

ϮϬϭϮͲϴ

ϮϬϭϮͲϵ

ϮϬϭϮͲϭϬ ϮϬϭϮͲϭϭ

ϮϬϭϮͲϭϮ

ϮϬϭϮͲϭ

ϮϬϭϮͲϮ

ϮϬϭϮͲϯ

ϮϬϭϮͲϰ

ϮϬϭϮͲϱ

ϮϬϭϮͲϳ

ϮϬϭϮͲϴ

ϮϬϭϮͲϵ

ϮϬϭϮͲϭϬ ϮϬϭϮͲϭϭ

ϮϬϭϮͲϭϮ

U

V

S

Ϭ͕Ϭ

S

ϭ͕ϭ

S

Ϯ͕Ϯ

ϮϬϭϮͲϲ

S

Ϭ͕Ϭ

S

ϭ͕ϭ

S

Ϯ͕Ϯ

図 4 contains(A, B)

表 1 Allen の時区間関係

Allen

の時区間関係

2 つの時区間の始点，終点の条件

bef ore(A, B)

A.T

E

< B.T

S

meets(A, B)

A.T

E

= B.T

S

overlaps(A, B)

A.T

S

< B.T

S

< A.T

E

< B.T

E

during(A, B)

B.T

S

< A.T

S

∧ A.T

E

< B.T

E

starts(A, B)

A.T

S

= B.T

S

∧ A.T

E

< B.T

E

af ter(A, B)

B.T

E

< A.T

S

met-by(A, B)

A.T

S

= B.T

E

overlapped-by(A, B) B.T

S

< A.T

S

< B.T

E

< A.T

E

f inishes(A, B)

B.T

S

< A.T

S

∧ A.T

E

= B.T

E

equal(A, B)

A.T

S

= B.T

S

∧ A.T

E

= B.T

E

f inished-by(A, B)

A.T

S

< B.T

S

∧ A.T

E

= B.T

E

started-by(A, B)

A.T

S

= B.T

S

∧ B.T

E

< A.T

E

contains(A, B)

A.T

S

< B.T

S

∧ B.T

E

< A.T

E

を辿ることができない．

Allen

の時区間関係は

13 個の関係で

構成されているが，そのうち

12 個に対しても同様である．

［例

3.2 ］時間範囲

[2012-1, 2012-12]

であるリレーション

r

と，

[2012-2, 2012-12]

であるリレーション

s

を入力とする．各

_OIP

Configuration

を

(r, 3)

と

(s, 3)

とする．このとき

r

と

s

のパー

ティションの一部とタプルの一部を図

4 に示す．

r

のパーティ

ション

p

1,1

に存在するタプル

r

と，

contains(A, B)

の関係に

あるタプル

s

が格納されている可能性がある

s

のパーティショ

ンは，

p

0,0

と

p

1,1

である．よって，

2 回結合演算をする必要が

ある．

_□

このように，既存手法では

r

と

k

により

Configuration

が決ま

るため，結合対象となるパーティションの数が増えて効率的な

演算ができない場合がある．

そこで本研究では，これらの課題を解決するため，

Allen

の

時区間関係を条件とする結合演算に対して，効率的な計算を可

能にするデータ構造とそれに対するアルゴリズムを提案する．

4. 提案手法

本稿で扱う

Allen

の

13 個の時区間関係を表

1 に示す．この

13 個の関係の集合を

Θ =

{before, meets, overlaps, during,

starts, af ter, met-by, overlapped-by, f inishes, equal,

f inished-by, started-by, contains}

とする．本稿が対象とする

問題は，

2 つのリレーション

r

と

s

，及び関係

θ

∈ Θ

が入力とし

て与えられたとき，

_{{r ◦ s | r ∈ r ∧ s ∈ s ∧ θ(r.T, s.T ) = true}}

を効率良く求めることである．

前節で述べた課題を克服するために，パーティションを構

成するための設定を改良する．リレーション

r

に対する

OIP

(4)

表 2 q

i

′

,j

′

と結合演算が可能なパーティションの集合

θ

S(r, q

i

′

,j

′

, θ)

bef ore

{p

i,j

∈ P (r) | j

′

<

_{= i <}

_{= j <}

_{= k − 1}}

meets

{p

i,j

∈ P (r) | i = j

′

<

_{= j <}

_{= k − 1}}

overlaps

{p

i,j

∈ P (r) | i

′

<

_{= i <}

_{= j}

′

<

_{= j <}

_{= k − 1}}

during

{p

i,j

∈ P (r) | 0 <

_{= i <}

_{= i}

′

∧ j

′

<

_{= j <}

_{= k − 1}}

starts

{p

i,j

∈ P (r) | i = i

′

∧ j

′

<

_{= j <}

_{= k − 1}}

af ter

{p

i,j

∈ P (r) | 0 <

_{= i <}

_{= j <}

_{= i}

′

}

met-by

{p

i,j

∈ P (r) | 0 <

= i <

= i

′

= j

}

overlapped-by

{p

i,j

∈ P (r) | 0 <

_{= i <}

_{= i}

′

<

_{= j <}

_{= j}

′

}

f inishes

{p

i,j

∈ P (r) | 0 <

_{= i <}

_{= i}

′

∧ j = j

′

}

equal

{p

i,j

∈ P (r) | i = i

′

∧ j = j

′

}

f inished-by

{p

i,j

∈ P (r) | i

′

<

_{= i <}

_{= j}

′

= j

}

started-by

{p

i,j

∈ P (r) | i = i

′

<

_{= j <}

_{= j}

′

}

contains

{p

i,j

∈ P (r) | i

′

<

_{= i <}

_{= j <}

_{= j}

′

}

Configuration

は，

(r, k)

で表される．これに対して，提案手法

では，

(r, d, o)

を入力として与える．ここで

d

はパーティショ

ンの最少構成区間の長さであり，

o

はある時刻である．パーティ

ションへの分割数は

k =

⌈

U

E

−o

d

⌉

で決められる．ここで

r

の時

間範囲

U

の始点

U

S

と

o

は，必ずしも一致するとは限らないこ

とに注意されたい．提案手法では，

2 つのリレーション

r

と

s

が与えられたとき，各リレーションに対して

(r, d, o)

と

(s, d, o)

によりパーティションの最少構成区間を構成する．ここで，

2 つのリレーションに対する

d

，及び

o

は同一の値が用いられる．

これにより，

r

のあるパーティション

p

r

i,j

と

r

のあるパーティ

ション

p

s

i,j

は等しくなるので，前節で述べた

2 つ目の課題を克

服することができる．

P (r)

を

r

のパーティションの集合とする．

i

′

番目から

j

′

番

目のパーティションに跨るパーティション

q

i

′

,j

′

と時区間関係

θ

∈ Θ

が与えられたとき，

θ(q

i

′

,j

′

, p

i,j

)

を満たす

r

のパーティ

ションの集合を

S(r, q

i

′

,j

′

, θ)

とする．すなわち

S(r, q

i

′

,j

′

, θ) =

{p

i,j

∈ P (r) | θ(q

i

′

,j

′

, p

i,j

) = true

} (1)

である．

θ = equal

のとき，式

(1)

は

S(r, q

i

′

,j

′

, equal) =

{p

i,j

∈ P (r) | i = i

′

∧ j = j

′

}

となる．これは

θ

として

equal

が指定されたとき，

q

i

′

,j

′

に含ま

れるタプルと結合可能なタプルを含むパーティションが

p

i

′

,j

′

のみであることを意味している．同様にして，

Θ

の各要素に対

して，

S(r, q

i

′

,j

′

, θ)

をまとめたものが表

2 である．ここで，す

べての

θ

∈ Θ

に対して

S(r, q

i

′

,j

′

, θ)

が

o

や

d

に依存しないこ

とに注意されたい．これに対して，既存手法では，補題

2.4 に

示されたように，クエリ区間と結合可能なタプルを含むパー

ティションを求めるには，パーティションの最少構成区間の長

さと

r

の時間範囲の始点が必要になる．

図

5 は

S(r, q

i

′

,j

′

, θ)

が返すパーティション

p

i,j

に相当する点

(i, j)

の集合が存在する領域を図示したものである．いずれの領

域も連続する

1 つの凸領域である．この領域の点

(i, j)

を効率

ĞƋƵĂů

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ŬͲϭ

ŝ͛

ũ͛

ŝ͛

ũ͛

ŝ

ũ

ĨŝŶŝƐŚĞĚͲďǇ

ƐƚĂƌƚĞĚͲďǇ

ĨŝŶŝƐŚĞƐ

ŽǀĞƌůĂƉƉĞĚͲďǇ

ŽǀĞƌůĂƉƐ

ŵĞƚͲďǇ

ŵĞĞƚƐ

ĂĨƚĞƌ

ĚƵƌŝŶŐ

ĐŽŶƚĂŝŶƐ

ďĞĨŽƌĞ

ƐƚĂƌƚƐ

ŬͲϭ

図 5 q

_i

′

,j

′

と結合演算が可能な領域

良く返すために，図

6 に示す

Partition Array

を用いる．図

6 は

k = 4

の場合の

Partition Array

である．

Partition Array

は

2 次配列であり，その

(i, j)

要素がパーティション

p

i,j

に相

当する．全要素のうち，タプルが存在するパーティションに相

当する要素は青色で描かれている．また，パーティション

p

i,j

に対して

i <

_{= j}

を満たすので，この図の右下三角領域は空と

なる．空のパーティションを辿ることなく，

S(r, q

i

′

,j

′

, θ)

を求

めるために，各要素は

down

と

right

のリンクをもつ．また，

p

0,j

や

p

i,k

−1

が空の場合もあるため，

H Index

と

V Index

と

いうリンクの配列をもち，各行，各列の要素のうち，空でない

Allenの時区間関係を条件とする時区間データの効率的な結合演算手法

DEIM Forum 2016 D3-1