Đề tài Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian

Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


1

LỜI CẢM ƠN Trong thời gian thực hiện đề tài khóa luận tốt nghiệp, dưới sự hướng dẫn tận tình của giáo viên hướng dẫn và được phía nhà trường tạo điều kiện thuận lợi, tôi đã có một quá trình nghiên cứu, tìm hiểu và học tập nghiêm túc để hoàn thành đề tài. Kết quả thu được không chỉ do nỗ lực của cá nhân tôi mà còn có sự giúp đỡ của quý thầy cô, gia đình và các bạn. Tôi xin chân thành cảm ơn Bán giám hiệu nhà trường, Ban chủ nhiệm khoa Công Nghệ Thông Tin – Trường Đại học Công Nghệ đã quan tâm, tạo điều kiện giúp tôi hoàn thành hoàn thành khóa luận tốt nghiệp. Thầy Nguyễn Hải Châu: Thầy đã hướng dẫn, hỗ trợ tôi hoàn thành tốt đề tài về phương pháp, lý luận và nội dung trong suốt thời gian thực hiện khóa luận tốt nghiệp. Gia đình đã tạo điều kiện học tập tốt nhất. Các bạn đã giúp đỡ, trao đổi thông tin về đề tài trong quá trình thực hiện khóa luận. Trong quá trình thực hiện và trình bày khóa luận không thể tránh khỏi những sai sót và hạn chế, do vậy tôi rất mong nhận được sự góp ý, nhận xét phê bình của quý thầy cô và các bạn. Kính chúc quý thầy cô và các bạn sức khỏe! Người thực hiện đề tài Hoàng Thị Hồng Trang Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


2

MỤC LỤC MỤC LỤC........................................................................................................................ 2  MỤC LỤC BẢNG BIỂU ................................................................................................ 5  A.  PHẦN MỞ ĐẦU...................................................................................................... 7  1.  Giới thiệu .............................................................................................................. 7  2.  Ý nghĩa khoa học và thực tiễn .............................................................................. 8  3.  Mục đích nghiên cứu ............................................................................................ 9  4.  Đối tượng nghiên cứu ......................................................................................... 10  5.  Phạm vi nghiên cứu ............................................................................................ 10  B.  NỘI DUNG ............................................................................................................ 11  CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN....................... 11  1.  Khái niệm........................................................................................................... 11  1.1  Hệ thống cơ sở dữ liệu không gian............................................................... 11  1.2. Cơ sở dữ liệu không gian (Spatial Database) .............................................. 12  2.  Mô hình cơ sở dữ liệu không gian ................................................................... 16  2.1 Xây dựng mô hình CSDL không gian ............................................................ 17  2.2 Cơ sở hình học trong tổ chức các đối tượng không gian cơ bản.................. 25  3.  Truy vấn thực hiện trong CSDL không gian.................................................. 30  CHƯƠNG 2: BÀI TOÁN TÍNH TOÁN XẤP XỈ VỚI CÁC TRUY VẤN LIÊN QUAN ĐẾN KHOẢNG CÁCH TRONG CƠ SỞ DỮ LIỆU KHÔNG GIAN........ 34  1.  Các truy vấn liên quan đến khoảng cách........................................................ 34  1.1 Truy vấn khu vực theo khoảng cách δ ........................................................... 37  1.2 Truy vấn K vùng lân cận gần nhất................................................................. 38  1.3 Truy vấn nối các khu vực theo khoảng cách δ (truy vấn đệm).................... 39  1.4  Phép nối khoảng cách Iceberg...................................................................... 39  1.5 Truy vấn K cặp đối tượng gần nhất .............................................................. 39  Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


3

1.6  Nối K vùng lân cận gần nhất ........................................................................ 40  1.7 Truy vấn K- nối khoảng cách ......................................................................... 40  2  R – Tree.............................................................................................................. 42  2.1 Khái niệm.......................................................................................................... 43  2.2 Cấu trúc của một R-tree.................................................................................. 45  2.3 Thuật toán R-Tree ........................................................................................... 47  3  Các kỹ thuật tính toán xấp xỉ khoảng cách .................................................... 56  3.1  Thu nhỏ không gian tìm kiếm ...................................................................... 56  3.2  Kỹ thuật tìm kiếm theo kinh nghiệm........................................................... 59  3.2.1 Tìm kiếm khu vực.......................................................................................... 59  3.2.2 Simulated Annealing ..................................................................................... 60  3.2.3 Thuật toán phát sinh ..................................................................................... 61  CHƯƠNG 3 MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN TÍNH TOÁN XẤP XỈ KHOẢNG CÁCH TRONG THỰC TẾ....................................................................... 63  1.  Ứng dụng trong việc xây dựng một hệ thống khung (framework) xử lý hiệu quả các truy vấn không gian cơ bản. ...................................................................... 64  2.  Tăng tốc quá trình phân tích, thực thi và hiển thị dữ liệu địa lý trong các truy vấn liên quan đến khoảng cách (DBQs) ......................................................... 66  3.  Xây dựng thuật toán xấp xỉ như một công cụ hạn chế những khó khăn phát sinh đối với kích thước địa lý của đối tượng .......................................................... 68  4.  Tính toán độ chính xác về vị trí trên bản đồ và chênh lệch về khoảng cách giữa các đối tượng trong truy vấn ........................................................................... 70  CHƯƠNG 4 MỘT SỐ THUẬT TOÁN TÍNH KHOẢNG CÁCH TRONG KHÔNG GIAN ĐỊA LÝ & ĐÁNH GIÁ HIỆU NĂNG.............................................................. 74  1.  Tính toán khoảng cách giữa các đối tượng địa lý theo công thức Haversine 74  1.1  Công thức Haversine..................................................................................... 74  Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


4

1.2  Công thức Haversine trong truy vấn tìm khoảng cách ngắn nhất............ 77  1.3 Đánh giá thuật toán Haversine ....................................................................... 81  2.  Tính toán khoảng cách trong hệ tọa độ địa lý theo khoảng cách Vincenty. 82  2.1 Khái niệm.......................................................................................................... 82  2.2 Thuật toán Vincenty ........................................................................................ 85  3. Đánh giá thuật toán Haversine và Vincenty....................................................... 89  C.  KẾT LUẬN............................................................................................................ 91  1.  Những kết quả đạt được...................................................................................... 91  2.  Đánh giá .............................................................................................................. 92  3.  Hướng phát triển ................................................................................................. 92  TÀI LIỆU THAM KHẢO............................................................................................ 93  Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


5

MỤC LỤC BẢNG BIỂU Hình 1: Trang WebGis www.bando.com.vn ........................................................15  Hình 2: (a) Một region mẫu, (b) Biểu diễn dạng mảng nhị phân của region, (c) Các khối cực đại và các khối phổ thông được chia sẻ trong region - (d) quadtree tương ứng. .............................................................................................................20  Hình 3: Ví dụ một PR quadtree.............................................................................22  Hình 4: Biểu diễn dạng đường..............................................................................24  Hình 5: Biểu diễn dạng khu vực ...........................................................................24  Hình 6: Biểu diễn tập đối tượng trong khu vực ....................................................24  Hình 7: Biểu diễn đối tượng dạng mạng lưới .......................................................25  Hình 8: Mô hình d-simplex..................................................................................26  Hình 9: Phép toán hợp trong không gian địa lý ....................................................28  Hình 10: Phép toán trừ trong không gian địa lý....................................................28  Hình 11: Phép toán giao trong không gian địa lý .................................................28  Hình 12: Phép toán bao phủ trong không gian địa lý ...........................................29  Hình 13 Các hàm toán tử trong không gian địa lý................................................30  Hình 14: Mô hình dữ liệu quan hệ xây dựng dựa trên Benchmark database........36  Hình 15: R-Tree và MBRs trong truy vấn ............................................................42  Hình 16: R-Tree và truy vấn trong hai cấu trúc MBR khác nhau.........................42  Hình 17: Ví dụ về R-Tree .....................................................................................44  Hình 18: Cây biểu diễn R-Tree.............................................................................47  Hình 19: Biểu diễn hai chiều của một R-Tree ......................................................47  Hình 20: Cấu trúc một R-Tree ..............................................................................48  Hình 21: Các quan hệ có thể có giữa các MBR (chứa trong, chồng lấn…) .........49  Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


6

Hình 22: Trường hợp phân chia node ...................................................................53  Hình 23: Phân chia entry thành các nhóm node mới ............................................54  Hình 24: Minh họa cấu trúc sản phẩm ArcGIS của ESRI ....................................66  Hình 25: Kiến trúc CSDL trên nền tảng Microsoft...............................................68  Hình 26: Trang web bản đồ trực tuyến diadiem.com ...........................................72  Hình 27: Trang web bản đồ trực tuyến basao.com ...............................................73  Hình 28: Hình dạng Elip của trái đất ....................................................................76  Hình 29: Khoảng cách AB tính theo công thức Haversine trên bản đồ địa lý......79  Hình 30: Mô hình dữ liệu quan hệ ........................................................................80  Hình 31: Thông số các hệ tọa độ elip tròn xoay ...................................................84  Hình 32: Khoảng cách tính theo thuật toán Haversine và Vincenty.....................89  Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


7

A. PHẦN MỞ ĐẦU 1. Giới thiệu Trong vài năm trở lại đây, cùng với sự phát triển không ngừng của các kỹ thuật công nghệ hiện đại, “kỷ nguyên số” đã được bắt đầu và ứng dụng trong mọi lĩnh vực khoa học cũng như phục vụ nhu cầu sử dụng của con người. Nếu như cách đây vài thập kỷ, câu chuyện con người có thể quan sát toàn cảnh trái đất từ trên cao xuống thông qua các thiết bị kỹ thuật như máy tính, tivi… tại bất kỳ đâu và bất kỳ lúc nào vẫn là một viễn cảnh xa vời thì ngày nay điều này đã trở nên quá đơn giản. Để có thể quan sát Trái đất từ mọi góc độ, một cá nhân chỉ cần trang bị cho mình một máy tính nối mạng, và một phần mềm hiển thị hình ảnh 3D như Google Earth hay truy cập vào các trang web bản đồ trực tuyến sẵn có trên mạng Internet… Như vậy, trong bối cảnh hiện tại, sự hiện thực hóa bản đồ số và đưa các kỹ thuật lập bản đồ cũng như phân tích địa lý vào sử dụng rộng rãi với mục đích dân sự cho tất cả các tổ chức, cá nhân có nhu cầu đang trở thành một ngành kinh doanh nhiều lợi nhuận. Trong đó phải kể đến GIS – Hệ thống thông tin địa lý – với rất nhiều công cụ ứng dụng trợ giúp đắc lực cho quá trình xây dựng hệ thống hạ tầng cơ sở dữ liệu không gian và quản lý dữ liệu địa lý. Cùng với đó là hàng loạt các sản phẩm toàn diện và chuyên biệt sử dụng trong ngành khoa học bản đồ và xử lý dữ liệu không gian địa lý được các hãng sản xuất tung ra. Công nghệ GIS cùng với các sản phẩm phần mềm hỗ trợ có rất nhiều ứng dụng trong khoa học nghiên cứu, phục vụ trong đời sống, dịch vụ công ích, quản lý tài nguyên…. và nhiều lĩnh vực khác. Trong cuộc cạnh tranh ngôi vị nhà cung cấp hàng đầu các sản phẩm ứng dụng GIS và xử lý dữ liệu địa lý thì yếu tố giá thành cũng như hiệu năng của chương trình là quan trọng nhất. Trong cuộc cạnh tranh về công nghệ này, nhiều nghiên cứu đã được đưa ra như: Tối ưu hóa khả năng quản lý dữ liệu địa lý bằng phương pháp đánh chỉ Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


8

mục động với cấu trúc dạng cây (tree-like structure) phục vụ tăng tốc quá trình tìm kiếm dữ liệu – đây là vấn đề đặc biệt quan trọng với một khối lượng dữ liệu khổng lồ và phức tạp như thông tin địa lý. Tăng tốc quá trình thực thi với các truy vấn đến Cơ sở dữ liệu không gian, tối thiểu hóa thời gian thực thi của hệ thống, đơn giản hóa độ phức tạp tính toán trong giải thuật nhằm tiết kiềm thời gian thực hiện và tăng hiệu năng tính toán. Trong vấn đề về giải thuật, phương pháp ưu việt chính là tìm ra và áp dụng các thuật toán tính toán khoảng cách tốt nhất, đảm bảo yêu cầu dung hòa giữa độ phức tạp tính toán, tốc độ thực thi và độ chính xác càng cao càng tốt. Nhận thấy sự cần thiết trong ngành khoa học nghiên cứu lý thuyết về các thuật toán tính toán khoảng cách giữa các đối tượng địa lý trong thực tế và vai trò to lớn của các bài toán tính toán gần đúng này, đề tài khóa luận tốt nghiệp “Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian” đã được xây dựng dựa trên quá trình nghiên cứu các thành tựu khoa học trong lĩnh vực này và hệ thống lại một cách bài bản và chi tiết. Bố cục khóa luận Khóa luận tốt nghiệp được trình bày với phần nội dung gồm 04 chương: Chương 1: Tổng quan về cơ sở dữ liệu không gian. Chương 2: Bài toán tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian. Chương 3: Một số ứng dụng của bài toán tính toán xấp xỉ khoảng cách trong thực tế. Chương 4: Một số thuật toán tính toán khoảng cách trong không gian địa lý và đánh giá hiệu năng. 2. Ý nghĩa khoa học và thực tiễn Về khía cạnh nghiên cứu khoa học, các tập đoàn công nghệ trong lĩnh vực GIS vẫn không ngừng nghiên cứu các phương pháp tối ưu hóa các sản phẩm sử dụng thông tin địa lý trong các thiết bị hỗ trợ bản đồ, tìm đường và xác Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


9

