6_Temporal_Database

Bitemporal Conceptual Data Model (BCDM)

BCDM bertujuan menangkap semantik esensial dari relasi time-varying (bitemporal) — model ini bukan dimaksudkan untuk presentasi, penyimpanan, atau evaluasi query secara langsung. Oleh karena itu BCDM adalah model konseptual, bukan model representasional (fisik).

Conceptual (semantics) model vs representational (physical, performance-relevant) model — dibahas lebih lanjut di Representational Model of BCDM.
BCDM ditekankan penggunaannya untuk desain basis data dan sebagai basis bahasa query.

Karakteristik BCDM

Mendukung valid time dan transaction time sekaligus (bitemporal).
Kedua domain waktu bersifat linear dan diskret:
- Domain valid-time: $D_{V T} = {t_{1}, t_{2}, \dots, t_{k}}$
- Domain transaction-time: $D_{TT} = {t_{1}^{'}, t_{2}^{'}, \dots, t_{j}^{'}} \cup {U C}$ — dengan UC (Until Changed) sebagai penanda bahwa fakta masih current (belum di-update/dihapus).
Model bersifat point-based (tidak dapat menangkap semantik period-based secara langsung — lihat Temporal Database Introduction untuk perbandingan point-based vs period-based).

Bitemporal chronon adalah pasangan chronon transaction-time dan valid-time: $(tt, v t)$ . Bitemporal element adalah himpunan bitemporal chronon.

Timestamping pada BCDM bersifat tuple-timestamping: setiap tuple memiliki satu atribut timestamp $T$ yang domainnya adalah himpunan bitemporal element.

Skema dan Tuple BCDM

Diberikan atribut eksplisit (non-timestamp) $D_{A} = {A_{1}, \dots, A_{n}}$ :

$BCDM Schema : (A_{1}, A_{2}, \dots, A_{n}, T)$ $BCDM Tuple : x = (a_{1}, a_{2}, \dots, a_{n}, t_{b})$

Aturan penting: tuple value-equivalent (memiliki nilai atribut eksplisit yang identik) tidak diperbolehkan ada lebih dari satu dalam relasi BCDM. Konsekuensinya: seluruh histori sebuah fakta terkandung dalam satu tuple.

Contoh: Informasi Pegawai/Departemen

Misal pegawai Jake dipekerjakan di departemen shipping (Ship) dari valid time 10 hingga 15, dan fakta ini menjadi current di basis data pada transaction time 5. Sebelum ada penghapusan, transaction-time-nya masih UC:

Emp   Dept   T
Jake  Ship   {(UC,10), ..., (UC,15)}

Ketika terjadi koreksi (mis. departemen personalia menemukan bahwa Jake sebenarnya dipekerjakan dari valid time 5 hingga 20, dikoreksi mulai transaction time 10; lalu dikoreksi lagi kembali ke versi awal pada transaction time 15), bitemporal element pada tuple tersebut akan terus bertambah mencerminkan semua koreksi yang tercatat — direpresentasikan secara visual sebagai region pada bidang VT×TT.

Ketika Jake dipindahkan ke departemen Load (fakta lama (Jake,Ship) dihapus secara logis dari state current, fakta baru (Jake,Load) disisipkan) dan pegawai baru Kate dipekerjakan di Ship, relasi bitemporal pada transaction time 20 berisi tiga fakta:

Emp   Dept   T
Jake  Ship   {(5,10), ..., (5,15), (9,10), ..., (9,15), (10,5), ..., (10,20),
              (14,5), ..., (14,20), (15,10), ..., (15,15), (19,10), ..., (19,15)}
Jake  Load   {(UC,10), ..., (UC,15)}
Kate  Ship   {(UC,25), ..., (UC,30)}

Diagram berikut mengilustrasikan region bitemporal (pada bidang VT×TT) dari ketiga fakta di atas:

Update dalam BCDM

Tiga jenis operasi update: insert, update (ts_update), dan delete.

Insert: mencatat fakta $(a_{1}, \dots, a_{n})$ yang belum tercatat sebagai current di relasi $r$ . Tiga kasus:
1. Jika $(a_{1}, \dots, a_{n})$ belum pernah tercatat sama sekali → tuple baru disisipkan.
2. Jika $(a_{1}, \dots, a_{n})$ pernah menjadi bagian dari state current sebelumnya (tapi sudah dihapus) → tuple yang mencatatnya di-update (ditambahkan bitemporal chronon baru).
3. Jika $(a_{1}, \dots, a_{n})$ sudah current saat ini → tidak perlu modifikasi (insersi ditolak).

$in ser t (r, (a_{1}, \dots, a_{n}), t_{v}) = ⎩ ⎨ ⎧ r \cup {(a_{1}, \dots, a_{n} ∣ {U C} \times t_{v})} r - {(a_{1}, \dots, a_{n} ∣ t_{b})} \cup {(a_{1}, \dots, a_{n} ∣ t_{b} \cup {{U C} \times t_{v}})} r jika ∄ t_{b} ((a_{1}, \dots, a_{n} ∣ t_{b}) \in r) jika \exists t_{b} (\dots) \land ∄ (U C, c_{v}) \in t_{b} selainnya$

ts_update: rutin khusus untuk menambahkan chronon baru seiring berjalannya waktu (clock tick) — diterapkan ke semua relasi bitemporal pada setiap detak waktu. Setiap bitemporal chronon dengan transaction time UC menghasilkan chronon tambahan dengan UC diganti nilai transaction time saat ini:

ts_update(r, c_t):
    for each x in r
        for each (UC, c_v) in x[T]
            x[T] <- x[T] ∪ {(c_t, c_v)}

Delete: penghapusan logis dari state valid-time current — menghapus semua chronon $(U C, c_{v})$ dari timestamp tuple. Timestamp tidak lagi diperluas oleh ts_update selanjutnya, sehingga tuple tidak lagi muncul di state valid-time masa depan.

$d e l e t e (r, (a_{1}, \dots, a_{n})) = {r - {(a_{1}, \dots, a_{n} ∣ t_{b})} \cup {(a_{1}, \dots, a_{n} ∣ t_{b} - uc_ts (t_{b}))} r jika \exists t_{b} (\dots) selainnya$ dengan $uc_ts (t_{b}) = {(U C, c_{v}) ∣ (U C, c_{v}) \in t_{b}}$ .

Modify: modifikasi tuple current, didefinisikan sebagai kombinasi delete lalu insert:

$m o d i f y (r, (a_{1}, \dots, a_{n}), t_{v}) = in ser t (d e l e t e (r, (a_{1}, \dots, a_{n})), (a_{1}, \dots, a_{n}), t_{v})$

BCDM Pro dan Kontra

Kelebihan:

Karena tuple value-equivalent tidak diperbolehkan, seluruh histori sebuah fakta terkandung dalam tepat satu tuple.
Relasi yang berbeda secara sintaksis pasti memiliki isi informasi berbeda, dan sebaliknya.

Kekurangan:

Representasi internal dan tampilan ke pengguna kurang baik untuk informasi temporal.
Timestamp tuple yang panjangnya bervariasi dan voluminous sulit dikelola secara langsung.
Nilai timestamp sulit dipahami dalam format BCDM mentah (himpunan chronon individual).

Karena kekurangan ini, dibutuhkan model representasional yang lebih praktis untuk implementasi — lihat Representational Model of BCDM.

Aljabar Relasional untuk BCDM

Aljabar relasional untuk BCDM menyediakan bahasa operasional bagi struktur data BCDM, dengan operator standar yang diperluas:

$π_{D}^{B} : r \to r σ_{P}^{B} : r \to r \cup^{B} : r \times r \to r ⋈^{B} : r \times r \to r -^{B} : r \times r \to r$ $ρ_{t}^{B} : r \to r_{v t} τ_{t}^{B} : r \to r_{tt}$

Temporal Projection

Memproyeksikan relasi $r$ dengan atribut non-timestamp $A_{1}, \dots, A_{n}$ ke subset atribut $D$ . Perhitungan timestamp hasil harus memenuhi dua aturan: semua chronon dari tuple value-equivalent di $r$ harus disertakan, dan tidak ada chronon spurious (tambahan tak-sah) yang muncul:

$π_{D}^{B} (r) = {z^{(∣ D ∣ + 1)} ∣ \exists x \in r (z [D] = x [D]) \land \forall y \in r (y [D] = z [D] \Rightarrow y [T] \subseteq z [T]) \land \forall t \in z [T] \exists y \in r (y [D] = z [D] \land t \in y [T])}$

Temporal Selection

Memilih tuple dari $r$ yang memenuhi predikat $P$ pada atribut non-timestamp:

$σ_{P}^{B} (r) = {z ∣ z \in r \land P (z [A])}$

Temporal Union

Menggabungkan tuple dari dua relasi $r_{1}, r_{2}$ dengan skema yang kompatibel. Klausa pertama menangani tuple value-equivalent di kedua relasi (timestamp digabung dengan union); klausa kedua/ketiga menangani tuple yang hanya ada di salah satu relasi:

$r_{1} \cup^{B} r_{2} = {z^{(n + 1)} ∣ (\exists x \in r_{1} \exists y \in r_{2} (z [A] = x [A] = y [A] \land z [T] = x [T] \cup y [T])) \lor (\exists x \in r_{1} (z [A] = x [A] \land \neg\exists y \in r_{2} (\dots)) \land z [T] = x [T]) \lor \dots}$

Temporal Difference

Menghitung tuple yang ada di $r_{1}$ tetapi tidak ada di $r_{2}$ . Timestamp hasil dihitung dari set difference bitemporal element, bergantung apakah ditemukan tuple value-equivalent di $r_{2}$ atau tidak:

$r_{1} -^{B} r_{2} = {z^{(n + 1)} ∣ \exists x \in r_{1} ((z [A] = x [A]) \land ((\exists y \in r_{2} (z [A] = y [A]) \land z [T] = x [T] - y [T]) \lor (\neg\exists y \in r_{2} (\dots) \land z [T] = x [T])))}$

Temporal Join

Dua tuple bergabung bila cocok pada atribut join dan memiliki timestamp bitemporal-element yang overlap. Timestamp hasil adalah irisan timestamp kedua tuple argumen:

$r ⋈^{B} s = {z^{(n + l + m + 1)} ∣ \exists x \in r \exists y \in s (x [A] = y [A] \land x [T] \cap y [T] \neq = \emptyset \land z [A] = x [A] \land z [B] = x [B] \land z [C] = y [C] \land z [T] = x [T] \cap y [T])}$

Contoh: join relasi dept (siapa bekerja di departemen mana) dengan relasi mgr (siapa manajer tiap departemen) menghasilkan relasi “siapa dikelola oleh siapa”, dengan timestamp hasil berupa overlap region kedua tuple sumber (dapat divisualisasikan sebagai irisan dua region VT×TT).

Timeslice Operators

Transaction-timeslice $ρ_{t_{1}}^{B}$ : memilih relasi pada transaction time $t_{1}$ (tidak melebihi waktu sekarang), mengembalikan relasi valid-time (menghilangkan dimensi transaction time).
Valid-timeslice $τ_{t_{2}}^{B}$ : memilih relasi pada valid time $t_{2}$ , mengembalikan relasi transaction-time.

$ρ_{t_{1}}^{B} (r) = {z^{(n + 1)} ∣ \exists x \in r (z [A] = x [A] \land z [T_{v}] = {t_{2} ∣ (t_{1}, t_{2}) \in x [T]} \land z [T_{v}] \neq = \emptyset)}$ $τ_{t_{2}}^{B} (r) = {z^{(n + 1)} ∣ \exists x \in r (z [A] = x [A] \land z [T_{t}] = {t_{1} ∣ (t_{1}, t_{2}) \in x [T]} \land z [T_{t}] \neq = \emptyset)}$

Operator ini analog dengan operator timeslice pada basis data temporal biasa, memungkinkan “memotong” relasi bitemporal menjadi snapshot pada satu titik di salah satu dimensi waktu.

Sumber

C. S. Jensen, M. D. Soo, R. T. Snodgrass: “Unifying temporal data models via a conceptual model”, Information Systems, vol. 19, no. 7, 1994.
J. Gamper: “Chapter 4: Relational Algebra for Bitemporal Relations”, TSDB course materials, Free University of Bozen, 2012.

Flashcard

flashcards Apa tujuan utama BCDM dan mengapa disebut model konseptual? :: Menangkap semantik esensial relasi time-varying; disebut konseptual karena tidak dimaksudkan untuk presentasi/penyimpanan/evaluasi query langsung, melainkan basis desain dan bahasa query. Apa itu bitemporal chronon dan bitemporal element? :: Bitemporal chronon = pasangan (tt, vt) satu chronon transaction-time dan satu chronon valid-time; bitemporal element = himpunan bitemporal chronon. Apa arti UC (Until Changed) pada domain transaction-time BCDM? :: Penanda bahwa fakta tersebut masih current (belum diubah/dihapus) di basis data. Kenapa BCDM tidak mengizinkan tuple value-equivalent lebih dari satu dalam relasi? :: Agar seluruh histori satu fakta terkandung dalam tepat satu tuple, sehingga relasi yang berbeda secara sintaksis pasti berbeda informasinya (dan sebaliknya). Bagaimana operasi delete didefinisikan secara logis dalam BCDM? :: Menghapus semua chronon (UC, cv) dari timestamp tuple, sehingga timestamp tidak lagi diperluas oleh ts_update berikutnya (tuple tidak muncul di state valid-time masa depan). Bagaimana operasi modify didefinisikan dalam BCDM? :: Sebagai kombinasi delete kemudian insert: modify(r, fakta, tv) = insert(delete(r, fakta), fakta, tv). Sebutkan dua kelemahan utama BCDM sebagai model praktis :: Representasi internal/tampilan kurang baik, dan timestamp tuple yang panjangnya bervariasi/voluminous sulit dikelola serta sulit dipahami pengguna. Bagaimana timestamp hasil dihitung pada temporal join BCDM? :: Sebagai irisan (intersection) dari timestamp bitemporal-element kedua tuple argumen yang cocok pada atribut join dan saling overlap. Apa perbedaan transaction-timeslice dan valid-timeslice pada BCDM? :: Transaction-timeslice memilih relasi pada suatu transaction time tertentu (hasil = relasi valid-time); valid-timeslice memilih relasi pada suatu valid time tertentu (hasil = relasi transaction-time).

Catatan Kuliah

Penjelajah

6_Temporal_Database_BCDM