1. Giới thiệu

*

Các nghiên cứu về công nghệ cũng như ứng

dụng trong lĩnh vực cơ sở dữ liệu (CSDL) đang

tăng trưởng với một sức mạnh đáng kinh ngạc.

Cùng với sự tăng trưởng nhanh chóng của

lượng thông tin cũng như sự đa dạng về thể loại

thông tin cần lưu trữ và xử lý, chúng ta ngày

càng nhận ra những hạn chế của các Hệ Quản trị

cơ sở dữ liệu quan hệ truyền thống, và nhu cầu

cần phải có các hệ Quản trị cơ sở dữ liệu với các

dịch vụ phù hợp chính là yếu tố thúc đẩy những

nghiên cứu mới trong lĩnh vực này. Một trong

các mô hình cơ sở dữ liệu được quan tâm nhất

hiện nay chính là mô hình cơ sở dữ liệu không

gian - Spatial DataBase (SDB) xử lý các đối

tượng dữ liệu không gian, chẳng hạn dữ liệu

bản đồ, dữ liệu multimedia . và mở rộng hơn

nữa là kho dữ liệu không gian - Spatial Data

Warehouse (SDW). Các nghiên cứu trên lĩnh

vực này đã thu được rất nhiều thành tựu, tuy

nhiên cũng còn không ít khó khăn và thách thức

đòi hỏi phải có các giải pháp mới.

Bài báo này trình bày một phương pháp

đánh chỉ mục trên SDB, là sự kết hợp giữa hai

phương pháp đánh chỉ mục phổ biến là Q-tree

và R-tree, kết hợp các ưu điểm của cả hai

phương pháp này cũng như giảm thiểu nhược

điểm của chúng, nhằm tăng hiệu suất thực thi

các phép toán.

2. Khái niệm cơ bản

Phần này sẽ được tập trung trình bày những

khái niệm cơ bản liên quan đến mô hình SDB.

2.1. Dữ liệu không gian

Thuật ngữ dữ liệu không gian (spatial data)

được sử dụng theo nghĩa rộng, bao gồm các D.P. Hạnh

điểm đa chiều, các đường thẳng, hình khối . và

các đối tượng hình học nói chung. Mỗi đối

tượng dữ liệu này chiếm một vùng không gian

(spatial extent) được đặc trưng bởi hai thuộc

tính vị trí (location) và biên (boundary). Dưới

góc nhìn từ một hệ Quản trị cơ sở dữ liệu, có thể

phân chia dữ liệu không gian thành hai kiểu: dữ

liệu điểm (point data) và dữ liệu vùng (region

data)

Dữ liệu điểm; Với kiểu dữ liệu này, không

gian ứng với một điểm được đăc trưng bởi tọa

độ của nó; theo trực giác thì nó không chiếm

một vùng không gian hay một đơn vị thể tích

nào cả. Dữ liệu điểm là tập hợp các điểm trong

không gian nhiều chiều, được lưu trữ trong

CSDL dựa trên các tọa độ được tính toán trực

tiếp, hoặc được sinh ra nhờ quá trình chuyển

hóa dữ liệu thu được từ các phép đo khiến cho

việc lưu trữ và thực hiện truy vấn trở nên dễ

dàng hơn. Chẳng hạn Raster data là một ví dụ

dữ liệu điểm được lưu trữ trực tiếp thông qua

các bit maps hoặc pixel maps (chẳng hạn như

ảnh vệ tinh, hoặc phim điện não đồ 3 chiều, ).

Trong khi đó, feature vectors data được lưu trữ

thông qua các dữ liệu được trích chọn, chuyển

đổi từ một đối tượng dữ liệu điểm (thu được từ

ảnh, văn bản .). Có thể thấy rằng, sử dụng các

dữ liệu đã được biểu diễn để trả lời các truy vấn

luôn dễ dàng hơn sử dụng ảnh hoặc ký hiệu

nguyên bản