định vị trí địa lý của đối tượng. Trong đó, giải pháp đặt ra không chỉ dừng ở việc xây dựng một hệ quản trị cơ sở dữ liệu chuyên biệt quản lý dữ liệu không gian và các thuộc tính đặc biệt của nó với dung lượng khổng lồ và phức tạp, quan trọng hơn là giải pháp nào để tối ưu hóa hiệu năng truy xuất dữ liệu, các giải thuật đề xuất giúp hệ thống thực thi các phép toán (đặc biệt là các phép tính khoảng cách quy mô hàng chục ngàn km) phải thật nhanh chóng nhưng vẫn đảm bảo độ chính xác cần thiết. Trong không gian địa lý với đặc thù bề mặt Trái đất không ổn định, việc dùng các phương pháp tính toán gần đúng là không thể tránh khỏi, tuy nhiên sai số đặt ra cần nằm trong khoảng chấp nhận được, sự cân bằng giữa độ chính xác và thời gian xử lý, trả lời truy vấn và giá thành chính là chìa khóa thành công cho bất kỳ sản phẩm có sử dụng thuật toán dò đường và tính khoảng cách nào. Khóa luận trình bày cụ thể về các giải pháp sử dụng trong bài toán tính toán xấp xỉ khoảng cách, hệ thống một cách khoa học các kỹ thuật sử dụng trong tìm kiếm đối tượng cũng như tính khoảng cách giữa các đối tượng trong truy vấn. Đây hầu hết là những kỹ thuật quan trọng và hiệu quả đang được sử dụng rộng rãi trong các ứng dụng khai thác thông tin về đường đi, địa điểm và quảng cáo trên nền tảng bản đồ số. Do đó các vấn đề về lý thuyết trong lĩnh vực này luôn là đề tài khoa học có tính chất thời sự trên các diễn đàn công nghệ GIS cũng như trong đội ngũ các nhà phân tích, thiết kế sản phẩm. Từ các thuật toán có sẵn, nhà sản xuất hoàn toàn có thể cài đặt và “nhúng” vào trong nhiều ứng dụng như: Bản đồ kỹ thuật số, phần mềm định vị và chỉ đường trên các thiết bị cầm tay, các thiết bị di động đi kèm các phương tiện giao thông, thiết bị tìm vết và đường đi ngắn nhất tích hợp GPS (Hệ thống định vị toàn cầu), …. 3. Mục đích nghiên cứu Đề tài được thực hiện với mục đích Tìm hiểu khái niệm Cơ sở dữ liệu không gian, các công nghệ GIS đương đại. Nghiên cứu các kỹ thuật tính toán gần đúng về khoảng cách và các thuật Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


10

toán liên quan sử dụng trong các truy vấn trên CSDL không gian. Các ứng dụng thiết thực của bài toán tính toán xấp xỉ trong công nghệ thông tin địa lý. Thử nghiệm một số truy vấn sử dụng kỹ thuật tính toán xấp xỉ trong một số truy vấn tiêu biểu. 4. Đối tượng nghiên cứu Mô hình, cấu trúc dữ liệu và cách xây dựng dữ liệu không gian và hệ quản trị CSDL không gian, các phép toán thực thi. Các kỹ thuật tính toán xấp xỉ khoảng cách trong không gian tìm kiếm và các thuật toán. Sản phẩm ứng dụng các kỹ thuật tính toán xấp xỉ đang được sử dụng trong thực tế. Thuật toán tính toán khoảng cách trên bề mặt cầu ứng dụng trong truy vấn về khoảng cách trong không gian địa lý: Haversine, Vincenty. 5. Phạm vi nghiên cứu Do hạn chế về thời gian và giới hạn trong khuôn khổ một đề tài khóa luận tốt nghiệp, đề tài tập trung trình bày các thuật toán và giải pháp sử dụng trong các truy vấn liên quan đến khoảng cách trong CSDL không gian, phục vụ trong quá trình xử lý, phân tích và hiển thị dữ liệu địa lý của một ứng dụng GIS bất kỳ trong thực tế. Qua đó đưa ra đánh giá hiệu năng của từng giải pháp và đề xuất các hướng phát triển cho thuật tính toán gần đúng trong tương lai. Qua đó, độc giả có được cái nhìn tổng quan về các kỹ thuật cũng như thuật toán tính toán gần đúng đang được sử dụng trong các ứng dụng xây dựng, quản lý và thiết kế dữ liệu thông tin địa lý, cơ sở dữ liệu không gian và hướng phát triển của chúng trong công cuộc nghiên cứu nhằm hoàn thiện tốc độ xử lý, tính toán, truy xuất dữ liệu của hệ thống với sự trợ giúp của các thuật toán tích hợp hiệu quả và chính xác. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


11

B. NỘI DUNG CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG GIAN 1. Khái niệm 1.1 Hệ thống cơ sở dữ liệu không gian Hệ thống cơ sở dữ liệu không gian – Spatial Database System – là hệ thống quản lý dữ liệu liên quan đến các đối tượng không gian (không gian địa lý), ra đời trước yêu cầu đặt ra trong thực tế là cần một hệ thống để lưu trữ các dữ liệu trong không gian địa lý. Như vậy việc quản lý hệ CSDL không gian phụ thuộc vào hai công nghệ: Một là phương tiện lưu trữ cố định và một là CSDL không gian. Các không gian: Không gian hai chiều (2D): Các không gian hình học (Các bề mặt trên mặt đất ở tỉ lệ co giãn lớn hoặc nhỏ) ™ Hệ thống thông tin địa lý (GIS – Geographic Information System) ™ Cơ sở dữ liệu đặt tại Luxembourg (LIS - Luxembourg Income Study) lưu trữ dữ liệu về các quốc gia. ™ Urban planning – quy hoạch sử dụng không gian địa lý (sử dụng đất, quy hoạch xây dựng đô thị….) Không gian ba chiều (3D): Nghiên cứu vũ trụ, thiên văn học, nghiên cứu bộ não con người trong y học, nghiên cứu cấu trúc phân tử trong ngành sinh học. Yêu cầu đặt ra với hệ thống này là khả năng quản lý và xử lý một khối lượng thông tin khổng lồ của tập hợp các đối tượng địa lý đặt trong mối quan hệ chặt chẽ với nhau. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


12

Theo G.H.Guting[]: Hệ quản trị cơ sở dữ liệu không gian (Spatial Database Management System): Là một hệ CSDL sử dụng kiểu dữ liệu không gian trong mô hình dữ liệu và ngôn ngữ truy vấn, hệ thống hỗ trợ việc thực thi với kiểu dữ liệu không gian bằng việc cung cấp cách đánh chỉ mục và các thuật toán hiệu quả trong trường hợp liên kết các không gian với nhau. Kiểu dữ liệu không gian (Spatial Data type): Kiểu dữ liệu biểu diễn các đối tượng trong không gian Dữ liệu không gian là những mô tả số của hình ảnh bản đồ, chúng bao gồm toạ độ, quy luật và các ký hiệu dùng để xác định một hình ảnh bản đồ cụ thể trên từng bản đồ. Hệ thống thông tin địa lý dùng các số liệu không gian để tạo ra một bản đồ hay hình ảnh bản đồ trên màn hình hoặc trên giấy thông qua thiết bị ngoại vi, … Dữ liệu không gian thường được biểu diễn bằng điểm, đường và vùng. Với hệ thống thông tin địa lý (GIS) có 2 kiểu dữ liệu cơ bản đó là vectơ và raster. 1.2. Cơ sở dữ liệu không gian (Spatial Database) Cơ sở dữ liệu không gian là một mô hình hướng đối tượng cho phép tích hợp thông tin địa lý và thông tin thuộc tính trong cùng một cơ sở dữ liệu theo mô hình dữ liệu quan hệ. Như vậy đây là cơ sở dữ liệu lưu trữ vị trí, hình dạng của các đối tượng không gian cùng với đặc điểm thuộc tính của chúng. Một số hãng phát triển GIS trên thế giới đã có những sản phẩm theo hướng CSDL không gian như: ERSI, Oracle, Intergraph, MapInfo… Cơ sở hạ tầng dữ liệu không gian (Spatial Data Infrastructure - SDI) là nền tảng để dữ liệu không gian và lý lịch dữ liệu cùng với người sử dụng và các công cụ có thể kết nối trong mối quan hệ tương tác lẫn nhau với mục đích sử dụng được các thông tin dữ liệu không gian một cách hiệu quả và linh hoạt. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


13

1.2.1 Hạ tầng CSDL không gian ™ Công nghệ (technology) ™ Chính sách (policies) ™ Chuẩn (standards) ™ Nguồn nhân lực (human resources) ™ Qui trình (procedures) Được xây dựng để đáp ứng yêu cầu thu nhận, xử lý, lưu trữ, phân phối và nâng cao tính hữu dụng của dữ liệu địa lý, làm cơ sở cho việc sản xuất và chia sẻ dữ liệu địa lý giữa các cơ quan, đơn vị,… VD: Cơ sở hạ tầng dữ liệu không gian của một thành phố là một thành phần trong Cơ sở hạ tầng thông tin quốc gia (siêu xa lộ thông tin) nhằm cung cấp những thông tin thiết thực cho mọi người. Các chức năng của quản lý cơ sở dữ liệu ™ Cho phép giảm thiểu sự trùng lặp dữ liệu nhằm tiết kiệm chi phí, sẵn sàng trợ giúp ra quyết định trên một vùng địa lý dựa trên dữ liệu chính xác và hiện thời (cập nhập dữ liệu), người sử dụng dễ dàng biết được tỉ lệ bản đồ gốc (mức độ chi tiết), nguồn gốc dữ liệu, quy trình nhập dữ liệu, kết quả kiểm tra độ chính xác dữ liệu, cấu trúc dữ liệu,… được mô tả bởi lý lịch dữ liệu (metadata). ™ Với một hệ quản trị cơ sở dữ liệu thông thường kiểu dữ liệu bảng hiện nay được sử dụng rất phổ biến. Tuy nhiên, tiến trình tham chiếu với dữ liệu địa lý được thực hiện phức tạp vì chỉ một sự thay đổi nhỏ của dữ liệu địa lý cũng làm cho các dữ liệu bảng khó tham chiếu. Cấu trúc cơ sở dữ liệu định hướng đối tượng không thích hợp cho việc lưu trữ những dữ liệu đặc trưng cũng như phân tích không gian phức tạp. Nhờ tính mở cao, cơ sở dữ liệu quan hệ ngày càng được sử dụng phổ biến trong các hệ thống thông tin địa lý. Mô hình hệ quản trị cơ sở dữ liệu 3 tầng (3-tier) sẽ được sử dụng phổ biến để tăng khả năng cung cấp và Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


14

tích hợp dữ liệu của nhiều ngành theo thời gian thực. Hiện nay, hầu hết các quốc gia đều hướng đến xây dựng cơ sở hạ tầng dữ liệu không gian theo kiến trúc hướng đến dịch vụ (Service Oriented Architecture - SOA) sử dụng các chuẩn mở quốc tế như OpenGIS (OGC) hoặc ISO/TC 211. Tư tưởng chính là coi việc xây dựng cơ sở hạ tầng dữ liệu không gian tương tự như cơ sở hạ tầng trong các lĩnh vực khác: bưu điện, điện thọai, đường giao thông,…như vậy người dùng khi có nhu cầu sẽ tham gia kết nối vào cơ sở hạ tầng để sử dụng và đóng góp các dữ liệu, thông tin về GIS. Đây là một dự án lớn có nền tảng lý luận và cơ sở thực tiễn cao, được phát triển theo cách thức: “Phát triển trước, xây dựng đặc tả sau”. Có nghĩa là: Để giải quyết 1 vấn đề, các tổ chức nghiên cứu hướng tới nhiều giải pháp, sau nhiều năm thử nghiệm sẽ đúc kết thành đặc tả (hay chuẩn mở) công bố cho cộng đồng. Đối với Việt Nam và các nước đang phát triển thì thời điểm hiện nay là cơ hội lớn để chúng ta tiếp cận những tinh hoa từ các tổ chức này để xây dựng những hệ thống GIS tương tự (đa mục tiêu, đa thành viên). Trên cơ sở đó, Việt Nam cần tiến hành xây dựng cơ sở hạ tầng dữ liệu không gian cho mình với các tầm nhìn đều hướng đến một nền tảng để đưa dữ liệu không gian địa lý đến tay người sử dụng một cách đơn giản, dễ dàng và minh bạch. Khảo sát có một số tổ chức đã ứng dụng WebGis để xây dựng bản đồ trực tuyến ™ Trang web của Nhà xuất bản bản đồ - Bộ Tài nguyên và môi trường Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


15

Hình 1: Trang WebGis www.bando.com.vn 1.2.2 Các bước thiết kế CSDL không gian Thiết kế CSDL không gian cần tiến hành qua những bước cơ bản sau ™ Xác định nội dung CSDL ™ Chọn cấu trúc CSDL ™ Thiết kế chi tiết CSDL ™ Phân phối dữ liệu đến người sử dụng ™ Duy trì, cập nhật dữ liệu và vận hành hàng ngày Các thành phần của cơ sở dữ liệu không gian ™ Tập hợp các dữ liệu dạng vector (tập các điểm, đường và vùng) ™ Tập hợp các dữ liệu dạng raster (dạng mô hình DEM hoặc ảnh) ™ Tập hợp các dữ liệu dạng mạng lưới (đường giao thông, lưới cấp thoát nước, lưới điện ...) ™ Tập hợp các dữ liệu địa hình 3 chiều và bề mặt khác ™ Dữ liệu đo đạc ™ Dữ liệu dạng địa chỉ ™ Các bảng dữ liệu: Là thành phần quan trọng của cơ sở dữ liệu không gian, được liên kết với các thành phần đồ họa với nhiều kiểu liên kết khác nhau. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


16

