- 67 -
MỤC LỤC
CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT 1
DANH MỤC CÁC BẢNG 1
DANH MỤC CÁC HÌNH 2
Chương 1. 5
TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ 5
CƠ SỞ DỮ LIỆU KHÔNG GIAN 5
1.1. Tổng quan về hệ thống thông tin địa lý (GIS) 5
1.1.1. Khái niệm 5
1.1.2. Các thành phần của hệ thống thông tin địa lý 7
2.3.1. Chèn và tìm kiếm trong cây tứ phân điểm 37
2.3.2. Thao tác xoá trên cây tứ phân điểm 39
2.3.3. Truy vấn khoảng trong cây tứ phân điểm 41
- 68 -
2.4. Cây tứ phân matrix MX (MX-Quadtrees) 41
2.4.1. Chèn và tìm kiếm trong MX-Quadtree 42
2.4.2. Thao tác xoá trong MX-Quadtrees 44
2.4.3. Truy vấn khoảng trong MX-Quadtrees 45
2.5. Cây R (R-Trees) 45
2.5.1. Chèn và tìm kiếm trong R-Trees 46
2.5.2. Xoá trong cây R-Trees 48
2.6. So sánh các cấu trúc dữ liệu 49
Chương 3. 51
CÀI ĐẶT VÀ THỬ NGHIỆM 51
3.1. Bài toán 51
3.1.1. Phát biểu bài toán 51
3.1.2. Cách giải quyết 51
3.2. Công cụ xây dựng chương trình 52
3.3. Dữ liệu xây dựng trong chương trình 52
3.4. Thiết kế đặc tả chức năng 53
3.4.1. Chuyển đổi dữ liệu từ cấu trúc tuyến tính sang cấu trúc cây 53
3.4.2. Lưu trữ sang cấu trúc cây 53
3.4.3. Hiển thị bản đồ 53
3.4.4. Truy vấn trên bản đồ 53
3.5. Cài đặt và thử nghiệm 54
3.5.1. Cài đặt chương trình 54
3.5.2. Kết quả thử nghiệm 54
3.6. Nhận xét kết quả đạt được 59
KẾT LUẬN 60
TÀI LIỆU THAM KHẢO 61
Database Management System
Hệ quản trị cơ sở dữ liệu DANH MỤC CÁC BẢNG Bảng 1.1. So sánh giữa mô hình vectơ và mô hình raster 23
Bảng 2.1 Các trường hợp của phép chèn vào cây tứ phân điểm 40
Bảng 2.2. Mô tả bốn cành của nút N trong cây tứ phân MX 42
Bảng 3.1. Các nút lệnh trên thanh công cụ của chương trình 55
- 2 -
Hình 2.13. Bản đồ mẫu mô tả phép chèn trong cây R 48
Hình 2.14. Bản đồ mẫu mô tả phép chèn trong cây R 48
Hình 2.15. Mô tả phép xóa trong cây R 49
Hình 3.1. Mô hình Use Case 52
Hình 3.2. Giao diện chính của chương trình 54
Hình 3.3. Bảng đồ sau khi hiển thị cả lớp đường và lớp điểm. 56
Hình 3.4. Bảng đồ hiển lớp điểm 56
Hình 3.5. Truy vấn vùng trên bản đồ lớp điểm 57
Hình 3.6. Kết quả của truy vấn trên hình 3.4 57
Hình 3.7. Truy vấn vùng trên bản đồ tổng thể 58
Hình 3.8.Kết quả của truy vấn vùng trên bản đồ tổng thể 58
- 3 -
MỞ ĐẦU
Thời gian gần đây, tại Việt Nam, các hệ thống thông tin địa lý –
Geographic Information System(GIS) đã bắt đầu quen thuộc và đã là nhu cầu
không thể thiếu đối với hầu hết các chuyên ngành từ địa chính, đo đạc trắc địa,
viễn thông cho đến du lịch, điện lực. Vì GIS được thiết kế như một hệ thống
chung để quản lý dữ liệu không gian, nó có rất nhiều ứng dụng trong việc phát
triển đô thị và môi trường tự nhiên như là: quy hoạch đô thị, quản lý nhân lực,
nông nghiệp, điều hành hệ thống công ích, lộ trình, nhân khẩu, bản đồ, giám sát
vùng biển, cứu hoả và bệnh tật. …Trong phần lớn lĩnh vực này, GIS đóng vai
trò như là một công cụ hỗ trợ quyết định cho việc lập kế hoạch hoạt động môi
trường.
Tuy nhiên việc vận dụng, chọn lựa giải pháp GIS như thế nào cho phù
hợp đối với từng chuyên ngành với mỗi quy mô và mức độ phức tạp riêng cũng
như đáp ứng vừa đủ các yêu cầu cụ thể về GIS là điều không phải dễ dàng. Việc
mỗi nhu cầu thực tế. Có thể nói cấu trúc dữ liệu là phần khung và bản chất nhất
của các hệ thống GIS, nó là cơ sở của các giải thuật GIS cũng như nói đến khả
năng lưu trữ, khai thác, phát triển hệ thống dữ liệu. Xuất phát từ thực tế Tôi
chọn đề tài “ Một số vấn đề lưu trữ và chỉ mục trong cơ sở dữ liệu không gian”.
Trong khuôn khổ một luận văn, tôi trình bày một số vấn đề cơ bản về hệ
thống thông tin địa lý (GIS), hệ quản trị CSDL không gian chẳng hạn các khái
niệm, kiến trúc hệ thống, các mô hình dữ liệu không gian. Trong đó, tập trung
nghiên cứu và cài đặt thử nghiệm một số cấu trúc lưu trữ dữ liệu không gian.
Bố cục của luận văn bao gồm phần mở đầu, phần kết luận và ba chương
nội dung được tổ chức như sau:
Chương 1: Tổng quan về hệ thống thông tin địa lý (GIS) - Cơ sở dữ liệu không gian
Chương này trình bày tổng quan về hệ thống thông tin địa lý: định nghĩa
hình thức về hệ thống thông tin địa lý, các thành phần, chức năng và các ứng
dụng của hệ thống thông tin địa lý. Cơ sở dữ liệu không gian bao gồm: chỉ mục
không gian, truy vấn không gian, phương pháp quản trị CSDL phi không gian
và không gian, trong đó gồm các mô hình Vector, Raster, Topology
Chương 2: Một số kỹ thuật chỉ mục và tìm kiếm trong CSDL không gian
Chương này mô tả cấu trúc, các phép toán chèn, xoá, duyệt, truy vấn trên
các kỹ thuật chỉ mục và tìm kiếm không gian như: cây k-d(k-d tree), cây tứ
phân(Quadtree), cây R (R tree) và so sánh giữa chúng
Chương 3: Cài đặt và thử nghiệm
Cài đặt thử nghiệm kỹ thuật chỉ mục và tìm kiếm không gian:cây tứ phân điểm.
Chương trình được cài đặt từ cơ sở dữ liệu đã có định dạng bằng
Shapefile, với ngôn ngữ lập trình C#.NET cùng với thư viện hỗ trợ SharpMap.
- 5 -
Chương 1.
TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN ĐỊA LÝ
– CƠ SỞ DỮ LIỆU KHÔNG GIAN
1.1. Tổng quan về hệ thống thông tin địa lý (GIS)
1.1.1. Khái niệm
Tầng Đ-ờng quốc lộ
hố
Tầng Khách hàng
Tầng Biên
hành chính
Thuỷ lợi
Cây trồng
Khí hậu
Dân c-
Mô hình hóa
Giám sát
Lập bản đồ
Đo đạc
t3
t2
t1
Hệ thông tin địa lý
- 7 -
1.1.2. Các thành phần của hệ thống thông tin địa lý
Công nghệ GIS gồm 5 hợp phần cơ bản là:
- Thiết bị (Hardware)
- Phần mềm (Software).
- Số liệu (Geographic data)
- Con người (Person)
- Chính sách và cách thức quản lý (Policy and Management) Hình 1.3. Các hợp phần thiết yếu cho công nghệ GIS.
1.1.2.1. Thiết bị (Hardware)
Bao gồm máy vi tính (computer), máy vẽ (plotter), máy in (printer), bàn
số hóa (digitizer), thiết bị quét ảnh (scaner), các phương tiện lưu trữ số liệu
(Floppy diskettes,optical cartridges, CD ROM. . .)
dụng đó.
Các phần mềm tiêu chuẩn và sử dụng phổ biến hiện nay trong khu vực Châu Á là:
ARC/INFO, MAPINFOR, IL WIS, WINGIS, SPANS, IDRISIW, Hiện nay có rất nhiều
phần mềm máy tính chuyên biệt cho GIS, bao gồm các phần mềm sau:
+ Phần mềm dùng cho lưu trữ, xử lý số liệu thông tin địa lý: ACR/INFO,
SPAN, ERDAS-Imagine, IL WIS, MGE/MICROSTATION, IDRISIW
+ Phần mềm dùng cho lưu trữ, xử lý và quản lý các thông tin địa lý: ER-
MAPPER, ATLASGIS, ARCVIEW, MAPINFO - 9 -
1.1.2.3. Con người (Person)
Con người bao gồm: người sử dụng hệ thống (system user), thao tác viên
hệ thống (system operator), nhà cung cấp GIS (GIS supplier), nhà cung cấp dữ
liệu (data supplier), người phát triển ứng dụng (application developer), chuyên
viên phân tích hệ thống GIS (GIS system analysts)
1.1.2.4. Số liệu, dữ liệu địa lý (Geographic data)
Số liệu được sử dụng trong GIS không chỉ là số liệu địa lý riêng lẽ mà còn
được thiết kế trong một cơ sở dữ liệu. Những thông tin địa lý bao gồm những dữ
kiện về: vị trí địa lý, thuộc tính, mối liên hệ không gian của các thông tin và thời
gian. Có 2 dạng số liệu được sử dụng trong kỹ thuật GIS là:
- Cơ sở dữ liệu bản đồ: là những mô tả hình ảnh bản đồ được số hóa theo
một khuôn dạng nhất định mà máy tính hiểu được. Hệ thống thông tin địa lý
dùng cơ sở dữ liệu này để xuất ra các bản đồ trên màn hình hoặc ra các thiết bị
ngoại vi khác như máy in, máy vẽ.
+ Số liệu vector: được hiển thị dưới dạng điểm, đường và vùng, mỗi dạng
có liên quan đến 1 số liệu thuộc tính được lưu trữ trong cơ sở dữ liệu.
+ Số liệu raster: được thể hiện dưới dạng lưới ô vuông hay ô chữ nhật đều
nhau, giá trị được ấn định cho mỗi ô sẽ chỉ định giá trị của thuộc tính. Số liệu
của ảnh vệ tinh và số liệu của bản đồ được quét là các loại số liệu raster.
cu trỳc. H thng GIS phi cú phn mm cụng c t chc v lu tr cỏc loi
d liu khỏc nhau t d liu thụ n d liu din gii. Phn mm cụng c ny
phi cú cỏc thao tỏc lu tr, truy nhp; ng thi cú kh nng hin th , tng tỏc
ha vi tt c loi d liu.
Hỡnh 1.5. Cỏc nhúm chc nng trong GIS
CSDL
Hiện t-ợng
quan sát
Tài liệu và
bản đồ giấy
Thu thập
dữ liệu
Dữ liệu
thô
Xử lý sơ
một số khía cạnh chọn lọc từ thế giới thực. Mô hình là mô tả đầy đủ hệ thống từ
một góc nhìn cụ thể và được hình thành nhờ tiến trình trừu tượng hóa (đơn giản
hóa thông minh)[1]. Cơ sở dữ liệu không gian hình thành từ các mô hình mô tả
trạng thái và bản chất của hiện thực (hình 1.6).
Hình 1.6. Minh hoạ mô hình hoá
* Định nghĩa CSDL không gian:
Cơ sở dữ liệu không gian là tập hợp dữ liệu tham chiếu không gian, có
vai trò như mô hình của hiện thực:
- 12 -
+ CSDL là mô hình hiện thực theo nghĩa nó biểu diễn tập lựa chọn hay
xấp xỉ các hiện tượng
+ Các hiện tượng lựa chọn này được xem là quan trọng, đủ để biểu
diễn đặc trưng dưới dạng số cho hiện tại, quá khứ và tương lai.
1.2.1. Tổ chức các mẩu tin trong tệp
Dữ liệu trên đĩa được tổ chức thành: trường (field), mẩu tin (record), tệp
(file). Trong đó, trường mô tả đặc tính hoặc thuộc tính của một quan hệ hoặc
một thực thể. Mẩu tin mô tả một hàng (row) trong một bảng quan hệ, tập hợp
của những trường cho những thuộc tính trong mô hình quan hệ của bảng. Những
tệp là tập hợp của những mẩu tin có thể được mô tả một quan hệ, những tập hợp
khác có thể là sự kết hợp của những quan hệ liên quan.
tự được sắp dựa trên một khoá tìm kiếm (search key) nào đó. Để cho phép tìm
lại nhanh chóng các mẩu tin theo thứ tự khoá tìm kiếm, ta "xích" các mẩu tin lại
bởi các con trỏ. Con trỏ trong mỗi mẩu tin trỏ tới mẩu tin kế tiếp theo thứ tự
khoá tìm kiếm. Hơn nữa, để tối ưu hoá số khối truy xuất trong xử lý tệp tuần tự,
ta lưu trữ vật lý các mẩu tin theo thứ tự khoá tìm kiếm.
Tổ chức tệp tuần tự cho phép đọc các mẩu tin theo thứ tự được sắp mà nó
có thể hữu dụng cho mục đích trình bày cũng như cho các thuật toán xử lý truy
vấn (query-processing algorithms).
Tệp có thứ tự tổ chức những mẩu tin bằng việc sắp xếp chúng dựa vào
trường khóa đã cho, ví dụ hình 1.7 hiển thị một tệp sắp xếp được tổ chức những
mẩu tin trong bảng City với trường khóa sắp xếp City name
Hình 1.8. Tổ chức tệp có thứ tự cho bảng City
• Tổ chức tệp băm (Hashed File Organization): trong cách tổ chức này, có
một hàm băm được tính toán trên thuộc tính nào đó của mẩu tin. Kết quả của
hàm băm xác định mẩu tin được bố trí trong khối nào trong tệp. Cách tổ chức
này liên hệ chặt chẽ với cấu trúc chỉ mục.
- 14 -
Tệp băm được tổ chức chia những mẩu tin thành một tập những thùng
(buckets), sử dụng một hàm gọi là hàm băm (hashed fuction ), hàm băm ánh xạ
những giá trị trên một trường khóa được chọn (ví dụ: City name), trong hình 1.8
hiển thị một hàm băm với 4 thùng (bucket), mỗi thùng được lưu trữ vào một
- 15 -
Truy vấn này tính một phép nối của các quan hệ Depositor và Customer.
Như vậy, đối với mỗi bộ của Depositor, hệ thống phải tìm bộ của Customer có
cùng giá trị Customer_Name. Một cách lý tưởng là việc tìm kiếm các mẩu tin
này nhờ sự trợ giúp của chỉ mục. Bỏ qua việc tìm kiếm các mẩu tin như thế nào,
ta chú ý vào việc truyền từ đĩa vào bộ nhớ. Trong trường hợp xấu nhất, mỗi mẩu
tin ở trong một khối khác nhau, điều này buộc ta phải đọc một khối cho một
mẩu tin được yêu cầu bởi truy vấn. Ta sẽ trình bày một cấu trúc tệp được thiết
kế để thực hiện hiệu quả các truy vấn liên quan đến Depositor.Customer. Các bộ
Depositor đối với mỗi Customer_Name được lưu trữ gần bộ Customer có cùng
Customer_Name. Cấu trúc này trộn các bộ của hai quan hệ với nhau, nhưng cho
phép xử lý hiệu quả phép nối. Khi một bộ của quan hệ Customer được đọc, toàn
bộ khối chứa bộ này được đọc từ đĩa vào trong bộ nhớ chính. Do các bộ tương
ứng của Depositor được lưu trữ trên đĩa gần bộ Customer, khối chứa bộ
Customer chứa các bộ của quan hệ Depositor cần cho xử lý truy vấn. Nếu một
Customer có nhiều Account đến nỗi các mẩu tin Depositor không lấp đầy trong
một khối, các mẩu tin còn lại xuất hiện trong khối kế cận. Cấu trúc tệp này, được
gọi là gom cụm (clustering), cho phép ta đọc nhiều mẩu tin được yêu cầu chỉ sử
dụng một đọc khối, như vậy ta có thể xử lý truy vấn đặc biệt này hiệu quả hơn.
Tuy nhiên, cấu trúc tệp gom cụm trên lại tỏ ra không có lợi bằng tổ chức
lưu mỗi quan hệ trong một tệp riêng, đối với một số truy vấn, chẳng hạn:
SELECT *
FROM Customer
Việc xác định khi nào thì gom cụm thường phụ thuộc vào kiểu truy vấn
mà người thiết kế CSDL nghĩ rằng nó xảy ra thường xuyên nhất. Sử dụng thận
trọng gom cụm có thể cải thiện hiệu năng đáng kể trong việc xử lý truy vấn.
1.2.2. Chỉ mục không gian (Spatial indexing )
Tệp chỉ mục là tệp bổ trợ để cải tiến việc tìm kiếm. Mỗi bản ghi trong tệp
chỉ mục chỉ có 2 trường: giá trị khóa, địa chỉ của những trang trong tệp dữ liệu,
những bản ghi trong tệp chỉ mục thường có thứ tự, có thể sử dụng thứ tự không
Hình 1.11. Chỉ mục chính trên bảng City
Một cấu trúc chỉ mục không gian tổ chức những đối tượng với một tập
những thùng (bucket) thông thường những thùng này tương ứng với những trang
trong bộ nhớ phụ (second memory), mỗi thùng (bucket) có một liên kết vùng,
một phần của không gian chứa tất cả những đối tượng lưu trữ trong thùng
(bucket), những vùng thường là những hình chữ nhật đối với những cấu trúc dữ
liệu điểm, những vùng này thường rời rạc và chúng chia cắt không gian và chính
vì vậy mỗi điểm có liên quan chính xác đến một thùng (bucket), đối với một vài
cấu trúc dữ liệu hình chữ nhật những vùng có thể chồng lên nhau.
- 17 -
Có 2 lợi ích cơ bản của chỉ mục không gian:
1. Cấu trúc dữ liệu không gian ngoài được thêm vào hệ thống, cung cấp
những thuộc tính không gian cây B (B tree) cho những thuộc tính tuyến tính.
2. Những đối tượng không gian được ánh xạ vào không gian một chiều 1-
D, sử dụng một trật tự không gian (ví dụ: trật tự Z, trật tự Hilbert), vì vậy chúng
được lưu trữ trong một chỉ mục chuẩn 1-D như cây B (B tree)
Chỉ mục không gian giống như bất kỳ chỉ mục khác cung cấp một cơ chế
để giới hạn tìm kiếm, nhưng trong trường hợp này cơ chế dựa vào tiêu chuẩn
không gian như sự giao nhau và chứa đựng nhau. Một chỉ mục không gian cần:
- Tìm những đối tượng trong khoảng một không gian dữ liệu chỉ mục mà
nó tương tác với một điểm đã cho hoặc một vùng quan tâm (truy vấn vùng)
- Tìm những cặp đối tượng từ khoảng 2 không gian dữ liệu chỉ mục mà
chúng tương tác không gian với mỗi trong chúng (kết nối không gian).
Chỉ mục không gian được sử dụng bởi những cơ sở dữ liệu không gian để
tối ưu truy vấn không gian. Những phương pháp chỉ mục không gian phổ biến
bao gồm: lưới (Grid), cây tứ phân (Quadtree), Cây R (R tree), cây kd (k-d tree),
Octree, UB tree. Các chỉ mục này được mô tả chi tiết trong chương 2.
1.2.3. Phương pháp quản trị CSDL phi không gian
Các hệ thống quản trị cơ sở dữ liệu thông dụng như SQL_Server, Oracle,
k
WHERE F
Ý nghĩa của truy vấn trên là chọn những giá trị của các thuộc tính A
1
,
A
2
,….,A
n
trong quan hệ R
1
, R
2
,….,R
k
với điều kiện F cho trước. Trong ví dụ mô
tả ở trên, giả sử ta muốn biết số điện thoại của một khách hàng có tên “ John
Smith”, khi đó truy vấn trong SQL có thể như sau:
SELECT PhoneNum
FROM Client
WHERE Fname=”John” and Lname= “Smith”.
Mô hình dữ liệu quan hệ được sử dụng rộng rãi trong các ứng dụng hiện
nay. Tuy nhiên CSDL quan hệ gặp phải một số trở ngại cụ thể là:
- Dữ liệu được tổ chức dưới dạng các bộ quan hệ và các bộ với các trường
khó phản ảnh được các cấu trúc dữ liệu phức tạp.
- Cơ chế quan hệ trên là một quan hệ tĩnh, không có cách để thay đổi số
lượng các thuộc tính trong quan hệ.
- Mỗi quan hệ nội dung giữa một bảng này với một bảng khác phải được
mã hóa một cách rõ ràng thông qua cách sử dụng của cấu trúc, ví dụ các ràng
1
:T
1
, A
2
:T
2
,…,
A
n
:T
n
) trong đó, A
i
là một thuộc tính của quan hệ và T
i
là một đối tượng nào đó
với các thuộc tính và phương thức riêng. Theo mô hình này, ta có thể mở rộng
mô hình quan hệ để quản lý được các dữ liệu phức tạp hơn. Xét ví dụ đã đề cập
ở trên, trong quan hệ Client, để dễ quản lý các khách hàng ta bổ sung vào quan
hệ này một thuộc tính mới đó là Pic mô tả ảnh của khách hàng. Dựa trên mô
hình quan hệ- đối tượng, quan hệ Client sẽ có lược dồ sau:
Client (Comp:String, Fname:String,Lname:String, AcountNum:Integer,
PhoneNum:Integer, StreetNum:Integer, StreetName:String, City:String, Pic:
Image), trong đó Image là một lớp đối tượng.
1.2.4. Phương pháp quản trị CSDL không gian
Có hai vấn đề về quản trị CSDL của GIS là quản trị dữ liệu không gian
(Spatial Data) và quản trị dữ liệu phi không gian (Non-Spatial Data). Đó là hai
mảng dữ liệu căn bản và không thể tách rời của một hệ thống GIS. Do vậy hệ
thống GIS phải giải quyết các vấn đề của một DBMS thông thường cho phần dữ
Hình 1.12. Số liệu Vector được biểu thị dưới dạng điểm ( Point)
* Kiểu đối tượng đường (Lines hoặc Arcs)
Đường được xác định như một tập hợp dãy của các điểm, mô tả các đối
tượng địa lý dạng tuyến, có các đặc điểm sau:
- 21 -
- Là một dãy các cặp tọa độ
- Một đường bắt đầu và kết thúc bởi nút (node)
- Các đường nối với nhau và cắt nhau tại nút
Hình 1.13. Số liệu vector được biểu thị dưới dạng arc.
* Kiểu đối tượng vùng (area):
Vùng được xác định bởi ranh giới các đường thẳng, các đối tượng địa lý
có diện tích và đóng kín bởi một đường được gọi là đối tượng vùng, có các đặc
điểm sau:
- Vùng (area) được mô tả bằng tập các đường (arc) và điểm nhãn (label points).
- Một điểm nhãn nằm trong vùng để mô tả, xác định cho mỗi một vùng.
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ị) Hình 1.15. Biểu diễn raster
* So sánh mô hình Raster và mô hình Vectơ
Bảng 1.1 là một vài so sánh hai mô hình thường được sử dụng trong GIS:
mô hình raster và mô hình vectơ, mỗi mô hình đều có ưu nhược điểm riêng.
Thực tế, các hệ thống GIS thị trường được xây dựng trên cơ sở mô hình vectơ
hay raster. Tuy nhiên nhiều hệ thống GIS được xây dựng trên cơ sở cả hai loại
mô hình này . Do vậy, tùy theo ứng dụng cụ thể để lựa chọn công cụ phần mềm
GIS cho phù hợp.
Copyright: Tài liệu đại học ©