4_Spatial_Queries

Spatial Queries

Query spasial menghubungkan operasi aljabar spasial dengan fasilitas bahasa query DBMS. Ada dua isu utama: (1) operasi fundamental (aljabar) untuk memanipulasi himpunan objek basis data, dan (2) input/output grafis.

Operasi Fundamental

Spatial selection — memilih objek yang memenuhi predikat spasial terhadap objek query:

-- Semua kota di Bavaria
select c.cname from cities c where c.center inside Bavaria.area
 
-- Semua sungai yang beririsan window tertentu
select r.* from rivers r where r.route intersects window
 
-- Kota besar dalam radius 100 km dari Hagen
select c.cname from cities c where dist(c.center, Hagen.center) < 100

Spatial join — membandingkan dua himpunan objek berdasarkan predikat pada atribut spasialnya:

-- Kota dalam radius 50 km dari sungai yang melewati Bavaria
select r.rname, c.cname from rivers r, cities c
where r.route intersects Bavaria.area and dist(r.route, c.area) < 50
 
-- Total populasi kota di Prancis
select sum(c.pop) from cities c, states s
where c.location inside s.area and s.name = 'France'

Spatial function application — menerapkan fungsi spasial ke setiap anggota himpunan:

select intersection(r.route, s.area)
from rivers r, states s
where r.name = 'Rhine' and s.name = 'Germany'

Operasi himpunan lain — beroperasi pada keseluruhan himpunan objek spasial, berada di antarmuka aljabar spasial dan aljabar objek DBMS:

Overlay: menghitung region-region elementer hasil overlay dua partisi.
Fusion: mengelompokkan objek berdasarkan nilai atribut tertentu.
Voronoi: dari himpunan titik $S$ , menghitung himpunan region — untuk setiap titik $p$ , region-nya berisi titik-titik bidang yang lebih dekat ke $p$ dibanding titik lain di $S$ .

Kebutuhan Input/Output Grafis

Berbeda dari DBMS tradisional yang menangani data alfanumerik, spatial DBMS memerlukan presentasi grafis: bagaimana menentukan input query (mis. window atau area query digambar di layar) dan bagaimana menampilkan hasil (overlay pada peta). Kebutuhan umum meliputi: tampilan hasil grafis, overlay grafis dari beberapa hasil query, tampilan konteks (peta latar), legenda, penempatan label, pemilihan skala, dan subarea untuk query interaktif.

Spatial Indexing

Mengapa Diperlukan?

Struktur indeks konvensional seperti B-tree tidak dirancang untuk query spasial: B-tree hanya mengelompokkan objek pada satu dimensi dan tidak menjaga kedekatan spasial (spatial proximity). Struktur indeks spasial berusaha mengelompokkan objek yang berdekatan secara ruang ke dalam data page yang sama. Tantangannya: ukuran (jumlah byte) untuk menyimpan objek spasial berukuran besar (garis, poligon) bervariasi.

MBR dan Strategi Filter-and-Refine

Solusi umum: menyimpan aproksimasi objek spasial di struktur indeks, biasanya berupa MBR (Minimum Bounding Rectangle) yang sejajar sumbu (axis-parallel). Representasi eksak (ER — Exact Representation) disimpan terpisah, dan indeks hanya menunjuk (pointer) ke ER tersebut.

Pendekatan aproksimasi ini menghasilkan strategi filter and refine dalam pemrosesan query:

Filter: gunakan indeks untuk menemukan semua aproksimasi yang memenuhi query, hasilnya berupa himpunan kandidat (superset dari objek yang benar-benar memenuhi predikat — beberapa objek sudah pasti memenuhi berdasar aproksimasi, sisanya perlu dicek).
Refine: muat representasi eksak dari kandidat, lalu uji apakah kandidat benar-benar memenuhi query (menyaring false hit).

Dua tipe aproksimasi:

Continuous approximation (mis. bounding box).
Grid approximation (dekomposisi objek menjadi sel-sel grid).

Dua Pendekatan Utama Spatial Indexing

Memetakan objek spasial ke ruang 1-D, lalu memakai teknik indeks standar, mis. Z-order + B-tree.
Struktur indeks spasial khusus (dedicated):
- Data organizing (mengelompokkan berdasarkan data), mis. R-tree.
- Space organizing (mengelompokkan berdasarkan ruang), mis. Quadtree.