2. Mô hình cơ sở dữ liệu không gian Trong những năm gần đây, đã có rất nhiều nghiên cứu đang được triển khai về vấn đề quản lý dữ liệu không gian. Cách phương pháp tiếp cận ban đầu trong lĩnh vực GIS đã gần như làm cạn kiệt những nỗ lực của các nhà khoa học trong việc tìm kiếm hình thức biểu diễn hình học chính xác của dữ liệu không gian và việc bổ sung những phép toán mới giữa các đối tượng không gian. Sau đó, chỉ có một cải tiến thô sơ là việc kết hợp dữ liệu không gian với dữ liệu thông thường. Và kết quả là việc quản lý dữ liệu địa lý phải chia thành 2 quá trình xử lý riêng biệt nhau: một là cho dữ liệu không gian và một là để xây dựng các thuộc tính cho dữ liệu thông thường và sự kết hợp của chúng với dữ liệu không gian. Nỗ lực để định nghĩa một ngôn ngữ thông dụng và khả dụng để đơn giản thao tác xử lý các truy vấn hầu như không mang lại kết quả, và do đó quá nhiều chương trình bắt buộc phải sử dụng đến. Kết quả là việc xử lý dữ liệu không gian thiếu đi những giải pháp hình thức cơ bản. Theo một khía cạnh khác, năng lực xử lý của dữ liệu thông thường chỉ có thể được lưu trữ thông qua Hệ quản trị CSDL. Bên cạnh đó, do tính chất phức tạp của kiểu dữ liệu không gian dẫn đến việc quản lý dữ liệu loại này không thể sử dụng Hệ quản trị cơ sở dữ liệu truyền thống. Vì những lí do trên mà nhiều công trình nghiên cứu liên quan đến dữ liệu không gian đã được tiến hành bao gồm nhiều lĩnh vực như: Thiết kế cấu trúc dữ liệu vật lý tối ưu và các phương pháp truy cập, nghiên cứu việc xử lý truy vấn và tối ưu hóa các kỹ thuật, giao diện tương tác ảo… Tất cả các cách tiếp cận này chắc chắn sẽ đưa ra một mô hình dữ liệu không gian theo cách gián tiếp trong đó mô hình này sẽ không đóng vai trò là đối tượng chính. Về khía cạnh công nghệ, hình thể, vị trí không gian của các đối tượng cần quản lý, được miêu tả bằng các dữ liệu đồ hoạ. Trong khi đó, tính chất các đối tượng này được miêu tả bằng các dữ liệu thuộc tính. Mô hình cơ sở dữ liệu không gian không những quy định mô hình dữ liệu với các đối tượng đồ hoạ, đối tượng thuộc tính mà còn quy định liên kết giữa chúng thông qua mô hình quan hệ và định nghĩa hướng đối tượng bao gồm các tính chất như thừa kế (inherit), đóng gói (encapsulation) và đa hình Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


17

(polymorphism). Ngoài ra, cơ sở dữ liệu không gian hiện đại còn bao gồm các ràng buộc các đối tượng đồ hoạ ngay trong cơ sở dữ liệu, được gọi là topology (tương quan không gian) - Phương thức thể hiện các ràng buộc đối với các đối tượng đồ hoạ ngay trong cơ sở dữ liệu. Đặc điểm chung của một số mô hình CSDL không gian: ™ Hỗ trợ tập hợp các kiểu dữ liệu đã định dạng sẵn: Tập các điểm, tập các bề mặt… ™ Có thể sử dụng một hoặc hai kiểu cấu trúc dữ liệu phức tạp để lưu lại các dữ liệu không gian, với việc sử dụng hai kiểu cấu trúc cùng một lúc tức là một để ghi nhận dữ liệu không gian và một để ghi nhận dữ liệu thông thường. ™ Định nghĩa được các phép toán áp dụng với một kiểu dữ liệu không gian riêng biệt bất kỳ. 2.1 Xây dựng mô hình CSDL không gian ™ Xây dựng mô hình các đối tượng riêng lẻ. ™ Xây dựng mô hình cho một tập hợp các đối tượng có liên quan đến nhau trong không gian địa lý. Việc vận dụng dữ liệu mật độ cao hoặc dữ liệu không gian để lưu trữ và phục hồi trong cơ sở dữ liệu đa phương tiện là một điều rất quan trọng. Dữ liệu không gian bao gồm các điểm, đường, hình chữ nhật, đa giác, bề mặt hay các đối tượng mật độ cao bao gồm cả thời gian. Các phương thức đánh chỉ mục cung cấp đường dẫn đến dữ liệu hướng không gian được gọi là các phương thức truy nhập không gian (Spatial Access Methods – SAM). Đến nay đã có rất nhều SAM được giới thiệu bao gồm các grid file[1], K-D-B-tree [2], R-trees [3], R*-trees [4] , Filter Trees [5] , TV-tree[6], X-trees[7] và SS-tree[8]. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


18

Trong các cơ sở dữ liệu không gian, các đối tượng không gian thông thường được ánh xạ thành các véc-tơ đặc trưng trong không gian mật độ cao và các truy vấn được xử lý trên cơ sở dữ liệu của các véc-tơ đặc trưng này. Các véc-tơ đặc trưng thường thấy đó là biểu đồ màu, mô tả hình thức, các biểu diễn văn bản,…mà mỗi một loại có những đặc tính khác nhau. Tuy nhiên điều quan trọng là phải tìm ra được một cách biểu diễn thích hợp cho các véc-tơ đặc trưng và nhằm xác định chính xác việc đo lường tính đồng dạng hoặc khoảng cách giữa chúng. Bởi vậy một hệ thống đa phương tiện cần phải có nhiều phương thức truy cập không gian để xử lý một truy vấn. Trong quá khứ đã có một số nhà nghiên cứu đề xuất các phép toán ghép nối không gian cho các tập dữ liệu không gian khác nhau. Tất cả các phương pháp này đề đòi hỏi các cặp SAM có cùng một kiểu cấu trúc. Các đặc tính cơ bản của phép truy nhập không gian. ™ Cấu trúc dữ liệu không gian CSDL không gian bao gồm các đối tượng không gian như điểm, đường, vùng, hình chữ nhật, bề mặt, hình khối và thậm chí là các dữ liệu mật độ cao trong đó gồm cả thời gian. Một ví dụ của CSDL không gian là các thành phố, những con sông, đường xá, quốc gia, bang, các dãy núi, các thành phần trong một hệ thống CAD[9] (Thiết kế sử dụng sự trợ giúp của máy tính),…Ví dụ về các thuộc tính của dữ liệu không gian có thể có là lưu vực của một con sông, hay biên giới của một quốc gia…Thông thường các thuộc tính còn có thể gắn thêm các các thuộc tính thông tin dạng phi không gian (non-spatial) như độ cao, tên thành phố,…với CSDL không gian. Các cơ sở dữ liệu không gian thuận tiện cho việc lưu trữ và đạt hiệu quả tốt cho quá trình xử lý các thông tin dạng spatial[10] và non-spatial[11] một cách lý tưởng mà không cần thiết phải quan tâm đến các mối liên hệ khác. Vì thế các sơ sở dữ liệu sẽ nâng cao khả năng đáp ứng của các ứng dụng kiểm soát môi trường, khoảng không, phát triển đô thị, quản lý nguồn lực, và trong các hệ thống GIS [Buchmann et al. 1990; Günther and Schek 1991] []. ™ Phương pháp lưu trữ, quản lý và biểu diễn dữ liệu không gian Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


19

Mọi hệ thống quản trị cơ sở dữ liệu đều thực hiện việc sắp xếp dữ liệu theo khóa riêng của mình. Trong trường hợp với CSDL không gian, việc sắp xếp dựa trên tất cả các khóa spatial, điều đó có nghĩa rằng không giống như trong các hệ thống quản trị cơ sở dữ liệu truyền thống, việc sắp xếp dựa trên tất cả các dữ liệu đang sử dụng. Vì vậy các kỹ thuật này được biết với tên gọi các phương pháp spatial indexing[12] – đánh chỉ mục không gian. Một hướng tiếp cận trong việc biểu diễn spatial data là phân chia một cách có cấu trúc từ những dữ liệu non-spatial đồng thời quản lý một cách thích hợp các mối liên kết giữa chúng [Aref and Samet 1991a]. Đây được xem như là một trong những nguyên nhân gây nên tình trạng phải mất nhiều băng thông hơn cho việc thu thập dữ liệu không gian. Trong trường hợp như vậy, các phép toán không gian (spatial operation) được thực hiện trực tiếp trên các cấu trúc spatial data. Điều này cung cấp tính linh hoạt hơn nữa cho việc chọn lựa cấu trúc spatial thích hợp thay vì phụ thuộc vào các cấu trúc non-spatial (ví dụ như với một cơ sở dữ liệu quan hệ). Một ví dụ về kiểu truy vấn được đặt ra cho một hệ thống cơ sở dữ liệu không gian là “Hãy tìm các tên đường đi ngang qua trường đại học của vùng RiverSide”. Yêu cầu này đòi hỏi phải trích xuất các bản ghi có trường “region name” mang giá trị là “trường đại học vùng RiverSide” và xây dựng một bản đồ A. Kế tiếp, thực hiện phép giao giữa A với bản đồ đường đi B tạo được bản đồ mới C có các con đường được chọn lựa. Bây giờ tạo một mối liên kết mới chỉ gồm một thuộc tính là các tên đường hợp lệ từ các đường trong bản đồ C. Tất nhiên là còn có các hướng tiếp cận khác trả lời câu truy vấn trên. Hiệu quả của chúng phụ thuộc vào tính tự nhiên và các tính chất của dữ liệu. Khái quát các khái niệm dữ liệu cơ sở trong CSDL không gian Trong phần dưới đây, đề tài sẽ trình bày một cách khái quát các khái niệm dữ liệu cơ sở trong CSDL không gian như vùng, điểm, chữ nhật, và đường. Để biết thêm các thông tin chi tiết về các thành phần này, xin tham khảo thêm trong [Samet 1990a; Samet 1990b]. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


20

™ Dữ liệu vùng - Region Data Một region có thể được biểu diễn bằng đường biên hoặc nội dung bên trong của chính nó. Trong phần này, region được hiểu theo cách biểu diễn nội tại của nó. Một cách biểu diễn thông dụng nhất của region là mảng hình ảnh. Trong trường hợp này, ta có một tập các phần tử ảnh (gọi là các pixel). Khi số lượng các phần tử trong mảng quá lớn, phải tiến hành động thái là giảm bớt kích thước mảng bằng cách kết hợp các pixel tương tự (đồng nhất hay có cùng giá trị). Ở đây có hai hướng tiếp cận cơ bản. Hướng tiếp cận đầu tiên là của [Rutovitz 1968]: phân chia mảng thành 1*m khối. Đây là cách biểu diễn theo hàng và nó được biết với tên runlength code. Một hướng tiếp cận khác xem region như là một tập các khối vuông cực đại (hoặc các khối có hình dạng bất kỳ). Thông thường các khối được xác định bởi tâm và radii của chúng. Sự biểu diễn này được gọi là medial axis transformation (MAT). Hình 2: (a) Một region mẫu, (b) Biểu diễn dạng mảng nhị phân của region, (c) Các khối cực đại và các khối phổ thông được chia sẻ trong region - (d) quadtree tương ứng. Thuật ngữ quadtree (cây tứ phân) là chỉ số không gian được dùng để phân chia đệ quy một tập hợp dữ liệu (chẳng hạn, một ảnh) thành các ô vuông cho đến khi mỗi ô vuông có một giá trị thuần nhất. Cây tứ phân thường được dùng để lưu trữ dữ liệu raster. Ở đây quadtree được sử dụng để mô tả rất nhiều phần tử của các cấu trúc dữ liệu có thứ bậc (dựa trên nguyên Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


21

tắc đệ quy hay còn gọi là các phương pháp chia để trị). ™ Dữ liệu điểm - Point Data Dữ liệu điểm đa chiều có thể được biểu diễn dưới rất nhiều hình thức khác nhau. Sự lựa chọn sau cùng cho một tác vụ cụ thể sẽ bị ảnh hưởng bởi kiểu operation sẽ được thực hiện trên dữ liệu. Phần này đề cập chủ yếu đến kiểu biểu diễn PR quadtree (P: Point và R: Region) là phương thức phân ly chủ đạo. Đây là sự lắp ghép giữa region quadtree và point data, và PR quadtree được tổ chức tương tự như region quadtree. Chỉ có một sự khác biệt đó là các nút lá hoặc là rỗng (ở đây biểu diễn bằng màu TRẮNG), hoặc chứa dữ liệu điểm (màu ĐEN) và các giá trị tương ứng của chúng. Hình vẽ sau là một PR quadtree tương ứng với một số lượng nhất định point data: Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


22

Hình 3: Ví dụ một PR quadtree Điểm bất lợi của PR quadtree là mức phân chia tối đa phụ thuộc vào sự phân ly tối thiểu giữa hai point. Trong những trường hợp đặc biệt, nếu hai point là rất gần nhau thì sự phân chia là rất nhỏ. ™ Dữ liệu kiểu chữ nhật - Rectangle Data Kiểu dữ liệu rectangle nằm đâu đó giữa kiểu dữ liệu point và region. Rectangle thường được sử dụng để làm xấp xỉ với các đối tượng khác trong một bức ảnh. Ví dụ các rectangle biên thường được sử dụng trong các ứng dụng bản đồ để làm xấp xỉ các đối tượng như hồ nước, rừng, đồi,… [Hinrichs and Nieverglt 1983] đã suy giảm mỗi rectangle thành một điểm trong không gian đa chiều lớn, và họ đối xử với các vấn đề phát sinh như một tập các điểm chứ không phải hình. Mỗi rectangle trong một sản phẩm Cartesian (Hệ toạ độ Đề-các) có hai interval (khoảng không gian) một chiều trong đó mỗi interval được biểu diễn bởi trọng tâm và quy mô của chúng. Mỗi một tập interval trong một chiều cụ thể được biểu diễn bởi một grid file. ™ Dữ liệu đường - Line Data Line data là một hình thức biểu diễn xác định các biên của các region. Cách biểu diễn đơn giản nhất là đa giác gồm có các véc-tơ xác định khuôn dạng của các liệt kê các cặp giá trị x và y tương xứng với điểm bắt đầu và kết thúc của chúng. Các véc-tơ thường được sắp xếp theo liên kết của chúng. Một trong những cách biểu diễn thông dụng nhất là chain code[13] [Freeman 1974]. ™ Dữ liệu không gian - Spatial (High-dimentional) Data Rất nhiều các cấu trúc SAM (Spatial Access methods) thành công dựa trên nguồn gốc của sự phân ly không gian có thứ bậc. Ý tưởng ở đây là đánh chỉ mục một cách liên tục các vùng không gian, như vậy việc tìm kiếm có Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


