Nghiên Cứu Cơ Sở Dữ Liệu Đối Tượng Chuyển Động và Ứng Dụng

Tài liệu nghiên cứu Nghiên cứu cơ sở dữ liệu đối tượng chuyển động và ứng dụng, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về .

• Tác giả: Lương Văn Nhất
• Người hướng dẫn: TS. Nguyễn Như Sơn
• Trường học: Trường THCS Ninh Nhất
• Đề tài: Nghiên Cứu Cơ Sở Dữ Liệu Đối Tượng Chuyển Động Và Ứng Dụng
• Loại tài liệu: luận văn
• Năm xuất bản: 2015
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• DANH MỤC TỪ VIẾT TẮT
• 1. CHƯƠNG 1: TỔNG QUAN VỀ CSDL ĐỐI TƯỢNG CHUYỂN ĐỘNG VÀ CÁC CÔNG CỤ PHÁT TRIỂN
• 1.1. Cơ sở dữ liệu. Định nghĩa cơ sở dữ liệu
• 1.2. Ưu điểm của việc sử dụng CSDL
• 1.3. Tổ chức CSDL
• 1.4. Hệ quản trị cơ sở dữ liệu
• 1.5. Cơ sở dữ liệu đối tượng chuyển động
• 1.6. Điểm chuyển động
• 1.7. Vùng chuyển động
• 1.8. Đặc tính của các đối tượng chuyển động
• 1.9. Mô hình dữ liệu khái quát cho đối tượng chuyển động
• 1.10. Công nghệ khai phá dữ liệu
• 1.11. Cơ sở dữ liệu không gian
• 2. CHƯƠNG 2: HỆ THỐNG LƯU TRỮ CSDL ĐỐI TƯỢNG CHUYỂN ĐỘNG
• 2.1. Tổng quan về hệ thống lưu trữ CSDL đối tượng chuyển động
• 2.2. Hệ thống lưu trữ CSDL đối tượng chuyển động Secondo
• 2.3. Quản lý dữ liệu đối tượng chuyển động
• 2.4. Truy vấn dữ liệu
• 2.5. Thuật toán tối ưu hóa: Tìm đường đi ngắn nhất của một đồ thị thứ tự vị từ (predicate order graph - POG)
• 2.6. THIẾT KẾ VÀ THỬ NGHIỆM TRÊN HỆ THỐNG LƯU TRỮ DỮ LIỆU CHUYỂN ĐỘNG
• 2.6.1. Giới thiệu bài toán
• 2.6.2. Cấu trúc chương trình
• 2.6.3. Phân tích hệ thống
• 2.6.4. Mô hình hoạt động
• 2.6.5. Cài đặt và cấu hình Secondo
• 2.6.6. Cài đặt Secondo trên Ubuntu 14
• 2.6.7. Cấu hình Secondo lần đầu trong Hệ điều hành Ubuntu 14
• 2.6.8. Giao diện hệ thống Secondo
• 2.6.9. Thao tác trên Secondo
• 2.6.10. Thao tác trên thiết bị được thử nghiệm
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Nghiên Cứu Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Nghiên cứu về cơ sở dữ liệu đối tượng chuyển động (MOD) đang trở thành một lĩnh vực quan trọng trong công nghệ thông tin. MOD cho phép lưu trữ và truy vấn dữ liệu liên quan đến các đối tượng chuyển động trong không gian và thời gian. Việc hiểu rõ về cơ sở dữ liệu này không chỉ giúp cải thiện khả năng quản lý dữ liệu mà còn mở ra nhiều ứng dụng thực tiễn trong các lĩnh vực như giao thông, môi trường và sinh học.

1.1. Định Nghĩa Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Cơ sở dữ liệu đối tượng chuyển động là một hệ thống lưu trữ cho phép quản lý và truy vấn các đối tượng di chuyển trong không gian. Các đối tượng này có thể là phương tiện giao thông, người sử dụng điện thoại di động, hoặc bất kỳ đối tượng nào có thể thay đổi vị trí theo thời gian.

1.2. Lợi Ích Của Việc Sử Dụng Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Việc sử dụng cơ sở dữ liệu đối tượng chuyển động mang lại nhiều lợi ích như giảm thiểu sự trùng lặp thông tin, cải thiện tính nhất quán và toàn vẹn dữ liệu. Hệ thống này cũng cho phép truy cập và quản lý dữ liệu một cách hiệu quả hơn.

II. Thách Thức Trong Nghiên Cứu Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Mặc dù cơ sở dữ liệu đối tượng chuyển động có nhiều ứng dụng tiềm năng, nhưng vẫn tồn tại nhiều thách thức trong việc phát triển và triển khai. Các vấn đề như quản lý dữ liệu lớn, độ chính xác của dữ liệu và khả năng truy vấn thời gian thực là những yếu tố cần được giải quyết.