1D Embedding via Space-Filling Curve (Z-order)

Ide dasar: ruang data dipartisi menjadi sel-sel grid, lalu dicari urutan linear untuk sel-sel tersebut sehingga sel yang berdekatan secara ruang juga berdekatan pada urutan linearnya (menjaga locality/proximity, dan mudah dihitung) — menggunakan space filling curve.

Z-order (juga disebut Morton order/bit interleaving) adalah pendekatan paling populer: setiap sel pada tiap level hierarki subdivisi memiliki bit string terkait yang panjangnya sesuai levelnya, dan urutan sel ditentukan oleh urutan leksikografis dari bit string tersebut. Objek/shape diapproksimasi menjadi himpunan sel-sel grid pada level tertinggi yang mungkin, menghasilkan himpunan bit string yang disebut z-elements, yang menjadi spatial key objek tersebut. Z-elements ini kemudian disimpan sebagai key pada B-tree biasa dalam urutan leksikografis, sehingga query containment/range dapat dijawab dengan menentukan z-elements dari rectangle query, lalu men-scan bagian leaf B-tree yang berprefiks sama.

Diagram berikut membandingkan Z-order dan Hilbert-curve sebagai dua jenis space-filling curve (Z-order lebih mudah dihitung, Hilbert-curve menjaga proximity relatif lebih baik):

Struktur Indeks Spasial Khusus (Dedicated)

Struktur indeks spasial dedicated mengorganisasikan objek ke dalam bucket, masing-masing memiliki bucket region (bagian ruang yang memuat semua objek dalam bucket tersebut).

Untuk data titik (point), region antar-bucket bersifat disjoint (ruang dipartisi, setiap titik masuk tepat satu bucket).
Untuk data rectangle, region antar-bucket boleh overlap.

Struktur untuk data titik:

Struktur	Ciri Khas
Grid file (Nievergelt et al., 1984)	Membagi ruang data dengan grid tak-beraturan; directory berupa array k-dimensi berisi pointer logis ke bucket; scale disimpan di memori, directory di disk
kd-tree (Bentley, 1975)	Binary tree; setiap level membagi ruang berdasarkan satu dimensi secara bergantian (mis. level 0 dimensi-x, level 1 dimensi-y, dst); daun menyimpan titik
KDB-tree (Robinson, 1981)	Memaginasi kd-tree menjadi bucket; seluruh daun berada pada level yang sama (mirip B-tree)
LSD-tree (Heinrich et al., 1989)	Tidak lagi mengikuti strict cycling antar-dimensi; algoritma paging menjaga panjang jalur eksternal tetap seimbang meski binary tree tidak seimbang
Quadtree	Membagi ruang secara rekursif menjadi 4 kuadran (NW, NE, SW, SE); sering dipakai pada GIS komersial untuk kompresi/penyimpanan citra raster

Struktur untuk data rectangle — karena rectangle tidak selalu masuk ke satu sel partisi (bisa memotong batas partisi), ada tiga pendekatan utama:

Transformation approach: rectangle k-dimensi ditransformasi menjadi titik 2k-dimensi, lalu dipakai struktur indeks titik biasa.
Overlapping bucket regions (mis. R-tree): partisi ruang ditinggalkan, region antar-bucket boleh overlap. Kelebihan: satu objek spasial hanya berada di satu bucket. Kekurangan: query bisa membutuhkan multiple search path karena bucket region saling overlap.
Clipping (mis. R+-tree, Sellis et al., 1987): bucket region tetap disjoint, tetapi rectangle data yang memotong batas partisi dipotong (clipped) menjadi beberapa bagian. Kelebihan: lebih sedikit percabangan saat pencarian. Kekurangan: satu objek spasial bisa memiliki banyak entri (redundansi).

Diagram berikut membandingkan struktur pohon overlapping bucket regions yang menjadi basis R-tree:

Basic Queries (Tipe Query Spasial)

Point query: kasus khusus containment query dengan $R$ berupa titik.
Containment query: diberikan objek spasial $R$ , cari semua objek yang memuat sepenuhnya $R$ .
Region query: diberikan region $R$ (polygon/circle), cari semua objek yang beririsan dengan $R$ . Kasus khusus dengan $R$ berupa rectangle disebut window query.
Enclosure query: diberikan polygon $R$ , cari semua objek yang sepenuhnya berada di dalam $R$ .
k-nearest neighbor (k-NN) query: diberikan objek titik $P$ , cari $k$ objek terdekat dari $P$ (umumnya untuk data titik).

