ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC KHOA HỌC TỰ NHIÊN

NGUYỄN BÍCH HẰNG

MỘT SỐ VẤN ĐỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

Người hướng dẫn: PGS.TS Đặng Văn Đức

HÀ NỘI


ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC KHOA HỌC TỰ NHIÊN

NGUYỄN BÍCH HẰNG

MỘT SỐ VẤN ĐỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN

Mã số

: 1.01.10

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

HÀ NỘI


MỤC LỤC

Giới thiệu ......................................................................................... 10

1.3.2

Sử dụng mô hình cơ sở dữ liệu quan hệ ............................................ 11

1.3.3

Sử dụng kiến trúc song song. ............................................................ 12

1.3.4

Tích hợp trên cơ sở mở rộng hệ quản trị cơ sở dữ liệu ...................... 14

1.4

Kết luận ............................................................................................. 14

Chương 2 - Mô hình dữ liệu, mối quan hệ và ràng buộc không gian . 15
2.1 Giới thiệu............................................................................................... 15
2.2 Mô hình dữ liệu không gian ................................................................... 16
2.2.1 Mô hình dữ liệu raster ............................................................................. 17
2.2.2 Mô hình dữ liệu Vectơ ............................................................................. 20


2.2.3 Mô hình dữ liệu không gian trên có sở các ràng buộc ............................. 25

2.3 Mối quan hệ không gian ........................................................................ 31
2.3.1 Quan hệ tôpô........................................................................................... 31



Kết luận................................................................................................ 111
Tài liệu tham khảo .............................................................................. 113


1

DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Ký hiệu

Tên đầy đủ

Ý nghĩa

ADT

Astract data type

Kiểu dữ liệu trừu tượng

DBMS

Database Management System

Hệ quản trị cơ sở dữ liệu

DB

Database



OODBMS

Object-oriented database

Hệ quản trị cơ sở dữ liệu

management system

hướng đối tượng

QEP

Query Execution Plan

Chiến lược xử lý truy vấn

SDB

Spatial databasse

Cơ sở dữ liệu không gian

SDBMS

Spatial database management

Hệ quản trị cơ sở dữ liệu

system

Luận văn với chủ đề “Một số vấn đề về cơ sở dữ liệu không gian”, em chủ
yếu tập trung vào nghiên cứu những đặc trưng của cơ sở dữ liệu (Spatial
database), một số khái niệm, công nghệ và thuật toán cơ bản đã được phát triển
xung quanh vấn đề quản lý cơ sở dữ liệu, bao gồm:
Chương 1: Giới thiệu chung về cơ sở dữ liệu không gian. Chương này tập
trung vào giới thiệu hệ quản trị cơ sở dữ liệu DBMS, trên cơ sở đó phát triển và
quản trị dữ liệu không gian.


3

Chương 2. Mô hình hóa dữ liệu, các mối quan hệ không gian và ràng
buộc toàn vẹn dữ liệu. Chương này tập trung giới thiệu cách xây dựng mô hình
dữ liệu và biểu diễn các mối quan hệ không gian. Dữ liệu không gian tích hợp
trong cơ sở dữ liệu cần duy trì tính nhất quán điều này được thể hiện ở ràng buộc
toàn vẹn dữ liệu không gian.
Chương 3. Cấu trúc dữ liệu không gian, các thuật toán cơ sở và phương
thức xâm nhập dữ liệu. Chương này giới thiệu cấu trúc dữ liệu không gian, các
thuật toán hình học được phát triển để thao tác với dữ liệu không gian và phương
thức xâm nhập dữ liệu không gian
Chương 4. Khảo sát hệ quản trị cơ sở dữ liệu không gian thương mại và
phát triển ứng dụng


4

Chương 1 - Giới thiệu chung về cơ sở dữ liệu không gian
1.1 Giới thiệu chung về cơ sở dữ liệu
Cơ sở dữ liệu (Database) là tập dữ liệu có mối quan hệ tương quan nhau
và lưu trữ trong môi trường máy tính, Database có thể được xem như một hoặc

 Mô hình dữ liệu phân cấp ngày nay đã quá lỗi thời, hệ quản trị cơ sở dữ
liệu phân cấp (hierarchical DBMS) giả sử rằng dữ liệu có mối quan hệ thứ
bậc cha và con. Cấu trúc dữ liệu bắt buộc phải xây dựng phù hợp với mô
hình này để thực hiện được lợi ích và hiệu quả trong quản lý.
 Hệ quản trị cơ sở dữ liệu mạng (network DBMS) cho phép các cấu trúc dữ