23

thể được xuất phát ở mức cao hướng về những vùng không gian thích hợp. Một cách thức phổ biến và khả quan để tổ chức và truy cập các đối tượng đa chiều là sử dụng R-tree hoặc các biến thể của nó bởi vì trong R-tree, không gian dữ liệu được phân ly liên tiếp nhau thành các rectangle, còn gọi là hyper-rectangle. Với hệ thống thông tin địa lý - GIS Hệ thống thông tin địa lý làm việc với hai dạng mô hình dữ liệu địa lý khác nhau về cơ bản - mô hình vector và mô hình raster. 9 Trong mô hình vector, thông tin về điểm, đường và vùng được mã hoá và lưu dưới dạng tập hợp các toạ độ x,y. Vị trí của đối tượng điểm, như lỗ khoan, có thể được biểu diễn bởi một toạ độ đơn x,y. Đối tượng dạng đường, như đường giao thông, sông suối, có thể được lưu dưới dạng tập hợp các toạ độ điểm. Đối tượng dạng vùng, như khu vực buôn bán hay vùng lưu vực sông, được lưu như một vòng khép kín của các điểm toạ độ. 9 Mô hình vector rất hữu ích đối với việc mô tả các đối tượng riêng biệt, nhưng kém hiệu quả hơn trong miêu tả các đối tượng có sự chuyển đổi liên tục như kiểu đất hoặc chi phí ước tính cho các bệnh viện. Mô hình raster được phát triển cho mô phỏng các đối tượng liên tục như vậy. Một ảnh raster là một tập hợp các ô lưới. Cả mô hình vector và raster đều được dùng để lưu dữ liệu địa lý với nhưng ưu điểm, nhược điểm riêng, Các hệ GIS hiện đại có khả năng quản lý cả hai mô hình này. 2.1.1 Xây dựng mô hình của các đối tượng riêng lẻ Sử dụng phương pháp trừu tượng hóa cơ bản để mô phỏng các đối tượng riêng lẻ trong không gian, thông qua việc sử dụng các kí hiệu hình học có tính chất tượng trưng: Các kí hiệu hình học thường gặp trong bản đồ địa lý thông thường và những đối tượng cần được biểu diễn trong CSDL không gian tương ứng: ™ Điểm: y Kí hiệu thành phố Mô phỏng hình học của một đối tượng trong trường hợp này chỉ xác định Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


24

vị trí của nó trên không gian bản đồ chứ không thể hiện phạm vi hay tỉ lệ kích thước tương ứng của đối tượng. ™ Đường thẳng, đoạn thẳng: Dòng sông Đường dây Đường giao thông Hình 4: Biểu diễn dạng đường Kí hiệu hình học của đối tượng kéo dài trong không gian hoặc kết nối các không gian địa lý. Vùng miền, lãnh thổ: Diễn tả phạm vi và khu vực của đối tượng Rừng Hồ ao Thành phố Hình 5: Biểu diễn dạng khu vực 2.1.2 Xây dựng mô hình cho một tập hợp các đối tượng có liên quan trong không gian địa lý ™ Ranh giới phân chia giữa các đối tượng Qui hoạch đất Phân chia quận huyện Sở hữu đất Không gian các điểm Hình 6: Biểu diễn tập đối tượng trong khu vực Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


25

™ Xây dựng mô phỏng mạng lưới các đối tượng Hệ thống giao thông Mạng lưới viễn thông Hệ thống đường thủy Đường điện, điện thoại Hình 7: Biểu diễn đối tượng dạng mạng lưới 2.2 Cơ sở hình học trong tổ chức các đối tượng không gian cơ bản Câu hỏi đặt ra là liệu hệ quy chiếu hình học cổ điển có thích hợp để xây dựng mô hình CSDL không gian? Vấn đề đặt ra là không gian địa lý trong thực tế có tính chất liên tục và liền mạch trong khi máy tính chỉ có thể xử lý và lưu trữ những số liệu dưới dạng số học rời rạc. Với hệ quy chiếu 2 chiều Euclidean điểm P được biểu diễn bởi cặp tọa độ (x, y): P = (x, y) € R2 (real * real) Dễ dàng nhận thấy với hình học Euclidean các đối tượng được quy về mặt phẳng với 2 thông số tọa độ x, y. Dẫn đến khó có thể xác định một điểm bất kỳ có thuộc một đường thẳng nối 2 điểm khác trong không gian hay không? Mục đích xây dựng cơ sở hình học để tổ chức hợp lý các đối tượng không gian: Tránh phải sử dụng phép tính toán thêm các giao điểm mới trong giới hạn các phép toán hình học. Có 2 cách tiếp cận: ™ Simplicial Complexes – Tổ hợp đơn giản (từ combinatorial topology – tổ hợp tương quan không gian) ™ Realms 2.2.1 Simplicial Complexes Định nghĩa: Simplicial Complexes – Tổ hợp đơn giản là một tập hữu hạn các đỉnh (simplices) để giao điểm các đoạn thẳng nối giữa chúng tạo thành các bề Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


26

mặt. d-simplex (d hình): Số lượng đối tượng nhỏ nhất trong không gian d chiều y 0 - simplex Hình 8: Mô hình d-simplex d-simplex bao gồm (d + 1) đỉnh trong không gian d-1 chiều Các thành phần tạo nên một hình (simplex) được gọi là các bề mặt (faces) 2.2.2 Realms Định nghĩa khái niệm Realms Theo cách trực quan: Realms là toàn bộ sự mô tả hình học (tất cả các điểm, các đường) của ứng dụng. Định nghĩa chính thức: Realms là tập hợp các điểm và đoạn thẳng định nghĩa một mạng lưới thỏa mãn các tính chất sau: ™ Mỗi một điểm hoặc điểm kết thúc của một đoạn phải là một điểm của mạng lưới. ™ Mỗi điểm kết thúc của đoạn cũng phải thuộc Realms ™ Không có điểm nào thuộc Realms lại nằm trong một đoạn thẳng (không tính hai đầu mút) ™ Hai đoạn bất kỳ riêng biệt không giao nhau hoặc nằm trùng lên nhau Như vậy Realms (vùng, khu vực) là nền tảng hình học rời rạc cơ bản làm cơ sở trong việc xây dựng một hay nhiều kiểu dữ liệu không gian. Một Realm là một tập hữu hạn các điểm và các đoạn thẳng không giao nhau nằm trong một khung lưới các điểm rời rạc và mô tả một cách tổng quát cơ sở hình học 1- simplex 2- simplex 3- simplex Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


27

hoàn chỉnh của không gian ứng dụng liên quan trong không gian 2 chiều. Ý tưởng là xây dựng kiến trúc hình học của các đối tượng địa lý bằng cách dựng chúng dựa vào các điểm và đoạn trong một Realm đã xác định trước. Cơ sở toán học sử dụng trong việc thiết kế các kiểu dữ liệu không gian mặc định là không gian Euclidean. Một điểm theo đó sẽ được biểu diễn bởi một cặp số thực. Tuy nhiên, trong thực tế không tồn tại một cặp số thực như vậy trên máy tính mà chỉ có các tập hợp xấp xỉ. Điều này dẫn đến rất nhiều vấn đề nảy sinh trong tính toán hình học. Khái niệm khu vực – Realm góp phần giải quyết các vấn đề của dữ liệu số học thô và sự chính xác theo hình học topo bằng các lớp khu vực – Realm layer. Mặt khác nó cũng khắc phục vấn đề xảy ra khi có đoạn thẳng cắt qua mạng lưới các điểm rời rạc ban đầu và đảm bảo tính chính xác hình học của các đối tượng địa lý. Hơn thế nữa, nó cho phép việc định nghĩa chính thức các kiểu dữ liệu không gian chung hoặc các phép toán đại số, như vậy các đặc tính đóng hữu dụng sẽ không chỉ được đặt ra trên lý thuyết mà còn được ứng dụng trong thực tế ngành công nghệ thông tin. Ví dụ với dữ liệu ứng dụng là một tập hợp các điểm và các đoạn thẳng giao nhau. Cần đặt một đoạn thẳng cắt các đoạn thẳng khác: Ý tưởng cơ bản là làm thay đổi không đáng kể vị trí các đường thẳng. 2.2.3 Minh họa một số phép toán thực hiện trên dữ liệu không gian Phép toán thực hiện trên hai đối tượng không giain gA & gB trong không gian địa lý với các trường hợp (i), (ii), (iii) và (iv) dựa vào vị trí tương đối giữa các đối tượng ban đầu. Giả thiết với các đối tượng trong không gian địa lý với mô phỏng hình học là 3 kiểu dữ liệu không gian phổ biến: Điểm, đường và vùng/miền. Các phép toán tương tự như các phép toán với tập hợp trong đại số học. 2.2.3.1 Phép toán hợp Hợp hai đối tượng: gA & gB. Kết quả trả về là một hoặc nhiều đối tượng với thuộc tính tương đương. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


28

Hình 9: Phép toán hợp trong không gian địa lý 2.2.3.2 Phép toán trừ (cắt bởi một đối tượng) Đối tượng gA bị cắt bởi gB, cho kết quả là một hoặc hai đối tượng mới Hình 10: Phép toán trừ trong không gian địa lý 2.2.3.3 Phép toán giao Kết quả trả về phần giao nhau giữa hai đối tượng Hình 11: Phép toán giao trong không gian địa lý 2.2.3.4 Phép toán bao phủ Với hai đối tượng SA và SB bao gồm các thuộc tính tương ứng (A, G) = (a, gA) và (B, G) = (b, gB) (Hình 12) Kí hiệu miền giao nhau của hai thuộc tính dạng vùng – region là: g2 gA ∩ gB = g2 Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


29

gA = g1 hợp g2 gB = g2 hợp g3 Kết quả của các phép bao phủ theo vị trí tương đối: SA – Left, SB – Right là tập các thuộc tính của cả hai đối tượng ban đầu (A, B, G) ™ Inner Overlay (bao phủ bên trong) ™ Left Overlay (bao phủ bên trái – theo SA) ™ Right Overlay (bao phủ bên phải – theo SB) ™ Full Overlay (Bao phủ hoàn toàn) Hình 12: Phép toán bao phủ trong không gian địa lý e. Minh họa các hàm toán tử đặc trưng trong CSDL không gian Đối tượng ban đầu - g qua các phép toán định dạng cho kết quả tương ứng như hình dưới đây (áp dụng với các đối tượng hình học trong không gian) (Hình 14) ™ Spatial complemenation (Phép tính phần bù): Kết quả trả về gC1 và gC2 ™ Spatial Boundary (Phép lấy đường biên): Kết quả trả về gB1 và gB2 - đường biên phân chia ranh giới giữa các đối tượng. ™ Spatial Envelope (Phép bao): Kết quả trả về gE – Vùng bao trùm ngoài cùng lên các đối tượng, không hiển thị các phần cắt hoặc các đường giao nhau. gE ở đây đóng vai trò như một phong bì bên ngoài (envelope) chứa Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


30

toàn bộ đối tượng g ban đầu. ™ Spatial Buffer (Phép vùng đệm): Kết quả trả về gB – Vùng đệm chỉ chứa các đối tượng. Hình 13 Các hàm toán tử trong không gian địa lý 3. Truy vấn thực hiện trong CSDL không gian Một đặc điểm nổi bật giúp cho CSDL không gian trở thành một công cụ mạnh mẽ là khả năng xử lý dữ liệu không gian, không chỉ với mục đích đơn giản là lưu trữ và biểu diễn dữ liệu đó. Một trong những mục đích chính của loại CSDL đặc trưng này là trả lời các truy vấn liên quan đến các thuộc tính không gian của dữ liệu. Một số kiểu truy vấn không gian tiêu biểu: ™ Truy vấn xác định vị trí điểm – Point location Query: Tìm kiếm đối tượng rơi vào vị trí điểm đưa ra (ví dụ tìm kiếm thành phố, quốc gia mà một quận, huyện hay địa danh cho trước nằm trong đó). ™ Truy vấn giới hạn – Range Query: Tìm kiếm đối tượng nằm trong vùng khu vực được đưa ra, thường biểu diễn đối tượng trả về bằng một hình chữ nhật hoặc vòng kín khoanh vùng khu vực đã xác định thỏa mãn truy vấn (ví dụ như xác định vùng hoạt động của các loại xe du lịch trong khu di tích quốc gia). . ™ Truy vấn ghép nối – Join Query: Có rất nhiều dạng cho phép truy vấn nối. Nó bao gồm hai hay nhiều tập các dữ liệu không gian và các cặp đối tượng thỏa mãn những thuộc tính đã cho trước, tất cả các cặp chữ nhật gối lên nhau sẽ được truy xuất trong kết quả truy vấn. ™ Truy vấn lân cận gần nhất – Nearest neighbor Query: Tìm kiếm đối tượng dữ liệu cố định gần nhất đối với đối tượng ban đầu sẽ được tìm thấy Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


31

