8_SpatioTemporal

Definisi dan Motivasi

Spatio-temporal database adalah basis data yang mengelola data spasial yang geometrinya berubah terhadap waktu. Contoh aplikasi: pelacakan objek bergerak (kendaraan, pesawat, orang — biasanya menempati satu posisi pada suatu waktu), basis data jaringan komunikasi nirkabel yang hanya eksis sementara pada suatu wilayah, indeks spesies pada suatu wilayah geografis (spesies baru muncul/migrasi/punah dari waktu ke waktu), pelacakan historis aktivitas tektonik, dan basis data video/animasi. Contoh nyata: perubahan garis pantai dan kota Banda Aceh sebelum/sesudah Tsunami 2004, atau peta banjir Jakarta dari waktu ke waktu.

Riset spatial database dan temporal database berkembang terpisah pada dekade 1980-90an; pada 1990-an keduanya mulai disatukan menjadi spatio-temporal data model. Upaya awal menambahkan atribut waktu ke model spasial atau menambahkan objek spasial ke model temporal; kemudian berkembang model ST yang memperlakukan ruang dan waktu setara sebagai dimensi/domain yang serupa (unified ST view). Hingga kini, belum ada produk RDBMS komersial dengan ekstensi spatio-temporal penuh.

Spatio-temporal database dapat dipandang sebagai:

Temporal database khusus: memiliki semua fitur basis data temporal, dengan atribut yang juga bisa bertipe spasial.
Ekstensi spatial database: objek berubah (bukan statis); pada setiap timestamp tetap merupakan spatial database konvensional.
Tipe basis data baru: membutuhkan representasi ruang & waktu yang efisien, model data baru, bahasa query baru, pemrosesan query & indeks baru, serta GUI khusus untuk dataset spatio-temporal.

Rekap Semantik Temporal dan Spasial

Semantik temporal (lihat Temporal DB Introduction): structure (linear/branching), density (discrete/dense/continuous), granularity, dimension (snapshot/valid-time/transaction-time/bitemporal), timestamp type (point/period/temporal element), timestamping (tuple/attribute), operasi temporal (projection, selection, join, union, set difference, timeslice).

Semantik spasial (lihat Intro Spatial DB & Spatial Data Modeling): model ruang geografis (entity/feature-based vs field/space-based), spatial data types (point, line, region), representation mode (tesselation, vector, half-plane), geometri kumpulan objek (spaghetti, network, topological), operasi spatial ADT, dan 8 hubungan topologis (disjoint, meet, overlap, equal, covers, coveredBy, contains, inside).

Semantik Spatio-Temporal

Spatio-temporal database mengelola data spasial yang berubah terhadap waktu. Perubahan mengacu pada: pergerakan (motion), penyusutan, pertumbuhan, transformasi bentuk, pemisahan (split), penggabungan (merge), menghilang, atau muncul kembali.

Tipe perubahan:

Diskret: mis. perencanaan tata kota — munculnya/hilangnya bangunan pada titik waktu tertentu.
Kontinu: mis. objek bergerak (kendaraan) — posisi berubah secara terus-menerus.

Sebuah objek spatio-temporal dapat mengalami delapan kemungkinan tipe perubahan kombinasi dari tiga aspek: geometri, topologi, dan atribut (mencakup kombinasi “no change” hingga “change in geometry, topology, & attribute”):

Evolusi dalam Ruang dan Waktu

Diperlukan fungsi untuk mengamati dan mendeskripsikan pergerakan/perubahan objek dalam ruang secara independen dari identitas objeknya (mis. evolusi, penciptaan, fusi), termasuk kecepatan dan/atau akselerasi pergerakan objek spatio-temporal. Kesulitan muncul karena objek berbeda berevolusi pada kecepatan berbeda: objek fisik dianggap bergerak/berubah secara kontinu sepanjang masa hidupnya, sedangkan event yang berulang harus dipandang secara diskret.