liệu phức tạp được xây dựng nhưng không có tính mềm dẻo và đòi hỏi
thiết kế phải hết sức cẩn thận, tuy nhiên lợi ích của mô hình này là nhanh
và hiệu quả.
1.1.1 Mô hình quan hệ
Cơ sở dữ liệu quan hệ phát triển trên cơ sở mô hình quan hệ, ở đó dữ liệu
tổ chức vào các quan hệ hay các bảng. Một lược đồ quan hệ bao gồm tập các tên
thuộc tính và chúng được ánh xạ tới miền giá trị, lược đồ quan hệ chỉ ra cấu trúc
của quan hệ chứ không chứa dữ liệu. Quan hệ là tập các bản ghi lưu dữ liệu của
các tập thuộc tính trong lược đồ quan hệ.


6

Hệ quản trị cơ sở dữ liệu quan hệ được sử dụng một cách áp đảo so với
các hệ quản trị cơ sở dữ liệu khác bởi lợi ích nhanh chóng và tin cậy. Tuy nhiên,
với những ứng dụng lớn nó tỏ ra chậm chạp vì relation DBMS phải sử dụng rất
nhiều bảng cho hàng loạt các quy tắc
1.1.2 Mô hình hướng đối tượng
Hệ quản trị cơ sở dữ liệu hướng đối tượng OODBMS (Object-oriented
database management system) tích hợp giữa hướng đối tượng và cơ sở dữ liệu.
Cơ sở dữ liệu hướng đối tượng được đặc trưng bởi mô hình dữ liệu hướng đối
tượng và ngôn ngữ lập trình hướng đối tượng, ở đó các đơn vị dữ liệu là các đối
tượng cơ sở. Các đối tượng này có định danh, thuộc tính và hành vi được định
nghĩa qua phương thức, tất cả được bao gói trong chính đối tượng đó.
1.1.3 Mô hình đối tượng-quan hệ

để lưu trữ và xâm nhập thông tin.
 Thứ hai, GIS là công nghệ tích hợp. Hệ GIS đầy đủ có đầy đủ khả năng
phân tích, bao gồm phân tích ảnh máy bay, ảnh vệ tinh hay tạo lập mô
hình thống kê, vẽ bản đồ... Cuối cùng, GIS được xem như tiến trình không
chỉ là phần cứng, phần mềm rời rạc mà GIS còn được sử dụng vào trợ
giúp quyết định. Cách thức nhập, lưu trữ, phân tích dữ liệu trong GIS phải
phản ánh đúng cách thức thông tin sẽ được sử dụng trong công việc lập
quyết định hay nghiên cứu cụ thể.


8

Định nghĩa của Viện Nghiên cứu Hệ thống Môi trường ESRI, Mỹ
GIS là công cụ trên cơ sở máy tính để lập bản đồ và phân tích những cái
đang tồn tại và các sự kiện xảy ra trên Trái đất. Công nghệ GIS tích hợp các thao
tác cơ sở dữ liệu như truy vấn và phân tích thống kê với lợi thế quan sát và phân
tích thống kê bản đồ. Các khả năng này sẽ phân biệt GIS với các hệ thông tin
khác. Có rất nhiều chương trình máy tính sử dụng dữ liệu không gian như
AutoCAD và các chương trình thống kê, nhưng chúng không phải là GIS vì
chúng không có khả năng thực hiện các thao tác không gian.
Định nghĩa của David Cowen, NCGIA, Mỹ
GIS là hệ thống phần cứng, phần mềm và các thủ tục được thiết kế để thu
thập, quản lý, xử lý, phân tích, mô hình hóa và hiển thị các dữ liệu qui chiếu
không gian để giải quyết các vấn đề quản lý và lập kế hoạch phức tạp.
Độ phức tạp của thế giới thực là không giới hạn. Càng quan sát thế giới
gần hơn càng thấy được chi tiết hơn. Con người mong mỏi lưu trữ, quản lý đầy
đủ các dữ liệu về thế giới thực. Nhưng sẽ dẫn đến phải có cơ sở dữ liệu lớn vô
hạn để lưu trữ mọi thông tin chính xác về chúng. Do vậy, để lưu trữ được dữ
liệu không gian của thế giới thực vào máy tính thì phải giảm số lượng dữ liệu
đến mức có thể quản lý được bằng tiến trình đơn giản hóa hay trừu tượng hóa

Ý nghĩa chủ yếu của tin học hóa thông tin địa lý là khả năng tích hợp các
kiểu và nguồn dữ liệu khác biệt. Mục tiêu của GIS là cung cấp cấu trúc một cách
hệ thống để quản lý các thông tin địa lý khác nhau và phức tạp, đồng thời cung
cấp các công cụ, các thao tác hiển thị, truy vấn, mô phỏng....

Tầng
Tầng Khách
Tầng Đường
hàng
Tần
g Nhà
quốc
lộ ở

hố

Biên
h
ành
chính

