Luận Văn Thạc Sĩ Về Phương Pháp Tổ Chức Cơ Sở Dữ Liệu Cho Đối Tượng Chuyển Động

Luận văn thạc sĩ phân tích phương pháp tổ chức cơ sở dữ liệu cho đối tượng chuyển động 04, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực tiễn.

• Tác giả: Nguyễn Trung Quân
• Người hướng dẫn: TS. Hoàng Đỗ Thanh Tùng
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Phương Pháp Tổ Chức Cơ Sở Dữ Liệu Cho Đối Tượng Chuyển Động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• DANH SÁCH TỪ VIẾT TẮT
• DANH SÁCH BẢNG
• DANH SÁCH HÌNH
• PHẦN MỞ ĐẦU
• 0.1. Tính cấp thiết của đề tài
• 0.2. Mục tiêu nghiên cứu của đề tài
• 0.3. Đối tượng và phạm vi nghiên cứu
• 0.4. Ý nghĩa khoa học của đề tài
• 0.5. Bố cục luận văn
• 1. CHƯƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG THỜI GIAN VÀ ĐÁNH CHỈ MỤC
• 1.1. Hệ thống cơ sở dữ liệu không gian
• 1.2. Cơ sở dữ liệu không gian (Spatial Database)
• 1.3. Hạ tầng CSDL không gian
• 1.4. Các chức năng của quản lý cơ sở dữ liệu
• 1.5. Mô hình cơ sở dữ liệu không gian
• 1.6. Khái quát các khái niệm dữ liệu cơ sở trong CSDL không gian
• 2. CHƯƠNG 2: CÁC PHƯƠNG PHÁP TỔ CHỨC CƠ SỞ DỮ LIỆU CHO ĐỐI TƯỢNG CHUYỂN ĐỘNG
• 3. CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về cơ sở dữ liệu không thời gian và đánh chỉ mục

Cơ sở dữ liệu không thời gian là một lĩnh vực quan trọng trong công nghệ thông tin, đặc biệt là trong việc quản lý và truy vấn dữ liệu không gian. Cơ sở dữ liệu không gian (Spatial Database) cho phép tích hợp thông tin địa lý và thuộc tính trong cùng một hệ thống. Hệ thống này không chỉ hỗ trợ việc lưu trữ mà còn cung cấp các phương pháp truy vấn hiệu quả cho các đối tượng không gian. Hệ thống cơ sở dữ liệu không gian (Spatial Database System) ra đời nhằm đáp ứng nhu cầu lưu trữ và quản lý dữ liệu địa lý, từ đó giúp cho việc phân tích và xử lý thông tin trở nên dễ dàng hơn. Việc sử dụng các công nghệ như GPS đã mở ra nhiều ứng dụng thực tiễn trong việc theo dõi và quản lý đối tượng chuyển động. Đặc biệt, cơ sở dữ liệu không-thời gian cho phép quản lý các đối tượng theo thời gian và không gian, giúp cho việc dự đoán vị trí tương lai của các đối tượng trở nên khả thi. Các ứng dụng này không chỉ giới hạn trong lĩnh vực giao thông mà còn mở rộng ra nhiều lĩnh vực khác như môi trường, quy hoạch đô thị và quản lý tài nguyên.

1.1 Hệ thống cơ sở dữ liệu không gian

Hệ thống cơ sở dữ liệu không gian là một phần quan trọng trong việc quản lý dữ liệu địa lý. Nó cho phép lưu trữ và truy vấn các đối tượng không gian một cách hiệu quả. Cơ sở dữ liệu không gian (Spatial Database) không chỉ lưu trữ vị trí và hình dạng của các đối tượng mà còn tích hợp các thuộc tính liên quan. Các công nghệ như GIS (Geographic Information System) đã phát triển mạnh mẽ, cung cấp các công cụ cần thiết để xử lý và phân tích dữ liệu không gian. Hệ thống này yêu cầu một hạ tầng dữ liệu không gian vững chắc, bao gồm các công nghệ, chính sách và quy trình để đảm bảo tính chính xác và hiệu quả trong việc quản lý dữ liệu. Việc áp dụng các mô hình dữ liệu không gian hiện đại giúp cho việc truy vấn và phân tích dữ liệu trở nên nhanh chóng và chính xác hơn, từ đó hỗ trợ ra quyết định trong nhiều lĩnh vực khác nhau.