Space-Time Topology, Object Identity, dan Dimensionality

Space-time topology: relasi yang didefinisikan sebagai kombinasi relasi spasial dengan relasi temporal Allen, memperkenalkan metrik seperti jarak, arah, dan perubahan ukuran suatu objek dari waktu ke waktu, serta hubungan topologis antarobjek spasial yang berevolusi sepanjang suatu periode.
Object identity: kapan “perubahan” cukup signifikan sehingga suatu objek tidak lagi dianggap sebagai objek yang sama? Termasuk isu pemisahan (split) dan penyatuan (unify) objek.
Dimensionality: spatial database murni bekerja pada 2 dimensi; ditambah dimensi waktu menjadi volumetrik 3 dimensi atau lebih.

Klasifikasi Data Spatio-Temporal

#	Kategori	Contoh
1	Event in space and time	Penemuan arkeologi, kecelakaan pesawat, letusan gunung berapi, gempa bumi (skala besar di mana durasi tidak relevan)
2	Location valid for a certain period of time	Kota yang dibangun pada suatu waktu (masih ada atau sudah hancur), lokasi konstruksi (gedung, jalan tol)
3	Set of location events	Kumpulan letusan gunung berapi tahun lalu
4	Stepwise constant locations	Ibu kota suatu negara, akomodasi wisatawan selama perjalanan
5	Moving entities (moving points)	Orang, pesawat, mobil
6	Region events in space and time	Kebakaran hutan (skala besar)
7	Regions valid for some period of time	Area yang ditutup sementara setelah kecelakaan lalu lintas
8	Set of region events	Olimpiade (secara kolektif, skala besar)
9	Stepwise constant regions	Negara, real estat, tata guna lahan pertanian
10	Moving entities with extent (moving region)	Pertumbuhan hutan, kebakaran hutan (skala kecil)

Kategori 5 dan 10 (moving points dan moving regions) menjadi fokus utama pada model Moving Object Database — lihat catatan terpisah.

Query Spatio-Temporal

Query tentang lokasi, properti spasial, dan hubungan spasial (melibatkan objek referensi statis), mis. atribut independen ruang/waktu (“siapa pemilik lahan ini?”), point query, range/distance-based query, nearest neighbor, dan topological query (“jalan mana yang melintasi suatu area?”).
Query tentang waktu, properti temporal, dan hubungan temporal, mis. simple temporal query (“apa state fitur spasial pada waktu $t$ ?”), temporal range query (“apa yang terjadi pada fitur tersebut selama periode tertentu?”), dan temporal relationship query (“stadion mana di Athena yang dibangun bersamaan dan pembangunannya kurang dari 6 bulan?”).
Query tentang perilaku dan hubungan spatio-temporal, dengan subkategori:
- Query spatio-temporal sederhana dengan objek referensi berubah diskret atau bergerak: distance-based query (“temukan orang yang lewat dekat saya kemarin”), similarity-based query (“temukan trajectory yang mirip dengan yang saya lalui hari ini”).
- Query range/join spatio-temporal: distance-join (“3 restoran terdekat dari armada saya”), similarity-join (“2 pasang trajectory paling mirip di bulan Januari”).
- Query perilaku spatio-temporal dengan operator unary, mis. “berapa kecepatan rata-rata pada malam Sabtu?”, “kapan/di mana kebakaran mencapai laju penyebaran maksimal?“.

Model Data Spatio-Temporal

Riset spatio-temporal data model relatif muda, tetapi telah menghasilkan banyak model, di antaranya: The Snapshot Model (Langran, 1988), Space-Time Composite (STC) (Langran, 1988), model berbasis Simple-Time Stamping (Hunter & Williamson, 1990), Three-Domain Model (Yuan, 1994/1996), History Graph Model (Renolen, 1996), Spatio-Temporal Entity-Relationship (STER) Model (Tryfona & Jensen, 1999/2000), dan Object-Relationship (O-R) Model (Claramunt et al., 1998).