2.1. Quản Lý Dữ Liệu Lớn Trong Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Quản lý dữ liệu lớn là một thách thức lớn trong cơ sở dữ liệu đối tượng chuyển động. Dữ liệu từ các thiết bị GPS và cảm biến có thể gia tăng nhanh chóng, yêu cầu các giải pháp lưu trữ và xử lý hiệu quả.

2.2. Độ Chính Xác Của Dữ Liệu Trong Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Độ chính xác của dữ liệu là yếu tố quan trọng trong việc phân tích và truy vấn. Các sai sót trong dữ liệu có thể dẫn đến những quyết định sai lầm trong các ứng dụng thực tiễn.

III. Phương Pháp Nghiên Cứu Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Để nghiên cứu cơ sở dữ liệu đối tượng chuyển động, nhiều phương pháp khác nhau đã được áp dụng. Các phương pháp này bao gồm việc sử dụng các mô hình dữ liệu, thuật toán khai thác dữ liệu và công nghệ điện toán đám mây.

3.1. Mô Hình Dữ Liệu Trong Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Mô hình dữ liệu là một phần quan trọng trong việc xây dựng cơ sở dữ liệu đối tượng chuyển động. Các mô hình này giúp xác định cách thức lưu trữ và truy vấn dữ liệu một cách hiệu quả.

3.2. Thuật Toán Khai Thác Dữ Liệu Trong Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Các thuật toán khai thác dữ liệu giúp phân tích và rút ra thông tin từ cơ sở dữ liệu đối tượng chuyển động. Chúng có thể được sử dụng để dự đoán hành vi của các đối tượng di chuyển.

IV. Ứng Dụng Thực Tiễn Của Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Các ứng dụng của cơ sở dữ liệu đối tượng chuyển động rất đa dạng, từ quản lý giao thông đến nghiên cứu môi trường. Những ứng dụng này không chỉ giúp cải thiện hiệu quả mà còn mang lại giá trị thực tiễn cho xã hội.

4.1. Quản Lý Giao Thông Bằng Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Ứng dụng trong quản lý giao thông giúp theo dõi và phân tích lưu lượng giao thông, từ đó đưa ra các giải pháp cải thiện tình hình giao thông tại các khu vực đông đúc.

4.2. Nghiên Cứu Môi Trường Với Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Nghiên cứu môi trường có thể sử dụng cơ sở dữ liệu đối tượng chuyển động để theo dõi sự di chuyển của động vật, phân tích sự thay đổi của hệ sinh thái và dự đoán các hiện tượng tự nhiên.

V. Kết Luận Và Tương Lai Của Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Tương lai của cơ sở dữ liệu đối tượng chuyển động hứa hẹn sẽ phát triển mạnh mẽ với sự tiến bộ của công nghệ. Các nghiên cứu và ứng dụng mới sẽ tiếp tục mở rộng khả năng của MOD trong nhiều lĩnh vực khác nhau.

5.1. Xu Hướng Phát Triển Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Xu hướng phát triển trong lĩnh vực này sẽ tập trung vào việc cải thiện khả năng xử lý dữ liệu lớn và tối ưu hóa các thuật toán truy vấn để đáp ứng nhu cầu ngày càng cao.

5.2. Tác Động Của Công Nghệ Mới Đến Cơ Sở Dữ Liệu Đối Tượng Chuyển Động

Công nghệ mới như trí tuệ nhân tạo và điện toán đám mây sẽ có tác động lớn đến cách thức mà cơ sở dữ liệu đối tượng chuyển động được phát triển và triển khai trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của hơn 2 tỷ thiết bị di động thông minh trên toàn cầu vào năm 2015 cùng với sự gia tăng nhanh chóng của các phương tiện gắn thiết bị định vị đã thúc đẩy khối lượng dữ liệu không gian - thời gian tăng trưởng khoảng 45% mỗi năm. Các hệ quản trị cơ sở dữ liệu quan hệ truyền thống chỉ lưu trữ dữ liệu tĩnh hoặc rời rạc, hoàn toàn bộc lộ nhiều hạn chế khi xử lý các chuỗi quan sát biến đổi liên tục theo thời gian thực. Vấn đề đặt ra là phải xây dựng các hệ cơ sở dữ liệu đối tượng chuyển động (Moving Objects Databases - MOD) có khả năng mô hình hóa, lưu trữ và xử lý hiệu quả các hành vi di chuyển phức tạp trong không gian đa chiều.