1.2 Các chức năng của quản lý cơ sở dữ liệu

Quản lý cơ sở dữ liệu không gian bao gồm nhiều chức năng quan trọng nhằm tối ưu hóa việc lưu trữ và truy vấn dữ liệu. Một trong những chức năng chính là giảm thiểu sự trùng lặp dữ liệu, giúp tiết kiệm chi phí và nâng cao hiệu quả sử dụng. Quản lý dữ liệu không gian còn cho phép người dùng dễ dàng truy cập và cập nhật thông tin, đảm bảo rằng dữ liệu luôn chính xác và kịp thời. Hệ thống cũng hỗ trợ việc ra quyết định dựa trên dữ liệu chính xác, từ đó nâng cao khả năng phân tích và dự đoán. Việc áp dụng các chuẩn mở quốc tế trong thiết kế cơ sở dữ liệu không gian giúp tăng cường khả năng tích hợp và chia sẻ dữ liệu giữa các hệ thống khác nhau. Điều này đặc biệt quan trọng trong bối cảnh toàn cầu hóa và sự phát triển nhanh chóng của công nghệ thông tin.

II. Các phương pháp tổ chức cơ sở dữ liệu cho đối tượng chuyển động

Các phương pháp tổ chức cơ sở dữ liệu cho đối tượng chuyển động đóng vai trò quan trọng trong việc quản lý và truy vấn dữ liệu không-thời gian. Việc lập chỉ mục cho các đối tượng chuyển động giúp tối ưu hóa quá trình truy vấn và nâng cao hiệu suất của hệ thống. Lập chỉ mục quá khứ tiến trình không-thời gian là một trong những phương pháp quan trọng, cho phép lưu trữ và truy xuất thông tin về vị trí và trạng thái của các đối tượng theo thời gian. Phương pháp này không chỉ giúp theo dõi các đối tượng trong quá khứ mà còn dự đoán vị trí tương lai của chúng. Các phương pháp tiếp cận như TPR-tree (Time Parameterized R-tree) đã được phát triển để hỗ trợ việc lập chỉ mục cho các quỹ đạo của đối tượng chuyển động, từ đó nâng cao khả năng truy vấn và phân tích dữ liệu. Việc áp dụng các phương pháp này không chỉ giúp cải thiện hiệu suất của hệ thống mà còn mở ra nhiều cơ hội mới trong việc phát triển các ứng dụng thông minh.

2.1 Lập chỉ mục cho các quỹ đạo của các vị trí

Lập chỉ mục cho các quỹ đạo của các vị trí là một phương pháp quan trọng trong việc quản lý dữ liệu không-thời gian. Phương pháp này cho phép lưu trữ thông tin về vị trí của các đối tượng theo thời gian, từ đó hỗ trợ việc truy vấn và phân tích dữ liệu một cách hiệu quả. TPR-tree là một trong những cấu trúc dữ liệu được sử dụng phổ biến để lập chỉ mục cho các quỹ đạo. Cấu trúc này cho phép lưu trữ thông tin về vị trí hiện tại và các vị trí trong quá khứ của đối tượng, giúp cho việc truy vấn trở nên nhanh chóng và chính xác. Việc áp dụng các thuật toán hiệu quả trong việc chèn và xóa các đối tượng trong TPR-tree giúp tối ưu hóa hiệu suất của hệ thống, từ đó nâng cao khả năng quản lý và phân tích dữ liệu không-thời gian.

2.2 Lập chỉ mục cho hiện tại và tương lai của đối tượng chuyển động

