読者です 読者をやめる 読者になる 読者になる

BiTemporal Data Modelに入門中

BiTemporal Modelingについてちょっとだけ調べたりしたのでメモ。 基本的に Temporal
Data Models(ppt注意)Temporal Databasesを大幅に端折ったものに他の資料を少しだけ入れた感じの内容です。

Temporal Data Models

BiTemporal ModelingはTemporal Data Modelsという分野で研究されているモデリングの一種です。 Temporal Data Modelでは時間によって変わっていくデータを扱います。 ちなみにここでいうData ModelはData Structure+Query Languageを意味します。

データが時間によって変わるということは何らかのUpdate操作が必要です。一番単純な方法を考えるとDBのレコードを直接更新(無効になったデータは削除)することでUpdate操作を実現できそうです。 この方式を使う場合、DBはある瞬間におけるシステムの状態を保持していることになります。

一方で、データの変化を後から追跡したい場合には単純なUpdate処理に加えて履歴データを含めた更新処理を作り込むことになります。 例えば人事管理システムでは、このユーザーが今どの部署に在籍しているのか?も重要ですが、このユーザーは今までどんな部署に在籍していたのかという履歴も重要になるためこのような作り込みが必要になります。

データの変化を追跡可能にするためには履歴データを保存する必要があります。このとき、履歴データにはなんらかの意味での時刻を含める必要があります。 考えられる時刻にはtransaction time, valid time, publication time,…など様々な種類の時間が考えられます。 どういう時刻が必要とされるかはアプリケーション次第・・なのですが、valid timeとtransaction timeが重要というbroad consensusがあるようです。[1]

valid time, transaction timeとは

valid timeは、あるfactがtrueになる時刻のことです。 例えば「Johnは10/1に入社した」という事実があればvalid timeは10/1 ~ infinityとなります。 また、「Johnの給料は8/1から8/4まで10ドルだった」という事実を考えるとvalid timeは8/1~8/4となります。

valid timeは定義上どのようなデータにも存在し、DBに登録されているかどうかは関係がありません。(factがtrueになるかどうかが問題) また、期間が定まっていてもよいですし無期限でも構いません。

一方transaction timeは、DBにデータが存在した時間 = (insertされた時刻〜delete時刻された時刻)です。 例えば「Johnは10/1に入社した」というデータが10/5にinsertされ3/31にdeleteされた場合、transaction timeは10/5~3/31です。

4つのデータモデル

さきほど説明した2種類の時間を使うか使わないかで4つのデータモデルが考えられます。

  • どちらもなし => Snapshot Model
  • valid timeのみ => Valid Time Data Model
  • transactional timeのみ => Transactional Data Model
  • valid time & transactional timeの組み合わせ => BiTemporal Data Model

なおこれらのデータモデルを使ったDBにはそれぞれ名前がついているようです[3]

  • Historical DB → valid-time DB
  • Rollback DB → transaction-time DB
  • Temporal DB → bitemporal DB

4つのデータモデルについて

さて、それぞれについて見ていきます。   Snapshot Modelは時刻情報を保持しません。そのため履歴の追跡などは行えません。*1 ということで、ここからはSnapshot Model以外の3つについて見ていきます。

[1]のp.9にある例そのままですが、以下のようなケースを考えます。

  1. John was hired as a programmer (PRG) 
 with initial salary 2000 at time 1;
  2. John’s salary was raised to 3000 at time 3 
 (but recorded in the DB at time 4);
  3. John became a database administrator (DBA)
 at time 6.

Transaction-Time Model

transaction-time Modelで上記の例を考えると以下のようになります。

step1.(時刻1)

name job salary transaction_time
john PRG 2000 [1,NOW]

step2.(時刻4)

※1レコード目のtransaction-timeをNOWから3に更新することでdeleteを表現しています。

name job salary transaction_time
john PRG 2000 [1,3]
john PRG 3000 [4,NOW]

step3.(時刻6)

name job salary transaction_time
john PRG 2000 [1,3]
john PRG 3000 [4,5]
john DBA 3000 [6,Now]

transaction-timeではDBの記録時刻単位でしか保存できないのでデータの変更を遡って行うケースをうまく表現できません。 そのため本来は時刻3から給料が上がったはずのjohnの給料が実際には時刻4から反映されることになってしまいます。*2

Valid-Time Model

valid-timeでは以下のようになります。

step1.(時刻1)

name job salary valid_time
john PRG 2000 [1,NOW]

step2.(時刻4)

name job salary valid_time
john PRG 2000 [1,2]
john PRG 3000 [3,NOW]

step3.(時刻6)

name job salary valid_time
john PRG 2000 [1,2]
john PRG 3000 [3,5]
john DBA 3000 [6,Now]

valid-timeではfactの時刻を記録するため、transaction-timeのときと違い遡ったデータの更新を正確に表現できています。 これでいいような気もしますが、これだけだとどの時点のデータが遡って更新されたのかが判別できません。 step3でいうと2レコード目が遡って更新されたデータですが、これは1, 3レコード目となんら違いはない普通のデータに見えます。