Hình 1.3 Tầng bản đồ
GIS lưu trữ thông tin thế giới thực thành các tầng (layer) bản đồ chuyên
đề mà chúng có khả năng liên kết địa lý với nhau (hình 1.3). Mỗi nhóm người sử
dụng sẽ quan tâm nhiều hơn đến một hay vài loại thông tin. Thí dụ, Sở Giao
thông công chính sẽ quan tâm nhiều đến hệ thống đường phố. Sở Nhà đất quan


10


 Trước hết, đó phải là một hệ cơ sở dữ liệu,
 Các kiểu dữ liệu không gian phải được cung cấp trong các mô hình dữ liệu
và ngôn ngữ truy vấn, các phép toán truy vấn quan hệ như phép nối, chọn,
… Có thể được sử dụng ở Hệ quản trị cơ sở dữ liệu không gian (SDBMSSpatial database management system- ). Cần thiết xây dựng thêm một số
phép toán mới với các kiểu dữ liệu hình học,
 Biểu diễn dữ liệu logic phải được mở rộng tới dữ liệu kiểu hình học và
thoả mãn tính độc lập dữ liệu, duy trì tính đơn giản nhất có thể và tính
đóng đối với người sử dụng,
 Ngôn ngữ truy vấn phải tích hợp với các hàm nhằm hỗ trợ xây dựng ứng
một cách phong phú các đối tượng hình học,
 Có thể biểu diễn vật lý một cách hiệu quả dữ liệu không gian,
 Truy nhập dữ liệu không gian một cách hiệu quả, hiện nay, B-tree không
còn là tiếp cận với truy nhập dữ liệu không gian. Và theo đó chúng ta cần
xây dựng cấu trúc mới cho việc đánh chỉ mục cơ sở dữ liệu không gian.
Xuất phát từ những yêu cầu trên, có ba cách tiếp cận khi xây dựng hệ quản
trị cơ sở dữ liệu không gian Relational DBMS.
1.3.2 Sử dụng mô hình cơ sở dữ liệu quan hệ
Sử dụng hệ quản trị cơ sở dữ liệu quan hệ để quản lý GIS có những đặc
trưng chính như:


12

 Biểu diễn các đối tượng bằng các quan hệ (bảng). Mỗi hàng thể hiện
một đối tượng, mỗi cột là thuộc tính mô tả đối tượng đó,
 Thuộc tính có kiểu alphanumeric (ví dụ như Strinh hay real),
 Truy vấn dựa vào SQL,
Đây là cách tiếp cận xoay quanh chuẩn SQL, nhưng khi điều khiển các
ứng dụng về không gian địa lý có những hạn chế sau:
 Vi phạm nguyên lý độc lập dữ liệu, các truy vấn trên đối tượng đòi hỏi có

Tuy nhiên tiếp cận này cũng có mặt hạn chế như:
 Hai thành phần trên xuất hiện cùng nhau mà mô hình dữ liệu của
chúng lại không đồng nhất, do vậy khi mô hình phải sử dụng kết hợp
những thực thi khác nhau,
 Mất một phần chức năng cơ bản của Hệ quản trị cơ sở dữ liệu như:
Phục hồi, sao lưu dữ liệu, truy vấn và tối ưu dữ liệu.


14

1.3.4 Tích hợp trên cơ sở mở rộng hệ quản trị cơ sở dữ liệu
Mô hình này đã nhận được sự quan tâm rất lớn từ nhiều năm trước đó ở
nhiều ứng dụng và được phát triển trên cơ sở thêm các kiểu, các toán tử mới vào
hệ thống cơ sở dữ liệu quan hệ như sau:
 Ngôn ngữ truy vấn SQL được mở rộng để thực thi dữ liệu không
gian. Toán tử không gian được điều khiển trên cơ sở các kiểu dữ liệu
alphanumeric,
 Một số chức năng khác của cơ sở dữ liệu như tối ưu hoá truy vấn,
được sửa đổi nhằm thích nghi với các dữ liệu không gian một cách
hiệu quả.
Hầu hết các hệ quản trị cơ sở dữ liệu có sẵn đều sử dụng cách tiếp cận mở
rộng không gian ví dụ như Oracle (Bắt đầu từ phiên bản 8i) và PostgreSQL.
1.4 Kết luận
Xây dựng và phát triển cơ sở dữ liệu không gian hiệu quả sử dụng mô
hình object-relational hay có thể nói tích hợp dữ liệu không gian vào cơ sở dữ
liệu quan hệ trên cơ sở mở rộng hệ quản trị cơ sở dữ liệu, như vậy sẽ tận dụng
được sức mạnh của hướng đối tượng mà vẫn duy trì được các chức năng quan
trọng trong cơ sở dữ liệu quan hệ. Tích hợp dữ liệu không gian như thế nào? Sẽ
được đề cập ở chương 3. Cấu trúc dữ liệu không gian, các thuật toán cơ sở và
phương thức xâm nhập.