Lập chỉ mục cho hiện tại và tương lai của đối tượng chuyển động là một thách thức lớn trong việc quản lý dữ liệu không-thời gian. Phương pháp này yêu cầu một cách tiếp cận linh hoạt để có thể dự đoán vị trí tương lai của các đối tượng dựa trên các thông tin hiện tại. Việc sử dụng TPR-tree không chỉ giúp lưu trữ thông tin về vị trí hiện tại mà còn cho phép dự đoán các vị trí trong tương lai. Các thuật toán được phát triển để tối ưu hóa quá trình truy vấn, giúp người dùng dễ dàng tìm kiếm thông tin về các đối tượng chuyển động. Điều này không chỉ nâng cao hiệu suất của hệ thống mà còn mở ra nhiều cơ hội mới trong việc phát triển các ứng dụng thông minh, từ đó hỗ trợ việc ra quyết định trong nhiều lĩnh vực khác nhau.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của công nghệ định vị toàn cầu GPS và các vệ tinh quan sát trái đất, việc quản lý và lưu trữ dữ liệu đối tượng chuyển động trở thành một thách thức lớn trong lĩnh vực công nghệ thông tin, đặc biệt là hệ thống thông tin và cơ sở dữ liệu không gian - thời gian. Từ năm 2008 đến 2012, Việt Nam đã phóng thành công hai vệ tinh, mở ra nhiều cơ hội ứng dụng trong quản lý dữ liệu không gian địa lý và đối tượng chuyển động. Với sự gia tăng nhanh chóng về lượng dữ liệu và tính đa dạng của các đối tượng chuyển động, các hệ quản trị cơ sở dữ liệu quan hệ truyền thống không còn đáp ứng được yêu cầu về hiệu quả lưu trữ và truy vấn.

Mục tiêu nghiên cứu của luận văn là phát triển các phương pháp tổ chức cơ sở dữ liệu hiệu quả cho đối tượng chuyển động, tập trung vào việc lập chỉ mục hiện tại và dự đoán tương lai của các đối tượng này. Phạm vi nghiên cứu tập trung vào mô hình và tổ chức đánh chỉ mục cho cơ sở dữ liệu hiện tại của các đối tượng chuyển động trong không gian hai chiều, với dữ liệu được thu thập và xử lý trong khoảng thời gian thực tế. Ý nghĩa của nghiên cứu thể hiện qua việc nâng cao hiệu quả truy vấn và lưu trữ dữ liệu, hỗ trợ các ứng dụng quản lý giao thông, viễn thông và các hệ thống theo dõi đối tượng chuyển động trong thực tế.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính: lý thuyết cơ sở dữ liệu không gian - thời gian và mô hình cấu trúc dữ liệu cây R-tree cùng các biến thể của nó. Cơ sở dữ liệu không gian - thời gian (Spatio-Temporal Database) là mô hình tích hợp thông tin địa lý và thuộc tính theo thời gian, cho phép quản lý các đối tượng chuyển động với vị trí và trạng thái thay đổi liên tục. Các khái niệm chính bao gồm:

• Cơ sở dữ liệu không gian (Spatial Database): lưu trữ dữ liệu địa lý dưới dạng điểm, đường, vùng với các thuộc tính liên quan.
• R-tree và các biến thể (3DR-tree, HR-tree, MV3R-tree, TPR-tree): cấu trúc cây cân bằng dùng để đánh chỉ mục dữ liệu không gian đa chiều, hỗ trợ truy vấn hiệu quả.
• Chỉ mục tham số thời gian (Time-parameterized R-tree - TPR-tree): mở rộng R-tree bằng cách mô hình hóa vị trí đối tượng chuyển động theo hàm tuyến tính của thời gian, giúp dự đoán vị trí tương lai.
• Chỉ mục ảnh chụp (Snapshot index): lưu trữ trạng thái đối tượng tại các mốc thời gian khác nhau, hỗ trợ truy vấn lịch sử.

Phương pháp nghiên cứu

Nguồn dữ liệu được xây dựng giả lập với các đối tượng chuyển động trong không gian hai chiều, tọa độ trong phạm vi [0, 10000] trên mỗi trục, vận tốc thay đổi trong khoảng [-50, 50] với bước cập nhật vận tốc tối đa 5. Cỡ mẫu thử nghiệm dao động từ 10.000 đến 50.000 đối tượng chuyển động, được tạo ngẫu nhiên và cập nhật theo thời gian.

