Báo cáo Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian

Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian . Bài báo này đề cập đến khái niệm và một số phương pháp đánh chỉ mục trong cơ sở dữ liệu không gian (spatial datadase – SDB). Là một trong những mô hình cơ sở dữ liệu được quan tâm hiện nay, SDB cho phép xử lý các đối tượng dữ liệu không gian. Một trong những bài toán cơ bản của SBD chính là việc tối ưu hóa quá trình dữ liệu và truy vấn...
Nội dung trích xuất từ tài liệu:
Báo cáo " Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian "Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 ng d ng cây QR t o ch m c trong cơ s d li u không gian Dư Phương H nh* Trư ng ð i h c Công ngh , ð i h c Qu c gia Hà N i, 144 Xuan Th y, Hà N i, Vi t Nam Nh n ngày 7 tháng 01 năm 2011 Tóm t t. Bài báo này ñ c p ñ n khái ni m và m t s phương pháp ñánh ch m c trong cơ s d li u không gian (spatial datadase – SDB). Là m t trong nh ng mô hình cơ s d li u ñư c quan tâm hi n nay, SDB cho phép 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... ñ t ñó có th xây d ng nên nh n g kho d li u không gian. M t trong nh n g bài toán cơ b n trong SDB chính là vi c t i ưu hoá quá trình lưu tr d li u và truy v n. Trong bài báo này, chúng tôi s trình bày v hai ph ương pháp ñánh ch m c ñi n hình liên quan ñ n v n ñ ñánh ch m c gi i bài toán trên, R-tree và Q-tree. T ñó, ý tư ng k t h p hai phương pháp này s chính là ñ nh hư ng ch ñ o cho vi c t i ưu hoá lưu tr d li u cũng như truy v n trên cơ s d li u không gian. T khóa: Spatial database, spatial indexing, R-tree, Q-tree, QR-Tree. Warehouse (SDW). Các nghiên c u trên lĩnh1. Gi i thi u∗ v c này ñã thu ñ ư c r t nhi u thành t u, tuy Các nghiên c u v công ngh cũng như ng nhiên cũng còn không ít khó khăn và thách th cd ng trong lĩnh v c cơ s d li u (CSDL) ñang ñòi h i ph i có các gi i pháp m i.tăng trư ng v i m t s c m nh ñ áng kinh ng c. Bài báo này trình bày m t phương phápCùng v i s tăng trư ng nhanh chóng c a ñánh ch m c trên SDB, là s k t h p gi a hailư ng thông tin cũng như s ñ a d ng v th lo i phương pháp ñánh ch m c ph bi n là Q-treethông tin c n lưu tr và x lý, chúng ta ngày và R-tree, k t h p các ưu ñi m c a c haicàng nh n ra nh ng h n ch c a các H qu n tr phương pháp này cũng như gi m thi u như ccơ s d li u quan h truy n th ng, và nhu c u ñi m c a chúng, nh m tăng hi u su t th c thic n ph i có các h q u n tr cơ s d li u v i các các phép toán.d ch v phù h p chính là y u t t húc ñ y nh ngnghiên c u m i trong lĩnh v c này. M t trongcác mô hình cơ s d li u ñư c quan tâm nh t 2. Khái ni m cơ b nhi n nay chính là mô hình cơ s d li u không Ph n này s ñư c t p trung trình bày nh nggian - Spatial DataBase (SDB) x lý các ñ i khái ni m cơ b n liên quan ñ n mô hình SDB.tư ng d li u không gian, ch ng h n d li ub n ñ , d li u multimedia... và m r ng hơn 2.1. D li u không giann a là kho d li u không gian - Spatial Data Thu t ng d li u không gian (spatial data)_______ ñư c s d ng theo nghĩa r ng, bao g m các∗ ð T: 84-4-37547813. E-mail: hanhdp@vnu.edu.vn 14 15 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21ñi m ña chi u, các ñư ng th ng, hình kh i... và h p c a các ñ o n th ng; qu c gia, thành ph cócác ñ i tư ng hình h c nói chung. M i ñ i th ñư c bi u di n dư i d ng các hình ña giác...tư ng d li u này chi m m t vùng không gian(spatial extent) ñư c ñ c trưng b i hai thu c 2.2. Các phương pháp truy v n ph bi n trêntính v trí (location) và biên (boundary). Dư i d li u không giangóc nhìn t m t h qu n tr cơ s d li u, có th a) Truy v n theo ph m vi không gianphân chia d li u không gian thành hai ki u: d (Spatial range queries):li u ñi m (point data) và d li u vùng (regiondata) [1] Gi s chúng ta có yêu c u truy v n “ðưa ra tên t t c các thàn ...