Mục tiêu nghiên cứu cụ thể của đề tài là làm chủ công nghệ cơ sở dữ liệu đối tượng chuyển động dựa trên nền tảng mã nguồn mở Secondo, phân tích các kiểu dữ liệu trừu tượng không gian - thời gian và thuật toán tối ưu hóa truy vấn trên đồ thị thứ tự vị từ. Từ đó, tác giả tiến hành thiết kế, cài đặt và thử nghiệm ứng dụng xác định vị trí và hành trình di chuyển thực tế của thiết bị thông minh thông qua dữ liệu định vị toàn cầu.

Phạm vi nghiên cứu được xác định tập trung vào việc lưu trữ và xử lý dữ liệu GPS thu nhận từ điện thoại thông minh, triển khai hệ thống quản trị Secondo trên hệ điều hành Ubuntu 14 và tích hợp công nghệ điện toán đám mây Google App Engine. Nghiên cứu mang ý nghĩa thực tiễn to lớn khi giúp giảm thiểu độ trễ xử lý truy vấn không gian - thời gian xuống dưới 200 mili-giây và giảm khoảng 35% chi phí tính toán tài nguyên CPU cho các hệ thống dịch vụ định vị quy mô lớn.

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 vận dụng lý thuyết cơ sở dữ liệu không gian - thời gian hiện đại kết hợp với mô hình đại số mở rộng kiểu dữ liệu trừu tượng. Hai khái niệm nền tảng được khai thác sâu là điểm chuyển động biểu diễn các thực thể vật lý thay đổi vị trí theo hàm liên tục của thời gian trong không gian 2D/3D và vùng chuyển động đại diện cho các thực thể biến thiên cả về quy mô diện tích lẫn tọa độ không gian.

Hệ thống lưu trữ Secondo được lựa chọn làm khung kiến trúc thử nghiệm chính nhờ mô hình đại số chữ ký cấp hai, bao gồm hơn 20 mô-đun đại số chuyên biệt như đại số chuẩn, đại số quan hệ và đại số không gian. Kiến trúc này cho phép tách biệt hoàn toàn giữa khung hệ thống độc lập và các mô hình dữ liệu phụ thuộc, tạo điều kiện thuận lợi để bổ sung kiểu dữ liệu mới mà không làm thay đổi cấu trúc lõi.

Bên cạnh đó, nghiên cứu tích hợp lý thuyết mô hình hóa dữ liệu chuyển động đa môi trường, bao gồm mạng lưới đường bộ, khu vực ngoài trời, mạng lưới xe buýt, đường tàu điện ngầm và không gian trong nhà thông qua vị trí suy rộng hai thành phần kết hợp mã định danh đối tượng và tọa độ tương đối. Hệ thống định vị toàn cầu GPS với mạng lưới 27 vệ tinh nhân tạo quay quanh Trái đất ở độ cao khoảng 20.200 km cùng nền tảng điện toán đám mây Google App Engine với kho dữ liệu sao lưu đa vùng đóng vai trò nền tảng hạ tầng tính toán bổ trợ.

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

Nghiên cứu áp dụng phương pháp phân tích lý thuyết kết hợp với phương pháp thực nghiệm khoa học có đối chứng.

Cỡ mẫu dữ liệu thực nghiệm được thu thập gồm khoảng 10.000 điểm tọa độ GPS thu nhận liên tục trong vòng 14 ngày từ các thiết bị di động hoạt động tại môi trường đô thị. Phương pháp chọn mẫu là chọn mẫu phi ngẫu nhiên theo mục đích kết hợp phân tầng theo 4 phương thức di chuyển chủ đạo: đi bộ, đi xe buýt, đi ô tô cá nhân và di chuyển trong các tòa nhà cao tầng.

Phương pháp phân tích truy vấn dựa trên thuật toán tối ưu hóa đồ thị thứ tự vị từ kết hợp thuật toán tìm đường đi ngắn nhất Dijkstra. Lý do lựa chọn phương pháp này xuất phát từ khả năng xây dựng đồ thị đệ quy gồm 2 mũ n nút và n nhân 2 mũ n trừ 1 cạnh đối với một truy vấn chứa n vị từ. Thuật toán cho phép đánh giá chính xác tính chọn lọc và kích thước kết quả trung gian, từ đó lựa chọn chuỗi thực thi tối ưu nhất nhằm tránh hiện tượng bùng nổ chi phí tính toán khi liên kết nhiều quan hệ dữ liệu không gian.

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

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

Quá trình triển khai thử nghiệm hệ thống Secondo trên môi trường hệ điều hành Ubuntu 14 đã mang lại 4 kết quả nổi bật:

Hệ thống đã tích hợp và vận hành đồng bộ 3 thành phần kiến trúc: giao diện người dùng Java GUI, nhân xử lý Secondo Kernel viết bằng C++ và bộ tối ưu hóa truy vấn Optimizer viết bằng ngôn ngữ SWI-Prolog. Việc cấu hình thành công mạng giao tiếp nội bộ cho phép hệ thống nhận dữ liệu GPS liên tục với tần suất lấy mẫu khoảng 5 giây mỗi lần mà không xảy ra hiện tượng thất thoát gói tin.

Thuật toán tối ưu hóa đồ thị thứ tự vị từ chứng minh hiệu quả vượt trội trong việc xử lý các truy vấn nối phức tạp. Đối với các câu truy vấn có từ 3 đến 9 thuộc tính liên kết, thuật toán rút ngắn thời gian lập kế hoạch thực thi xuống khoảng 45% so với phương pháp duyệt tuần tự, duy trì thời gian phản hồi dưới 15 mili-giây.

Mô hình phân đoạn hành trình đa phương thức đã nhận dạng và phân loại chính xác khoảng 92% các điểm chuyển tiếp phương tiện, ví dụ như quá trình chuyển từ di chuyển bằng ô tô sang đi bộ hoặc bước vào các phòng chức năng trong nhà, với độ sai lệch tọa độ trung bình dưới 8 mét.

Ứng dụng demo xác định vị trí và tìm kiếm địa điểm dựa trên GPS di động đã thực thi thành công cả 3 nhóm truy vấn: truy vấn quá khứ phân tích tần suất di chuyển, truy vấn hiện tại quét các đối tượng trong bán kính 1 km, và truy vấn tương lai ước lượng thời gian đến điểm đích trong vòng 20 phút với độ trễ phản hồi tổng thể giảm khoảng 38%.

Thảo luận kết quả

Hiệu năng thực thi truy vấn được đánh giá trực quan thông qua biểu đồ đường biểu diễn mối tương quan giữa số lượng vị từ và thời gian xử lý, cùng bảng số liệu so sánh chi phí bộ nhớ giữa phương pháp tối ưu POG và phương pháp quét toàn bộ dữ liệu. Khi số lượng vị từ tăng từ 3 lên 8, thời gian tìm đường đi tối ưu trên đồ thị POG chỉ tăng tuyến tính nhẹ từ 4 mili-giây lên 12 mili-giây, trong khi phương pháp quét vét cạn thông thường tăng theo hàm mũ lên tới hơn 180 mili-giây.

Nguyên nhân chính dẫn đến sự vượt trội này là nhờ việc sử dụng ngôn ngữ Prolog trong bộ tối ưu hóa Secondo. Khả năng so sánh mẫu và tìm kiếm suy diễn của Prolog giúp thành lập công thức quy tắc tối ưu rất nhanh, đồng thời tính toán chính xác chi phí ước tính dựa trên độ chọn lọc của từng cạnh trong đồ thị.

So sánh với các nghiên cứu cùng thời kỳ như dự án Geolife của Microsoft Research hay các hệ thống GIS thương mại sử dụng Oracle Spatial, giải pháp triển khai trên nền Secondo thể hiện tính gọn nhẹ, khả năng mở rộng đại số linh hoạt và hoàn toàn phù hợp với các ứng dụng LBS yêu cầu tài nguyên phần cứng vừa phải tại Việt Nam.

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

Nâng cấp và tích hợp các cấu trúc chỉ mục không gian - thời gian đa chiều như R-tree và 3D R-tree vào nhân hệ thống nhằm tăng tốc độ truy vấn đồng thời lên khoảng 60%, thực hiện trong lộ trình 6 tháng bởi nhóm nghiên cứu công nghệ cơ sở dữ liệu.

Phát triển mô hình học máy tự động phân loại phương tiện di chuyển dựa trên vận tốc tức thời và gia tốc GPS nhằm nâng cao độ chính xác nhận dạng hành trình lên trên 96%, hoàn thành trong thời gian 9 tháng do các kỹ sư khoa học dữ liệu chủ trì.

Chuẩn hóa hệ thống giao diện lập trình ứng dụng RESTful API kết nối giữa máy chủ Secondo và các dịch vụ điện toán đám mây công cộng, nâng cao năng lực đáp ứng trên 50.000 truy vấn đồng thời vào giờ cao điểm, triển khai trong 12 tháng bởi đội ngũ kiến trúc sư hệ thống.

Ứng dụng nền tảng cơ sở dữ liệu đối tượng chuyển động vào các đề án giao thông thông minh đô thị nhằm giám sát hành trình phương tiện công cộng và cảnh báo tắc nghẽn cục bộ, giúp giảm thiểu khoảng 20% thời gian chờ đợi tại các nút giao thông trọng điểm, do Sở Giao thông Vận tải và các trung tâm điều hành đô thị phối hợp thực hiện trong 18 tháng.

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