Phương pháp phân tích sử dụng các thuật toán lập chỉ mục dựa trên cấu trúc TPR-tree, kết hợp với bộ nhớ đệm (cache) để tối ưu hiệu suất truy vấn. Các thuật toán chèn, xóa, cập nhật và truy vấn được thiết kế dựa trên nguyên lý của R-tree và mở rộng cho dữ liệu chuyển động theo thời gian. Timeline nghiên cứu bao gồm giai đoạn thiết kế mô hình, xây dựng chương trình thử nghiệm, thu thập và phân tích kết quả trong khoảng thời gian thực tế.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả truy vấn mốc thời gian (timeslice query): TPR-tree cho phép truy vấn vị trí đối tượng tại một thời điểm xác định với chi phí truy cập trung bình giảm khoảng 30% so với R-tree truyền thống nhờ mô hình hóa vị trí theo hàm tuyến tính thời gian.

2. Giảm chi phí truy vấn nhờ cache: Việc sử dụng bộ nhớ đệm lưu trữ các node đã truy cập giúp giảm chi phí truy vấn trung bình từ 3 node xuống còn 1-2 node, tương đương tiết kiệm khoảng 40-50% chi phí truy cập đĩa.

3. Khả năng dự đoán vị trí tương lai: TPR-tree hỗ trợ dự đoán vị trí đối tượng trong khoảng thời gian giới hạn (Time Horizon), giúp nâng cao hiệu quả trong các ứng dụng theo dõi giao thông và truyền thông di động.

4. Không gian lưu trữ tối ưu: So với các phương pháp như HR-tree và MV3R-tree, TPR-tree sử dụng không gian lưu trữ hiệu quả hơn khoảng 20-30%, giảm thiểu việc nhân bản dữ liệu khi đối tượng chuyển động liên tục.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả trên là do TPR-tree mô hình hóa vị trí đối tượng chuyển động bằng các hàm tuyến tính theo thời gian, giúp giảm thiểu việc lưu trữ trạng thái từng mốc thời gian và tránh trùng lặp dữ liệu. Việc sử dụng cache làm giảm đáng kể số lần truy cập đĩa, từ đó tăng tốc độ truy vấn. Kết quả này phù hợp với các nghiên cứu gần đây trong lĩnh vực cơ sở dữ liệu không gian - thời gian, đồng thời khắc phục hạn chế của các phương pháp lập chỉ mục truyền thống như 3DR-tree hay HR-tree.

Dữ liệu có thể được trình bày qua biểu đồ so sánh chi phí truy vấn giữa các phương pháp, biểu đồ hiệu quả sử dụng bộ nhớ cache và bảng thống kê số lượng node truy cập trung bình theo từng kích thước mẫu dữ liệu. Những kết quả này có ý nghĩa quan trọng trong việc phát triển các hệ thống quản lý đối tượng chuyển động thực tế, đặc biệt trong các ứng dụng giám sát giao thông và quản lý tài nguyên.

Đề xuất và khuyến nghị

1. Triển khai TPR-tree trong hệ thống quản lý giao thông: Áp dụng phương pháp lập chỉ mục TPR-tree để nâng cao hiệu quả truy vấn vị trí xe cộ trên các tuyến đường cao tốc, giảm thời gian phản hồi truy vấn xuống dưới 1 giây, thực hiện trong vòng 12 tháng, do các cơ quan quản lý giao thông thực hiện.

2. Tích hợp bộ nhớ đệm thông minh: Phát triển các thuật toán quản lý cache như LRU, LFU để tối ưu hóa bộ nhớ đệm trong hệ thống cơ sở dữ liệu, giảm chi phí truy cập đĩa ít nhất 30%, triển khai trong 6 tháng, do đội ngũ phát triển phần mềm đảm nhiệm.

3. Mở rộng mô hình cho dữ liệu 3 chiều: Nghiên cứu và phát triển mở rộng TPR-tree cho dữ liệu không gian 3D phục vụ các ứng dụng y học, thiên văn học, hoàn thành trong 18 tháng, do các viện nghiên cứu chuyên ngành thực hiện.

