Báo Cáo Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian

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) [1]
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.