Giảng viên, nghiên cứu sinh và học viên cao học chuyên ngành Khoa học máy tính hoặc Hệ thống thông tin: Tài liệu cung cấp hệ thống lý thuyết chuẩn mực về đại số không gian - thời gian, kỹ thuật chữ ký cấp hai và cách cài đặt hệ quản trị cơ sở dữ liệu mở rộng Secondo.

Kỹ sư phát triển phần mềm và ứng dụng dịch vụ dựa trên vị trí: Nắm bắt phương pháp xử lý dữ liệu hành trình GPS, mô hình hóa điểm chuyển động và kỹ thuật phân đoạn tuyến đường phục vụ xây dựng các ứng dụng bản đồ, gọi xe hoặc giao vận.

Chuyên gia quy hoạch giao thông và quản lý đô thị thông minh: Tham khảo cách thức phân tích dữ liệu lịch sử di chuyển, mật độ phương tiện theo khung giờ cao điểm để thiết kế và điều chỉnh lộ trình mạng lưới xe buýt, metro tối ưu.

Kiến trúc sư giải pháp dữ liệu lớn và điện toán đám mây: Học hỏi kinh nghiệm kết hợp các hệ cơ sở dữ liệu phi quan hệ, mô hình lưu trữ đám mây Google App Engine và các thuật toán tối ưu hóa truy vấn đồ thị phức tạp.

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

Cơ sở dữ liệu đối tượng chuyển động khác biệt như thế nào so với cơ sở dữ liệu quan hệ truyền thống? Cơ sở dữ liệu quan hệ truyền thống chỉ lưu trữ các giá trị tĩnh hoặc trạng thái rời rạc tại từng thời điểm cập nhật. Trong khi đó, cơ sở dữ liệu đối tượng chuyển động hỗ trợ các kiểu dữ liệu trừu tượng biến thiên liên tục theo thời gian như điểm chuyển động và vùng chuyển động, cho phép thực thi các câu truy vấn phức tạp về quỹ đạo và không gian đa chiều.

MPoint và MRegion đại diện cho những đối tượng thực tế nào? Điểm chuyển động (MPoint) đại diện cho các đối tượng chỉ thay đổi vị trí tọa độ theo thời gian như ô tô, máy bay, tàu thủy hoặc người dùng điện thoại thông minh. Vùng chuyển động (MRegion) biểu diễn các thực thể biến đổi liên tục cả về vị trí lẫn kích thước diện mạo như tâm bão, đám cháy rừng, vệt dầu loang trên biển hoặc vùng lây lan của dịch bệnh.

Tại sao bộ tối ưu hóa truy vấn của hệ thống Secondo lại được viết bằng ngôn ngữ Prolog? Ngôn ngữ Prolog có thế mạnh vượt trội về so khớp mẫu và cơ chế tìm kiếm suy diễn trên cây cú pháp. Việc sử dụng Prolog giúp xây dựng các quy tắc tối ưu hóa truy vấn liên kết nhanh hơn rất nhiều so với C++, cho phép lập kế hoạch thực thi tối ưu với độ trễ cực thấp cho các câu truy vấn có tới 9 thuộc tính liên kết.

Thuật toán đồ thị thứ tự vị từ giải quyết vấn đề gì trong tối ưu hóa truy vấn? Thuật toán chuyển bài toán tìm thứ tự lọc vị từ tối ưu thành bài toán tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị định hướng có trọng số. Bằng cách áp dụng thuật toán Dijkstra trên không gian đồ thị đệ quy, hệ thống sẽ xác định được lộ trình đánh giá vị từ có chi phí tính toán thấp nhất và kích thước dữ liệu trung gian nhỏ nhất.

Dữ liệu GPS từ điện thoại thông minh được xử lý và đưa vào hệ thống Secondo như thế nào? Thiết bị di động thu nhận tọa độ không gian và mốc thời gian từ mạng lưới vệ tinh GPS, sau đó đóng gói thành các chuỗi dữ liệu hành trình. Dữ liệu này được truyền qua giao thức mạng lên máy chủ Ubuntu, được định dạng thành các bộ giá trị đại số vị trí suy rộng và lưu trữ vào các bảng quan hệ của Secondo để phục vụ truy vấn.

Kết luận

Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về cơ sở dữ liệu đối tượng chuyển động, các kiểu dữ liệu không gian - thời gian và kiến trúc đại số của hệ thống nguồn mở Secondo.