tùy thuộc và khoảng cách hoặc thỏa mãn tính đồng nhất. Khi thực hiện việc mở rộng các truy vấn không gian cơ bản nêu trên, các dạng truy vấn mới đã được xây dựng. Ví dụ như khi nghiên cứu những đặc điểm tương đồng hoặc khác nhau của một tập hợp lớn các đối tượng phức tạp, những vector đặc trưng thứ nguyên bậc cao được lấy ra từ đó và được tổ chức trong các bảng chỉ mục đa hướng. Đặc điểm quan trọng nhất trong phép biến đổi đặc trưng này là vector đặc trưng tương ứng với các điểm trong không gian Euclidean đa chiều (một kiểu dữ liệu không gian đã được tổng quát hóa). Sau đó, các truy vấn về khoảng cách được áp dụng trên các điểm đa chiều. Các phương pháp truy cập đa chiều nằm trong R-Tree – Khái niệm R*- Tree [Beckmann, Kriegel, Schneider, & Seeger, 1990] và X-Tree đặc biệt [Berchtold, Kiem, & Kriegel, 1996] được coi là sự lựa chọn tốt cho việc đánh chỉ mục tập dữ liệu điểm thứ nguyên bậc cao với mục đích thực thi các truy vấn liên quan đến khoảng cách (DBQs). Và quá trình này được thực hiện bằng thuật toán phân nhánh và giới hạn trong các hàm khoảng cách và rút gọn theo phương pháp đánh giá kinh nghiệm dựa trên Khung giới hạn nhỏ nhất (Minimum Bounding Rectangles – MBRs [14]) – nhằm giảm bớt không gian tìm kiếm. Việc thực thi các thuật toán trên góp phần làm giảm sự gia tăng về số lượng các bậc thứ nguyên. Tuy nhiên nó có thể được cải tiến nếu không gian tìm kiếm được giới hạn theo cách thức nào đó. Với mục đích thực hành, các phương pháp giới hạn không gian tìm kiếm tỏ ra thực sự có giá trị do chúng có khả năng đưa ra các kết quả xấp xỉ trạng thái nhanh hơn rất nhiều so với các phương pháp trước đó. Một hướng nghiên cứu khác cũng với mục đích làm giảm chi phí cho việc xây dựng các truy vấn khoảng cách trong không gian, thỏa mãn các giới hạn về độ chính xác, là sử dụng kỹ thuật tìm kiếm theo kinh nghiệm trên R-Tree như tìm kiếm khu vực – Local search, Simulated Annealing và Thuật toán phát sinh - Genetic Algorithms. Sau đây, ta sẽ xem xét những kỹ thuật xấp xỉ trong các truy vấn liên quan đến khoảng cách trong CSDL không gian quan trọng nhất, các kỹ thuật này có thể được áp dụng trên cấu trúc cây như R-tree (có khả năng chấp nhận rộng rãi đối với các phương pháp truy cập không gian). Chú trọng vào các lựa chọn Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


32

thiết kế của các thuật toán xấp xỉ có hiệu quả trong các truy vấn khoảng cách, với mục đích giảm tối thiểu thời gian đáp ứng của hệ thống và số lượng các phép toán vào ra trong khi vẫn đưa ra được kết quả khả quan với hiệu suất cao. Chú thích [1] Grid file: Là một kiểu dữ liệu dạng mảng đa chiều (multidimensinal array), thường được lưu trữ trên ổ cứng, và được sử dụng như một dạng chỉ mục trong cơ sở dữ liệu. [2] K-D-B-tree: Một kiểu cấu trúc dữ liệu, là sự kết hợp các đặc tính của hai kiểu cấu trúc dữ liệu khác là K-D-tree và B-tree. K-D-B-tree được biết đến như một cấu trúc tìm kiếm hiệu quả trong các chỉ mục động đa chiều lớn. [3] R-tree: Thuật toán được phát minh bởi Antonin Gutman - Trường đại học Berkely California. Ý tưởng của phương pháp này là xây dựng một cách truy xuất nhanh các vùng không gian, bằng cách chia nhỏ không gian thành cách vùng nhỏ và tạo index-chỉ mục cho các vùng không gian nhỏ này, sau đó áp dụng lý thuyết cây trong đồ thị để quản lý, lưu trữ và truy xuất các vùng không gian này. [4] R*-trees: Thuật toán xây dựng dựa trên thuật toán R-tree theo hình thức cải tiến hơn và hạn chế các hạn chế trong thuật toán R-tree. [5] Filter Trees: Một cách tổ chức file để lưu trữ và sử dụng dữ liệu không gian (đa chiều) ứng dụng trong việc thực thi các phép toán nối trong CSDL không gian một cách hiệu quả. Cấu trúc thông tin trong Filter Trees là cách tổ chức phân cấp với mục đích tách rời các thực thể không gian theo kích cỡ, đặt các thực thể lớn hơn ở mức cao hơn trên Filter Trees, và ngược lại. [6] TV-tree: Một dạng cấu trúc chỉ mục sử dụng trong không gian đa chiều [7] X-tree: Cấu trúc chỉ mục trong không gian đa chiều, được xây dựng với ý tưởng tránh hiện tượng chồng chéo các bounding box (khung giới hạn – cách viết khác của MBR) trong thư mục bằng cách sử dụng cách tổ chức thư mục mới tối ưu hơn cho không gian đa chiều bậc cao. [8] SS-tree: Cấu trúc chỉ mục xây dựng dựa trên nền tảng của R-Tree. SS-Tree sử Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


33

dụng vùng giới hạn dạng elip (ellipsoid bounding region) trong không gian thứ nguyên bậc thấp và ứng dụng cách biến đổi khác nhau cho mỗi node trong thư mục. [9] CAD – Computer-Aided design: Thiết kế dựa trên sự trợ giúp của máy tính. [10] Spatial hoặc Spatial data: Dữ liệu không gian – bao gồm các thông tin thực thể về đối tượng trong không gian khi đã được mô hình hóa trên bản đồ và biểu diễn dưới dạng đối tượng của thông tin địa lý. [11] Non-spatial (data): Dữ liệu phi không gian – dữ liệu của đối tượng địa lý, bao gồm các thông tin về thuộc tính và các đặc điểm đi kèm của đối tượng mà không thể lưu trữ dưới dạng dữ liệu địa lý trong CSDL. [12] Spatial indexing: Phương pháp đánh chỉ mục không gian tương tự như trong CSDL thông thường, đây là phương pháp dùng trong quản lý CSDL sử dụng trong việc sắp xếp, tổ chức và truy xuất các dữ liệu đặc biệt trong CSDL thông tin địa lý. [13] chain code [Freeman 1974]. [14] Minimum bounding Rectangle (tên khác là bounding box hoặc envelop): Khung giới hạn nhỏ nhất là biểu diễn phạm vi lớn nhất của hai đối tượng trong không gian hai chiều (như điểm, đường hoặc vùng) với chỉ số (x, y) trong hệ thống tọa độ với tọa độ tương ứng là min(x), min(y), max(x), max(y). MBR thường được sử dụng như một minh họa biểu diễn vị trí tổng quát của của một đặc trưng hình học bất kỳ hoặc sử dụng trong biểu diễn các truy vấn không gian có tính chất gần đúng và đánh chỉ mục không gian. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


34

CHƯƠNG 2: BÀI TOÁN TÍNH TOÁN XẤP XỈ VỚI CÁC TRUY VẤN LIÊN QUAN ĐẾN KHOẢNG CÁCH TRONG CƠ SỞ DỮ LIỆU KHÔNG GIAN 1. Các truy vấn liên quan đến khoảng cách Các chức năng liên quan đến khoảng cách tiêu biểu đều dựa trên khoảng cách tính theo hệ mét ( thỏa mãn các thuộc tính về tính chất không phủ định, tính đồng nhất, tính đối xứng và bất đẳng thức tam giác) đã xác định trên các điểm trong không gian. Hệ đo theo khoảng cách chung được gọi là Lt – khoảng cách Lt, hệ đo Lt hoặc khoảng cách Minkowski[1] giữa hai điểm: P = (p1, p2, …, pd) và q = (q1, q2, …, qd) trong không gian thứ nguyên, Rd và được định nghĩa dưới đây: Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


35

Với t = 1, ta thu được hệ khoảng cách Manhattan. Với t = 2, ta có được hệ khoảng cách Euclidean. Đây là hai hệ khoảng cách được biết đến nhiều nhất của hệ đo Lt trong nội dung CSDL không gian. Khoảng cách Euclidean thường được sử dụng như chức năng riêng biệt trong tính toán khoảng cách tuy nhiên phụ thuộc vào ứng dụng thực tế mà các hệ khoảng cách khác có thể hiệu quả hơn. Trong các ứng dụng về CSDL không gian, hệ đo khoảng cách được sử dụng trong rất nhiều dạng của các truy vấn CSDL. Ví dụ minh họa các truy vấn liên quan đến khoảng cách Để minh họa các truy vấn liên quan đến khoảng cách trong CSDL không gian, dưới đây đề tài nghiên cứu và tham khảo xây dựng vắn tắt CSDL Benchmark[2]: CSDL xây dựng phục vụ cho việc quản lý dữ liệu và truy xuất, xử lý các truy vấn trong dịch vụ liên quan đến định vị vị trí địa lý của đối tượng (Location-based Queries) ứng dụng trong các phương tiện trợ giúp cá nhân – PDA với chức năng tìm đường và xác định vị trí của người sử dụng dựa trên thiết bị định vị và các dữ liệu thông tin địa lý. Mô tả các thực thể, thuộc tính và mối quan hệ giữa các thuộc tính thông qua mô hình dữ liệu quan niệm: Giả sử với người dùng sử dụng thiết bị di động cài đặt chương trình quản lý và tìm đường trong một khu vực nhất định thông qua bản đồ và tín hiệu định vị ví trí hiện tại của họ. Ta có mô hình dữ liệu quan hệ Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


36

Hình 14: Mô hình dữ liệu quan hệ xây dựng dựa trên Benchmark database Các thực thể ™ Human – người sử dụng Thuộc tính Tính chất Ghi chú Id Khóa chính Route Lộ trình đường đi đã định sẵn của người dùng Interests Thuộc tính đa trị Request Thuộc tính đa trị Lưu trữ thông tin về sở thích của người dùng hoặc các yêu cầu gần nhất. ™ Road Thuộc tính Tính chất Ghi chú Id Khóa chính Shape Lưu trữ hình dạng (đa giác) và thời gian đã đi qua-Pass các tuyến đường hoặc thăm-Visit các tòa nhà. ™ Building: Bao gồm hai thực thể con là Shop và Other Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


37

Thuộc tính Tính chất Ghi chú Id Khóa chính Location Lưu trữ vị trí các tòa nhà, các shop và thời gian di chuyển ™ Shop Thuộc tính Tính chất Id Khóa chính Location Offer Thuộc tính đa trị ™ Other Thuộc tính tập hợp nhiều giá trị bao gồm các thông tin như tên sản phẩm, thông tin về thời gian đáp ứng yêu cầu hợp lệ. Thuộc tính Tính chất Id Khóa chính Location Type Một số truy vấn liên quan đến khoảng cách tiêu biểu được sử dụng khá phổ biến trong hệ thống CSDL không gian. Với mỗi loại truy vấn sẽ đưa ra ví dụ ứng dụng một truy vấn cụ thể dựa trên CSDL Benchmark đã trình bày ở trên. Giả sử với người sử dụng có Id = 20 (Human.id = 20) 1.1 Truy vấn khu vực theo khoảng cách δ Truy vấn khu vực theo khoảng cách δ - δ-distance range query: Truy vấn dạng này bao gồm một tập dữ liệu không gian, điểm truy vấn và giới hạn Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


38

khoảng cách δ. Kết quả đưa ra là một tập các đối tượng không gian từ tập dữ liệu đầu vào nằm trong vùng giới hạn một khoảng cách là δ tính từ điểm truy vấn (query point). Truy vấn 1: Tìm các shop nằm trong khoảng bán kính 500m tính từ vị trí tôi đang đứng có bán quần áo thể thao. Sử dụng hàm giới hạn khoảng cách tìm kiếm trong khoảng 500m với vị trí hiện thời làm tâm là Circle (curr_space(), δ) SELECT Shop.id, Offer.id, Offer.info FROM Human, Shop, Offer WHERE Offer.infor = `sportwear` AND Offer.shop_id = Shop.id AND Human.id = 20 AND Shop.Location INSIDE Circle (curr_space(Human.route), 500) ; Với δ = 500 (m). Hàm Circle(point reference, number K): Đường tròn được định nghĩa bởi tâm là điểm tham chiếu cho trước và bán kính bằng K. Hàm Curr_space (point reference): Hàm toán tử trả về giá trị khả dụng trong thời điểm hiện tại như giá trị lần cập nhật cuối cùng, thông tin gần nhất về điểm truy vấn, ở đây hàm Curr_space() sử dụng như hàm trả về thông tin vị trí tại thời điểm truy cập của người dùng. 1.2 Truy vấn K vùng lân cận gần nhất Truy vấn K vùng lân cận gần nhất - K nearest neighbour query (K- NNQs): K-NNQs bao gồm một tập dữ liệu không gian và một điểm truy vấn. Nó tìm ra K đối tượng riêng biệt từ tập dữ liệu đầu vào và lần lượt có các khoảng cách nhỏ nhất tính từ điểm truy vấn. Ví dụ một truy vấn dạng K-NNQ trong CSDL Benchmark: Truy vấn 2: Tìm hai nhà hàng gần nhất (giả thiết với Other.type = 1) tính từ khu vực hiện tại tôi đang đứng ( với giá trị Human.Id = 20) Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


39

SELECT Other.id FROM Human, Other WHERE Other.type = 1 AND Human.Id = 20 ORDER BY Spatial_Neighbour (Other.Location, curr_space (Human.Route) ) ASC = 2; Trong trường hợp này K = 2. Chú ý ™ Với câu lệnh SQL: ORDER BY Spatial_Neighbour (Other.Location, curr_space (Human.Route) ) ASC = 2; ™ Hàm Spatial_Neighbour (attribute, reference) được sử dụng để biểu diễn truy vấn dạng K-NN giữa các thuộc tính. Kết quả trả về được sắp xếp theo quy tắc tăng dần (ở đây là khoảng cách giữa người dùng và nhà hàng). 1.3 Truy vấn nối các khu vực theo khoảng cách δ (truy vấn đệm) Truy vấn nối các khu vực theo khoảng cách δ (truy vấn đệm) - δ– distance range join query: Truy vấn trên bao gồm hai tập dữ liệu không gian và giới hạn khoảng cách δ. Kết quả trả về là một tập các cặp đối tượng không gian từ hai tập dữ liệu đầu vào, nằm trong giới hạn khoảng cách δ tính từ mỗi đối tượng. 1.4 Phép nối khoảng cách Iceberg Phép nối khoảng cách Iceberg - Iceberg distance join: Bao gồm hai tập dữ liệu không gian, giới hạn khoảng cách δ và số yếu tố ngưỡng K. Kết quả trả về là một tập các cặp đối tượng từ hai tập dữ liệu đầu vào, nằm trong phạm vi khoảng cách δ từ mỗi đối tượng, quy định rằng đối tượng đầu tiên xuất hiện ít nhất K lần trong kết quả của phép nối. 1.5 Truy vấn K cặp đối tượng gần nhất Truy vấn K cặp đối tượng gần nhất - K closet pair query (K-CPQ): Bao gồm hai tập dữ liệu không gian và số yếu tố ngưỡng K. Nó tìm kiếm K cặp đối tượng riêng biệt từ hai tập dữ liệu đầu vào và có khoảng cách nhỏ nhất Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