4. Đào tạo và chuyển giao công nghệ: Tổ chức các khóa đào tạo về cơ sở dữ liệu không gian - thời gian và kỹ thuật lập chỉ mục TPR-tree cho cán bộ kỹ thuật và sinh viên, nâng cao năng lực ứng dụng công nghệ mới, thực hiện liên tục hàng năm, do các trường đại học và viện nghiên cứu phối hợp thực hiện.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và giảng viên công nghệ thông tin: Nắm bắt các phương pháp tổ chức cơ sở dữ liệu không gian - thời gian tiên tiến, áp dụng trong giảng dạy và nghiên cứu chuyên sâu về hệ thống thông tin.

2. Kỹ sư phát triển phần mềm quản lý giao thông và viễn thông: Áp dụng các thuật toán lập chỉ mục TPR-tree để xây dựng hệ thống theo dõi và dự đoán vị trí đối tượng chuyển động, nâng cao hiệu quả xử lý dữ liệu.

3. Quản lý dự án và nhà hoạch định chính sách: Hiểu rõ về tầm quan trọng và ứng dụng của cơ sở dữ liệu không gian - thời gian trong quản lý đô thị, giao thông và phát triển hạ tầng công nghệ.

4. Sinh viên chuyên ngành hệ thống thông tin và công nghệ thông tin: Học tập và nghiên cứu các kỹ thuật lập chỉ mục dữ liệu chuyển động, chuẩn bị nền tảng cho các đề tài luận văn và nghiên cứu khoa học.

Câu hỏi thường gặp

1. Tại sao cần sử dụng TPR-tree thay vì R-tree truyền thống?
   TPR-tree mô hình hóa vị trí đối tượng chuyển động theo hàm tuyến tính thời gian, giúp dự đoán vị trí tương lai và giảm chi phí lưu trữ, trong khi R-tree chỉ lưu trữ trạng thái tại các mốc thời gian cụ thể, gây trùng lặp dữ liệu và truy vấn kém hiệu quả.

2. Phương pháp lập chỉ mục nào phù hợp cho dữ liệu chuyển động có tốc độ thay đổi liên tục?
   TPR-tree là lựa chọn phù hợp vì nó cập nhật vị trí dựa trên hàm vận tốc, giảm số lần cập nhật dữ liệu so với phương pháp lưu trữ từng trạng thái như HR-tree hay MV3R-tree.

3. Cache giúp cải thiện hiệu suất truy vấn như thế nào?
   Cache lưu trữ các node đã truy cập giúp giảm số lần truy cập đĩa, tiết kiệm chi phí truy vấn trung bình từ 30-50%, đặc biệt hiệu quả khi có nhiều truy vấn liên tiếp đến các đối tượng gần nhau.

4. Có thể áp dụng mô hình này cho dữ liệu 3D không?
   Có thể, tuy nhiên cần mở rộng cấu trúc TPR-tree để xử lý dữ liệu không gian ba chiều, đây là hướng nghiên cứu tiếp theo nhằm phục vụ các lĩnh vực như y học và thiên văn học.

5. Thời gian cập nhật dữ liệu ảnh hưởng thế nào đến hiệu quả của TPR-tree?
   Thời gian cập nhật càng ngắn và chính xác thì dự đoán vị trí tương lai càng chính xác, giúp truy vấn nhanh và hiệu quả hơn. Tuy nhiên, cập nhật quá thường xuyên có thể làm tăng chi phí xử lý, cần cân bằng giữa tần suất cập nhật và hiệu quả truy vấn.

Kết luận

• Luận văn đã phát triển và thử nghiệm thành công phương pháp tổ chức cơ sở dữ liệu cho đối tượng chuyển động dựa trên cấu trúc TPR-tree, nâng cao hiệu quả truy vấn và lưu trữ.
• Kết quả thử nghiệm cho thấy TPR-tree giảm chi phí truy vấn trung bình khoảng 30% so với các phương pháp truyền thống, đồng thời tiết kiệm không gian lưu trữ.
• Việc sử dụng bộ nhớ đệm (cache) giúp giảm chi phí truy cập đĩa đến 50%, tăng tốc độ truy vấn đối tượng chuyển động.
• Nghiên cứu mở ra hướng phát triển cho các hệ thống quản lý giao thông, viễn thông và các ứng dụng theo dõi đối tượng chuyển động trong thực tế.
• Đề xuất triển khai ứng dụng TPR-tree trong các hệ thống thực tế và mở rộng nghiên cứu cho dữ liệu không gian 3 chiều trong tương lai gần.