Dua model dibahas lebih mendalam berdasarkan tipe perubahan:

Perubahan diskret: Spatio-bitemporal Object Model (Worboys et al., 1990) dan Event-Based Models (Peuquet et al., 1994) — dibahas di bawah.
Perubahan kontinu: Moving Object Data Models (Erwig, Güting, Schneider, et al., sejak 1999) — dibahas di catatan terpisah.

Manfaat Pendekatan Object-Oriented

Menurut Montgomery (1995), pemodelan spatio-temporal berorientasi objek memiliki keunggulan: satu objek dapat merepresentasikan seluruh histori suatu entitas, query menjadi sederhana karena hanya berurusan dengan satu objek per entitas, penanganan data temporal lebih efisien, dan penanganan data spasial & temporal menjadi seragam.

Studi Kasus: Kepemilikan Lahan (Land Ownership)

Kasus ilustratif: sebidang lahan (jalan, parsel milik beberapa pemilik) berevolusi dari tahun 1908 hingga 1974 — parsel dibeli/dijual, digabung, dipisah, bangunan dihancurkan/dibangun, jalan baru dibangun melintasi parsel yang ada, hingga terjadi illegal possession sebagian parsel. Kasus ini menjadi contoh baku untuk mengilustrasikan model Spatio-Bitemporal Object.

Spatio-Bitemporal Objects (Worboys et al., 1990)

Memperkenalkan spatio-bitemporal object (ST object): objek terpadu dengan cakupan spasial dan bitemporal sekaligus.

Bitemporal Element (BTE): union dari himpunan berhingga cartesian product periode berbentuk $I_{T} \times I_{V}$ , dengan $I_{T}$ = periode pada domain transaction time, $I_{V}$ = periode pada domain valid time. Digambarkan sebagai region pada bidang $T_{T} \times T_{V}$ (mirip visualisasi bitemporal element pada BCDM), mencerminkan koreksi bertahap suatu fakta spasial dari waktu ke waktu.
Objek spasial dimodelkan sebagai simplicial complex: sebuah d-simplex adalah objek minimal berdimensi $d$ (0-simplex = titik, 1-simplex = segmen garis, 2-simplex = segitiga, 3-simplex = tetrahedron); simplicial complex adalah himpunan berhingga simplex yang irisan sepasang simplex-nya selalu berupa face (muka) dari keduanya.
ST-simplex: pasangan terurut $(S, T)$ dengan $S$ = simplex, $T$ = BTE (label bitemporal yang ditempelkan ke komponen simplicial complex).
ST-complex $C$ : himpunan berhingga ST-simplex yang memenuhi properti tertentu, salah satunya proyeksi spasial dari ST-simplex di $C$ harus saling disjoint.

Diagram berikut mengilustrasikan anotasi boundary dan face suatu parsel lahan dengan BTE (contoh ST-complex dari studi kasus kepemilikan lahan):

Operasi Spatio-Bitemporal

Operasi	Nama	Signature
$=$	ST-equal	ST-complex × ST-complex → bool
$\subset_{ST}$	ST-subset	ST-complex × ST-complex → bool
$\partial$	ST-boundary	ST-complex → ST-complex
$π_{s}$	S-project	ST-complex → S-complex
$π_{t}$	T-project	ST-complex → BTE
$\times_{β}$	ST-β-product	ST-complex × ST-complex → ST-complex
$\cup_{ST}$	ST-union	ST-complex × ST-complex → ST-complex
$\cap_{ST}$	ST-intersection	ST-complex × ST-complex → ST-complex
$∖_{ST}$	ST-difference	ST-complex × ST-complex → ST-complex
$σ_{X}^{s}$	S-select	ST-complex → ST-complex
$σ_{ϕ}^{t}$	T-select	ST-complex → ST-complex

Event Based Models