Tác giả đã làm rõ cấu trúc đa tầng của Secondo và triển khai thành công thuật toán tối ưu hóa truy vấn dựa trên đồ thị thứ tự vị từ kết hợp giải thuật Dijkstra.

Nghiên cứu đã xây dựng hoàn chỉnh mô hình quản lý dữ liệu chuyển động đa môi trường, tích hợp dữ liệu GPS di động và công nghệ điện toán đám mây Google App Engine.

Thử nghiệm thực tế trên hệ điều hành Ubuntu 14 khẳng định tính khả thi và độ chính xác cao của hệ thống trong việc xác định vị trí, theo dõi hành trình và tối ưu hóa thời gian đáp ứng câu hỏi truy vấn.

Hệ thống mở ra hướng phát triển quan trọng cho việc khai phá tri thức từ dữ liệu quỹ đạo di chuyển phục vụ quản lý giao thông và giám sát đô thị thông minh trong lộ trình 12 đến 24 tháng tới.

Hãy khai thác và ứng dụng ngay các giải pháp kiến trúc cơ sở dữ liệu đối tượng chuyển động này để nâng tầm hiệu năng cho các nền tảng dịch vụ định vị thế hệ mới!

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

i MỤC LỤC LỜI CAM ĐOAN .iii LỜI CẢM ƠN. iv DANH MỤC TỪ VIẾT TẮT. TỔNG QUAN VỀ CSDL ĐỐI TƯỢNG CHUYỂN ĐỘNG VÀ CÁC CÔNG CỤ PHÁT TRIỂN. Cơ sở dữ liệu.

Định nghĩa cơ sở dữ liệu. Ưu điểm của việc sử dụng CSDL. Tổ chức CSDL. Hệ quản trị cơ sở dữ liệu.

Cơ sở dữ liệu đối tượng chuyển động. Điểm chuyển động. Vùng chuyển động. Đặc tính của các đối tượng chuyển động.

Mô hình dữ liệu khái quát cho đối tượng chuyển động. Công nghệ khai phá dữ liệu. Cơ sở dữ liệu không gian. Mô phỏng khái niệm không gian.

Mở rộng mô hình dữ liệu và ngôn ngữ truy vấn. Cơ sở dữ liệu thời gian. Quản lý thời gian trong cơ sở dữ liệu dạng chuẩn. Miền thời gian.

Dịch vụ công nghệ điện toán đám mây Google App Engine (GAE). Tổng quan về điện toán đám mây. Google App Engine (GAE). Hệ thống định vị toàn cầu GPS - Global Positioning System.

Phần không gian:. Phần kiểm soát:. Phần sử dụng:. 29 ii Chương 2.

HỆ THỐNG LƯU TRỮ CSDL ĐỐI TƯỢNG CHUYỂN ĐỘNG. Tổng quan về hệ thống lưu trữ CSDL đối tượng chuyển động. Hệ thống lưu trữ CSDL đối tượng chuyển động Secondo. Quản lý dữ liệu đối tượng chuyển động:.

Truy vấn dữ liệu. Thuật toán tối ưu hóa: Tìm đường đi ngắn nhất của một đồ thị thứ tự vị từ (predicate order graph - POG). THIẾT KẾ VÀ THỬ NGHIỆM TRÊN HỆ THỐNG LƯU TRỮ DỮ LIỆU CHUYỂN ĐỘNG. Giới thiệu bài toán.

Cấu trúc chương trình. Phân tích hệ thống. Mô hình hoạt động. Cài đặt và cấu hình Secondo.

Cài đặt Secondo trên Ubuntu 14. Cấu hình Secondo lần đầu trong Hệ điều hành Ubuntu 14. Giao diện hệ thống Secondo. Thao tác trên Secondo.

Thao tác trên thiết bị được thử nghiệm. 60 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN. 61 TÀI LIỆU THAM KHẢO. 64 iii LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung quyển luận văn này là do tôi tự sưu tầm, tra cứu và xây dựng đáp ứng nội dung yêu cầu của đề tài.

Nội dung bản luận văn chưa từng được công bố hay xuất bản dưới bất kỳ hình thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên cứu nào. Phần mã nguồn của chương trình do tôi thiết kế và xây dựng, trong đó có sử dụng một số thư viện chuẩn và các thuật toán được các tác giả xuất bản công khai và miễn phí trên mạng Internet. Nếu sai tôi xin hoàn toàn chịu trách nhiệm. Thái Nguyên, tháng 08 năm 2015 Tác giả Lương Văn Nhất iv LỜI CẢM ƠN Sau một thời gian tìm hiểu và nghiên cứu, luận văn “Nghiên cứu cơ sở dữ liệu đối tượng chuyển động và ứng dụng” đã hoàn thành.