40

giữa chúng là K. Truy vấn 3: Tìm năm shop gần nhất tính từ khu vực tôi đang đứng có bán giày dép đã được lưu trong mục Interest của người sử dụng. SELECT Human.id, Shop.id, Offer.id FROM Human, Shop, Offer WHERE `shoes` in Human.Interests AND Offer.Info = `shoes` AND Offer.Shop_id = Shop.id ORDER BY All_Spatial_Neighbour_Pairs (Shop.Location, curr_space (Human.route)) ASC 5; Với K = 5. Chú ý: ™ Tương tự như với câu truy vấn dạng K-NN, câu lệnh SQL: ORDER BY All_Spatial_Neighbour_Pairs(Shop.Location, curr_space (Human.route)) ASC 5; Cũng được sử dụng để biểu diễn các truy vấn dạng K-CP 1.6 Nối K vùng lân cận gần nhất Nối K vùng lân cận gần nhất - K nearest neighbour join: Bao gồm hai tập dữ liệu không gian và số yếu tố ngưỡng K. Kết quả trả về là tập các cặp đối tượng từ hai tập dữ liệu đầu vào thỏa mãn, với mỗi đối tượng của tập dữ liệu đầu tiên, một cặp được tạo thành với mỗi K vùng lân cận gần nhất của nó trong tập dữ liệu thứ hai. 1.7 Truy vấn K- nối khoảng cách Truy vấn K- nối khoảng cách - K-Multi-way distance join query: Một truy vấn theo dạng này bao gồm n tập dữ liệu không gian, một đồ thị truy vấn (là một đồ thị định hướng có trọng số định nghĩa hành trình có hướng giữa n tập dữ liệu đầu vào) và số yếu tố ngưỡng K. Kết quả trả về là một tập bao gồm K bộ dữ liệu riêng biệt, mỗi bộ có n đối tượng – n-tuples ( bộ dữ liệu chứa n đối Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


41

tượng từ n tập dữ liệu thỏa mãn biểu đồ truy vấn). với K giá trị Ddistance nhỏ nhất (Hàm Ddistance là một hàm bậc nhất về khoảng cách với n đối tượng tạo nên n-bộ dữ liệu, chiếu theo các cạnh của đồ thị truy vấn ban đầu). Kết luận Các truy vấn liên quan đến khoảng cách trong CSDL không gian rất hữu ích trong nhiều ứng dụng sử dụng dữ liệu không gian cho việc lập quyết định và nhiều phép toán yêu cầu xừ lý dữ liệu khác. Ví dụ trong trường hợp sử dụng truy vấn cặp gần nhất – K-CPQ, tập dữ liệu đầu tiên có thể biểu diễn các ranh giới về văn hóa của Mỹ, trong khi tập dữ liệu thứ hai có thể bao gồm những địa danh nổi tiếng nhất tại Bắc Mỹ. Kết quả trả về cho loại truy vấn này sẽ bao gồm K cặp gần nhất các thành phố và vùng văn hóa, nó cung cấp một trình tự cho các nhà tổ chức để sắp xếp được lịch trình du lịch hợp lý trong các chuyến tham quan của du khách... Giá trị K ở đây có thể phụ thuộc vào ngân sách mà nhà tổ chức dự định chi trả cho mục đích sử dụng này. Trong giới hạn nghiên cứ của đề tài, chúng ta sẽ chú trọng tìm hiểu hai loại truy vấn là K-NNQ và K-CPQ, qua đó nắm được cách thiết kế các thuật toán xấp xỉ trong các truy vấn liên quan đến khoảng cách. Hình dưới minh họa một tập các điểm trong không gian hai chiều được tổ chức theo cấu trúc R-tree (MBR-based index – Minimum bounding Rectangle- based index -phương pháp đánh chỉ mục dựa trên khung giới hạn nhỏ nhất), mục đích là tìm ba vùng lân cận gần nhất (K = 3 Ù 3-NNQ) với điểm truy vấn q. Dễ thấy kết quả của phép truy vấn 3-NNQ là (p11, p8, p4) Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


42

Hình 15: R-Tree và MBRs trong truy vấn Với ví dụ minh họa dưới đây, ta xét với hai tập điểm 2 chiều khác nhau (tổ chức theo cấu trúc R-Tree, một tập dữ liệu được thể hiện với MBR không tô màu, tập còn lại được thể hiện theo cấu trúc MBR chia sẻ). Nếu ta muốn bao gồm 3 cặp điểm gần nhất (3-CPs) từ hai tập dữ liệu trên thì thu được kết quả là ((p8, q8), (p11, q10), (p4, q6)) Hình 16: R-Tree và truy vấn trong hai cấu trúc MBR khác nhau 2 R – Tree Kỹ thuật Phân nhánh-và-giới hạn (branch-and-bound) đang là một kỹ thuật thành công nhất sử dụng trong việc thiết kế các thuật toán giải quyết các câu hỏi của ngôn ngữ truy vấn trên cấu trúc dạng cây. Hàm chức năng giới Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


43

hạn thấp hơn và giới hạn cao hơn là nền tảng cơ bản của hiệu năng tính toán trong thuật toán phân nhánh-và-giới hạn. Kỹ thuật giả định cơ bản sử dụng trong các thuật toán truy vấn khoảng cách là các tập dữ liệu không gian được đánh chỉ mục bởi cấu trúc của họ R-Tree. R-Tree và các biến thể của nó được đánh giá là sự lựa chọn hoàn hảo trong việc đánh chỉ mục cho rất nhiều loại dữ liệu không gian (điểm, đoạn thẳng, hình chữ nhật, đa giác…) và vẫn đang được tiếp tục phát triển trong các hệ thống thương mại như Informix và Oracle. 2.1 Khái niệm R-Tree là các cấu trúc cây dữ liệu sử dụng cho dữ liệu không gian đa chiều, có tính chất cân bằng độ cao và có thứ tự, được thiết kế cho thiết bị lưu trữ thứ cấp, và là sự tổng quát hóa của B-tree[3] cho các không gian dữ liệu đa chiều. Chúng được sử dụng để tổ chức động các đối tượng trong không gian d chiều được biểu diễn bởi Đường biên d-chiều tối thiểu (Minimum Bounding d-dimentional hyper-Rectangle – MBR – hoặc khung giới hạn d-chiều nhỏ nhất). Một MBR được xác định bởi hai điểm trong không gian d chiều thuộc bề mặt của nó, một điểm là tọa độ d nhỏ nhất và một điểm là tọa độ d lớn nhất (chúng là các điểm kết thúc của các đường chéo thuộc MBR). Một nút trong cây R-Tree tương ứng với MBR bao gồm cả các nút con của nó. Các lá của cây bao gồm nhiều con trỏ trỏ đến các đối tượng của CSDL thay vì các con trỏ trỏ đến các nút con. Các nút được xử lý giống như các trang nhớ trên đĩa. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


44

Hình 17: Ví dụ về R-Tree Hình trên mô tả một số hình chữ nhật ở bên trái và cây R-Tree tương ứng ở phía bên phải. Các đường ba chấm biểu thị khung giới hạn của cây con đã được phát sinh từ nút bên trong. Với các kiểu cấu trúc cây khác như cấu trúc chỉ mục, một chỉ mục của cây R-Tree phân chia không gian đa chiều bằng cách nhóm các đối tượng trong từng loại thứ tự. Một không gian con chứa bởi một nút thuộc cây R-Tree luôn phải nằm trong không gian con của nút cha của nó, đó là đặc tính bao đóng MBR. Theo đặc tính này, một MBR của một nút R-tree (ở bất cứ tầng nào ngoại trừ phía bên trái cây) luôn bao trọn MBR của nút R-tree con cháu của nó. Đặc điểm này của kỹ thuật giới hạn không gian giữa các MBR của các nút trong cây R-tree thường được sử dụng trong thuật toán nối không gian và thuật toán truy vấn liên quan đến khoảng cách. Chú ý rằng MBR – Đường biên tối thiểu - và thuộc tính đi kèm MBR chính là các kỹ thuật xấp xỉ cơ bản. Ở tầng bên trái, một khu vực xấp xỉ MBR được bao phủ bởi các đối tượng nó đi kèm, trong khi tại các tầng bên trong một khu vực xấp xỉ MBR lại được bao phủ bởi các cây con của các nút tương ứng. Một thuộc tính quan trọng khác của R-tree là MBR face property (tạm dịch: thuộc tính bề mặt MBR) – mỗi bề mặt của bất kỳ MBR của mỗi nút R-tree (tại bất kỳ tầng nào) liền kề ít nhất một điểm của một số đối tượng không gian trong CSDL không gian. Đặc điểm này được sử dụng trong các thuật toán truy vấn liên quan đến khoảng cách. Một trong những phiên bản phổ biến và có hiệu năng cao nhất là R* -tree (Beckmann et al.,1990). R* đã bổ sung hai cải tiến lớn vào cấu trúc R-Tree ban đầu trong trường hợp xảy ra việc quá tải các nút trong cây. Đầu tiên, hơn cả việc chỉ tính toán đến các khu vực , thuật toán phân tách nút trong R*-tree còn tối thiểu hóa chu vi và các phần mở rộng nằm gối lên nhau của MBRs. Thứ hai, việc tràn nút không được phân tách ngay lập tức, nhưng các phần chia các mục trong nút được chèn lại từ đầu của cây R*- tree (việc chèn bắt buộc) Corall et al (2000) đã đưa ra một sự tổng quát hóa của các chức năng dùng trong việc tính toán khoảng cách tối thiểu giữa điểm và MBRs (MINMINDIST). Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


45

Giả sử có (A, B) biểu diễn một MBR trong không gian d-chiều, với A = (a1, a2, …, ad) và B = (b1, b2, …, bd) sao cho ai ≤ bi, với 1 ≤ i ≤ d là các điểm kết thúc của một trong những đường chéo chính của nó. Ta có hai MBRs là M1 (A, B) và M2 (C, D), MINMINDIST (M1, M2) được định nghĩa như sau: Chúng ta có thể áp dụng chức năng về khoảng cách này cho một cặp các loại phần tử bất kỳ (MBRs hoặc điểm) lưu trữ trong cấu trúc R-tree trong quá trình tính toán của thuật toán rẽ nhánh và cận nhằm thu nhỏ không gian tìm kiếm. Những đặc tính quan trọng nhất của MINMINDIST: ™ Nếu bất kỳ một hoặc một cặp MBR (dạng chữ nhật) nào suy biến thành một hoặc một cặp điểm, ta phải thu được khoảng cách nhỏ nhất giữa điểm đó và MBR hoặc giữa hai điểm này. ™ Đặc điểm của đường biên cấp thấp hơn: Với mỗi cặp điểm trong không gian đa chiều (p ; q) đi cùng với một cặp MBR tương ứng (Mp; Mq), chứng minh được rằng MINMINDIST (Mp; Mq) ≤ MINMINDIST(p, q). ™ MINMINDIST là một dãy đơn điệu không giảm với các bậc của R-Tree. 2.2 Cấu trúc của một R-tree Một cách tổng quát, R-tree là một cấu trúc chỉ mục cho các đối tượng không gian n-chiều và nó tương tự như B-tree. Cấu trúc chỉ mục này là thực sự linh động, thao tác chèn và xóa có thể kết hợp với phép tìm kiếm và phải tái tổ chức theo chu kỳ. Các nút lá trong cây chứa chỉ mục dẫn đến chúng theo khuôn dạng: Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


46

(MBR, object_ptr) - Trong đó object_ptr tham chiếu đến một bộ dữ liệu trong cơ sở dữ liệu và MBR là một rectangle n-chiều chứa các đối tượng không gian nó biểu diễn. Các nút không phải lá có khuôn dạng sau: (MBR, chirld_ptr) - Với chirld_ptr là địa chỉ một nút khác trong cây và MBR bao gồm các rectangle trong các nút thấp hơn. Nói cách khác, không gian MBR chứa mọi đối tượng được đánh chỉ mục trong các cây con có gốc là đầu vào của MBR. Cho M là số lượng tối đa đầu vào có thể vừa đủ với một nút và cho tham số m xác định số lượng tối thiểu đầu vào tại một nút. Một R-tree thỏa mãn các thuộc tính sau: ™ Mỗi một nút chứa số lượng nút con trong khoảng m và M ngoại trừ nút gốc. ™ Đối với mỗi đầu vào dạng (MBR, object_ptr) tại nút lá, MBR là một rectangle nhỏ nhất có chứa đối tượng dữ liệu n-chiều được biểu diễn bởi object_ptr. ™ Mỗi nút không phải nút lá có số lượng nút con trong khoảng m và M ngoại trừ nút gốc. ™ Đối với mỗi đầu vào dạng (MBR, chirld_ptr) tại nút không phải nút lá, MBR là một rectangle nhỏ nhất có chứa rectangle trong chirld node. ™ Nút gốc có ít nhất là 2 nút con ngoại trừ đó là nút lá. ™ Đây là một loại cây cân bằng. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


47

Hình 18: Cây biểu diễn R-Tree Hình 19: Biểu diễn hai chiều của một R-Tree 2.3 Thuật toán R-Tree R-tree là một cây cân bằng tương tự như B-tree. Ý tưởng như sau: Các index sẽ nằm tại các nút lá chứa các điểm dữ liệu, khi đó việc tìm kiếm không gian sẽ thực hiện trên một số lượng nhỏ các nút. Một cơ sở dữ liệu không gian bao gồm tập hợp của các bộ đại diện cho các đối tượng trong không gian, mỗi bộ có một nhận biết duy nhất ,ta cóthể dùng nhận biết này để truy xuất nó. Các node lá trong R-Tree chứa các đầu vào mẫu tin chỉ mục (index record entries) (I, tuple-identifier [4]) với tuple- identifier (nhận dạng bộ dữ liệu) tham khảo đến một bộ trong cơ sở dữ liệu và I là hình chữ nhật n chiều, hình này là khung giới hạn nhỏ nhất - MBR của các index đối tượng không gian. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