Spatial Join

Diberikan dua himpunan objek spasial (biasanya berupa MBR) $S_{1} = {R_{1}, \dots, R_{m}}$ dan $S_{2} = {R_{1}^{'}, \dots, R_{n}^{'}}$ , spatial join menentukan semua pasangan objek yang memenuhi suatu predikat spasial (umumnya intersection).

Metode join tradisional (hash join, sort/merge join) tidak dapat langsung diterapkan karena melibatkan predikat spasial, dan memfilter cartesian product langsung sangat mahal. Ide sentral: filter + refine dan penggunaan struktur indeks spasial. Klasifikasi strategi berdasar:

Pendekatan aproksimasi: grid approximation atau bounding box.
Ketersediaan indeks pada operand: tidak ada / salah satu / kedua operand terindeks.

Bounding box approximation memiliki tiga varian algoritma:

Tidak ada indeks pada $R$ maupun $S$ : algoritma bb_join menggunakan algoritma geometri komputasional (mirip external merge sorting) untuk mendeteksi irisan rectangle.
Salah satu operand terindeks: algoritma index_join men-scan operand yang tidak terindeks, dan untuk tiap objeknya, bounding box-nya dipakai sebagai argumen pencarian pada operand yang terindeks (efisien hanya jika operand yang tidak terindeks berukuran kecil).
Kedua operand terindeks: dilakukan synchronized traversal pada kedua struktur, sehingga pasangan sel dari kedua partisi yang menutupi bagian ruang yang sama ditemukan bersamaan.

Ringkasan

Operasi spasial fundamental: spatial selection, spatial join, spatial function application, dan operasi himpunan lainnya.
Query spasial memerlukan dukungan input/output grafis.
Indeks spasial sangat penting untuk efisiensi query, dengan teknik utama: mapping ke ruang berdimensi lebih rendah (Z-order), grid file, kd-tree, dan keluarga R-tree.

Sumber

J. Gamper: “Chapter 9: An Introduction to Spatial Databases” & “Chapter 10: Spatial Indexing”, course materials on Temporal and Spatial Databases, 2012.
R. H. Güting: “An Introduction to Spatial Database Systems”, VLDB Journal 3: 357-399, 1994.

Flashcard

flashcards Mengapa B-tree biasa tidak cocok untuk indeks spasial? :: B-tree hanya mengelompokkan objek pada satu dimensi dan tidak menjaga kedekatan spasial (proximity) antarobjek. Jelaskan strategi filter-and-refine pada spatial indexing :: Filter menggunakan indeks (aproksimasi objek) untuk menghasilkan himpunan kandidat (superset jawaban); refine memuat representasi eksak kandidat lalu mengujinya secara pasti terhadap query. Apa itu MBR? :: Minimum Bounding Rectangle — persegi panjang sejajar sumbu terkecil yang membungkus suatu objek spasial, dipakai sebagai aproksimasi pada indeks. Apa itu Z-order/Morton order? :: Teknik pemetaan ruang 2-D ke urutan 1-D dengan bit-interleaving berdasarkan subdivisi hierarkis grid, sehingga sel yang berdekatan secara ruang cenderung berdekatan pada urutan leksikografisnya. Sebutkan tiga pendekatan utama untuk mengindeks data berbentuk rectangle :: Transformation approach (rectangle jadi titik 2k-dimensi), overlapping bucket regions (mis. R-tree), dan clipping (mis. R+-tree). Apa kelebihan dan kekurangan R-tree (overlapping bucket regions) dibanding R+-tree (clipping)? :: R-tree: satu objek hanya di satu bucket tapi search bisa multi-path karena overlap; R+-tree: search lebih sedikit percabangan tapi satu objek bisa punya banyak entri. Apa perbedaan window query dan enclosure query? :: Window query mencari objek yang beririsan dengan rectangle query; enclosure query mencari objek yang sepenuhnya berada di dalam polygon query. Sebutkan tiga skenario spatial join berdasarkan ketersediaan indeks pada operand :: Tidak ada indeks (bb_join, mirip external merge sort), salah satu terindeks (index_join), dan kedua operand terindeks (synchronized traversal).

Catatan Kuliah

Penjelajah

4_Spatial_Queries_Indexing