しかし、時刻3でのDBにSELECTをかけたとするとvalid_time=3でのJohnの給料は2000になっているはずです。 一方で時刻4でのDBにSELECTをかけたとするとvalid_time=3でのJohnの給料は3000になっているはずです。

遡った修正があるとこういった乖離が起こるわけですが、乖離が実際に存在するかどうか?(あるデータに遡った更新があったかどうか)はValid-Time Modelでは分かりません。

BiTemporal Model

Valid-Time Modelでは遡ったデータの更新があったかどうかを追跡することができませんでした。 医療情報などの特に重要なデータを扱う場合、このような遡った更新による影響も含めて追跡したいことがあります。*3

データの変更を遡って行えるようにしつつ、どのデータが遡って更新されたのか、遡った更新の前はどんな状態だったのか、といった色々な種類の履歴を追跡できるのがBiTemporal Modelです。

前述したようにBiTemporal Modelはvalid-timeとtransaction-timeの両方を保存する方式です。 BiTemporal Modelでさきほどの例を表現すると以下のようなデータになります。

step1.(時刻1)

name job salary transaction_time valid_time
john PRG 2000 [1,Now] [1,Now]

step2.(時刻4)

name job salary transaction_time valid_time
john PRG 2000 [1,3] [1,Now]
john PRG 2000 [4,Now] [1,2]
john PRG 3000 [4,Now] [3,Now]

step3.(時刻6)

name job salary transaction_time valid_time
john PRG 2000 [1,3] [1,Now]
john PRG 2000 [4,Now] [1,2]
john PRG 3000 [4,5] [3,Now]
john PRG 3000 [6,Now] [3,5]
john DBA 3000 [6,Now] [6,Now]

transaction_time.Start > valid_time.Start となっているデータが後から更新されたデータと捉えることができます。(正確にはfactがtrueになった後にinsertされたデータ) step3での2, 3, 4レコード目が該当します。

読み方が少しむずかしいですがtransaction_timeを固定するとわかりやすいです。

  • transaction_time=1とすると、1~Nowの時点でjohnは(job = PRG, salary = 2000)です。
  • transaction_time=4とすると、1~2の時点でjohnは(job = PRG, salary = 2000)で、3~NOWの時点でjohnは(job = PRG, salary = 3000)です。
  • transaction_time=6とすると、1~2の時点でjohnは(job = PRG, salary = 2000)で、3~5の時点でjohnは(job = PRG, salary = 3000)で6~NOWの時点でjohnは(job = DBA, salary = 3000)です。

履歴の変更という観点で見るとstep3における1レコード目のvalid_timeが2レコード目のvalid_time = [1, 2]によって変更されたとみることができます。この変更がinsertされた時刻はtransaction_timeを見れば良いので4だとわかります。 3レコード目は要件にあった遡った更新で入れたいデータです。このデータのvalid_timeは4レコード目によってvalid_time = [3,5]に変更されたと見ることができます。

アプリケーションで最も用があると思われる今現在アプリケーション的に有効なデータはtransaction_timeを最新に固定すれば取得することができます。 また、transaction_timeを過去のものに固定すれば、その時点でDBが認識していたデータも取得できます。 もちろん、transaction_timeを固定すれば、その時点でDBが認識していたvalid_timeベースでの変更履歴を取得することもできるため、様々な追跡の要望に答えられます。

まとめ

  • DBに保存する時刻としてはtransaction-time/valid-timeの二種類が有用
  • transaction-time DBでは過去に遡ったデータの更新は難しい
  • valid-time DBでは過去に遡ったデータの更新は可能だが、遡って更新を行ったデータか行っていないデータかの判別が難しい
  • BiTemporal Dataでは遡ったデータの更新も更新自体の追跡も可能

etc..

Temporal Database機能はOracleでサポートされているようです。  PostgreSQLにもextensionで存在しているようでした。これらのDBサポートがどこまでやってくれてどのくらい便利なのかは未調査です。

今回は期間で時刻を区切る方法にしか言及しませんでしたがTimestampの方式も色々あるようです。他にもRDBっぽいデータの持ち方以外の方法など、話題が結構あってそれに対応するクエリ言語をどうするかといった部分もおもしろそうですがなんとなく一区切りついたのでまた気が向いたら調べようかなと思います。

参考

  1. Temporal
Data Models(ppt)
  2. Temporal Databases - Richard T. Snodgrass 1998
  3. Temporal Databases - Richard T. Snodgrass and Ilsoo Ahn 1986
  4. Temporal and Real-Time Databases: A Survey(ppt)
  5. Temporal Data and The Relational Model

*1:とはいえ追跡が不要ならこれで十分です。

*2:現実的にはupdated_atをいじったりして反映できそうでが、その場合はvalid-time modelで時刻を管理していると言えそうです。

*3:valid-timeとtransaction-timeの乖離が発生する他の例としては、ある時間にセンサーで観測したデータが地理的に別の地点にあるDBに保存されるケースが考えられます。観測したデータに加えてデータが何分遅れで到着したのかといったデータも欲しい場合はvalid-time, transaction-timeの片方のみでは表現できないのでBiTemporal Modelのような柔軟なモデリングが必要になる可能性があります。