Các phần dưới đây sẽ trình bày kĩ hơn về mô hình dữ liệu không gian, mối
quan hệ và ràng buộc không gian.
2.2 Mô hình dữ liệu không gian
Cơ sở dữ liệu không gian cho phép quản lý dữ liệu không gian trong mô
hình dữ liệu và ngôn ngữ truy vấn, vấn đề rất quan trọng cần quan tâm là làm thế
nào để mô hình hóa các đối tượng không gian. Có hai vấn đề mà cần được biểu
diễn đó là: (i) Đối tượng trong không gian, là các đối tượng thực trong tự nhiên
được mô tả bởi hình dáng của nó như: sông, thành phố, rừng và (ii) không gian.
Nói một cách khác hai vấn đề này có thể được xem như: (i) Các đối tượng đơn lẻ
và (ii) Tập các đối tượng không gian.
Các đối tượng độc lập được biểu diễn một cách trừu tượng bởi điểm, đọan
thẳng và miền (minh họa hình 2.1).

Hình 2.1. Các kiểu cơ bản: Điểm, đoạn thẳng và miền
Tập các đối tượng có hai vấn đề đó phân cắt và mạng, phân cắt được xem
như tập các đối tượng (miền) không giao nhau, các miền này phân chia vùng
thành nhiều vùng con (hình 2.2), mạng có các đặc trưng như nút và tập đọan
thẳng mô tả các cạnh, chi tiết sẽ được thể hiện ở phần sau.


17

Hình 2.2. Phân cắt và mạng
Dữ liệu không gian được tổ chức theo những cách khác nhau và được
minh họa như hình 2.3. Gồm mô hình raster và vectơ, chúng thường được xem
như mô hình field-based hay object-based. Biểu diễn raster sử dụng tessellations
cho việc mô hình hóa tập dữ liệu và biểu diễn vectơ thì đối tượng là đơn vị cơ
sở, đồng thời có hai cấu trúc thể hiện tập các đối tượng đó là: Có cấu trúc (như
tôpô, network) và phi cấu trúc (spagetti). Mô hình tôpô tương đối phổ biến, nó
ko đơn giản như cấu trúc spagetti.


Giả sử phủ một lưới trên bản đồ gốc, dữ liệu raster được lập bằng cách mã
hóa mỗi tế bào bằng một giá trị dựa theo các đặc trưng trên bản đồ (hình 2.4).
Trong thí dụ này, đặc trưng "đường" được mã hóa là 2, đặc trưng "điểm" được
mã hóa là 1 còn đặc trưng "vùng" được mã hóa là 3. Kiểu dữ liệu của tế bào
trong lưới phụ thuộc vào thực thể được mã hóa; Có thể sử dụng số nguyên, số
thực, ký tự hay tổ hợp chúng để làm giá trị. Độ chính xác của mô hình này phụ
thuộc vào kích thước hay độ phân giải của các tế bào lưới. Một điểm có thể là
một tế bào, một đường là vài tế bào kề nhau, một vùng là tập hợp nhiều tế bào.
Mỗi đặc trưng là tập tế bào đánh số như nhau (có cùng giá trị).

Đ
ường

ùng

V
iểm

Đ

Bản đồ gốc

Lưới

Ma trận lưu trữ

H
C


còn là tập giới hạn các điểm nữa mà là tập vô hạn các điểm. Nói một cách khác
không gian không được coi như trường liên tục nữa mà rời rạc khi biểu diễn dữ
liệu.
Tóm lại, Lợi thế lớn nhất của hệ thống raster là dữ liệu hình thành nên bản
đồ trong bộ nhớ máy tính, các thao tác kiểu như so sánh lưới tế bào được thực
hiện dễ dàng. Tuy nhiên hệ thống raster sẽ không thuận tiện cho việc biểu diễn


20

đường, điểm vì mỗi loại là tập các tế bào trong lưới. Đường thẳng có thể bị đứt
đoạn hay rộng hơn.
2.2.2 Mô hình dữ liệu Vectơ
Trong phương pháp này, các đối tượng được cấu trúc chính từ các thành
phần cơ sở như: điểm, đọan thẳng (danh sách các điểm) và bề mặt của đối tượng
(danh sách các các cạnh). Hình 2.6 là minh họa cho phương pháp này. Trái với
biểu diễn raster, biểu diễn vector không tốn bộ nhớ.
Kiểu thành
phần sơ cấp

Biểu diễn bằng đồ họa

Biểu diễn số
Tọa độ (x,y) trong
2D
và (x,y,z) trong
3D
1. Danh sách tọa độ
2.
Hàm toán học