Khuyến khích các tổ chức nghiên cứu và doanh nghiệp ứng dụng phương pháp TPR-tree vào hệ thống quản lý dữ liệu chuyển động, đồng thời phát triển các giải pháp tối ưu bộ nhớ đệm và mở rộng mô hình cho dữ liệu đa chiều.

Trích đoạn nội dung tài liệu

PHẦN MỞ ĐẦU 1. Tính cấp thiết của đề tài Năm 2008, Việt Nam đã phóng vệ tinh đầu tiên vào trong quỹ đạo mở ra nhiều bước tiến mới cho ngành viễn thông. Công nghệ GPS (Global Positioning System) đã được giới thiệu và nhiều ứng dụng khác nhau trong cuộc sống, việc khai thác thông tin phục vụ con người là rất cần thiết, mang lại hiệu quả cao trong nhiều lĩnh vực khoa học công nghệ, phục vụ đời sống sản xuất Năm 2012, Việt Nam phóng thêm một vệ tinh nữa lên quỹ đạo và đã đưa những hình ảnh chụp trên lãnh thổ Việt Nam được rõ nét hơn phục vụ đắc lực trong công tác nghiên cứu khoa học. Với những vệ tinh này việc quản lý, theo dõi đối tượng chuyển động dễ dàng hơn, việc lưu trữ cơ sở dữ liệu (CSDL) được thuận tiện khi nó được đánh chỉ mục cho việc theo dõi, quản lý.

Cùng với sự tăng trưởng nhanh chóng của lượng thông tin cũng như sự đa dạng về thể loại thông tin cần lưu trữ và xử lý, chúng ta ngày càng nhận ra những hạn chế của các Hệ quản trị CSDL quan hệ truyền thống, và nhu cầu cần phải có các hệ quản trị CSDL với các dịch vụ phù hợp chính là yếu tố thúc đẩy những nghiên cứu mới trong lĩnh vực này. Một trong các mô hình CSDL được quan tâm nhất hiện nay chính là mô hình CSDL không gian - Spatial DataBase (SDB) xử lý các đối tượng dữ liệu không gian, chẳng hạn dữ liệu bản đồ, dữ liệu multimedia. và mở rộng hơn nữa là kho dữ liệu không gian - Spatial Data. Các nghiên cứu trên lĩnh vực này đã thu được rất nhiều thành tựu, tuy nhiên cũng còn không ít khó khăn và thách thức đòi hỏi phải có các giải pháp mới.

Cơ sở dữ liệu không gian tập trung vào hỗ trợ mô hình và truy vấn dạng hình học liên quan đến các đối tượng trong CSDL còn cơ sở dữ liệu thời gian tập trung vào tình trạng của đối tượng ở các thời điểm khác nhau. Vì vậy đòi hỏi hai CSDL không gian và thời gian liên kết chặt chẽ với nhau tạo thành một ứng dụng quan trọng đó là “cơ sở dữ liệu 1 không – thời gian” hay là cơ sở dữ liệu cho các đối tượng chuyển động. Từ thực tiễn trên tác giả lựa chọn đề tài “Phương pháp tổ chức cơ sở dữ liệu cho đối tượng chuyển động” z 2 2. Mục tiêu nghiên cứu của đề tài 2.

Mục tiêu chung Quản lý được cơ sở dữ liệu một cách có hiệu quả và việc truy vấn cơ sở dữ liệu dễ hơn, trong tất cả lĩnh vực so với Hệ quản trị cơ sở dữ liệu quan hệ truyền thống. Từ đó đưa ra những giải pháp nhằm nâng cao hơn nữa trong việc lưu trữ và tìm kiếm dữ liệu.2 Mục tiêu cụ thể Tìm hiểu các phương pháp tổ chức cơ sở dữ liệu cho đối tượng chuyển động. Tìm hiểu chi tiết phương pháp lập chỉ mục hiện tại và tương lai của đối tượng chuyển động. Đối tƣợng và phạm vi nghiên cứu - Mô hình, tổ chức đánh chỉ số cho cơ sở dữ liệu hiện tại.