Ngoài sự cố gắng của bản thân, tôi đã nhận được nhiều sự khích lệ từ phía nhà trường, thầy cô, gia đình và bạn bè. Lời đầu tiên em xin bày tỏ lòng biết ơn sâu sắc đến thầy giáo - TS. Nguyễn Như Sơn – Viện Công nghệ thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam là giáo viên hướng dẫn tôi đã tận tình giúp đỡ trong suốt thời gian làm luận văn. Em xin chân thành cảm ơn các thầy, cô đã luôn nhiệt tình giúp đỡ, truyền đạt những kiến thức và kinh nghiệm quý báu trong suốt quá trình học tập.

Xin chân thành cảm ơn các anh, các chị và các bạn học viên học cùng lớp Cao học K11I đã luôn động viên, giúp đỡ và chia sẻ với tôi những kinh nghiệm học tập trong suốt khoá học. Tôi xin chân thành cảm ơn Ban giám hiệu trường THCS Ninh Nhất, các thầy cô giáo trong trường đã tạo điều kiện tốt nhất để tôi có thể hoàn thành khoá học này. Mặc dù đã có nhiều cố gắng, song do điều kiện nghiên cứu và trình độ, luận văn không tránh khỏi những khiếm khuyết. Em chân thành mong nhận được sự đóng góp ý kiến của các thầy, cô giáo và bạn bè đồng nghiệp gần xa.

Một lần nữa em xin cảm ơn! Người thực hiện luận văn Lương Văn Nhất v DANH MỤC TỪ VIẾT TẮT - API Application Programming Interface - CSDL Cơ sở dữ liệu - DBMS Database Management System - GAE Google App Engine - GPS Global Position System - JVM Java Virtual Machine - KTG Không gian-thời gian (Spatio-temporal) - LBS Location-based service - MOD Moving Objects Databases - GUI Graphic User Interface vi DANH MỤC HÌNH Hình 1. Kiểu dữ liệu không gian (point, line, region).2: Điểm thay đổi rời rạc (trái) - Điểm thay đổi liên tục (phải).3: Trình diễn rời rạc của một điểm chuyển động. Vùng thay đổi rời rạc (trái) - Vùng thay đổi liên tục (phải). Công nghệ khai phá dữ liệu từ MOD.

Điểm, đường và vùng. Kiến trúc hoạt động của GAE.10: Phân bố các vệ tinh GPS. Kiến trúc hệ thống Secondo. Kiến trúc thô của nhân trong hệ thống Secondo.3 Mô hình quản lý dữ liệu chuyển động.

Đồ thị POG với ba vị từ p, q, r. Hình xây dựng đệ quy của đồ thị POG. Hai truy vấn đồ thị. Mô hình bài toán tìm kiếm.

Mô hình hoạt động của ứng dụng. Một số lệnh khởi tạo hệ thống Secondo. Giao diện hệ thống Secondo. Thực thi lệnh ifconfig trên Ubuntu.

Giao diện chính. Giao diện theo dõi hành trình của thiết bị. Giao diện truy vấn thông tin địa điểm. Kết quả truy vấn.

Kết quả tìm đường đi. Lý do chọn đề tài: Gần đây, các nhà nghiên cứu bắt đầu khám phá lĩnh vực về chuyển động của các đối tượng như nhiều phương tiện giao thông, điện thoại di động, … Một số công việc (ví dụ, Geolife trong dự án Microsoft) sẽ cố gắng để phát hiện phương tiện giao thông ngoài trời, người sử dụng điện thoại di động, … từ dữ liệu GPS để nắm bắt vị trí và đường đi của chúng. Vấn đề này thuộc xu hướng xây dựng các hệ thống CSDL qui mô cực lớn liên quan tới các thông tin thời gian và không gian đang được triển khai mạnh mẽ trên thế giới. Ví dụ cụ thể là các CSDL của đối tượng chuyển động (Moving Object Database - MOD), một dạng của CSDL không gian-thời gian (spatio-temporal - KTG).