48

I = (I0, I1,… In). n - số chiều không gian Ii - một khoảng biên khép kín [a,b], mô tả phạm vi của đối tượng cùng với chiều i. Một node không phải là node lá chứa các entry như sau (I, child-pointer), child-point là địa chỉ của node thấp hơn trong R-Tree và I bao phủ tất cả các hình chữ nhật trong các entry của các node thấp hơn. Hình 20: Cấu trúc một R-Tree Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


49

Hình 21: Các quan hệ có thể có giữa các MBR (chứa trong, chồng lấn…) 2.3.1 Tìm kiếm trong cấu trúc dữ liệu tổ chức dưới dạng R-Tree Tìm kiếm Thuật toán tìm kiếm duyệt cây từ gốc (root) đi xuống theo cách tương tự như B-tree. Tuy nhiên khi thăm một node sẽ có nhiều hơn một cây con dưới node đó cần được tìm kiếm, vì lý do đó thuật toán không thể bảo đảm thực hiện tốt trong các trường hợp xấu nhất. Tuy nhiên với nhiều kiểu của dữ liệu thuật toán cập nhật sẽ duy trì hình dạng của cây cho phép thuật toán tìm kiếm loại đi các vùng không liên quan của không gian được đánh chỉ mục, và kiểm tra duy nhất dữ liệu gần vùng tìm kiếm. Chúng ta sẽ biểu diễn phần hình chữ nhật của một chỉ mục E là EI, và phần nhận dạng dữ liệu hay child-pointer là Ep. Thuật toán tìm kiếm: Cho R-tree có root là T, tìm tất cả các mẫu tin chỉ mục mà có các hình chữ nhật chồng lên một hình chữ nhật cần tìm S. ™ S1 [Tìm kiếm trên cây con] Nếu T là một node lá, kiểm tra mỗi mục E để xác định xem Ei có trùng lên S hay không. Với tất cả các mục trùng nhau, thực hiện tìm kiếm trên cây mà node root của nó được chỉ bởi Ep. ™ S2 [Tìm kiếm trên node lá] NếuT là một lá, kiểm tra tất cả các mục E để xác định EI có trùng lên S hay không. Nếu trùng E là một record đủ tiêu chuấn. 2.3.1.1 Chèn (Insertion) Việc thêm các index cho các bộ dữ liệu mới giống như thêm trong B-tree là các index mới được thêm vào cho các lá, các node chứa quá số lượng sẽ bị Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


50

tách ra và quá trình tách này sẽ lan truyền lên phía trên cây. Thuật toán Chèn (Insert): Thêm một mục nhập chỉmục mới E vào trong R-tree ™ I1: [Tìm vị trí cho dữ liệu mới] dùng thuật toán chọn lá (ChooseLeaf) để chọn một node lá L để thêm E. ™ I2: [Thêm dữ liệu cho node lá] nếu L có chỗ cho một entry khác, thêm E nếu không thì dùng thuật toán chia node (SplitNode) đểcó được L và LL chứa E và tất cả các mục nhập của L. ™ I3: [Lan truyền các thay đổi lên phía trên] Dùng thuật toán điều chỉnh cây (AdjustTree) trên L, đồng thời bỏ qua LL nếu việc phân chia đã được thực hiện. ™ I4: [Tăng trưởng cây] Nếu việc phân chia node lan truyền làm cho root phân chia, tạo ra một root mới, mà con của root mới này là 2 node kết quả. 2.3.1.2 Thuật toán Chọn lá (ChooseLeaf): Chọn một node lá mà node lá này đặt một chỉ mục mới E. ™ CL1: [Khởi tạo] cho tập N là node root. ™ CL2: [Kiểm tra lá] Nếu N là một lá, trả về N. ™ CL3: [Chọn cây con] Nếu N không phải là một lá, cho F là entry trong N mà các hình chữ nhật của nó FI cần mở rộng lá để tính EI. Giải quyết các hạn chế bằng cách chọn entry với hình chữ nhật có diện tích nhỏ nhất. ™ CL4: [Đi xuống cho đến khi một node lá được tìm thấy] tập N là node con được chỉ đến bởi Fp và lặp lại từ CL2. 2.3.1.3 Thuật toán điều chỉnh cây (AdjustTree): Đi lên từ một node lá L đến root, điều chỉnh hình chữ nhật bao phủ và lan truyền phân chia các node chia khi cần thiết. Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


51

™ AT1: [Khởi tạo] cho tập N=L, nếu L đã được phân chia trước đó, tập NN là kết quả của node thứ hai . ™ AT2: [Kiểm tra nếu thực hiện] Nếu N là root, ngưng. ™ AT3: [Điều chỉnh vùng phủ hình chữ nhật trong mục nhập cha] Cho P là node cha của N và cho EN là các entry của N trong P. Điều chỉnh EN I để cho nó bao sát xung quanh tất cả các hình chữ nhật entry trong N. ™ AT4: [Lan truyền node bị tách lên phía trên] Nếu N có NN (partner) kết quả từ một phân chia mới nhất, tạo một entry mới ENN P trỏ đến NN và ENN I bao quanh tất cả các hình chữ nhật trong NN, thêm ENN vào P nếu có chỗ. Nếu không dùng SplitNode đểtạo ra P và PP chứa ENN và tất cả các entry của P. ™ AT5: [Di chuyển đến mức kết tiếp]. Cho tập N=P và tập NN=PP nếu có sự phân chia xảy ra. Lặp lại bước AT2. 2.3.2 Xóa (Deletion) Thuật toán xóa Thay đổi vị trí index của record E từ R-tree ™ D1: [Tìm node chứa record] thực hiện thuật toán FindLeaf để xác định vị trí node lá L chứa E. Ngưng nếu record được tìm thấy. ™ D2: [Xóa record] Xóa E từ L. ™ D3: [Lan truyền thay đổi] dùng thuật toán CondenseTree bỏ qua L. ™ D4: [Rút ngắn cây] Nếu root có duy nhất một con sau khi cây đã được điều chỉnh, tạo con cho root mới. 2.3.2.1 Thuật toán tìm lá (FindLeaf): Cho R-tree có root là T, tìm node lá chứa đầu vài chỉ mục E. ™ FL1: [Tìm cây con] nếu T không phải là node lá, kiểm tra mỗi entry F trong T để xác định, nếu FI chồng lấp với EI. Với mỗi entry thực hiện thuật toán FindLeaf trên cây mà root của nó được trỏ đến bởi Fp cho đến Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


52

khi E được tìm thấy hay tất cả các entry đã được kiểm tra. ™ FL2: [Tìm node lá cho mục cho record] Nếu T là lá, kiểm tra mỗi entry để xem nếu nó phù hợp với E, nếu E được tìm thấy trả về T. 2.3.2.2 Thuật toán Gom cây (CondenseTree): Cho một node lá L, mộtentry được xóa từ node lá này, loại ra node này nếu nó có quá ít các chỉ mục và xây dựng lại các entry của nó. Lan truyền việc loại node này lên trên khi cần thiết. Điều chỉnh các hình chữ nhậtbao phủ trên đường dẫn đến root, làm cho các hình chữ nhật này nhỏ hơn nếu có thể. ™ CT1: [khởi tạo] cho tập N=L, tập Q là tập của các node bịloạibỏ, Q là tập rổng. ™ CT2: [Tìm entry cha] nếu N và root, nhảy tới bước CT6. Nếu không thì cho P là cha của N, và cho EN là các entry của N trong P. ™ CT3: [Loạinode không đủ(Eliminate under-full node)] Nếu N có ít hơn m entry, xóa EN khỏi P và thêm N vào tập Q. ™ CT4: [Điều chỉnh hình chữ nhật bao phủ] Nếu N không bị loại bỏ, điều chỉnh EN I để chứa sát lại các entry trong N. ™ CT5: [Di chuyển lên trên mộtmức trong cây] Cho tập N=P và lặp lại từ CT2. ™ CT6: [Chèn lại các entry bị mồi côi (Re-insert orphaned entries)] Chèn lại vào tất cà các entry của các node trong tập Q. Các entry từ các node lá bị loại bỏ được chèn lại vào trong các lá của cây như đã được mô tả trong thuật toán Insert, nhưng các entry từ các node có mức cao hơn phải được đặt cao hơn trong cây, vì vậy các lá của các cây con phụ thuộc vào chúng sẽ nằm trên cùng mức như các lá của cây mẹ. 2.3.3 Cập nhật Nếu một bộ dữ liệu được cập nhật để cho hình chữ nhật bao phủ nó bị thay đổi, bản ghi chỉ mục của nó phải bị xóa, cập nhật và chèn lại, vì vậy nó sẽ phải Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


53

tìm cách để đặt đúng vị trí trong cây. Một cách tìm kiếm khác so với cách được mô tả ở trên có thể hữu ích hơn, ví dụ để tìm tất cả các đối tượng dữ liệu được chứa hoàn toàn trong một vùng tìm kiếm, hoặc tất cả các đối tượng chứa vùng tìm kiếm. Các bước thực hiện có thể được thực hiện bằng các biến đổi dễ hiểu trên thuật toán đã cho. Tìm một entry cụ thể mà nhận dạng của nó đã được biết trước cần đến thuật toán xóa và được thực hiện bằng thuật toán FindLeaf. Các biến đổi của phạm vi xóa, trong phạm vi này, tất cả các đối tượng dữliệu trên diện tích liên quan được xóa đi, cũng được R-tree cung cấp khá tốt. 2.3.3.1 Thuật toán tách node (Node Splitting) Để thêm một một entry mới để một node đầy chứa M các chỉ mục, cần phải phân chia tập hợp của M+1 các entry thành hai node. Sự phân chia nên được thực hiện theo cách làm cho nó không chắc có thể thực hiện được việc phân chia cả hai node mới sẽ cần được kiểm tra trên việc tìm kiếm thứ tự. Khi đó sự quyết định thăm một node phụ thuộc vào hình chữ nhật bao phủ nó có chồng lên diện tích tìm kiếm. Tổng số diện tích của hai hình chữ nhật bao phủ sau khi tách có thể được giảm đến mức tối thiểu. Hình dưới đây minh họa điều này. Diện tích của các hình chữ nhật trong trường hợp “bad split”lớn hơn nhiều so với trường hợp “good split”. Hình 22: Trường hợp phân chia node Cùng tiêu chuẩn đã được dùng trong thủ tục ChooseLeaf để quyết định xem nơi nào có thể chèn một chỉ mục mới vào tại mỗi mức trong cây, cây con được chọn là một cây mà hình chữ nhật bao phủ của nó phải được mở rộng ít Good Bad split Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


54

nhất khi chèn chỉ mục mới vào. Chúng ta quay lại thuật toán phân chia tập M+1 entry thành hai nhóm cho mỗi node mới. Hình 23: Phân chia entry thành các nhóm node mới Thuật toán A Quadractic-Cost Thuật toán này cố gắng tìm một vùng được tách ra có diện tích nhỏ, nhưng không bảo đảm là có thể tìm được một vùng có thể có diện tích nhỏ nhất. Chi phí là bậc hai theo M và tuyến tính theo số lượng của các chiều. Thuật toán chọn hai trong M+1 entry làm phần tử đầu tiên của hai nhóm mới bằng cách chọn hai entry này, hai entry này có thể làm lãng phí diện tích lớn nhất nếu cả hai được đặt trong cùng một nhóm. Như vậy diện tích hình chữ nhật bao phủ cả hai entry, trừ đi diện tích của chính các entry, sẽ là lớn nhất. Các entry còn lại được gán vào các nhóm cùng lúc. Tại mỗi bước, việc mở rộng diện tích đòi hỏi phải thêm mỗi entry còn lạicho mỗi nhóm được tính toán, và entry được gán thì sẽ xuất hiện một sự khác biệt lớn nhất giữa hai nhóm. Thuật toán Quadratic Split Phân chia một tập M+1 các chỉ mục thành hai nhóm. ™ QS1: [chọn entry đầu tiên cho mỗi nhóm] Áp dụng thuật toán PickSeeds để chọn hai entry làm các phần tử đầu tiên của các nhóm. Gán mỗi entry cho một nhóm. ™ QS2: [Kiểm tra nếu đã thực hiện] Nếu tất cả các entry đã được gán, ngưng. Nếu một nhóm có một vài entry mà tất cả những entry còn lại Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


55

phải được gán vào nó theo thứ tự để cho nhóm này có m nhỏ nhất, gán các entry và ngưng. ™ QS3: [Chọn entry để gán] Thực hiện thuật toán PickNext để chọn entry kế tiếp để gán. Thêm entry này vào nhóm mà hình chử nhật bao phủcủa nó sẽ phải mở rộng ít nhất để chứa entry này. Giải quyết các hạn chế bằng cách thêm entry vào nhóm có diện tích nhỏ nhất, khi đó nhóm này có các entry ít hơn nhóm khác. Lặp lại QS2. Thuật toán PickSeeds Chọn hai entry làm phần tử đầu tiên của các nhóm. ™ PS1: [Tính toán sự thiếu hiệu quảcủa việc nhóm các entry với nhau] Cho mỗi cặp các entry E1 và E2 , tạo một hình chữ nhật J bao gồm E1I và E2I Tính d = area(J) – area (E1I) - area(E2I). ™ PS2: [Chọn cặp gây lãng phí nhất] Chọn cặp có d lớn nhất. Thuật toán PickNext Chọn một mục còn lại để phân loại vào một nhóm. ™ PN1: [Xác định giá trị của việc đặt mỗi entry trong mỗi nhóm] Cho mỗi entry E chưa được phân nhóm, tính d1 = diện tích được yêu cầu tăng trong hình chữ nhật bao phủ của nhóm 1 để bao gồm EI, tính toán d2 tương tự như trên cho nhóm 2. ™ PN2: [Tìm entry thích hợp nhất cho một nhóm] Chọn bất kỳ entry nào có sự khác biệt lớn nhất giữa d1 và d2. Thuật toán LinearPickSeeds Chọn hai entry làm các phần tử đầu tiên của các nhóm. ™ LPS1: [Tìm các hình chữ nhật xa nhất theo tất cả các chiều] Theo mỗi chiều, tìm các entry mà hình chữ nhật của nó có cạnh dưới cao nhất và có cạnh trên thấp nhất. Ghi lại việc phân chia. ™ LPS2: [Điều chỉnh hình dạng của cụm hình chữ nhật] Chuẩn hóa việc phân chia bằng cách chia chiều rộng của toàn bộ các tập theo chiều Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