- Nghiên cứu, xây dựng phương pháp đánh chỉ mục cơ sở dữ liệu hiện tại cho các đối tượng chuyển động. Ý nghĩa khoa học của đề tài - Hỗ trợ việc mô hình hoá và truy vấn cơ sở dữ liệu để quản lý đối tượng chuyển động. - Hiểu rỗ các phương pháp tổ chức cơ sở dữ liệu mới cho các đối tượng chuyển động, giúp cho quá trình truy xuất, lưu trữ dữ liệu nhanh hơn và hiệu quả hơn. - Áp dụng hỗ trợ cơ sở dữ liệu cho các phần mềm quản lý và truy vấn các đối tượng chuyển động hiện tại hoặc quá khứ.

Bố cục luận văn Chƣơng 1: Tổng quan về cơ sở dữ liệu không thời gian và đánh mục Chƣơng 2: Các phương pháp tổ chức dữ liệu cho đối tượng chuyển động Chƣơng 3 Xây dựng chương trình thử nghiệm z 3 Chƣơng 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU KHÔNG THỜI GIAN VÀ ĐÁNH CHỈ MỤC 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.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.1 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 z 4 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. Trong những năm gần đây Hệ thống cơ sở dữ liệu quản lý đối tượng không gian và thời gian ngày càng nhận được nhiều sự quan tâm.

Cơ sở dữ liệu lưu trữ các đối tượng không gian, mà các thay đổi mức độ, vị trí của các đối tượng theo thời gian, được gọi là cơ sở dữ liệu không-thời gian. Trong các cơ sở dữ liệu này việc dự kiến các vị trí tương lai, mức độ của các đối tượng thường được quan tâm. Những ứng dụng về các đối tượng không thời gian như là: sự thay đổi toàn cầu(khí hậu,dữ liệu của vùng đất liền), giao thông vận tải( giám sát giao thông), xã hội( nhân khẩu, sức khỏe), đa phương tiện (phim hoạt hình). Dưới đây ví dụ về ứng dụng không thời gian Ví dụ tiên chúng ta xem xét một cơ sở dữ liệu quản lý phương tiện di chuyển (xe ô tô) trong một hệ thống đường cao tốc.

Ngày nay công nghệ GPS cho phép để xác định vị trí con người và phương tiện ở bất kỳ vị trí trên trái đất, với độ chính xác cao. Cần phải có một cơ sở dữ liệu lưu trữ các vị trí hiện tại của phương tiện di chuyển, cũng như định hướng và tốc độ. Từ đó phát sinh những truy vấn dành riêng cho cơ sở dữ liệu này. Ví dụ một người muốn tìm khách sạn gần nhất với mình trong 10 phút nữa.

Hay là công ty quản lý xe tải muốn tìm chiếc xe tải gần với nhà kho cụ thể. Hay tìm chiếc xe cứu thương gần nhất với vụ tai nạn giao thông xảy ra. Do đặc điểm của thời gian, cơ sở dữ liệu không thời gian phải quản lý lượng lớn dữ liệu. Một phương pháp để trả lời các câu truy vấn là đọc tất cả dữ liệu của tất cả đối tượng sau đó trả về đối tượng phù hợp với câu truy vấn.

Tuy nhiên cách này phát sinh vấn đề liên quan đến kích thước của dữ liệu. Một giải pháp tốt hơn là xây dựng chỉ mục dữ liệu và trả lời truy vấn bằng cách chỉ phải đọc một phần nhỏ của cơ sở dữ liệu Chỉ mục là một cách để tổ chức dữ liệu trên trang đĩa để trả lời hiệu quả các truy vấn, bằng cách đọc một phần nhỏ của dữ liệu.2 Hạ tầng CSDL không gian Công nghệ (technology) Chính sách (policies) Chuẩn (standards) z 5 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.3 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).