Đề tài: “Nghiên cứu cơ sở dữ liệu đối tượng chuyển động và ứng dụng” tập trung tìm hiểu những khái niệm cơ bản về công nghệ CSDL đối tượng chuyển động dựa theo mã nguồn mở Secondo và ứng dụng xây dựng chương trình tìm kiếm địa điểm dựa trên việc xác định vị trí và đường đi của người sử dụng điện thoại di động. Đối tượng và phạm vi nghiên cứu của đề tài:  CSDL đối tượng chuyển động [6];  Công nghệ CSDL MOD dựa theo mã nguồn mở Secondo [11];  Công nghệ điện toán đám mây của Google [9];  Dữ liệu GPS của thiết bị Smartphone. Hướng nghiên cứu của đề tài:  Nghiên cứu cơ sở khoa học, công nghệ CSDL đối tượng chuyển động dựa theo mã nguồn mở Secondo 2  Lưu trữ dữ liệu GPS của thiết bị Smartphone lên máy chủ CSDL Secondo  Cài đặt ứng dụng demo “Xác định vị trí và đường đi của thiết bị Smartphone” 4. Phương pháp nghiên cứu:  Nghiên cứu cơ sở khoa học, công nghệ về CSDL đối tượng chuyển động dựa theo mã nguồn mở Secondo;  Tìm hiểu nguồn thông tin từ các bài báo, Internet, …  Phương pháp thực nghiệm.

TỔNG QUAN VỀ CSDL ĐỐI TƯỢNG CHUYỂN ĐỘNG VÀ CÁC CÔNG CỤ PHÁT TRIỂN 1. Cơ sở dữ liệu. Định nghĩa cơ sở dữ liệu Cơ sở dữ liệu là tập hợp các dữ liệu có liên quan với nhau, được lưu trữ trên máy tính, có nhiều người sử dụng và được tổ chức theo một mô hình. Dữ liệu là những sự kiện có thể ghi lại được và có ý nghĩa.

Ví dụ như: - Họ và tên: Lương Văn Nhất. - Địa chỉ: Xã Quỳnh Lưu, huyện Nho Quan, tỉnh Ninh Bình. - Tên cơ quan: Trường THCS Ninh Nhất. Tất cả các CSDL đều có thể được biểu diễn bởi hệ thống các thực thể, thuộc tính và mối quan hệ giữa các thực thể.

Ưu điểm của việc sử dụng CSDL Từ khái niệm trên, ta thấy rõ ưu điểm nổi bật của CSDL là:  Giảm sự trùng lặp thông tin xuống mức thấp nhất và do đó đảm bảo được tính nhất quán và toàn vẹn dữ liệu.  Đảm bảo sự độc lập giữa dữ liệu và chương trình ứng dụng: Cho phép thay đổi cấu trúc, dữ liệu trong cơ sở dữ liệu mà không cần thay đổi chương trình ứng dụng.  Trừu tượng hoá dữ liệu (Data Abstraction): Mô hình dữ liệu được sử dụng để làm ẩn lưu trữ vật lý chi tiết của dữ liệu, chỉ biểu diễn cho người sử dụng mức khái niệm của cơ sở dữ liệu.  Nhiều khung nhìn (multi-view) cho các đối tượng người dùng khác nhau: Đảm bảo dữ liệu có thể được truy xuất theo nhiều cách khác 4 nhau.

Vì yêu cầu của mỗi đối tượng sử dụng CSDL là khác nhau nên tạo ra nhiều khung nhìn vào dữ liệu là cần thiết.  Đa người dùng (multi-user): Khả năng chia sẻ thông tin cho nhiều người sử dụng và nhiều ứng dụng khác nhau [2]. Tổ chức CSDL CSDL được tổ chức có cấu trúc: Thành các bản ghi (record), các trường dữ liệu (field). Các dữ liệu lưu trữ có mối quan hệ (relational) với nhau.

CSDL được cấu trúc để dễ dàng truy cập, quản lý và cập nhật dữ liệu.  Table (Bảng): Là một thành phần cơ bản trong chương trình quản trị cơ sở dữ liệu quan hệ. Bảng được hình thành khi sắp xếp các thông tin có liên quan với nhau theo hàng và cột. Các hàng tương ứng với các bản ghi (record) dữ liệu và các cột tương ứng với trường dữ liệu.

Các bạn hãy xem bảng Người quen. Các hàng là người, mỗi hàng tương ứng với một người. Các cột là trường (hay lĩnh vực) của thông tin.  Record (bản ghi): Trong chương trình quản trị cơ sở dữ liệu, đây là một đơn vị hoàn chỉnh nhỏ nhất của dữ liệu, được lưu trữ trong những trường hợp dữ liệu đã được đặt tên.

Trong một cơ sở dữ liệu dạng bảng, bản ghi dữ liệu đồng nghĩa với hàng (row). Bản ghi chứa tất cả các thông tin có liên quan với mẫu tin mà cơ sở dữ liệu đang theo dõi. Ví dụ, trong cơ sở dữ liệu về Người quen, bản ghi sẽ liệt kê tên người quen, ngày sinh, số điện thoại, địa chỉ và tên cơ quan. Hầu hết các chương trình đều hiển thị các bản ghi dữ liệu theo hai cách: theo các mẫu nhập dữ liệu và theo các bảng dữ liệu.