56

tương ứng. ™ LPS3: [Chọn cặp cách xa nhất] Chọn cặp có sự phân chia được chuẩn hóa lớn nhất theo bất kỳ chiều nào. Trên đây đề tài đã trình bày thuật toán R-tree, chúng ta có thể áp dụng phương pháp này để tạo index cho cụm. Ta xem các cụm như là các không gian mà chúng ta cần truy xuất, các vùng dữ liệu của cụm sẽ được phân chia để nằm trong các hình chữ nhật nhỏ (không gian 2 chiều), ta sẽ có các hình chữ nhật lớn hơn bao ngoài các hình chữ nhật nhỏ chứa dữ liệu này áp dụng R-tree để tạo cây, khi đó nếu cần truy xuất một vùng dữ liệu nào đó trong cụm ta sẽ dùng thuật toán tìm để xác định địa chỉ vùng dữ liệu này đang nằm ở lá nào trong cây hay nói cách khác là lá nào đang chứa thông tin về vị trí của vùng dữ liệu mà ta đang cần, khi biết các thông tin vềvịtrí trong không gian của vùng dữ liệu đang tìm ta sẽ truy xuất đến rất nhanh cụm dữ liệu này. Như vậy từ nếu tạo được index cho cụm thì việc tìm kiếm tương tự sẽ được giảiquyết nhanh chóng. Ta chỉ cần tìm xem vị trí không gian của đối tượng cần tìm tương tự nằm trong vùng địa chỉ không gian tại lá nào, truy xuất tất cả các dữ liệu nằm trong vùng không gian đó ra để xét tương tự. Nếu không có index cụm ta sẽ phải vét cạn các điểm trong cụm mới xác định được vị các vị trí không gian cần tìm. Index cụm cũng cho phép xây dựng thuật toán tăng trưởng cho gom cụm, từ index ta có thể xác định rất nhanh các vùng dữ liệu bị ảnh hưởng khi thêm hay xóa dữ liệu mà không phải xác định lại tất cả các cụm từ đầu. Tuy nhiên R-tree vẩn còn hạn chế về hiệu xuất và nó chưa tối ưu các vùng không gian của hình chữ nhật thư mục như: Diện tích bao phủ, vùng chồng lấn, lề. Thuật toán R*-tree đã đưa ra các phương pháp cải tiến các khuyết điểm này của R-tree. 3 Các kỹ thuật tính toán xấp xỉ khoảng cách 3.1 Thu nhỏ không gian tìm kiếm Thu nhỏ không gian tìm kiếm - Search space reduction - bằng những kỹ thuật xấp xỉ không gian tìm kiếm tiêu biểu nhất Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


57

Phương pháp xấp xỉ ε Cho một số thực dương e (ε ≥ 0) xác định sai số lớn nhất về khoảng cách có thể chấp nhận được, kết quả trả về của một truy vấn liên quan đến khoảng cách – DBQ (như K-NNQ hoặc K-CPQ) là đại lượng xấp xỉ (ε + 1) nếu khoảng cách của yếu tố i-th nằm trong khoảng sai số e (hoặc thừa số (ε + 1)) về khoảng cách của yếu tố đó (điểm cho K-NNQ hoặc cặp điểm đối với K- CPQ) của kết quả chính xác trong truy vấn tương tự (1 ≤ i ≤ K). Ví dụ: Đại lượng xấp xỉ (ε + 1) trả lời cho truy vấn theo K-CPQ là một chuỗi có thứ tự (kết quả được sắp xếp theo chiều tăng dần của khoảng cách) của K cặp điểm riêng biệt ((p1’,q1’), (p2’,q2’), …, (pk’,qk’)) € (P * Q)K với (pi’,qi’) là cặp điểm gần nhất với đại lượng xấp xỉ (ε + 1) trong tập các cặp điểm gần nhất (pi, qi) trong tập kết quả chính xác ((p1, q1), (p2, q2), …, (pk, qk)) € (P * Q)K với giá trị (dist(pi’,qi’) – dist (pi, qi)))/ dist (pi, qi) ≤ ε, 1 ≤ i ≤ K. Khi phương pháp lược bỏ theo kinh nghiệm được áp dụng trong thuật toán rẽ nhánh và cận, một thành phần X ( cặp MBR hoặc điểm) sẽ bị loại bỏ nếu: MINMINDIST (X) > z/ (ε + 1) Ù (MINMINDIST (X) + MINMINDIST (X) * ε) > z Ù MINMINDIST (X) > z – (MINMINDIST (X) * ε) Việc giảm giá trị của z (giá trị khoảng cách của k-th cặp điểm gần nhất có thể được truy xuất nhanh chóng trong quá trình xử lý của thuật toán) phụ thuộc vào giá trị của MINMINDIST (X) nhân với ε (một số thực dương bất kỳ và độc lập). Chú ý rằng với ε = 0, thuật toán xấp xỉ hoạt động như một phiên bản thuật toán tính toán chính xác và trả về kết quả là những đáp án chính xác. Phương pháp dung sai α (Corall et al, 2000a) Khi phương pháp lược bớt theo kinh nghiệm được áp dụng, thành phần X sẽ được loại bỏ nếu MINMINDIST (X) + α(z) > z, với z (z ≥ 0) là giá trị khoảng cách hiện thời đang được lược bớt (ví dụ, khoảng cách của K-th vùng lân cận gần nhất đã được truy xuất với K-NNQ) và α(z) là một hàm dung sai cho phép. Để áp dụng hiệu quả phương pháp xấp xỉ này, hàm α(z) phải thỏa Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


58

mãn điều kiện α(z) ≥ 0 với mọi z và z1 ≤ z2 chỉ ra rằng z1 - α(z1) ≤ z2 - α(z2). Dạng cơ bản của α(z) là : α(z) = β (β là một hằng số không âm) và α(z) = z * γ (γ là một hằng số với 0 ≤ γ ≤ 1). Trong trường hợp thứ hai, MINMINDIST(X) + (z * γ) > z Ù MINMINDIST(X) > z – (z*γ) Ù MINMINDIST(X) > z * (1- γ). Trong trường hợp này, việc tăng giá trị của z phụ thuộc vào γ (số thực dương nằm trong khoảng [0. 1]), với γ = 0 ta cũng có thuật toán tính toán chính xác. Phương pháp N-consider (Corall et al, 2000a) Trong trường hợp này, thuật toán rẽ nhánh và cận chỉ được sử dụng như một phần tử đã được xác định, hoặc tỷ lệ phần trăm N (0 ≤ N ≤ 1) của tổng số lượng các thành phần được khảo sát bởi thuật toán tính toán chính xác tương ứng, khi xem xét đến thành phần bên trong N1 hoặc nút lá NL trong K-NNQ, hoặc một cặp điểm N1 hoặc nút lá NL với K-CPQ. Với kỹ thuật xấp xỉ này ta cố gắng giảm thiểu được việc mất thời gian trong quá trình tính toán khoảng cách và làm giảm hiệu suất của chương trình một cách đáng kể. Thuật toán là tính toán chính xác trong trường hợp N = 1 (N1 = NL = 1) Phương pháp tính toán theo thời gian Phương pháp tính toán theo thời gian - Time-consider method: Với kỹ thuật này, thuật toán sẽ đưa ra một kết quả tốt nhât có thể (chính xác hoặc xấp xỉ) nằm trong khoảng giới hạn của thời gian xử lý truy vấn cho phép (tổng thời gian), và báo cáo kết quả tìm được một cách nhanh chóng. Ta sẽ có thuật toán tính toán chính xác khi tổng thời gian này là không giới hạn (vô hạn). Khi khảo sát kỹ thuật xấp xỉ này, với thời gian trả lời là một tham số quan trọng được điều khiển trong các truy vấn liên quan đến khoảng cách. Chú ý rằng phương pháp này không phải là phương pháp thu nhỏ không gian tìm kiếm tự nhiên nhưng nó sử dụng việc giảm bớt không gian một cách hiệu quả: Khi việc tính toán chưa hoàn tất, không gian cũng sẽ không được tìm kiếm triệt để. Các hàm khoảng cách dựa trên MBR trên đây cùng kỹ thuật lược bớt theo kinh nghiệm và các kỹ thuật xấp xỉ (tính toán gần đúng) dựa trên việc thu nhỏ Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


59

không gian tìm kiếm, có thể được “nhúng” vào thuật toán rẽ nhánh và cận gần đúng (approximate branch-and-bound algorithms) trong các truy vấn liên quan đến khoảng cách và ứng dụng vào việc đánh chỉ mục trong các họ R-tree và đáp ứng hiệu quả bài toán đặt ra bằng các kết quả gần đúng một cách nhanh chóng. Với mục đích thiết kế thuật tóan rẽ nhánh và cận gần đúng ứng dụng trong xử lý các truy vấn dạng K-NNQ và K-CPQ theo cách thức “non- incremental” - không gia số (K phải được hiểu theo nghĩa nâng cao), do vậy việc xây dựng một cấu trúc dữ liệu mở rộng để lưu trữ K lân cận gần nhất hoặc các cặp gần nhất theo thứ tự đã định sẵn là cần thiết. Cấu trúc dữ liệu này được gọi là K-heap – được tổ chức như một heap nhị phân lớn nhất. Nó có thể áp dụng được cả bốn kỹ thuật xấp xỉ vào các thuật tóan rẽ nhánh và cận có gia số và không có gia số (lặp và đệ quy) trong các truy vấn liên quan đến khoảng cách (bao gồm K-NNQ và K-CPQ) sử dụng cấu trúc dạng cây thuộc họ R- tree, mặc dù ta sẽ chỉ sử dụng chúng trong các kỹ thuật không gia số. P.156 3.2 Kỹ thuật tìm kiếm theo kinh nghiệm Dưới đây là một số kỹ thuật tìm kiếm dựa trên kinh nghiệm - Heuristic space techniques - (Tìm kiếm khu vực, simulated annealing – tạm dịch: mô phỏng sự xử lý nhiệt và các thuật toán phát sinh), các phương pháp này có thể kết hợp với kỹ thuật đánh chỉ mục không gian dạng cây (R-Tree) nhằm đạt được kết quả tốt nhất, nhưng không cần thiết phải tối ưu hóa, đây là một giải pháp tăng hiệu năng trong việc xử lý các truy vấn liên quan đến khoảng cách, và đưa ra câu trả lời truy vấn một cách nhanh chóng. 3.2.1 Tìm kiếm khu vực Tìm kiếm khu vực – Local search - hoặc phương pháp gia tăng lặp bắt đầu với một giá trị thỏa mãn ngẫu nhiên gọi là Seed, và sau đó nó cố gắng nắm bắt được một tối ưu mang tính khu vực bằng quá trình thực thi kỹ thuật di chuyển leo đồi (là phương pháp khảo sát các lân cận thỏa mãn ở mức cao hơn). Khi tìm kiếm được một câu trả lời tối ưu trong khu vực (trong trường hợp không thể thực hiện tiếp việc tìm kiếm lân cận ở mức cao hơn), chương trình khởi tạo lại quá trình tìm kiếm trên tại một Seed khác cho đến khi đạt đến giới hạn thời gian xử lý cho phép của hệ thống. Thuật toán dựa trên khái niệm phổ biến Đề tài: Tính toán xấp xỉ với các truy vấn liên quan đến khoảng cách trong cơ sở dữ liệu không gian  2008


60

này đang rất thành công trong việc giải quyết một số vấn đề phức tạp hiện nay. Trong ngữ cảnh của kỹ thuật tính toán gần đúng, tìm kiếm khu vực được áp dụng với mục đích cải thiện chất lượng của các giải pháp tìm kiếm xấp xỉ ban đầu đang được sử dụng trong nhiều ứng dụng. Quá trình sắp xếp tổng quát một cách có hệ thống nhằm lặp lại việc tìm kiếm một đáp án chính xác hơn trong vùng lân cận N(x) với x là nghiệm gần đúng được đưa ra. Có rất nhiều giải thuật có thể được thiết kế dựa trên việc vùng lân cận N(x) được định nghĩa như thế nào, và N(x) có thể được định nghĩa một cách rõ ràng hoặc toàn diện (có nghĩa tương ứng với một thuật toán để tính toán các thành phần trong N(x)). Lược đồ tổng quát được mô tả như những bước dưới đây: Input: Một nghiệm gần đúng - x Output: Một nghiệm gần đúng x với độ chính xác cao hơn giả thiết. ™ LS1: Giả thiết có x. Kiểm tra sự tồn tại một giá trị nghiệm tốt hơn của hàm tính toán trong N(x) ™ LS2: Nếu có, thiết lập x là giá trị biểu diễn cho nghiệm chính xác hơn ở trên và quay trở lại bước LS1. Ngược lại, chương trình sẽ trả về giá trị x là nghiệm gần đúng tối ưu và dừng. 3.2.2 Simulated Annealing Simulated Annealing là phương pháp tìm kiếm theo kinh nghiệm dựa trên ý tưởng từ nghành vật lý học (xuất phát từ sự tương tự với quá trình xử lý nhiệt các vật liệu thủy tinh). Ý tưởng thiết yếu này không phải là ý tưởng nhằm giới hạn thuật toán tìm kiếm để chuyển đến không gian tìm kiếm, điều này có thể làm giảm hàm giá trị (trong khi với hàm giá trị, ta cần cố gắng tối thiểu hóa), nhưng việc cho phép dịch chuyển một phần (các thành phần có thể) có thể làm tăng việc phải tính toán các hàm giá trị. Về cơ bản, nó cho phép thuật toán tìm kiếm bỏ qua các tối thiểu k