Peuquet & Wentz (1994) mengusulkan pendekatan analisis berbasis waktu (time-based analysis) untuk data spatio-temporal, sebagai pelengkap analisis berbasis lokasi dan berbasis objek, diimplementasikan pada prototipe TGIS TEMPEST. Dimulai dari state awal (base map), event dicatat secara berantai dalam urutan waktu menaik, masing-masing terkait dengan daftar perubahan sejak pembaruan terakhir.

Peuquet & Duan (1995) mengimplementasikan pendekatan raster berbasis event yang disebut Event Oriented Spatio-Temporal Data Model (ESTDM):

Mengelompokkan layer bertimestamp untuk menunjukkan observasi dari satu event dalam urutan temporal.
Menyimpan perubahan relatif terhadap state sebelumnya (delta), bukan snapshot penuh pada setiap waktu — struktur terdiri atas Header (menunjuk base map) dan rangkaian Event (tiap event menyimpan komponen lokasi mana saja yang berubah beserta nilai barunya).

Tipe query khas pada model event-based (untuk satu sekuens temporal): mencari lokasi yang berubah pada waktu $t_{i}$ tertentu (dengan/tanpa nilai target tertentu), mencari lokasi yang berubah antara $t_{i}$ dan $t_{j}$ (dengan/tanpa nilai target), menghitung total perubahan area ke suatu nilai antara $t_{i}$ dan $t_{j}$ , menguji apakah lokasi $(x, y)$ berubah pada/antara suatu waktu, dan menentukan kapan lokasi $(x, y)$ berubah ke nilai baru.

Sumber

N. Pelekis, B. Theodoulidis, I. Kopanakis, Y. Theodoridis: “Literature Review of Spatio-Temporal Database Models”, 2004.
G. Kollios: “Spatio-Temporal Databases”, course materials, Boston University, 2011.
R. H. Güting, M. Schneider: “Moving Object Databases”, Morgan Kaufmann, 2005.

Flashcard

flashcards Sebutkan tiga cara memandang spatio-temporal database :: (1) Temporal database khusus dengan atribut spasial, (2) ekstensi spatial database dengan objek yang berubah, atau (3) tipe basis data baru yang butuh representasi/model/query/indeks khusus. Apa perbedaan perubahan diskret dan kontinu pada objek spatio-temporal? :: Diskret: perubahan terjadi pada titik waktu tertentu (mis. bangunan muncul/hilang); kontinu: perubahan terus-menerus sepanjang waktu (mis. objek bergerak). Sebutkan tiga aspek yang bisa berubah pada objek spatio-temporal (dasar 8 kombinasi tipe perubahan) :: Geometri, topologi, dan atribut. Apa itu Bitemporal Element (BTE) pada model Spatio-Bitemporal Object (Worboys et al.)? :: Union dari himpunan berhingga cartesian product periode berbentuk IT × IV (interval transaction-time × interval valid-time). Apa itu ST-complex dan salah satu propertinya? :: Himpunan berhingga ST-simplex (pasangan simplex + BTE); salah satu propertinya adalah proyeksi spasial antar-ST-simplex dalam satu ST-complex harus saling disjoint. Apa perbedaan pendekatan penyimpanan ESTDM (event-based) dibanding menyimpan snapshot penuh tiap waktu? :: ESTDM hanya menyimpan perubahan (delta) relatif terhadap state sebelumnya untuk tiap event, bukan snapshot lengkap pada setiap titik waktu. Sebutkan dua kategori dalam klasifikasi data spatio-temporal yang menjadi fokus Moving Object Database :: Moving entities/moving points dan moving entities with extent/moving region. Apa maksud “object identity” sebagai tantangan dalam evolusi objek spatio-temporal? :: Menentukan pada titik mana suatu perubahan (termasuk split/unify) membuat suatu objek tidak lagi dianggap sebagai objek yang sama.

Catatan Kuliah

Penjelajah

8_SpatioTemporal_Database