Khóa luận Tìm kiếm ứng dụng phần mềm mã nguồn mở hệ quản trị cơ sở dữ liệu hướng đối tượng Perst xây dựng ứng dụng quản lý hệ thống thông tin địa lý thành phố Hồ Chí Minh

SV ne t.vn TRѬӠNG ĈҤI HӐC KHOA HӐC TӴ NHIÊN KHOA CÔNG NGHӊ THÔNG TIN %Ӝ MÔN CÔNG NGHӊ PHҪN MӄM e&f NGUYӈN THӎ LÝ - NGUYӈN SAO Kǣ ӬNG DӨNG PHҪN MӄM Mà NGUӖN MӢ Hӊ QUҦN TRӎ CѪ SӢ DӲ LIӊU HѬӞNG ĈӔI TѬӦNG PERST XÂY DӴNG ӬNG DӨNG QUҦN LÝ Hӊ THӔNG THÔNG TIN ĈӎA LÝ THÀNH PHӔ HCM KHÓA LUҰN CӰ NHÂN TIN HӐC TpHCM, 2005 SV ne t.vn - 2 - TRѬӠNG ĈҤI HӐC KHOA HӐC TӴ NHIÊN KHOA CÔNG NGHӊ THÔNG TIN %Ӝ MÔN CÔNG NGHӊ PHҪN MӄM e&f NGUYӈN THӎ LÝ - 0112187 NGUYӈN SAO Kǣ- 0112186 ӬNG DӨNG PHҪN MӄM Mà NGUӖN MӢ Hӊ QUҦN TRӎ CѪ SӢ DӲ LIӊU HѬӞNG ĈӔI TѬӦNG PERST XÂY DӴNG ӬNG DӨNG QUҦN LÝ Hӊ THӔNG THÔNG TIN ĈӎA LÝ THÀNH PHӔ HCM KHÓA LUҰN CӰ NHÂN TIN HӐC GIÁO VIÊN HѬӞNG DҮN Th.s NGUYӈN MINH NAM NIÊN KHOÁ 2001-2005 SV ne t.vn - 3 - /ӠI CҦM ѪN Chúng em chân thành cám ѫn Khoa Công nghӋ Thông tin, trѭӡng Ĉҥi hӑc Khoa hӑc Tӵ nhiên tҥo ÿLӅu kiӋn cho chúng em thӵc hiӋn ÿӅ tài luұn văn tӕt nghiӋp này. Chúng em chân thành cám ѫn thҫy NguyӉn Minh Nam ÿã tұn tình hѭӟng Gүn, chӍ bҧo chúng em trong suӕt thӡi gian thӵc hiӋn ÿӅ tài. Chúng em chân thành cám ѫn quý thҫy cô trong khoa ÿã tұn tình giҧng Gҥy, trang bӏ cho chúng em nhӳng kiӃn thӭc quý báu trong nhӳng năm hӑc Yӯa qua. Chúng con xin nói lên lòng biӃt ѫn sâu sҳc ÿӕi vӟi cha mҽ, nhӳng ngѭӡi ÿã chăm sóc, nuôi dҥy chúng con thành ngѭӡi và luôn ÿӝng viên tinh thҫn cho chúng con. Và cNJng chân thành cám ѫn các anh chӏ và bҥn bè ÿã ӫng hӝ, giúp ÿӥ, trao ÿәi kiӃn thӭc, kinh nghiӋm và ÿӝng viên chúng em trong thӡi gian hӑc tұp và nghiên cӭu. 0һc dù chúng em ÿã cӕ gҳng hoàn thành luұn văn trong phҥm vi và khҧ Qăng cho phép nhѭng chҳc chҳn sӁ không tránh khӓi nhӳng sai sót. Chúng em kính mong nhұn ÿѭӧc sӵ cҧm thông và tұn tình chӍ bҧo cӫa quý thҫy cô và các bҥn. Tp.Hӗ Chí Minh, tháng 7 năm 2005 NguyӉn Thӏ Lý – 0112187 NguyӉn Sao KǤ - 0112186 SV ne t.vn - 4 - TÓM TҲT LUҰN VĂN Luұn văn ÿѭӧc tә chӭc thành các phҫn chính nhѭ sau: Chѭѫng 1: Giӟi thiӋu tҫm quan trӑng, mөc tiêu, phҥm vi cӫa ÿӅ tài, các cѫ sӣ lý thuyӃt và hѭӟng tiӃp cұn. Chѭѫng 2: Cách tә chӭc cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng PERST và nhӳng so sánh vӟi các cách tә chӭc cѫ sӣ dӳ liӋu quan hӋ và các hӋ cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng khác. Chѭѫng 3: Giӟi thiӋu vӅ mô hình Topology: nêu lên nhӳng khái niӋm cѫ bҧn, các ÿӕi tѭӧng trong Topology và các cҩp Topology. Chѭѫng 4: Giӟi thiӋu vӅ GIS: giӟi thiӋu tәng quan vӅ GIS, các giҧi pháp và ӭng Gөng vӅ GIS và ӭng dөng GIS trên PocketPC Chѭѫng 5: Giӟi thiӋu vӅ chuҭn OpenGIS Chѭѫng 6: Tәng quan vӅ PocketPC: Các vҩn ÿӅ và giҧi pháp trên thiӃt bӏ. Tình trҥng bӝ nhӟ, tҥo cѫ sӣ dӳ liӋu và ӭng dөng bҧn ÿӗ trên PocketPC. Chѭѫng 7: Ӭng dөng bҧn ÿӗ: mô hình phân tích thiӃt kӃ. Chѭѫng 8: KӃt luұn, ÿánh giá và hѭӟng phát triӇn Chѭѫng 9: Nhӳng tài liӋu tham khҧo khi thӵc hiӋn ÿӅ tài Chѭѫng 10:Nêu nhӳng thuұt toán chính trong chѭѫng trình SV ne t.vn - 5 - 0ӨC LӨC /ӠI CҦM ѪN ........................................................................................................................ 3 TÓM TҲT LUҰN VĂN......................................................................................................... 4 DANH SÁCH CÁC HÌNH..................................................................................................... 8 DANH SÁCH CÁC BҦNG...................................................................................................10 0ӜT SӔ KHÁI NIӊM, THUҰT NGӲ VÀ TӮ VIӂT TҲT ..................................................11 CHѬѪNG 1 : HiӋn trҥng và yêu cҫu .................................................................................15 1.1 HiӋn trҥng: .................................................................................................................15 1.2 Giҧi quyӃt bài toán: ....................................................................................................16 CHѬѪNG 2 : Tәng quan vӅ Perst .....................................................................................17 2.1 Giӟi thiӋu: ..................................................................................................................17 2.2 Ĉһc tính:.....................................................................................................................18 2.2.1 Persistency by reachability:....................................................................................18 2.2.2 Semi transparent object loading: ............................................................................21 2.2.3 Automatic scheme evaluation.................................................................................23 2.2.4 Relation: ................................................................................................................24 2.2.5 Index: ....................................................................................................................25 2.2.6 Giao tác (Transaction):...........................................................................................29 2.3 Transparent API: ........................................................................................................31 2.3.1 Dùng.NET Remoting API: .....................................................................................31 2.3.2 Dùng các thuӝc tính ҧo (virtual properties):............................................................32 2.4 Cѫ chӃ thӵc hiӋn giao tác (Transaction):.....................................................................33 2.5 Nhӳng trѭӡng hӧp nên dùng PERST: .........................................................................37 2.6 Các thông sӕ cӫa PERST:...........................................................................................38 2.7 Sѫ lѭӧc vӅ RTree:.......................................................................................................44 2.7.1 Giӟi thiӋu:..............................................................................................................44 2.7.2 Sѫ lѭӧc vӅ dӳ liӋu không gian (spatial data) và các giҧi pháp: ................................44 2.8 So sánh vӟi các hӋ quҧn trӏ cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng khác: ................................45 CHѬѪNG 3 : Giӟi thiӋu vӅ mô hình Topology.................................................................50 3.1 Giӟi thiӋu: ..................................................................................................................50 3.2 Các khái niӋm cѫ bҧn trong Topology: .......................................................................50 3.3 Các loҥi ÿӕi tѭӧng trong Topology: ............................................................................51 3.4 Các cҩp cӫa Topology: ...............................................................................................53 SV ne t.vn - 6 - 3.5 MBR – Minimum Bounding Rectangle: .....................................................................59 CHѬѪNG 4 : Giӟi thiӋu vӅ GIS .......................................................................................60 4.1 Giӟi thiӋu vӅ các ӭng dөng và giҧi pháp vӅ GIS: ........................................................60 4.2 Mô hình dӳ liӋu cӫa thông tin ÿӏa lý: ..........................................................................61 4.3 Thu thұp dӳ liӋu: ........................................................................................................64 4.4 Các giҧi thuұt nghiên cӭu vӅ GIS: ..............................................................................66 4.5 Các cҩu trúc dӳ liӋu không gian trong GIS: ................................................................67 4.5.1 Cây tӭ phân (Quad Tree):.......................................................................................67 4.5.2 k-d Tree: ................................................................................................................68 4.5.3 R-Tree: ..................................................................................................................69 4.5.4 R*-Tree: ................................................................................................................70 4.5.5 R+-Tree:.................................................................................................................71 4.6 Ӭng dөng bҧn ÿӗ: .......................................................................................................72 4.6.1 Các kiӇu bҧn ÿӗ: ....................................................................................................72 4.6.2 Các ÿӕi tѭӧng cӫa bҧn ÿӗ:......................................................................................72 4.7 Ӭng dөng GIS trên PocketPC:....................................................................................73 CHѬѪNG 5 : Giӟi thiӋu vӅ chuҭn OpenGIS .....................................................................75 5.1 Các kiӇu dӳ liӋu hình hӑc cӫa OpenGIS: ....................................................................75 5.2 OpenGIS Specification (ÿһc tҧ OpenGIS):..................................................................76 5.2.1 Các khái niӋm: .......................................................................................................76 5.2.2 Nhӳng dӏch vө OpenGIS (OpenGIS Services ):......................................................78 5.2.3 Mӝt mô hình nhӳng cӝng ÿӗng thông tin (Information Communities Model ): .......79 5.2.4 Ĉһc ÿLӇm: ..............................................................................................................79 5.2.5 Phân loҥi: ...............................................................................................................81 5.3 OpenGIS Abstract Specification: ................................................................................82 5.3.1 Essential Model (mô hình bҧn chҩt ): .....................................................................83 5.3.2 Abstract Model: .....................................................................................................85 CHѬѪNG 6 : Tәng quan vӅ PocketPC .............................................................................89 6.1 Tәng quan vӅ PocketPC: ............................................................................................89 6.2 Khҧ năng lұp trình trên PocketPC:..............................................................................89 6.3 Mӝt sӕ vҩn ÿӅ khi lұp trình ӭng dөng trên PocketPC: .................................................89 6.3.1 Tӕc ÿӝ và các hӛ trӧ khҧ năng hiӇn thӏ: ..................................................................89 6.3.2 Khҧ năng và hình thӭc lѭu trӳ:...............................................................................90 6.3.3 Tѭѫng tác giӳa ngѭӡi sӱ dөng và thiӃt bӏ: ..............................................................91 6.4 Các giҧi pháp cho ӭng dөng bҧn ÿӗ trên PocketPC: ....................................................92 6.4.1 Yêu cҫu chung: ......................................................................................................92 SV ne t.vn - 7 - 6.4.2 Vҩn ÿӅ tӕi ѭu tӕc ÿӝ hiӇn thӏ: .................................................................................93 6.5 Tә chӭc dӳ liӋu bҧn ÿӗ trên PocketPC:.......................................................................93 CHѬѪNG 7 : Ӭng dөng bҧn ÿӗ: .......................................................................................95 7.1 Phân tích và xác ÿӏnh yêu cҫu:....................................................................................95 7.2 Phân tích - thiӃt kӃ:.....................................................................................................96 7.2.1 Sѫÿӗ sӱ dөng: .......................................................................................................96 7.2.2 Ĉһc tҧ Use-Case chính: ..........................................................................................97 7.2.2.1 Tìm kiӃm ÿѭӡng ÿi: ...............................................................................................97 7.2.2.2 Tìm kiӃm Region: ..................................................................................................98 7.2.2.3 Tìm ÿѭӡng ÿi ngҳn nhҩt: ........................................................................................99 7.2.2.4 Tìm chu trình tӕi ѭu: ............................................................................................101 7.2.3 Sѫÿӗ lӟp Class Diagram:.....................................................................................102 7.2.3.1 Sѫÿӗ tәng quát:...................................................................................................102 7.2.3.2 Sѫÿӗ lӟp dӳ liӋu:.................................................................................................103 7.2.3.3 Sѫÿӗ lӟp vӁ:........................................................................................................103 7.2.3.4 Sѫÿӗ sӵ kiӋn: ......................................................................................................104 7.2.4 Mô tҧ các lӟp: ......................................................................................................104 7.2.5 Các lѭu ÿӗ hoҥt ÿӝng: ..........................................................................................111 7.3 ThiӃt kӃ giao diӋn: ....................................................................................................124 7.3.1 Giao diӋn trên Desktop: .......................................................................................124 7.3.2 Giao diӋn trên PocketPC: .....................................................................................131 7.4 Cài ÿһt:.....................................................................................................................131 CHѬѪNG 8 : KӃt Luұn, Ĉánh giá và hѭӟng phát triӇn ...................................................132 8.1 KӃt luұn, ÿánh giá:....................................................................................................132 8.2 Hѭӟng phát triӇn: .....................................................................................................132 CHѬѪNG 9 : Tài liӋu tham khҧo....................................................................................133 CHѬѪNG 10 : Phө lөc .................................................................................................134 10.1 Bài toán tìm ÿѭӡng ÿi ngҳn nhҩt giӳa hai ÿLӇm:........................................................134 10.1.1 Phát biӇu bài toán:................................................................................................134 10.1.2 Giҧi quyӃt bài toán:..............................................................................................134 10.2 Bài toán tìm chu trình tӕi ѭu .....................................................................................136 10.2.1 Phát biӇu bài toán.................................................................................................136 10.2.2 Giҧi quyӃt bài toán:..............................................................................................137 SV ne t.vn - 8 - DANH SÁCH CÁC HÌNH Hình 3.2-1 Các ÿӕi tѭӧng trong mô hình Topology...............................................................51 Hình 3.4-1 Quan hӋ Topology cҩp 0 .....................................................................................56 Hình 3.4-2 Quan hӋ Topology cҩp 1 và 2..............................................................................57 Hình 3.4-3 Quan hӋ Topology cҩp 3 .....................................................................................58 Hình 4.2-1 Thông tin cҫn lѭu trӳ ..........................................................................................61 Hình 4.2-2 So sánh Raster và Vector ....................................................................................64 Hình 4.3-1 Phѭѫng pháp Scanning .......................................................................................65 Hình 4.5.1-1 Cây tӭ phân .....................................................................................................67 Hình 4.5.2-1 K-D Tree .........................................................................................................68 Hình 4.5.3-1 R-Tree .............................................................................................................69 Hình 4.5.5-1 R+-Tree ...........................................................................................................71 Hình 4.6.2-1 Các ÿӕi tѭӧng chính trong bҧn ÿӗ ....................................................................73 Hình 5.1-1 HӋ phân cҩp các kiӇu dӳ liӋu hình hӑc cӫa OpenGIS. .........................................76 Hình 5.3.1-1 Lӟp khái niӋm..................................................................................................85 Hình 7.2.1-1 Sѫÿӗ sӱ dөng tәng quát...................................................................................96 Hình 7.2.2.1-1 Use Case - Tìm kiӃm Edge............................................................................97 Hình 7.2.2.2-1 Use Case: Tìm kiӃm Region..........................................................................98 Hình 7.2.2.3-1 Use Case – Tìm ÿѭӡng ÿi ngҳn nhҩt ..............................................................99 Hình 7.2.2.4-1 Use-Case - Tim chu trình tӕi ѭu ..................................................................101 Hình 7.2.3.1-1 Sѫÿӗ tәng quát ...........................................................................................102 Hình 7.2.3.2-1 Sѫ lӟp dӳ liӋu .............................................................................................103 Hình 7.2.3.3-1 Sѫÿӗ lӟp vӁ ................................................................................................103 Hình 7.2.3.4-1 Sѫÿӗ sӵ kiӋn ..............................................................................................104 Hình 7.2.4-1 Lӟp CNode ....................................................................................................106 Hình 7.2.4-2 Lӟp CEdge ....................................................................................................109 Hình 7.2.5-1 Sequense Diagram: HiӇn thӏ bҧn ÿӗ ...............................................................112 Hình 7.2.5-2 Collabration Diagram: HiӇn thӏ bҧn ÿӗ...........................................................113 Hình 7.2.5-3 Sequence Diagram: Tìm ÿѭӡng ngҳn nhҩt ......................................................113 Hình 7.2.5-4 Collabration Diagram: Tìm ÿѭӡng ngҳn nhҩt .................................................114 Hình 7.2.5-5 Sequence Diagram: Tìm Edge........................................................................115 Hình 7.2.5-6 Collabration Diagram: Tìm Edge ...................................................................116 Hình 7.2.5-7 Sequence Diagram: Tìm chu trình tӕi ѭu ........................................................117 Hình 7.2.5-8 Collabrotion Diagram: Tìm chu trình tӕi ѭu ...................................................118 Hình 7.2.5-9 Sequence Diagram: Dӏch chuyӇn vùng nhìn ...................................................119 SV ne t.vn - 9 - Hình 7.2.5-10 Collabrotion Diagram: Di chuyӇn vùng nhìn ................................................120 Hình 7.2.5-11 Sequence Diagram: TӍ lӋ lҥi bҧn ÿӗ..............................................................120 Hình 7.2.5-12 Collaboration Diagram: TӍ lӋ lҥi bҧn ÿӗ .......................................................121 Hình 7.2.5-13 Sequence Diagram: Tìm ÿӏa ÿLӇm ................................................................121 Hình 7.2.5-14 Collaboration Diagram: Tìm ÿӏa ÿLӇm..........................................................122 Hình 7.2.5-15 Sequence Diagram: Tìm giao lӝ ...................................................................123 Hình 7.2.5-16 Collaboration Diagram: Tìm giao lӝ.............................................................123 Hình 7.3.1-1 Khung nhìn tәng quát vӅ giao diӋn.................................................................124 Hình 7.3.1-2 Toolbar cӫa chѭѫng trình ...............................................................................124 Hình 7.3.1-3 Các chӭc năng chính trên thanh công cө ........................................................127 Hình 7.3.1-4 Thanh thӵc ÿѫn File .......................................................................................128 Hình 7.3.1-5 Thanh thӵc ÿѫn View.....................................................................................128 Hình 7.3.1-6 Khung nhìn bҧn ÿӗ thu nhӓ ............................................................................130 Hình 7.3.1-7 Khung Layer..................................................................................................130 Hình 7.3.1-8 Khung hiӇn thӏ thông tin ÿӕi tѭӧng.................................................................131 SV ne t.vn - 10 - DANH SÁCH CÁC BҦNG %ҧng 2.2.4-1 Các mӕi quan hӋ giӳa 2 lӟp A va B .................................................................25 %ҧng 2.2.5-1 Các kiӇu Index ÿѭӧc PERST hӛ trӧ: ................................................................29 %ҧng 2.6-1 Hҵng sӕÿѭӧc ÿӏnh nghƭa sҹn trong lӟp StorageImpl...........................................42 %ҧng 2.8-1 So sánh các ÿһc tính cӫa các hӋ quҧn trӏ .............................................................47 %ҧng 2.8-2 Bҧng so sánh kӃt quҧ cӫa các hӋ quҧn trӏ cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng.............49 %ҧng 3.4-1 Các cҩp Topology trong các lӟp VPF .................................................................55 %ҧng 3.4-2 Các cӝt ÿѭӧc yêu cҫu ÿӇÿӏnh nghƭa quan hӋ Topology trong VPF......................56 %ҧng 3.5-1. Ĉӏnh nghƭa khung chӳ nhұt nhӓ nhҩt MBR........................................................59 %ҧng 4.2-1 Bҧng so sánh kiӇu dӳ liӋu Raster va Vector...........................................................64 %ҧng 7.1-1 Các chӭc năng chính ..........................................................................................96 %ҧng 7.2.4-1 Lӟp CDatabase..............................................................................................105 %ҧng 7.2.4-2 Lӟp CMapView.............................................................................................105 %ҧng 7.2.4-3 Lӟp CMapEvent ............................................................................................106 %ҧng 7.2.4-4 Thuӝc tính lӟp CNode ...................................................................................107 %ҧng 7.2.4-5 Phѭѫng thӭc lӟp CNode ...............................................................................108 %ҧng 7.2.4-6 Thuӝc tính lӟp CEdge...................................................................................110 %ҧng 7.2.4-7 Phѭѫng thӭc lӟp CEdge................................................................................111 %ҧng 7.3.1-1 Các chӭc năng chính trên thanh thӵc ÿѫn ......................................................129 SV ne t.vn - 11 - 0ӜT SӔ KHÁI NIӊM, THUҰT NGӲ VÀ TӮ VIӂT TҲT Khái niӋm Ĉӏnh nghƭa Ghi chú OODBMS (Object- Oriented Database Management System) +Ӌ quҧn trӏ cѫ sӣ dӳ liӋu Kѭӟng ÿӕi tѭӧng PERST Là mӝt hӋ quҧn trӏ cѫ sӣ Gӳ liӋu hѭӟng ÿӕi tѭӧng Nhúng - -Embedded Có nghƭa là PERST ÿѭӧc tích hӧp chһt vào chѭѫng trình, gҫn nhѭ khoҧng cách giӳa database và chѭѫng trình rҩt nhӓ, PERST trӵc tiӃp lѭu dӳ liӋu trong các ÿӕi tѭӧng Fӫa chѭѫng trình và không cҫn có nhӳng ÿRҥn mã làm công viӋc chuyӇn Gӳ liӋu tӯ cѫ sӣ dӳ liӋu thành ÿӕi tѭӧng và ngѭӧc Oҥi Topology Là cҩu trúc cho mô hình Pҥng lѭӟi giao thông GIS ( Geography +Ӌ thӕng thông tin ÿӏa SV ne t.vn - 12 - Information System ) lý. Là mӝt công nghӋ Gӵa trên máy tính ÿӇ xây Gӵng bҧn ÿӗ, phân tích và xӱ lý các ÿӕi tѭӧng Wӗn tҥi và các sӵ kiӋn [ҧy ra trên trái ÿҩt. Thông tin không gian Thông tin vӅ nhӳng ÿһc ÿLӇm liên quan ÿӃn hình Gҥng, vӏ trí, quan hӋ cӫa các ÿӕi tѭӧng ÿӏa lý. Bao gӗm hai dҥng: ‡ 'ҥng hình hӑc: mô tҧ các ÿһc ÿLӇm hình dҥng, vӏ trí. Ví Gө nhѭ tӑa ÿӝ cӫa ÿLӇm, ÿѭӡng… ‡ Dҥng Topology: mô tҧ quan hӋ giӳa các ÿӕi tѭӧng hình Kӑc. Ví dө nhѭ nhӳng vùng nào kӅ Yӟi mӝt vùng xác ÿӏnh. Thông tin phi không gian ( thông tin thuӝc tính ) Thông tin vӅ nhӳng ÿһc ÿLӇm liên quan ÿӃn thӕng kê, thông tin sӕ, thông tin ÿһc trѭng gán cho Pӛi thuӝc tính cӫa ÿӕi Ví dө nhѭ tên ÿѭӡng phӕ, dân sӕ… SV ne t.vn - 13 - Wѭӧng PDA ( Personal Digital Assistant ) ThiӃt bӏ ÿLӋn tӱ hӛ trӧ cá nhân, giúp ngѭӡi sӱ Gөng lѭu trӳ các thông tin cá nhân, công viӋc Fҫn thiӃt cNJng nhѭ các phҫn mӅm tӕi thiӇu trên Pӝt thiӃt bӏ nhӓ gӑn Pocket PC Khái niӋm này có thӇ dùng ÿӇ chӍ: + HӋ ÿLӅu hành nhúng Pocket PC do Microsoft phát triӇn Gӵa trên nhân cӫa HӋ ÿLӅu hành Windows CE + Các thiӃt bӏ PDA sӱ dөng hӋÿLӅu hành Pocket PC Edge Ĉӕi tѭӧng cҥnh trong mô hình Topology Trong bài, Edge tѭѫng ÿѭѫng vӟi ÿѭӡng. Khi nhҳc Wӟi Edge, hay ÿѭӡng có thӇ hiӇu nghƭa nhѭ nhau. SV ne t.vn - 14 - Region Ĉӕi tѭӧng vùng ӣ ÿây không ÿӅ cұp ÿӃn quұn huyӋn nhѭng có thӇ hiӇu Region là quұn huyӋn. ID Ĉӏnh danh cӫa ÿӕi tѭӧng Trong bài không nhҳc tӟi tên ÿѭӡng, quұn huyӋn mà chӍ nhҳc tӟi ID vì cѫ sӣ dӳ liӋu không ÿӫ thông tin tên ÿѭӡng. Và khi nhҳc tӟi tên Fӫa ÿӕi tѭӧng bҩt kǤ thì hiӇu là ID. SV ne t.vn - 15 - CHѬѪNG 1 : HiӋn trҥng và yêu cҫu 1.1 HiӋn trҥng: Trên thӃ giӟi hiӋn nay ÿã có nhiӅu phҫn mӅm giҧi quyӃt các bài toán vӅ Eҧn ÿӗ giao thông nhѭ: RouteSmart, BusStops, Arclogistics, Routronic 2000, DynaRoute…Ӣ ViӋt Nam nói riêng cNJng có mӝt sӕ công ty nhѭ DolSoft, Hài Hoà, … ÿã có mӝt sӕ sҧn phҭm vӅ GIS nhѭ Street Finder, SmartMap…. Các Vҧn phҭm trên ÿa phҫn sӱ dөng cѫ sӣ dӳ liӋu ÿѭӧc tә chӭc trên các hӋ quҧn trӏ cѫ sӣ dӳ liӋu quan hӋ hoһc tӵ tҥo. Tuy nhiên vүn có vҩn ÿӅÿѭӧc ÿһt ra: 1.Chi phí cӫa càc hӋ quҧn trӏ cѫ sӣ dӳ liӋu thѭѫng mҥi nӃu có dùng. 2.Sӵ khó khăn và có khi là “rҳc rӕi” trong cách lұp trình giao tiӃp vӟi các Fѫ sӣ dӳ liӋu phӭc tҥp có nhiӅu bҧng, quan hӋ… Thұt ra, hai vҩn ÿӅ trên có thӇÿѭӧc giҧi quyӃt tѭѫng ÿӕi tӕt bҵng cách sӱ Gөng hӋ quҧn trӏ cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng PERST (mã nguӗn mӣ). PERST là mӝt hӋ cѫ sӣ dӳ liӋu tѭѫng ÿӕi nhӓ (so vӟi các hӋ cѫ sӣ dӳ liӋu khác) vӟi phҫn lõi chӍ gӗm khoҧng 5000 dòng mã. Yêu cҫu cҩu hình cӫa PERST tѭѫng ÿӕi thҩp. Hѫn nӳa, PERST cNJng không cҫn ÿӃn “sӵ quҧn trӏ” thѭӡng thҩy ӣ các hӋ cѫ sӣ dӳ liӋu. Mһc dù ÿѫn giҧn nhѭ vұy nhѭng PERST Yүn hӛ trӧÿҫy ÿӫ tính ACID trong viӋc thӵc hiӋn giao tác (transaction) và hӛ trӧ viӋc phөc hӗi (recovery) tѭѫng ÿӕi nhanh khi hӋ thӕng gһp sӵ cӕ. Không chӍ dӯng lҥi ӣÿó mà PERST có hӛ trӧ cҧ viӋc phát triӇn trên môi trѭӡng compact.NET framework nên có khҧ năng phát triӇn ӭng dөng trên các thiӃt bӏ di ÿӝng dùng WinCE hay PocketPC. SV ne t.vn - 16 - Vì vұy, ta có thӇ thҩy viӋc dùng PERST ÿӇ giҧi quyӃt bài toán vӅ quҧn lý KӋ thӕng thông tin ÿӏa lý (GIS) là hoàn toàn khҧ thi. 1.2 Giҧi quyӃt bài toán: 0ӝt trong các yӃu tӕ quan trӑng quyӃt ÿӏnh sӵ thành công hay thҩt bҥi cӫa Pӝt hӋ thӕng thông tin ÿӏa lí là viӋc lӵa chӑn mô hình cҩu trúc dӳ liӋu thích Kӧp, cho phép lѭu trӳ và khai thác thông tin mӝt cách hiӋu quҧ. Và mô hình Topology thӇ hiӋn tӕt nhӳng ÿòi hӓi trên (Mô hình này sӁÿѭӧc ÿӅ cұp sau trong luұn văn). Vì dӳ liӋu Topology trên PERST không có sҹn nên chúng ta Fҫn xây dӵng lҥi dӳ liӋu theo mô hình Topology. Dӳ liӋu thô (dӳ liӋu nguӗn) ÿѭӧc dùng trong ӭng dөng này là các tұp tin text. Bài toán sӁÿѭӧc giҧi quyӃt chӫ yӃu bҵng sӵ phӕi hӧp các kiӃn thӭc vӅ GIS,PERST và ÿӗ hoҥ. SV ne t.vn - 17 - CHѬѪNG 2 : 7әng quan vӅ PERST 2.1 Giӟi thiӋu: PERST là mӝt hӋ cѫ sӣ dӳ liӋu “nhúng” dành cho các ӭng dөng cҫn tính Qăng lѭu trӳ. PERST ÿѭӧc thiӃt kӃ dành riêng cho lұp trình và không có giao diӋn ÿӗ hӑa ÿӇ quҧn trӏ. ViӋc sӱ dөng PERST khá ÿѫn giҧn và ÿҥt ÿѭӧc hiӋu Qăng tѭѫng ÿӕi cao. Ĉһc ÿLӇm chính dӉ thҩy nhҩt cӫa PERST là sӵ tích hӧp chһt chӁ cӫa PERST vӟi mӝt ngôn ngӳ lұp trình xác ÿӏnh. HiӋn tҥi PERST chӍ hӛ trӧ cho 2 ngôn ngӳ lұp trình là Java và C#. Không giӕng vӟi các hӋ quҧn trӏ cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng khác (OODBMSes), PERST không cҫn dùng ÿӃn các bӝ biên dӏch hay các bӝ tiӅn [ӱ lý ÿһc biӋt khác. Nhѭ vұy, PERST có khҧ năng cung cҩp ÿѭӧc “tính trong suӕt” trong lұp trình ӣ mӭc ÿӝ cao. Các hàm API cӫa PERST tiӋn lӧi, dӉ sӱ Gөng và có tӕc ÿӝ cao. Có thӇ lҩy ví dө khi so sánh vӟi Ozone (mӝt hӋ cѫ sӣ Gӳ liӋu hѭӟng ÿӕi tѭӧng khác viӃt bҵng Java). Vӟi giӟi hҥn (benchmark) 007, PERST tҥo database nhanh gҩp 100 lҫn và thӵc hiӋn phép duyӋt qua các ÿӕi tѭӧng trong cѫ sӣ dӳ liӋu nhanh gҩp 10 lҫn so vӟi Ozone. Và khi so vӟi Pӝt hӋ cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng thѭѫng mҥi khác là ObjectStore PSE Pro, PERST nhanh hѫn gҩp 4 lҫn. PERST là mӝt hӋ cѫ sӣ dӳ liӋu tѭѫng ÿӕi nhӓ (so vӟi các hӋ cѫ sӣ dӳ liӋu khác) vӟi phҫn lõi chӍ gӗm khoҧng 5000 dòng mã. Yêu cҫu cҩu hình cӫa PERST tѭѫng ÿӕi thҩp. Hѫn nӳa, PERST cNJng không cҫn ÿӃn “sӵ quҧn trӏ” thѭӡng thҩy ӣ các hӋ cѫ sӣ dӳ liӋu. Mһc dù ÿѫn giҧn nhѭ vұy nhѭng PERST Yүn hӛ trӧÿҫy ÿӫ tính ACID trong viӋc thӵc hiӋn giao tác (transaction) và hӛ trӧ viӋc phөc hӗi (recovery) tѭѫng ÿӕi nhanh khi hӋ thӕng gһp sӵ cӕ. SV ne t.vn - 18 - Có hai bҧn cài ÿһt cӫa PERST, mӝt bҵng ngôn ngӳ Java và mӝt bҵng C#. %ҧn cài ÿһt trên C# ÿѭӧc chuyӇn tӯ Java dùng bӝ chuyӇn ÿәi Java sang C# (mһc dù phҧi có nhiӅu thay ÿәi cҫn thӵc hiӋn mӟi có ÿѭӧc bҧn hoàn chӍnh). 0һc dù bҧn cài ÿһt dùng C# hӛ trӧ nhiӅu kiӇu “nguyên thӫy” hѫn (gӗm có kiӇu sӕ nguyên không dҩu và kiӇu liӋt kê (enum)) nhѭng trong các phѭѫng diӋn khác, các tính năng cӫa hai bҧn là nhѭ nhau. Riêng PERST.NET có hӛ trӧ cҧ viӋc phát triӇn trên môi trѭӡng compact.NET framework nên có khҧ Qăng phát triӇn ӭng dөng trên các thiӃt bӏ di ÿӝng dùng WinCE hay PocketPC. 2.2 Ĉһc tính: Trong phҫn này chúng ta sӁ ÿi vào các tính chҩt quan trӑng nhҩt cӫa PERST. Cө thӇ chúng ta sӁ tìm hiӇu phiên bҧn cài ÿһt trên môi trѭӡng.NET (gӑi tҳt là PERST.NET). Ӣÿây các tính chҩt có tӯ nguyên gӕc tiӃng Anh sӁ ÿѭӧc giӳ nguyên do không có tӯ tiӃng ViӋt thay thӃ ngҳn gӑn mà ÿúng nghƭa.. 2.2.1 Persistency by reachability: Trong ӭng dөng dùng PERST, mӑi ÿӕi tѭӧng cӫa các lӟp ÿѭӧc dүn xuҩt tӯ Oӟp PersistentÿӅu có khҧ năng lѭu trӳ (persistent hay còn dӏch là bӅn vӳng). .Ӈ tӯ bây giӡ, ta sӁ gӑi tҳt các ÿӕi tѭӧng này là các ÿӕi tѭӧng persistent. Các ÿӕi tѭӧng này ÿѭӧc tӵÿӝng lѭu vào database khi nó ÿѭӧc tham chiӃu tӯ mӝt ÿӕi tѭӧng persistent khác và phѭѫng thӭc store cӫa ÿӕi tѭӧng khác ÿó ÿѭӧc Jӑi. Có nghƭa là ta không cҫn phҧi gӑi trӵc tiӃp, tѭӡng minh phѭѫng thӭc store cӫa mӝt ÿӕi tѭӧng khi muӕn lѭu ÿӕi tѭӧng ÿó. SV ne t.vn - 19 - Database có mӝt ÿӕi tѭӧng ÿһc biӋt gӑi là root. Ĉӕi tѭӧng root này là ÿӕi Wѭӧng duy nhҩt ÿѭӧc truy xuҩt mӝt cách ÿһc biӋt (dùng phѭѫng thӭc Storage.getRoot). Còn các ÿӕi tѭӧng persistent khác ÿѭӧc truy xuҩt theo cách bình thѭӡng: hoһc truy xuҩt bҵng tham chiӃu tӯ các ÿӕi tѭӧng persistent nhѭ trên hoһc truy xuҩt bҵng cách dùng các ÿӕi tѭӧng bao chӭa (container class) nhѭ Index,Link hay Relation. Không giӕng nhѭ các hӋ cѫ sӣ dӳ liӋu Kѭӟng ÿӕi tѭӧng khác, chӍ có thӇ có duy nhҩt mӝt ÿӕi tѭӧng root trong cѫ sӣ Gӳ liӋu. PERST yêu cҫu mӛi lӟp persistentÿӅu phҧi dүn xuҩt tӯ lӟp Persistent. Có nghƭa là các lӟp “ngoҥi lai” (không dүn xuҩt tӯ lӟp Persistent) không thӇ ÿѭӧc lѭu trong database. Ĉây chính là cái giá phҧi trҧ cӫa sӵÿѫn giҧn và không dùng ÿӃn các bӝ biên dӏch hay tiӅn xӱ lý ÿһc biӋt. Và các thành phҫn Fӫa các lӟp persistent cNJng bӏ giӟi hҥn trong các kiӇu sau: KiӇu vô hѭӟng (scalar type): Bool, int, short, double, enum … KiӇu chuӛi: KiӇu System.String. KiӇu ngày tháng: KiӇu System.DateTime. KiӇu tham chiӃu ÿӃn các ÿӕi tѭӧng persistent: các lӟp kӃ thӯa tӯ lӟp Persistent hay các giao diӋn (interface) kӃ thӯa tӯ giao diӋn IPersistent. KiӇu giá trӏ (value type): Các kiӇu giá trӏ cӫa C#. Các giá trӏ này ÿѭӧc lѭu trӵc tiӃp trong ÿӕi tѭӧng chӭa chúng. KiӇu dӳ liӋu nhӏ phân thô: Các lӟp cӫa C# kӃ thӯa tӯ giao diӋn IPersistent hay tӯ giao diӋn IValue và ÿѭӧc ÿánh dҩu là Serializable. Cѫ chӃ Serialization chuҭn sӁ ÿѭӧc dùng ÿӇ ÿóng gói dӳ liӋu cӫa các ÿӕi SV ne t.vn - 20 - Wѭӧng thành các mҧng byte và lѭu chúng vào database. Các lӟp này sӁ ÿѭӧc ÿánh dҩu là Serializable và không ÿѭӧc chӭa các tham chiӃu ÿӃn các ÿӕi tѭӧng persistent khác. KiӇu mҧng: Các mҧng mӝt chiӅu vӟi thành phҫn là các kiӇu dӳ liӋu ÿѭӧc nêu trên. KiӇu Link: ÿҥi diӋn cho quan hӋ mӝt-nhiӅu trong mô hình cѫ sӣ dӳ liӋu. Hay nhìn theo góc ÿӝ lұp trình ÿây chính là kiӇu mҧng ÿӝng chӭa các ÿӕi tѭӧng persistent. Có mӝt vҩn ÿӅ là PERST không tӵ biӃt ÿѭӧc rҵng liӋu mӝt ÿӕi tѭӧng persistent nào ÿó ÿã có thay ÿәi gì chѭa trong quá trình làm viӋc. Muӕn biӃt ÿѭӧc ÿLӅu ÿó chӍ có cách là ta tӵ so sánh tӯng field cӫa trҥng thái cNJ và mӟi Yӟi nhau. Nhѭng nhѭ vұy chi phí rҩt cao. Vì thӃ nên trong PERST, lұp trình viên hoàn toàn chӏu trách nhiӋm vӅ viӋc lѭu ÿӕi tѭӧng nào vào cѫ sӣ dӳ liӋu. Có hai cách trong PERST ÿӇ ta có thӇ lѭu mӝt ÿӕi tѭӧng vào cѫ sӣ dӳ liӋu: Cách thӭ nhҩt là dùng phѭѫng thӭc Persistent.Store. Phѭѫng thӭc này khi ÿѭӧc gӑi bӣi ÿӕi tѭӧng nào sӁ lѭu bҧn thân ÿӕi tѭӧng ÿó và các ÿӕi tѭӧng ÿѭӧc tham chiӃu tӯ nó mӝt cách trӵc tiӃp hay không trӵc tiӃp mà chѭa ÿѭӧc Oѭu. Có nghƭa là nӃu ta gӑi phѭѫng thӭc Store này ÿӕi vӟi ÿӕi tѭӧng gӕc cӫa Pӝt cây thì lҫn lѭӧt tҩt cҧ các ÿӕi tѭӧng cӫa cây này sӁÿѭӧc lѭu xuӕng bӝ nhӟ phө. Cách thӭ hai là dùng phѭѫng thӭc Persistent.Modify: Phѭѫng thӭc này chӍ ÿánh dҩu các ÿӕi tѭӧng rҵng chúng ÿã bӏ thay ÿәi chӭ không lѭu ngay lұp tӭc vào database. Cách này ÿһc biӋt hӳu dөng khi ÿӕi tѭӧng ÿѭӧc thay ÿәi nhiӅu SV ne t.vn - 21 - Oҫn trong mӝt giao tác. Lúc ÿó, thao tác ghi ÿƭa chӍ phҧi thӵc hiӋn mӝt lҫn vào cuӕi giao tác, tăng hiӋu suҩt lên ÿáng kӇ. 2.2.2 Semi transparent object loading: Nhѭÿã ÿӅ cұp ӣ trên, PERST không dùng bҩt cӭ bӝ biên dӏch hay tiӅn xӱ lý ÿһc biӋt nào. Và vì C# không cung cҩp thông tin vӅ các trҥng thái (behavior) hay sӵ thay ÿәi trҥng thái các ÿӕi tѭӧng trong thӡi gian thӵc thi (runtime) nên không thӇ cài ÿһt cѫ cҩu lѭu trӳ cӫa PERST hoàn toàn “trong suӕt” (transparent) ÿѭӧc (nghƭa là không thӇ truy xuҩt các ÿӕi tѭӧng ÿѭӧc Oѭu trӳ và không ÿѭӧc lѭu trӳ mӝt cách hoàn toàn giӕng nhau vì ta không thӇ phân biӋt ÿѭӧc khi nào ta ÿang truy xuҩt vào ÿӕi tѭӧng ÿѭӧc lѭu trӳ hay không ÿѭӧc lѭu trӳ). Thay cho sӵ cài ÿһt “trong suӕt” hoàn toàn, PERST ÿã Fӕ gҳng cung cҩp sӵ “trong suӕt” trong ÿa phҫn các trѭӡng hӧp. Giao diӋn IPersistent cung cҩp cho chúng ta phѭѫng thӭc recursiveLoading. Phѭѫng thӭc này mһc ÿӏnh ÿѭӧc cài ÿһt bҵng cách trҧ vӅ (return) giá trӏ true. Có nghƭa là PERST sӁ load (vào bӝ nhӟ chính) mӝt cách ÿӋ quy các ÿӕi tѭӧng ÿѭӧc tham chiӃu tӯ mӝt ÿӕi tѭӧng nguӗn khi ÿӕi tѭӧng nguӗn này ÿѭӧc load. Có nghƭa là cѫ chӃ này sӁ gây ra viӋc load ngҫm ÿӏnh toàn bӝ các ÿӕi tѭӧng vào bӝ nhӟ chính. Cѫ chӃ này tѭѫng tӵ cách làm viӋc Fӫa cѫ chӃ “chuӛi hóa” (serialization). ĈӇ tránh vҩn ÿӅ tràn bӝ nhӟ xҧy ra khi load ÿӕi tѭӧng lên bӝ nhӟ chính (do cѫ chӃ recursiveLoading gây ra), chúng ta phҧi quá tҧi (overload) phѭѫng thӭc recursiveLoading trong mӝt vài lӟp bҵng cách trҧ vӅ (return) giá trӏ false trong hàm. Các ÿӕi tѭӧng ÿѭӧc tham chiӃu tӯ các ÿӕi tѭӧng thuӝc các lӟp ÿã nói trên sӁ không ÿѭӧc load ngҫm ÿӏnh nӳa mà phҧi ÿѭӧc SV ne t.vn - 22 - load mӝt cách tѭӡng minh bҵng phѭѫng thӭc Persistent.Load. Vұy ta thҩy Uҵng phѭѫng thӭc recursiveLoading có thӇ dùng ÿӇ ÿLӅu khiӇn cách thӭc load các ÿӕi tѭӧng tӯ bӝ nhӟ phө vào bӝ nhӟ chính. /ѭu ý rҵng các ÿӕi tѭӧng dùng ÿӇ ”chӭa” các ÿӕi tѭӧng khác (container class) nhѭ Link,Relation,Index… chӍ load các ÿӕi tѭӧng mà nó chӭa khi cҫn thiӃt, không load tҩt cҧ theo cѫ chӃ recusiveLoading. Ngoài ra, viӋc truy xuҩt các ÿӕi tѭӧng thành phҫn cӫa mӝt lӟp kiӇu container ÿӅu thông qua các phѭѫng thӭc cӫa nó. PERST dùng phѭѫng thӭc khӣi tҥo mһc ÿӏnh (không có tham sӕ) ÿӇ khӣi Wҥo bѭӟc ban ÿҫu các ÿӕi tѭӧng ÿѭӧc load tӯ bӝ nhӟ phө. ĈLӅu này có nghƭa là: 1.Mӑi lӟp có khҧ năng lѭu trӳÿѭӧc (persistent capable class) ÿӅu nên có phѭѫng thӭc khӣi tҥo mһc ÿӏnh (hoһc là không có phѭѫng thӭc khӣi tҥo nào, khi ÿó trình biên dӏch sӁ tӵ tҥo ra cho ta). Phѭѫng thӭc này có thӇ có mӑi tҫm truy xuҩt có thӇÿѭӧc (public, private,protected … ). 2.Phѭѫng thӭc khӣi tҥo chӍ khӣi tҥo nhӳng thành phҫn không bӅn vӳng, không cҫn lѭu trӳ (transient) cӫa ÿӕi tѭӧng. 3.Phѭѫng thӭc khӣi tҥo mһc ÿӏnh dùng ÿӇ tҥo nhӳng thӇ hiӋn cӫa các ÿӕi Wѭӧng ÿѭӧc load tӯ bӝ nhӟ phө. Vұy tҥi thӡi ÿLӇm phѭѫng thӭc khӣi tҥo mһc ÿӏnh hoҥt ÿӝng các thành phҫn cӫa ÿӕi tѭӧng chѭa ÿѭӧc gán các giá trӏÿѭӧc Oѭu trӳ trong bӝ nhӟ phө. NӃu ta muӕn các thành phҫn này cNJng ÿѭӧc khӣi Wҥo nhѭ các thành phҫn transient nói trên, ta cҫn khӣi tҥo chúng trong hàm OnLoad, ÿѭӧc gӑi ngay khi các giá trӏ trong bӝ nhӟ phөÿѭӧc load lên bӝ nhӟ chính. SV ne t.vn - 23 - Tóm lҥi, các cѫ chӃ trên cho chúng ta sӵ thuұn tiӋn, dӉ dàng và mӅm dҿo trong lұp trình, vì nó không yêu cҫu lұp trình viên phҧi load tѭӡng minh các ÿӕi tѭӧng trong khi vүn cho phép viӋc này, nói cách khác là PERST hӛ trӧ Oұp trình viên trong viӋc kiӇm soát viӋc load các ÿӕi tѭӧng. ChӍ có các lӟp “chӭa” các ÿӕi tѭӧng khác là phҧi load tѭӡng minh các ÿӕi tѭӧng mà nó chӭa (vì các lӟp này ÿã mһc ÿӏnh ÿѭӧc overload phѭѫng thӭc recursiveLoadingÿӇ có giá trӏ trҧ vӅ (return) false). 2.2.3 Automatic scheme evaluation PERST hӛ trӧ “lazy automatic scheme evaluation”. Khi ÿӏnh nghƭa cӫa Pӝt lӟp bӏ thay ÿәi (thay ÿәi vӅ sӕ lѭӧng biӃn thành viên, thay ÿәi vӅ kiӇu Fӫa biӃn thành viên…), PERST sӁ chuyӇn các ÿӕi tѭӧng ÿã ÿѭӧc load sang ÿӏnh dҥng mӟi. NӃu ÿӕi tѭӧng ÿó trong quá trình hoҥt ÿӝng có thay ÿәi và Fҫn phҧi lѭu, nó sӁÿѭӧc lѭu dѭӟi dҥng mӟi. PERST có khҧ năng hӛ trӧ các kiӇu thay ÿәi ÿӏnh dҥng sau: 1.Các thay ÿәi “tѭѫng thích” lүn nhau giӳa các kiӇu dӳ liӋu vô Kѭӟng (thay ÿәi mà không cҳt bӟt dӳ liӋu). Ví dө nhѭ thay ÿәi tӯ kiӇu int sang float hay int sang long,… nhѭng ngѭӧc lҥi thì không ÿѭӧc. 2.Thay ÿәi thӭ tӵ các thành phҫn trong lӟp hay thêm, bӟt các thành phҫn trong lӟp này vào lӟp cha hay lӟp dүn xҩt cӫa nó. 3.Thêm vào hay bӓ lӟp khӓi cây thӯa kӃ cӫa lӟp. 4.Thay ÿәi ÿӏnh dҥng cӫa lӟp bҵng cách thay ÿәi ý nghƭa cӫa các giá trӏ. 0ӑi thay ÿәi khác trong cҩu trúc lӟp (ÿәi tên cho thành phҫn, chuyӇn kiӇu không tѭѫng thích ÿӕi vӟi các thành phҫn…) ÿӅu không ÿѭӧc quҧn lý bӣi cѫ SV ne t.vn - 24 - chӃ thay ÿәi cҩu trúc dӳ liӋu tӵÿӝng cӫa PERST. Trong các trѭӡng hӧp này ta có thӇ dùng cѫ chӃ xuҩt nhұp bҵng XML cӫa PERST. Cѫ sӣ dӳ liӋu có thӇ ÿѭӧc xuҩt ra dҥng XML bҵng cách dùng phѭѫng thӭc Storage.exportXML, Wҥo lҥi cѫ sӣ dӳ liӋu theo ÿӏnh dҥng mӟi rӗi nhұp dӳ liӋu vào bҵng phѭѫng thӭc Storage.importXML cӫa PERST. 2.2.4 Relation: 0ӕi quan hӋ mӝt-mӝt giӳa các ÿӕi tѭӧng trong cѫ sӣ dӳ liӋu ÿѭӧc thӇ hiӋn Eҵng tham chiӃu (references) trong C#. Nhѭng trong nhiӅu trѭӡng hӧp chúng ta cҫn ÿӃn quan hӋ mӝt-nhiӅu hay quan hӋ nhiӅu-nhiӅu. PERST cung cҩp giao diӋn (interface) Link dùng cho các trѭӡng hӧp này. Giao diӋn này ÿѭa ra các phѭѫng thӭc thêm, xóa, tìm kiӃm… các thành phҫn cӫa mӝt “bӝ” (relation) các ÿӕi tѭӧng persistent. Các thành phҫn cӫa “bӝ” (relation) này có thӇ ÿѭӧc truy xuҩt bҵng index hay ta có thӇ chuyӇn chúng thành mӝt Pҧng ÿӕi tѭӧng rӗi mӟi truy xuҩt. Tұp hӧp (relation) có 2 dҥng: 1. Dҥng “nhúng” (embedded relation): Các tham chiӃu ÿӃn các ÿӕi Wѭӧng tӯ mӝt ÿӕi tѭӧng ÿѭӧc chӭa trong chính ÿӕi tѭӧng ÿó. 2. Dҥng ÿӝc lұp (standalone relation): Khi ÿó relation là mӝt ÿӕi Wѭӧng riêng biӋt, chӭa các tham chiӃu ÿӃn các ÿӕi tѭӧng. Cҧ hai dҥng trên ÿӅu cài ÿһt giao diӋn Link. Cө thӇ Embedded relation ÿѭӧc tҥo bҵng cách dùng phѭѫng thӭc Storage.createLink, còn Standalone relation thì dùng phѭѫng thӭc Storage.createRelation. Bҧng sau ÿây minh hӑa các mӕi quan hӋ giӳa 2 lӟp A và B: SV ne t.vn - 25 - KiӇu quan hӋ Object A Object B 0ӝt-mӝt B bref; A aref; 0ӝt-nhiӅu Link bref; A aref; NhiӅu-mӝt B bref; Link aref; NhiӅu-nhiӅu Link bref; Link aref; %ҧng 2.2.4-1 Các mӕi quan hӋ giӳa 2 lӟp A va B 2.2.5 Index: Thông thѭӡng ÿӕi tѭӧng ÿѭӧc truy xuҩt tӯ mӝt ÿӕi tѭӧng khác bҵng tham chiӃu hay bҵng Link nhѭ trên. Tuy nhiên, chúng ta cNJng cҫn truy xuҩt các ÿӕi Wѭӧng thông qua khóa. Trong môi trѭӡng.NET, lӟp Hashtable là mӝt ví dө cho viӋc truy xuҩt theo khóa này. Ĉӕi vӟi cѫ sӣ dӳ liӋu, viӋc truy xuҩt ÿӕi Wѭӧng theo khóa dƭ nhiên là tѭѫng ÿӕi phӭc tҥp. Và viӋc cài ÿһt trong PERST Kҷn mӝt chӭc năng dӏch các câu truy vҩn SQL là không khҧ thi vì nó sӁ làm cho PERST phình to ra và chұm ÿi. Tuy nhiên trong phҫn lӟn trѭӡng hӧp, các ӭng dөng chӍ thӵc hiӋn các lӋnh truy vҩn dӳ liӋu tѭѫng ÿӕi ÿѫn giҧn nhѭ tìm theo mӝt khóa chính xác hay trong mӝt khoҧng giá trӏ nào ÿó. Trong PERST viӋc này ÿѭӧc thӵc hiӋn bҵng cách cài ÿһt các giao diӋn (interface) Index và FieldIndex. Giao diӋn Index dùng cho các khóa ÿӝc lұp và các giá trӏ tѭѫng ӭng cӫa khóa ÿó. Còn giao diӋn FieldIndex thì dùng ÿӇ lұp index cho các ÿӕi tѭӧng vӟi khóa chính là mӝt thành phҫn cӫa ÿӕi tѭӧng. Index ÿѭӧc tҥo trong PERST bҵng phѭѫng thӭc Storage.createIndexÿӕi Yӟi Index hay Storage.createFieldIndex ÿӕi vӟi FieldIndex. Có thӇ có vài cách cài ÿһt Index nhѭng hiӋn tҥi PERST chӍ dùng B+Tree ÿӇ cài ÿһt SV ne t.vn - 26 - (B+Tree là cҩu trúc dӳ liӋu hiӋu quҧ nhҩt cho database trên bӝ nhӟ phө). Các phѭѫng thӭc cӫa giao diӋn Index và FieldIndex cho phép thêm, xóa, tìm kiӃm ÿӕi tѭӧng theo khóa bҵng giá trӏ chính xác hoһc trong mӝt khoҧng giá trӏ nào ÿó. Vì vұy các trѭӡng hӧp tìm kiӃm sau ÿây là thӵc hiӋn ÿѭӧc: 1. Khóa bҵng giá trӏ VAL. 2. Khóa thuӝc khoҧng [MIN_VAL,MAX_VAL]. 3. Khóa thuӝc khoҧng [MIN_VAL,MAX_VAL). 4. Khóa thuӝc khoҧng (MIN_VAL,MAX_VAL]. 5. Khóa thuӝc khoҧng (MIN_VAL,MAX_VAL). 6. Khóa lӟn hѫn giá trӏ MIN_VAL. 7. Khóa lӟn hѫn hay bҵng giá trӏ MIN_VAL. 8. Khóa bé hѫn giá trӏ MAX_VAL. 9. Khóa bé hѫn hay bҵng giá trӏ MAX_VAL. Có mӝt sӕ cách chӑn ÿӕi tѭӧng theo khóa khác nhau nhѭ sau: a.IPersistent get(Key key): Chӑn ÿӕi tѭӧng bҵng khóa chính xác vӟi khóa này nên là khóa duy nhҩt cӫa ÿӕi tѭӧng. b.IPersistent[] get(Key from,Key till): Lҩy ra mӝt mҧng ÿӕi tѭӧng có khóa Qҵm trong mӝt khoҧng giá trӏ cho trѭӟc giӟi hҥn bӣi giá trӏ from và till. Trong ÿó from và till có thӇ mang giá trӏ tùy ý kӇ cҧ null. c.IEnumerator GetEnumerator(): Lҩy ra mӝt IEnumerator, có thӇ dùng câu lӋnh foreach ÿӇ duyӋt qua toàn bӝ các ÿӕi tѭӧng trong index này theo chiӅu tăng cӫa khóa. SV ne t.vn - 27 - d.IEnumerator GetEnumerator(Key from, Key till, IterationOrder order): /ҩy ra mӝt IEnumerator vӟi khóa nҵm trong khoҧng giá trӏ xác ÿӏnh bӣi from và till. Ta có thӇ duyӋt qua IEnumerator này vӟi chiӅu khóa tăng hay giҧm ÿӅu ÿѭӧc. 1Ӄu cҫn mӝt tұp hӧp các ÿӕi tѭӧng, chúng ta có thӇ sӱ dөng phѭѫng thӭc Storage.createSet. Tұp hӧp (set) ÿѭӧc cài ÿһt bҵng B+Tree vӟi object ID (OID) là khóa. Ngoài ra, PERST còn hӛ trӧ rҩt mҥnh cho dӳ liӋu “không gian” (spatial data) bҵng cách cung cҩp cҩu trúc SpatialIndex hӛ trӧ viӋc thêm, xóa, tìm kiӃm các ÿӕi tѭӧng “không gian” dӉ dàng. SpatialIndex ÿѭӧc cài ÿһt bҵng Fҩu trúc RTree cӫa Guttman vӟi thuұt toán “quadratic split” khá hiӋu quҧ trong viӋc tìm kiӃm các ÿӕi tѭӧng R2 (tìm kiӃm các ÿӕi tѭӧng không gian Yӟi khóa tìm kiӃm là các giá trӏ liên quan ÿӃn tӑa ÿӝ). Bҧng dѭӟi ÿây tóm tҳt các kiӇu Index ÿѭӧc PERST hӛ trӧ: Interface Mô tҧ KiӇu cӫa khóa Cài ÿһt Phѭѫng thӭc tҥo Index Index dùng tìm kiӃm Gӳ liӋu bҵng khóa chính xác hoһc nҵm trong mӝt khoҧng xác ÿӏnh. KiӇu vô Kѭӟng, chuӛi hay kiӇu tham chiӃu. B+Tree Storage.CreateIndex Index Nhѭ trên nhѭng áp Gөng cho trѭӡng KiӇu vô Kѭӟng, B+Tree Storage.CreateThinkI ndex SV ne t.vn - 28 - Kӧp có khóa trùng. chuӛi hay kiӇu tham hiӃu. FieldIndex Index vӟi khóa là Pӝt trong các trѭӡng cӫa lӟp ÿѭӧc Oұp Index. KiӇu vô Kѭӟng, chuӛi hay kiӇu tham chiӃu. B+Tree Storage.CreateFieldIn dex BitIndex BitIndex dùng tìm ÿӕi tѭӧng vӟi khóa cógiá trӏ nhӏ phân. KiӇu ÿӕi Wѭӧng có khҧ năng Oѭu trӳ. B+Tree Storage.CreaateBitInd ex ISet 7ұp hӧp các ÿӕi Wѭӧng có khҧ năng Oѭu trӳ. B+Tree Storage.CreateSet IPersisten tSet 7ұp hӧp các ÿӕi Wѭӧng có khҧ năng Oѭu trӳ ÿѭӧc và tұp Kӧp này có khҧ năng co giãn, có thӇ quҧn lý ÿѭӧc cҧ sӕ lѭӧng ít lүn sӕ lѭӧng nhiӅu. KiӇu ÿӕi Wѭӧng có khҧ năng Oѭu trӳ. Link hoһc B+Tree Storage.CreateScalabl eSet SV ne t.vn - 29 - SpatialInd ex Index dành cho dӳ liӋu không gian. Rectangle R-Tree Storage.CreateSpatialI ndex SpatialInd exR2 Index dành cho dӳ liӋu không gian nhѭng có tӑa ÿӝ thӵc. Rectangle R2 R-Tree Storage.CreateSpatialI ndexR2 SortedCol lection Index vӟi phép Toán so sánh do ngѭӡi dùng ÿӏnh nghƭa. 0ӑi kiӇu T-Tree Storage.CreateStorage Collection %ҧng 2.2.5-1 Các kiӇu Index ÿѭӧc PERST hӛ trӧ: 2.2.6 Giao tác (Transaction): Ӣÿây ta không ÿӏnh nghƭa lҥi chính xác giao tác là gì mà chӍ ÿѫn giҧn hình dung giao tác là mӝt tұp các lӋnh phҧi thӵc hiӋn và phҧi hoһc là thӵc hiӋn toàn bӝ các lӋnh ÿó hoһc là không lӋnh nào ÿѭӧc thӵc hiӋn cҧ. PERST cung cҩp tính năng bҧo vӋ sӵ nhҩt quán cӫa dӳ liӋu trong trѭӡng hӧp hӋ thӕng hay ӭng dөng có lӛi hay mҩt ÿLӋn phҧi tҳt ÿӝt ngӝt. Cѫ chӃ cài ÿһt giao tác sӁ giúp ta ÿҧm bҧo ÿLӅu này. Ĉӕi vӟi PERST, mӝt giao tác ÿѭӧc ngҫm ÿӏnh khӣi tҥo khi bҩt cӭ mӝt lӋnh update cѫ sӣ dӳ liӋu nào ÿѭӧc thӵc hiӋn và chҩm dӭt tѭӡng minh bҵng lӋnh commit, rollback hay close. ViӋc commit mӝt giao tác sӁ làm cho các trang (page) bӏ thay ÿәi trong quá trình thӵc hiӋn giao tác ÿѭӧc ghi vào bӝ nhӟ phөÿӗng bӝ (Asynchronous write: chѭѫng trình sӁ chӡ cho viӋc ghi vào ÿƭa xong mӟi làm tiӃp viӋc khác). Công viӋc này là công viӋc có chi phí rҩt cao. Trung bình viӋc ÿӏnh vӏ SV ne t.vn - 30 - ÿӕi vӟi các әÿƭa hiӋn ÿҥi là khoҧng 10ms, nghƭa là chӍ khoҧng 100 thao tác ÿӏnh vӏ trong 1 giây. Thêm vào ÿó các giao tác thѭӡng chӭa các thao tác update khoҧng vài trang cѫ sӣ dӳ liӋu nên trung bình chӍ còn khoҧng 10 giao tác mӛi giây. 0һc dù vұy, hiӋu suҩt thӵc thi sӁÿѭӧc nâng cao ÿáng kӇ khi ta hҥn chӃ sӕ Oҫn thӵc hiӋn lӋnh commit, có nghƭa là mӝt giao tác sӁ lӟn hѫn, thӵc hiӋn nhiӅu lӋnh hѫn. PERST dùng cѫ chӃ tҥo bóng (shadow mechanism) trong viӋc thӵc hiӋn giao tác. Khi mӝt ÿӕi tѭӧng ÿѭӧc thay ÿәi lҫn ÿҫu tiên trong Pӝt giao tác, mӝt bҧn copy (shadow) cӫa ÿӕi tѭӧng ÿó ÿѭӧc tҥo ra và ÿӕi Wѭӧng gӕc không thay ÿәi. Cho dù ÿӕi tѭӧng có ÿѭӧc thay ÿәi nhiӅu lҫn trong giao tác ÿó thì cNJng chӍ có mӝt bҧn copy cӫa ÿӕi tѭӧng ÿѭӧc tҥo ra. Nhѭ vұy cѫ chӃ này giúp PERST hoàn toàn không cҫn ÿӃn các tұp tin log trong cѫ sӣ dӳ liӋu thông thѭӡng và các giao tác dài không thӇ gây ra viӋc tràn log giao tác nhѭ các hӋ cѫ sӣ dӳ liӋu khác. Lѭu ý rҵng nӃu ta không gӑi OӋnh commit mӝt cách tѭӡng minh thì PERST sӁ chӍ hoҥt ÿӝng mӝt cách thông thѭӡng theo cѫ chӃ không hӛ trӧ giao tác. KhuyӃt ÿLӇm duy nhҩt cӫa viӋc giao tác dài hѫn bình thѭӡng là khҧ năng Pҩt ÿi nhiӅu sӵ thay ÿәi ÿã thӵc hiӋn ÿѭӧc trong giao tác nӃu giao tác hӓng hay hӋ thӕng gһp sӵ cӕ. Trong các trѭӡng hӧp nhѭ vұy, dӳ liӋu vүn ÿҧm bҧo tính nhҩt quán (consistency) nhѭng các thao tác thay ÿәi cѫ sѫ dӳ liӋu trong giao tác ÿó ÿӅu mҩt. SV ne t.vn - 31 - 2.3 Transparent API: 2.3.1 Dùng.NET Remoting API: .NET framework cung cҩp gói System.Runtime.Remoting nhҵm hӛ trӧ viӋc cài ÿһt các ӭng dөng phân tán. Ngѭӡi lұp trình chӍ cҫn dүn xuҩt các lӟp cӫa Kӑ tӯ lӟp ContextBoundObject và dùng ContextAttribute ÿӇ tҥo message sink: cѫ chӃ dùng ÿӇÿLӅu khiӇn viӋc gӑi hàm và truy xuҩt các thành phҫn cӫa ÿӕi tѭӧng. Dùng API này không nhӳng áp dөng cho các hӋ thӕng phân tán mà còn cho các hӋ thӕng dӵa trên giao thӭc metaobject (metaobject protocol): giao thӭc ÿLӅu khiӇn ÿӕi tѭӧng. Ví dө ta có thӇӭng dөng chúng ÿӇ cài ÿһt giao diӋn “trong suӕt” (transparent) cho cѫ sӣ dӳ liӋu hѭӟng ÿӕi Wѭӧng này, nghƭa là viӋc thao tác trên các ÿӕi tѭӧng persistent hoàn toàn bình thѭӡng nhѭ các ÿӕi tѭӧng khác. PERST.NET chӭa 2 lӟp PersistentContext và TransparentPersistentAttribute dùng tҥo tính “bӅn vӳng” mӝt cách “trong suӕt” cho các ÿӕi tѭӧng bҵng cách dùng.NET Remoting API. NӃu các lӟp cӫa ӭng dөng chúng ta ÿѭӧc dүn xuҩt tӯ lӟp PersistentContext và ÿѭӧc ÿánh dҩu Eҵng tính chҩt (attribute) TransparentPersistentAttribute, các thành phҫn cӫa nó sӁÿѭӧc load tӵÿӝng hay lѭu tӵÿӝng khi cҫn thiӃt (trѭӟc ÿây ta ÿӅu phҧi Wӵ làm các thao tác này). Vì hàm recursiveLoading trong lӟp PersistentContext trҧ vӅ false nên các ÿӕi tѭӧng sӁÿѭӧc load chӍ khi nào ta truy xuҩt nó. Tuy nhiên có 2 giӟi hҥn khi ta dùng remoting API: 1.Remoting API chӍ có thӇ áp dөng ÿӕi vӟi các thành phҫn có tҫm truy xuҩt public cӫa ÿӕi tѭӧng. SV ne t.vn - 32 - 2.Chi phí cӫa viӋc gӑi hàm thông qua remoting API cao gҩp khoҧng 100 Oҫn so vӟi gӑi hàm thông thѭӡng. 2.3.2 Dùng các thuӝc tính ҧo (virtual properties): Có mӝt ý tѭӣng khác tҥo nên sӵ “trong suӕt” cho PERST dӵa trên viӋc dùng các thuӝc tính ҧo (virtual properties). Không giӕng nhѭ Java, C# cung Fҩp cѫ chӃ cho phép ÿóng gói các thuӝc tính, thành phҫn cӫa mӝt lӟp. Ý Wѭӣng ban ÿҫu rҩt ÿѫn giҧn: Tҥo ra lӟp bao bӑc (wrapper class) sӁ cài ÿһt các thuӝc tính này. Nhѭ vұy lұp trình viên sӁÿѭӧc giҧi phóng khӓi nhiӅu viӋc nhӓ nhһt nhѭ không phҧi lo ÿӃn chuyӋn quá tҧi hàm recursiveLoading, hay Jӑi tѭӡng minh hàm LoadÿӇ load ÿӕi tѭӧng cNJng nhѭÿánh dҩu ÿӕi tѭӧng bӏ thay ÿәi bӣi hàm Modify nӳa…. Tuy nhiên cách này vүn có nhӳng hҥn chӃ Fӫa riêng nó: 1.Ĉӕi tѭӧng cӫa chúng ta không ÿѭӧc có các trѭӡng lѭu trӳ ÿѭӧc (persistent fields). Thay vì thӃ, ta phҧi ÿӏnh nghƭa các thuӝc tính trӯu Wѭӧng. C# cung cҩp cѫ chӃ cho phép ta dӉ dàng làm viӋc vӟi các thuӝc tính, nên viӋc lұp trình sӁÿӥ nһng nӅ hѫn. 2.Ta cNJng không thӇ tҥo ra các ÿӕi tѭӧng này bҵng toán tӱ new nhѭ bình thѭӡng. Ta phҧi dùng phѭѫng thӭc IStorage.CreateClass dùng ÿӇ tҥo Oӟp bao bӑc và tҥo ra ÿӕi tѭӧng cӫa lӟp này. Lӟp này cNJng không có hàm khӣi tҥo nào khác ngoài hàm khӣi tҥo mһc ÿӏnh, và hàm khӣi tҥo mһc ÿӏnh này cNJng không làm gì khác ngoài viӋc khӣi tҥo các thành phҫn không ÿѭӧc lѭu trӳ (vì hàm khӣi tҥo này sӁ ÿѭӧc gӑi mӛi khi ÿӕi tѭӧng ÿѭӧc load tӯ bӝ nhӟ phө). SV ne t.vn - 33 - 3.Ta cNJng không thӇ có thành phҫn cӫa ÿӕi tѭӧng là mҧng các tham chiӃu ÿӃn các ÿӕi tѭӧng khác. Ta phҧi dùng PERST.PArrayÿӇ thay thӃ. 4.Sӵ phát sinh lӟp bao bӑc nhѭ vұy có chi phí cao, làm giҧm hiӋu suҩt chѭѫng trình nӃu có nhiӅu lӟp. 5.Cuӕi cùng, cѫ chӃ này không ÿѭӧc hӛ trӧ trong môi trѭӡng .NET Compact framework do môi trѭӡng này không hӛ trӧ viӋc tҥo mã trong thӡi gian thӵc thi (runtime). 2.4 &ѫ chӃ thӵc hiӋn giao tác (Transaction): 0ӛi record hay ÿӕi tѭӧng trong PERST có duy nhҩt mӝt sӕÿӏnh danh gӑi là OID. OIDÿѭӧc dùng ÿӇ tham chiӃu giӳa các ÿӕi tѭӧng vӟi nhau. ĈӇÿӏnh Yӏ chính xác mӝt ÿӕi tѭӧng bҵng tham chiӃu, OID cӫa chúng ÿѭӧc dùng nhѭ chӍ sӕ trong mҧng các ÿӏa chӍ (offset) cӫa các ÿӕi tѭӧng trong database. 0ҧng này ÿѭӧc gӑi là mҧng chӍ mөc ÿӕi tѭӧng (object index) và mӛi thành phҫn cӫa mҧng này ÿѭӧc gӑi là mӝt mөc quҧn ÿӕi tѭӧng (object handle), giӳ ÿӏa chӍ trong database cӫa ÿӕi tѭӧng. Có 2 bҧn cӫa mҧng chӍ mөc ÿӕi tѭӧng trong PERST, mӝt là mҧng “hiӋn hành” (current) và mҧng còn lҥi gӑi là Pҧng “bóng” (shadow) cӫa mҧng này. Header cӫa database giӳ con trӓÿӃn Fҧ hai mҧng này và có mӝt biӃn chӍÿӏnh (indicator) ÿâu là mҧng “hiӋn hành” vào thӡi ÿLӇm hiӋn tҥi. Khi mӝt ÿӕi tѭӧng bӏ thay ÿәi lҫn ÿҫu tiên, ÿӕi tѭӧng ÿó sӁÿѭӧc copy ra Pӝt bҧn khác và mөc quҧn cӫa ÿӕi tѭӧng trong mҧng chӍ mөc ÿӕi tѭӧng “hiӋn hành” sӁ chuyӇn sang trӓ vào bҧn copy cӫa ÿӕi tѭӧng này còn mөc quҧn ÿӕi tѭӧng trong mҧng chӍ mөc ÿӕi tѭӧng “bóng” vүn trӓ vào ÿӕi tѭӧng Jӕc. Tҩt cҧ các thay ÿәi ÿӅu ÿѭӧc làm trên bҧn copy và bҧn gӕc ÿѭӧc giӳ SV ne t.vn - 34 - nguyên trҥng. PERST sӁÿánh dҩu trong trang Bitmap cӫa mҧng chӍ mөc ÿӕi Wѭӧng chӭa con trӓÿӃn ÿӕi tѭӧng bӏ thay ÿәi. Lúc giao tác (transaction) ÿѭӧc hoàn tҩt và lӋnh commit ÿѭӧc thӵc hiӋn, ÿҫu tiên PERST sӁ kiӇm tra xem kích thѭӟc cӫa mҧng chӍ mөc ÿӕi tѭӧng có Wăng hay không. NӃu có, PERST cNJng sӁ tăng kích thѭӟc cho mҧng chӍ mөc ÿӕi tѭӧng “bóng”. KӃÿӃn PERST sӁ giҧi phóng các vùng nhӟÿѭӧc dùng bӣi các ÿӕi tѭӧng gӕc, chính là các ÿӕi tѭӧng gӕc mà trѭӟc ÿây ÿã dùng chúng ÿӇ tҥo ra các bҧn copy. Các vùng nhӟ này không thӇÿѭӧc giҧi phóng trѭӟc khi giao tác commit vì nhѭ vұy có thӇ PERST sӁ cҩp phát cho các ÿӕi tѭӧng Pӟi ÿúng các vùng nhӟÿó, trong khi chúng ta muӕn các ÿӕi tѭӧng gӕc chӭa trong vùng nhӟ này không ÿәi. ĈLӅu này ҧnh hѭӣng ÿӃn tính nhҩt quán cӫa Fѫ sӣ dӳ liӋu. Vì viӋc giҧi phóng vùng nhӟ trong PERST cNJng ÿѭӧc thӵc hiӋn thông qua Bitmap nên khi giҧi phóng cҫn phҧi làm trӕng mӝt sӕ bit trong trang Bitmap tѭѫng ӭng vӟi các vùng nhӟ cҫn xóa. Mà các trang Bitmap này cNJng ÿѭӧc copy trѭӟc khi sӵ thay ÿәi xҧy ra. ViӋc copy các trang Bitmap này cNJng ÿòi hӓi vùng nhӟ, và ta có thӇ cNJng dùng các vùng nhӟ cӫa các ÿӕi tѭӧng bӏ giҧi phóng nhѭ trên. Rõ ràng ÿLӅu này lҥi vi phҥm tính nhҩt quán cӫa cѫ sӣ dӳ liӋu theo nhѭ lý do vӯa nêu. Tҩt cҧ nhӳng ÿLӅu trên chính là lý do tҥi sao viӋc giҧi phóng vùng nhӟ trong PERST ÿѭӧc chia thành hai bѭӟc. Ĉҫu tiên, khi ÿӕi tѭӧng ÿѭӧc copy, tҩt cҧ các trang Bitmap Wѭѫng ӭng vӟi vùng nhӟ cӫa ÿӕi tѭӧng cNJng ÿѭӧc copy theo (nӃu trѭӟc ÿó chѭa ÿѭӧc copy). Khi giao tác commit, PERST chӍ viӋc làm trӕng các bit trong các trang Bitmap tѭѫng ӭng và tҥi thӡi ÿLӇm này, không có mӝt yêu Fҫu vӅ cҩp phát bӝ nhӟ nào ÿѭӧc phép phát sinh. SV ne t.vn - 35 - Sau khi giҧi phóng các vùng nhӟ thuӝc vӅ các ÿӕi tѭӧng gӕc, PERST sӁ ÿӗng loҥt ghi các trang bӏ thay ÿәi lên ÿƭa ÿӇÿӗng bӝ thông tin trên bӝ nhӟ chính và trên ÿƭa. Sau ÿó PERST sӁ chuyӇn ÿәi giá trӏ biӃn chӍ ÿӏnh (indicator) chӍ ra mҧng chӍ mөc ÿӕi tѭӧng hiӋn tҥi trong database thành giá trӏ chӍÿӃn mҧng “bóng” ÿӇ chuyӇn ÿәi vai trò giӳa hai mҧng. Bây giӡ mҧng chӍ mөc ÿӕi tѭӧng hiӋn tҥi chuyӇn thành “bóng” và mҧng chӍ mөc ÿӕi tѭӧng “bóng” sӁ trӣ thành mҧng hiӋn tҥi. TiӃp theo mӝt lҫn nӳa PERST sӁ ghi trang chӭa header bӏ thay ÿәi cӫa database lên ÿƭa, chuyӇn database sang trҥng thái nhҩt quán mӟi. Cuӕi cùng PERST sӁ copy tҩt cҧ các mөc quҧn ÿӕi tѭӧng bӏ thay ÿәi tӯ mҧng chӍ mөc ÿӕi tѭӧng “bóng” (trѭӟc ÿây là hiӋn tҥi) sang mҧng chӍ mөc ÿӕi tѭӧng hiӋn tҥi (trѭӟc kia là mҧng “bóng”). Vào thӡi ÿLӇm này, Qӝi dung cӫa cҧ hai mҧng chӍ mөc ÿӕi tѭӧng ÿã ÿӗng nhҩt và PERST có thӇ Eҳt ÿҫu mӝt giao tác mӟi. Bitmap cӫa các ÿӕi tѭӧng bӏ thay ÿәi có tác dөng giҧm thӡi gian commit giao tác. Không phҧi tҩt cҧ mҧng chӍ mөc ÿѭӧc copy mà chӍ có các trang bӏ thay ÿәi mӟi ÿѭӧc copy, Sau khi giao tác commit, Bitmap ÿѭӧc làm trӕng nhѭÿã nói ӣ trên. Khi giao tác ÿѭӧc bӓ, không cho thӵc hiӋn nӳa bҵng lӋnh Storage.rollback Pӝt cách tѭӡng minh, mҧng chӍ mөc ÿӕi tѭӧng “bóng” sӁÿѭӧc copy ngѭӧc Oҥi vào mҧng chӍ mөc ÿӕi tѭӧng hiӋn tҥi, có nghƭa là các thay ÿәi nӃu có trѭӟc ÿó ÿӅu không có hiӋu lӵc. Sau khi copy, hai mҧng chӍ mөc lҥi ÿӗng nhҩt và cѫ sӣ dӳ liӋu lҥi trӣ vӅ trҥng thái nhҩt quán trѭӟc khi thӵc hiӋn giao tác. 6ӵ cҩp phát vùng nhӟ cho các mөc quҧn ÿӕi tѭӧng ÿѭӧc thӵc hiӋn bҵng freehandle list. Header cӫa list cNJng ÿѭӧc copy và cҧ hai bҧn cӫa header này SV ne t.vn - 36 - cùng ÿѭӧc lѭu trên header cӫa database. Sӵ chuyӇn qua lҥi giӳa hai bҧn này ÿѭӧc thӵc hiӋn tѭѫng tӵ nhѭ viӋc chuyӇn qua lҥi giӳa hai mҧng chӍ mөc ÿӕi Wѭӧng. Khi không còn chӛ trӕng trong mҧng chӍ mөc ÿӕi tѭӧng, mҧng sӁ ÿѭӧc cҩp phát thêm. Mҧng chӍ mөc ÿӕi tѭӧng là thӭ duy nhҩt trong cѫ sӣ dӳ liӋu không ÿѭӧc copy trong quá trình thay ÿәi. Thay vì thӃ, PERST luôn luôn Vӱ dөng hai bҧn cӫa mҧng này (mӝt bҧn hiӋn tҥi và mӝt bҧn “bóng”). Có mӝt vài giá trӏ OID ÿѭӧc dành riêng cho các ÿӕi tѭӧng ÿһc biӋt trong PERST. Giá trӏ OID 0 dùng cho các ÿӕi tѭӧng không hӧp lӋ ví dө nhѭ các ÿӕi tѭӧng ÿã bӏ xóa. Các giá trӏ OID bҳt ÿҫu tӯ 1 ÿѭӧc dùng cho các trang Bitmap. Sӕ trang Bitmap lҥi tùy thuӝc vào lѭӧng bӝ nhӟҧo tӕi ÿa cӫa cѫ sӣ Gӳ liӋu. Ví dө vӟi 1tetrabyte bӝ nhӟҧo thì kích thѭӟc trang 8Kb, kích thѭӟc ÿѫn vӏ vùng nhӟ cҩp phát (allocation quantum) 64 byte và 32K trang Bitmap là các sӕ liӋu tѭѫng ӭng. Có nghƭa là 32K mөc quҧn ÿӕi tѭӧng ÿѭӧc dành riêng cho các trang Bitmap trong mҧng chӍ mөc ÿӕi tѭӧng. Các trang Bitmap ÿѭӧc cҩp phát khi cҫn thiӃt khi mà kích thѭӟc database tăng lên. Theo các sӕ liӋu trên thì rõ ràng ÿӕi tѭӧng cӫa ngѭӡi dùng ÿҫu tiên sӁ mang giá trӏ OID Eҵng 0x8002 (tӭc là 32K + 2). Quá trình phөc hӗi cѫ sӣ dӳ liӋu trong PERST cNJng ÿѫn giҧn. Khi ta mӣ Fѫ sӣ dӳ liӋu, PERST sӁ kiӇm tra xem cѫ sӣ dӳ liӋu trѭӟc ÿó có ÿѭӧc ÿóng ÿúng cách không. NӃu không (cӡ dirty ÿѭӧc bұt lên trong header cӫa database), PERST sӁ thӵc hiӋn viӋc phөc hӗi (tѭѫng tӵ nhѭ cѫ chӃ rollbachk ÿã ÿӅ cұp phía trên). PERST sӁ làm nhѭ sau: BiӃn chӍÿӏnh chӍ ra mҧng chӍ mөc ÿӕi tѭӧng hiӋn tҥi sӁÿѭӧc PERST dùng ÿӇ quyӃt ÿӏnh xem mҧng nào là mҧng tѭѫng ӭng vӟi trҥng thái nhҩt quán. Khi ÿó, PERST sӁ copy các mөc quҧn ÿӕi tѭӧng trong mҧng này sang mҧng SV ne t.vn - 37 - còn lҥi, các thay ÿәi thӵc hiӋn trѭӟc ÿó nӃu có ÿӅu không cón hiӋu lӵc, PERST lҥi trӣ vӅ vӟ trҥng thái nhҩt quán. Thұt sӵ quá trình recovery chӍ làm chuyӋn copy trên (chӍ nhӳng mөc quҧn có giá trӏ khác nhau trên hai mҧng chӍ mөc ÿӕi tѭӧng mӟi ÿѭӧc copy ÿӇ giҧm Vӕ trang cҫn ghi lên ÿƭa) và kích thѭӟc cӫa mҧng chӍ mөc ÿӕi tѭӧng cNJng nhӓ nên viӋc phөc hӗi diӉn ra rҩt nhanh. ĈLӅu này giúp giҧm thӡi gian “out-of- service” cӫa ӭng dөng. 2.5 Nhӳng trѭӡng hӧp nên dùng PERST: PERST là cѫ sӣ dӳ liӋu dành cho lұp trình tѭѫng ÿӕi ÿѫn giҧn và nhanh. 1Ӄu ӭng dөng cӫa chúng ta cҫn có cѫ sӣ dӳ liӋu ÿѫn, không thӵc hiӋn nhӳng thao tác truy xuҩt dӳ liӋu quá “lҳt léo” và cái chúng ta cҫn là khҧ năng lѭu trӳ, truy xuҩt, ÿӏnh vӏ các ÿӕi tѭӧng trong cѫ sӣ dӳ liӋu thông qua tham chiӃu hay qua khóa thì PERST rҩt thích hӧp. Trong các trѭӡng hӧp này PERST sӁ có hiӋu năng làm viӋc tӕt hѫn so vӟi các cѫ sӣ dӳ liӋu quan hӋ hay các cѫ sӣ Gӳ liӋu hѭӟng ÿӕi tѭӧng phӭc tҥp hѫn khác. Ta sӁÿLӇm qua lҥi các tính năng nәi bұt cӫa PERST: 1.KӃt hӧp chһt chӁ, tӵ nhiên vӟi mӝt sӕ ngôn ngӳ lұp trình thông dөng nhҩt ÿӏnh (HiӋn tҥi chӍ mӟi hӛ trӧ Java và C#). 2.Mô hình dӳ liӋu trong ӭng dөng và database gҫn nhѭ tѭѫng tӵ nhau. 3.DӉ dàng sӱ dөng. 4.Yêu cҫu không cao (PERST package chӍ có dung lѭӧng 51Kb và PERST có thӇÿѭӧc cҩu hình lҥi sao cho có thӇ dùng ít bӝ nhӟ chính và phө khi làm viӋc). SV ne t.vn - 38 - 5.HiӋu năng cao (không có các chi phí cho viӋc truyӅn thông, khóa, phân tích cú pháp các câu SQL và thӵc hiӋn các câu truy vҩn). 6.Khҧ năng chӏu lӛi tӕt (cѫ chӃ thӵc hiӋn giao tác). 7.Khҧ năng phөc hӗi nhanh chóng khi gһp sӵ cӕ. 8.Không cҫn phҧi quҧn lý database nhiӅu vì database chӍ bao gӗm mӝt file duy nhҩt, viӋc các file log cӫa database quá lӟn sӁ không còn nӳa, hiӋu Qăng làm viӋc sӁ tăng cao. 'ƭ nhiên, PERST cNJng có các khuyӃt ÿLӇm tѭѫng ӭng: 1. Không hӛ trӧ ngôn ngӳ truy vҩn. 2. Không thích hӧp cho viӋc hӛ trӧÿa ngѭӡi dùng truy cұp database (NӃu muӕn chúng ta phҧi tӵ thiӃt kӃ mӝt server riêng, server này sӁ nhұn các yêu cҫu tӯ client rӗi tuҫn tӵ truy xuҩt database rӗi mӟi gӱi kӃt quҧ vӅ cho client). 3. Không hӛ trӧ viӋc phân tán dӳ liӋu. 4. Không tuân theo mӝt chuҭn nào cҧ (Ví dө không tuân theo chuҭn ODMG). 2.6 Các thông sӕ cӫa PERST: Phҫn này chúng ta sӁ xem xét sâu hѫn vӅ các thông sӕ cӫa database và các cách sӱ dөng chúng ÿӇ tăng hiӋu năng. 7ӕc ÿӝ truy xuҩt ÿƭa là rҩt chұm so vӟi tӕc ÿӝ truy xuҩt bӝ nhӟ chính. Vì Yұy lѭu giӳ các dӳ liӋu ÿѭӧc truy xuҩt thѭӡng xuyên (data caching) là chìa khóa chính ÿӇ tăng hiӋu năng làm viӋc cӫa cѫ sӣ dӳ liӋu. PERST dùng “ pool of pages” ÿӇ tӕi ѭu hóa viӋc truy cұp ÿƭa. Kích thѭӟc cӫa page pool có thӇ SV ne t.vn - 39 - ÿѭӧc xác ÿӏnh trong phѭѫng thӭc Storage.Open khi mӣ database (giá trӏ mһc ÿӏnh cӫa thông sӕ này là 4Mb). Thông thѭӡng tăng kích thѭӟc page pool sӁ Wăng hiӋu năng làm viӋc cӫa chѭѫng trình. Nhѭng chúng ta phҧi lѭu ý nhӳng ÿLӇm sau trѭӟc khi quyӃt ÿӏnh có tăng kích thѭӟc page pool hay không. 1. Có thӇӭng dөng chӍÿѭӧc cҩp mӝt lѭӧng nhҩt ÿӏnh memory nào ÿó khi làm viӋc thôi. 2. NӃu chúng ta tҥo ra page pool có kích thѭӟc quá lӟn, không ÿӇ lҥi ÿӫ chӛ cho hӋÿLӅu hành và các ӭng dөng khác làm viӋc thì toàn bӝ hӋ thӕng VӁ bӏҧnh hѭӣng chung, sӁ giҧm hiӋu năng do hӋ thӕng phҧi swap bӝ nhӟ liên tөc. 3. Bҧn thân hӋ ÿLӅu hành cNJng có cѫ chӃ cache dӳ liӋu cӫa riêng mình Eҵng file buffer. Vұy dӳ liӋu thұt sӵÿѭӧc cache hai lҫn. Tuy nhiên viӋc truy xuҩt dӳ liӋu tӯ page pool sӁ nhanh hѫn do không phҧi có các lӋnh gӑi hàm hӋ thӕng cNJng nhѭ chuyӇn ngӳ cҧnh (switch context) khi gӑi hàm. 4. ViӋc tҥo page pool có kích thѭӟc quá nhӓ hoһc thұm chí bҵng 0 (giao viӋc cache data toàn bӝ cho hӋÿLӅu hành) cNJng không thӇ vì sӁ gây ra lӛi. Khi dӳ liӋu ÿѭӧc truy cұp tӯ bӝ nhӟ phө, nó sӁÿѭӧc ÿѭa lên chӭa trong page pool. Có nghƭa là page pool phҧi ÿѭӧc thiӃt lұp cho ÿӫ lӟn ÿӇ có thӇ chӭa ÿѭӧc các trang này. Vì vұy, không nên tҥo page pool có kích thѭӟc bé hѫn 64kb. 1Ӄu chúng ta nghƭ rҵng mӑi dӳ liӋu nên ÿӇ hӃt trong bӝ nhӟ chính, chúng ta có thӇ dùng hҵng sӕ Storage.INFINITE_PAGE_POOL trong phѭѫng thӭc Storage.Open cӫa database. Trong trѭӡng hӧp này, page pool sӁ tӵ ÿӝng ÿѭӧc tăng kích thѭӟc mӛi khi có mӝt trang mӟi cҫn ÿѭa vào bӝ nhӟ chính. SV ne t.vn - 40 - Có nghƭa là lҫn lѭӧt mӑi trang sӁ ÿѭӧc cache và hiӋn diӋn trong bӝ nhӟ chính, chúng chӍÿѭӧc ÿӑc tӯ bӝ nhӟ phө lҫn ÿҫu tiên thôi. Trong trѭӡng hӧp này “strong object cache” sӁ ÿѭӧc dùng thay vì “weak object cache”. Có nghƭa là ÿӕi tѭӧng ÿѭӧc lҩy ra tӯ cѫ sӣ dӳ liӋu sӁ ÿѭӧc lѭu trong bӝ nhӟ chính và ÿӕi tѭӧng chӍÿѭӧc cҫn ÿѭӧc ÿӑc mӝt lҫn thôi. Chúng ta cNJng cҫn Oѭu ý rҵng kích thѭӟc database trong bӝ nhӟ chính sӁ lӟn hѫn trên bӝ nhӟ phө vì các ÿӕi tѭӧng sӁ tӗn tҥi trong bӝ nhӟ chính dѭӟi cҧ hai dҥng: Dҥng “gӕc”(packed: trong trang chӭa ÿӕi tѭӧng) và dҥng “ÿã có hình dáng” (unpacked: tham chiӃu tӯ bӝ cach ÿӕi tѭӧng). Trong mӝt vài ӭng dөng (nhѭ các ӭng dөng trên các thiӃt bӏ di ÿӝng), khҧ Qăng lѭu trӳ là không cҫn thiӃt nhѭng các lӟp bao chӭa (container class) cӫa PERST nhѭ Link, Index, FieldIndex, SpatialIndex… vүn có thӇÿѭӧc dùng. Trong trѭӡng hӧp này ta sӁ dùng cài ÿһt NullFile cӫa interface IFile cùng vӟi thông sӕ Storage.INFINITE_PAGE_POOL ÿӇ tҥo ra “database” trong bӝ nhӟ chính. Data trong trѭӡng hӧp này sӁ không phҧi ghi vào bӝ nhӟ phө. Có mӝt vài hҵng sӕ ÿѭӧc ÿӏnh nghƭa sҹn trong lӟp StorageImpl có ҧnh Kѭӣng ÿӃn kích thѭӟc khӣi ÿҫu và kích thѭӟc tӕi ÿa cӫa database. NӃu ta muӕn thay ÿәi các thông sӕ này, ta sӁ phҧi biên dӏch lҥi PERST. Thông sӕ Giá trӏ Pһc ÿӏnh Mô tҧ dbDefaultInitTi ndexSize 1024 Kích thѭӟc khӣi ÿҫu cӫa mҧng chӍ mөc ÿӕi tѭӧng. 0ҧng này sӁÿѭӧc tăng kích thѭӟc khi cҫn thiӃt. ViӋc cҩp phát lҥi vùng nhӟ cho mҧng này có chi SV ne t.vn - 41 - phí cao nên ÿӇ hҥn chӃ tác vө này, kích thѭӟc cӫa Pҧng chӍ mөc ÿӕi tѭӧng luôn ÿѭӧc cҩp phát dӵ trӳ gҩp ÿôi. Vұy viӋc cҩp phát vùng nhӟ cho Pҧng chӍ mөc ÿӕi tѭӧng lӟn hѫn sӁ giúp tăng hiӋu Qăng chѭѫng trình mӝt ít nhѭng bù lҥi sӁ làm tăng kích thѭӟc khӣi ÿҫu cӫa database. Vӟi giá trӏ mһc ÿӏnh cӫa thông sӕ này, kích thѭӟc ban ÿҫu cӫa database mӟi tҥo là khoҧng 50Kb dbDefaultExten sionQuantum 4Mb Ĉây chính là kích thѭӟc cҩp phát vùng nhӟ thêm trong PERST. Bӝ nhӟÿѭӧc cҩp phát bҵng cách quét Bitmap. NӃu không có ÿӫ chӛ trӕng liên tiӃp cho ÿӕi tѭӧng, database sӁÿѭӧc tăng kích thѭӟc Eҵng giá trӏ dbDefaultExtensionQuantum. Tăng giá trӏ cӫa tông sӕ này dүn ÿӃn viӋc PERST ít phҧi scan lҥi Bitmap tӯÿҫu, tӕc ÿӝ cӫa mӛi lҫn cҩp phát bӝ nhӟ sӁ tăng và các ÿӕi tѭӧng ÿѭӧc cҩp phát sӁ có nhiӅu cѫ hӝi nҵm liên tiӃp nhau hѫn. Nhѭ vұy sӁ dӉ tăng hiӋu năng chѭѫng trình nhѭng ngѭӧc lҥi ÿây có thӇ là mӝt sӵ sӱ dөng bӝ nhӟ không hiӋu quҧ. Và viӋc giҧm giá trӏ này sӁ gây tác dөng ngѭӧc lҥi ÿӕi vӟi nhӳng tác dөng khi Wăng nó. dbObjectCacheI nitSize 1319 Kích thѭӟc cӫa vùng cache ÿӕi tѭӧng. PERST dùng vùng này ÿӇ kiӇm tra xem liӋu ÿӕi tѭӧng vӟi Vӕ OID nào ÿó ÿã hiӋn diӋn trên bӝ nhӟ chính hay SV ne t.vn - 42 - chѭa. Vùng cache này dùng “weak reference” ÿӇ Eӝ dӑn rác có thӇ làm nhiӋm vө. Mӛi khi cache bӏ ÿҫy, cache sӁÿѭӧc cҩp phát lҥi vӟi kích thѭӟc khoҧng gҩp ÿôi lҫn trѭӟc. Mӝt lҫn nӳa, nӃu ta Wăng thông sӕ này thì sӁ làm giҧm sӕ lҫn phҧi cҩp phát lҥi vùng nhӟ cache. %ҧng 2.6-1 Hҵng sӕÿѭӧc ÿӏnh nghƭa sҹn trong lӟp StorageImpl 'ѭӟi ÿây là các cách ÿӇ tăng hiӋu năng và giҧm lѭӧng bӝ nhӟ chính phҧi Vӱ dөng. NӃu chѭѫng trình cӫa chúng ta thӵc hiӋn nhiӅu thao tác update các ÿӕi tѭӧng trên cѫ sӣ dӳ liӋu thì giӟi hҥn chính là thӡi gian ghi ÿƭa. NӃu chúng ta thӵc hiӋn lӋnh commit database mӛi khi có sӵ thay ÿәi thì trung bình ta thӵc hiӋn ÿѭӧc 10 lҫn commit nhѭ vұy trong mӝt giây (Giӟi hҥn này giҧ thiӃt rҵng mӛi thao tác truy cұp ÿƭa mҩt 10ms và mӛi giao tác khi commit Fҫn ghi xuӕng ÿƭa khoҧng 10 trang bҩt kǤ trong cѫ sӣ dӳ liӋu). Nhѭng ta có thӇ tăng hiӋu năng cӫa thao tác update mӝt cách ÿáng kӇ nӃu ta nhóm các thao tác update lҥi vӟi nhau trong cùng mӝt giao tác. PERST tҥo ÿӕi tѭӧng copy cӫa các ÿӕi tѭӧng cҫn update khi lҫn ÿҫu tiên nó bӏ thay ÿәi trong giao tác. NӃu ÿӕi tѭӧng bӏ update trong N giao tác mӛi giao tác mӝt lҫn thì N bҧn copy sӁÿѭӧc tҥo nhѭng nӃu ÿӕi tѭӧng bӏ update N lҫn trong mӝt giao tác thì chӍ mӝt bҧn copy ÿѭӧc tҥo ra. Ĉây chính là lӧi ích dӉ thҩy nhҩt cӫa viӋc thӵc hiӋn các giao tác lӟn, dài. Nhѭng nӃu ta thӵc hiӋn viӋc update cho nhiӅu ÿӕi tѭӧng trong cùng mӝt giao tác thì rõ ràng sӁ dүn ÿӃn viӋc tăng kích thѭӟc database vì các bҧn copy các ÿӕi tѭӧng ÿѭӧc tҥo ra nhiӅu mà viӋc giҧi phóng vùng nhӟ cNJ chӍÿѭӧc thӵc hiӋn khi commit giao tác. Vì vұy, cách tӕt nhҩt (mӝt cách tѭѫng ÿӕi) là SV ne t.vn - 43 - thӵc hiӋn lӋnh commit sau khoҧng 100 ÿӃn 1000 lҫn update, làm nhѭ vұy sӁ giҧm ÿѭӧc chi phí cӫa mӛi lҫn commit mà vүn không làm tăng kích thѭӟc database ÿáng kӇ. 1Ӄu các ÿӕi tѭӧng cӫa chѭѫng trình ÿѭӧc tә chӭc dѭӟi dҥng cây hay danh sách liên kӃt thì mӝt khi ta ÿã load lên bӝ nhӟ chính ÿӕi tѭӧng gӕc cӫa cây hay danh sách liên kӃt và ÿӕi tѭӧng ÿó ÿѭӧc tham chiӃu tӯ mӝt biӃn cӫa chѭѫng trình thì bӝ dӑn rác sӁ không thӇ nào thu dӑn ÿѭӧc bҩt cӭÿӕi tѭӧng nào ÿѭӧc load lên tӯÿӕi tѭӧng gӕc (vì ÿӕi tѭӧng ÿó có thӇÿѭӧc tham chiӃu Wӯÿӕi tѭӧng gӕc bҩt cӭ lúc nào). Cӭ nhѭ vұy khi ta truy xuҩt lҫn lѭӧt cho ÿӃn hӃt các ÿӕi tѭӧng trong cây hay danh sách liên kӃt ÿó thì toàn bӝ các ÿӕi Wѭӧng sӁ nҵm trong bӝ nhӟ chính. ĈLӅu này có thӇ dүn ÿӃn sӵ tràn bӝ nhӟ. Vì Yұy ta nên cҭn thұn, không nên ÿӇ mӝt biӃn nào ÿó tham chiӃu ÿӃn ÿӕi tѭӧng Jӕc cӫa cây mà không quҧn lý chһt. Tuy nhiên, vӟi các lӟp bao chӭa cӫa PERST, truy xuҩt các ÿӕi tѭӧng bҵng khóa nhѭ Index, SpatialIndex, FieldIndex… thì lo lҳng này là không cҫn thiӃt vì các ÿӕi tѭӧng thành phҫn Fӫa các ÿӕi tѭӧng này sӁ bӏ bӝ don rác thu gom bình thѭӡng. Ĉôi ÿLӅu ghi chú thêm: Khi nào thì nên dùng cҩu trúc nào cho viӋc lѭu trӳ: 1. Link: Dùng cho các tұp hӧp nhӓ (sӕÿӕi tѭӧng trong tұp hӧp khoҧng 100 trӣ xuӕng). 2. FieldIndex: Dùng cho các tұp hӧp có sӕ phҫn tӱ lӟn (khoҧng hѫn 100). ChӍ mөc ÿѭӧc tҥo trên mӝt trѭӡng cӫa ÿӕi tѭӧng hay nhiӅu trѭӡng (trong trѭӡng hӧp này ÿѭӧc gӑi là khóa phӭc) cӫa ÿӕi tѭӧng. FieldIndex ÿѭӧc cài SV ne t.vn - 44 - ÿһt bҵng B+Tree. Kích thѭӟc trang BTree là 4kb, vì vұy kích thѭӟc nhӓ nhҩt ÿѭӧc dùng bӟi index là 4kb. 3. Index: CNJng dùng cho các tұp hӧp có sӕ phҫn tӱ lӟn. ViӋc ÿánh chӍ mөc cho Index ÿѭӧc thӵc hiӋn ngay lúc thêm ÿӕi tѭӧng vào Index. 4. BitIndex: dùng cho tұp hӧp các ÿӕi tѭӧng vӟi khóa là các trѭӡng có giá trӏ nhӏ phân. 5. SpatialIndex: dùng cho dӳ liӋu không gian vӟi khóa là tӑa ÿӝ cӫa các ÿӕi tѭӧng. SpatialIndex ÿѭӧc cài ÿһt bҵng cây RTree cӫa Guttman. 2.7 6ѫ lѭӧc vӅ RTree: 2.7.1 Giӟi thiӋu: HiӋn nay, trong các lƭnh vӵc ӭng dөng máy tính nhѭ CAD (Computer Aided Design) hay Geo-data Application, viӋc xӱ lý dӳ liӋu không gian (spatial data – gҳn liӅn vӟi tӑa ÿӝ, vӏ trí cӫa mӝt ÿӕi tѭӧng) rҩt cҫn ÿӃn mӝt Fҩu trúc dӳ liӋu hiӋu quҧ trong viӋc thao tác trên dӳ liӋu liên quan ÿӃn tӑa ÿӝ, Yӏ trí cӫa các ÿӕi tѭӧng. Tuy nhiên, các cҩu trúc dӳ liӋu cәÿLӇn không thích Kӧp cho công viӋc này. Vì vұy, chúng ta sӁ tìm hiӇu mӝt loҥi cҩu trúc dӳ liӋu Pӟi: RTree, có khҧ năng ÿáp ӭng các yêu cҫu trên. 2.7.2 6ѫ lѭӧc vӅ dӳ liӋu không gian (spatial data) và các giҧi pháp: Các ÿӕi tѭӧng cӫa dӳ liӋu không gian (quұn, huyӋn, khu vӵc, ÿӗi núi, sông ngòi…) thѭӡng bao phӫ mӝt vùng trong không gian n chiӅu nào ÿó (n=2,3…) chӭ thѭӡng không thӇ hiӋn bҵng mӝt ÿLӇm ÿѫn thuҫn. ĈӇ dӉ hình SV ne t.vn - 45 - dung, các ví dөÿѭӧc nêu sӁ tұp trung vào không gian mһt phҷng 2 chiӅu, các không gian nhiӅu chiӅu khác sӁ áp dөng tѭѫng tӵ. Ví dө: 1 quұn sӁ bao phӫ mӝt vùng không gian xác ÿӏnh trong không gian 2 chiӅu. 0ӝt trong nhӳng thao tác thѭӡng xuyên nhҩt trong nhӳng ӭng dөng có liên quan ÿӃn dӳ liӋu không gian nhѭ CAD, CAM, GIS là tìm xem có tҩt cҧ bao nhiêu ÿӕi tѭӧng nҵm trong mӝt vùng nào ÿó. Vì vұy khҧ năng xác ÿӏnh ÿӕi tѭӧng dөa vào tӑa ÿӝ, vӏ trí cӫa ÿӕi tѭӧng mӝt cách nhanh và chính xác là Yҩn ÿӅ rҩt quan trӑng. Rõ ràng, các cҩu trúc cә ÿLӇn không thích hӧp vӟi viӋc tìm kiӃm trong không gian nhiӅu chiӅu. Cө thӇ: Các cҩu trúc dӵa trên giá trӏ chính xác nhѭ HashTable không thích hӧp vì yêu cҫu thѭӡng là tìm trong khoҧng còn các Fҩu trúc hӛ trӧ tìm trong khoҧng nhѭ BTree hay ISAM index thì không thích Kӧp cho không gian nhiӅu chiӅu. Thӵc tӃÿã có nhiӅu công trình nghiên cӭu nhҵm tìm ra giҧi pháp cho vҩn ÿӅ này, trong ÿó RTree là mӝt giҧi pháp tӕt. Các giҧi pháp khác nhѭ Cell, QuadTree, k-d Tree, K-D-B Tree, Corner stiching, Grid file, … ÿӅu có nhѭӧc ÿLӇm riêng. 2.8 So sánh vӟi các hӋ quҧn trӏ cѫ sӣ dӳ liӋu hѭӟng ÿӕi Wѭӧng khác: Trên thӏ trѭӡng hiӋn có không nhiӅu hӋ quҧn trӏ cѫ sӣ dӳ liӋu nhúng cho Java và C# nhѭng bҥn băn khoăn không biӃt chӑn hӋ quҧn trӏ nào cho phù Kӧp.Bӣi không có cái gì là hoàn hҧo. Ӣÿây xin ÿѭa ra 6 hӋ quҧn trӏ khác nhau ÿó là ObjectStore PSE Pro cӫa Progress Software, FastObject cӫa SV ne t.vn - 46 - Versant, Berkelay DB JE cӫa Sleepycat, JISP cӫa CoyoteGulch, db4o cӫa db4oObjects, và PERST.cӫa Knizhnik. Sau ÿây là bҧng so sánh các ÿһc tính Fѫ bҧn cӫa 6 hӋ quҧn trӏ: OODBMS Ngôn ngӳ Kӛ trӧ &ҩp phát vùng nhӟ +ӛ trӧ giao tác Scheme Evaluation Ngôn ngӳ truy Yҩn TiӅn [ӱ lý ObjectStore PSE Pro C++ Java Khai báo Wѭӡng minh hay ngҫm ÿӏnh (nhѭ Gabage Collection) Log file Dùng cѫ chӃ Serialization. Truy vҩn theo thuӝc tính ÿӇ tìm kiӃm ÿӕi Wѭӧng trong tұp Kӧp %ҳt buӝc Db4o Java C# (Standard, Compact và nhӳng Framwork ÿѫn) Khai báo Wѭӡng minh Không Kӛ trӧ phөc Kӗi khi KӋ thӕng có sӵ Fӕ. Có thӇ thêm, xoá, sӱa các trѭӡng và cұp nhұt qua lҥi giӳa các phiên Eҧn. CNJng có thӇ thay ÿәi tên và trѭӡng Fӫa các lӟp. Không có ngôn ngӳ truy Yҩn nhѭng cung cҩp API cho viӋc tҥo ÿӕi Wѭӧng truy vҩn. Không bҳt buӝc Berkeley Java Khai báo Tùy Không Không Không bҳt SV ne t.vn - 47 - DB JE Wѭӡng minh chӑn buӝc JISP Java Khai báo Wѭӡng minh Không Không Không Không bҳt buӝc FastObject Java C# J# VB Khai báo Wѭӡng minh Có Có JDOQL Bҳt buӝc PERST Java (bao Jӗm cҧ JDK 1.5), C# (Standard, Compact và Framwork ÿѫn) Khai báo Wѭӡng minh hay ngҫm (nhѭ Background Gabage Collection) ÿӕi Wѭӧng ÿúp hay ÿӕi Wѭӧng bóng Lazy scheme evaluation Không Kӛ trӧ ngôn ngӳ truy Yҩn Không bҳt buӝc, Và có thӇ tích hӧp Yӟi ASpectJ và JAssist ÿӇ cung cҩp tính trong suӕt trong Oұp trình (tranparent persistent) %ҧng 2.8-1 So sánh các ÿһc tính cӫa các hӋ quҧn trӏ ĈӇ so sánh tӕc ÿӝ cӫa các hӋ quҧn trӏ cѫ sӣ dӳ liӋu, ta cài ÿһt mӝt ví dө thӵc hiӋn các chӭc năng ÿѫn giҧn nhѭ lѭu trӳ dӳ liӋu (Storing), lҩy dӳ liӋu (Fetching), ÿӏnh vӏÿӕi tѭӧng (Locating) bҵng phѭѫng pháp chӍ mөc trên hai ngôn ngӳ là C# và Java vӟi các hӋ quҧn trӏ cѫ sӣ dӳ liӋu tѭѫng ӭng.. Ví dө này ÿѭӧc thӵc hiӋn theo ba bѭӟc cѫ bҧn nhѭ sau: + Ĉҫu tiên là tҥo ngүu nhiên ÿӕi tѭӧng có khoá kiӇu long và khoá kiӇu string, trong ÿó chӍ mөc là kiӇu string. Sau ÿó lѭu vào cѫ sӣ dӳ liӋu. SV ne t.vn - 48 - + Sau ÿó tìm kiӃm các ÿӕi tѭӧng dùng khoá long và string. + Cuӕi cùng là tìm và xóa tӯng ÿӕi tѭӧng và cұp nhұt (ÿánh dҩu) vào cѫ sӣ dӳ liӋu. Ĉѫn vӏ thӡi gian mӛi bѭӟc thӵc thi ÿѭӧc tính bҵng giây. Sӕ lѭӧng các ÿӕi Wѭӧng trong mӛi trѭӡng hӧp là giӕng nhau và bҵng 100000. Tҩt cҧ ÿѭӧc kiӇm tra thӱ nghiӋm trên cùng mӝt máy và cҩu hình máy là AMD Athlon 64 (3200+), 1.5Gb RAM, windowsXP. Ngôn ngӳ dùng lұp trình ӣÿây là Csharp và Java ( Sun Java JDK 1.4.2_04). Sau ÿây là bҧng kӃt quҧ, bҧng sҳp tăng dҫn theo thӡi gian thӵc hiӋn: +Ӌ quҧn trӏ Ngôn ngӳ %ѭӟc Tҥo dӳ liӋu %ѭӟc tìm kiӃm %ѭӟc xóa dӳ liӋu PERST Java 3 775 1 683 3 275 PERST CSharp 4 446 2 403 3975 ObjectStore PSE Pro Java 8 272 9 413 3 104 FastObjects J2 Java 13 399 10 856 38 435 FastObjects.Net CSharp 43 012 2 714 7 461 Db4o – 4.0 Java 18 457 6 279 38 886 DB4o – 4.0 CSharp 31 725 41 099 88 517 Berkeley DB JE Java(*) 15 513 10 755 12 758 JISP Java 350 674 343 063 527 248 SV ne t.vn - 49 - %ҧng 2.8-2 Bҧng so sánh kӃt quҧ cӫa các hӋ quҧn trӏ cѫ sӣ dӳ liӋu hѭӟng ÿӕi tѭӧng (*) – JE dùng Xmxl128M ÿӇ tránh tràn bӝ nhӟ, và ÿLӅu này làm cho thӡi gian chӍ sai sӕ xҩp xӍ 64 giây nên chúng ta không cҫn phҧi quan tâm. 'ӵa vào bҧng so sánh kӃt quҧ trên thì chúng ta nhұn ra rҵng PERST nhanh nhҩt, giӡ thì không phҧi băn khoăn chӑn lӵa giӳa các hӋ quҧn trӏ nӳa. Chúng ta hãy chӑn PERST ÿӇ cho ra mӝt ӭng dөng tӕi ѭu vӅ tӕc ÿӝ. SV ne t.vn - 50 - CHѬѪNG 3 : Giӟi thiӋu vӅ mô hình Topology 3.1 Giӟi thiӋu: 'ӳ liӋu Topology ÿѭӧc xây dӵng tӯ các ÿӕi tѭӧng hình hӑc cѫ bҧn và chúng có quan hӋ vӟi nhau. Mӭc ÿӝ quan hӋ tuǤ thuӝc vào cҩp Topology. 0ӝt vҩn ÿӅ khó khăn khi xây dӵng các ӭng dөng dӵa trên dӳ liӋu Topology là nguӗn dӳ liӋu Topology không có sҹn. Muӕn có dӳ liӋu Topology chúng ta phҧi chuyӇn tӯ dӳ liӋu hình hӑc cѫ bҧn thành dӳ liӋu Topology. Và các phѭѫng pháp hay công cө chuyӇn ÿәi còn ít ÿѭӧc hӛ trӧ. Trong nӝi dung ÿӅ tài, chúng ta sӁ xây dӵng công cөÿӇ chuyӇn ÿәi dӳ liӋu tӯ dҥng Text thành Gӳ liӋu Topology nhѭ mong muӕn. 3.2 Các khái niӋm cѫ bҧn trong Topology: Start Node: Nút bҳt ÿҫu cӫa cҥnh. End Node: Nút kӃt thúc cӫa cҥnh. Right Edge: Cҥnh ÿҫu tiên gһp khi di chuyӇn ngѭӧc chiӅu kim ÿӗng hӗ quanh nút kӃt thúc cӫa cҥnh hiӋn tҥi. Left Edge: Cҥnh ÿҫu tiên gһp khi di chuyӇn ngѭӧc chiӅu kim ÿӗng hӗ quanh nút bҳt ÿҫu cӫa cҥnh hiӋn tҥi. First Edge: Cҥnh ÿѭӧc chӑn ngүu nhiên, ÿѭӧc xem nhѭ là cҥnh ÿҫu tiên cho viӋc tìm kiӃm các cҥnh kӅ cӫa nút. SV ne t.vn - 51 - Hình 3.2-1 Các ÿӕi tѭӧng trong mô hình Topology 0ӝt sӕ khái niӋm cѫ bҧn trong mô hình Topology. Left Face: Mһt ӣ bên trái cӫa cҥnh khi di chuyӅn tӯ nút bҳt ÿҫu ÿӃn nút kӃt thúc. Right Face: Mһt ӣ bên phҧi cӫa cҥnh khi di chuyӇn tӯ nút bҳt ÿҫu ÿӃn nút NӃt thúc. Minimum Bounding Rectangle (MBR): Khung chӳ nhұt nhӓ nhҩt chӭa toàn bӝÿӕi tѭӧng. Inner Ring: Biên trong cӫa mһt. Mӛi ÿӕi tѭӧng vùng có thӇ không có, có Pӝt hoһc nhiӅu biên trong. Outer Ring: Biên bao ngoài cӫa mһt. Mӛi ÿӕi tѭӧng vùng có duy nhҩt mӝt biên ngoài. Ĉ̿c tr˱ng: mô hình cӫa ÿӕi tѭӧng ÿӏa lí thӃ giӟi thӵc. Các ÿӕi tѭӧng này có thӇ là ÿӕi tѭӧng vô hѭӟng, mӝt chiӅu, hai chiӅu và ba chiӅu. 3.3 Các loҥi ÿӕi tѭӧng trong Topology: Có 4 loҥi ÿӕi tѭӧng hình hӑc cѫ sӣ là: SV ne t.vn - 52 - + Node (nút): EntityNode (nút thӵc thӇ), Connected node (nút nӕi NӃt) +Edge (cҥnh) +Face (mһt) + Text (văn bҧn): chӍ làm rõ ÿӕi tѭӧng chӭ không thӇÿѭӧc liên kӃt Yӟi nhau bӣi mӕi quan hӋ Topology Nodes: Là các ÿӕi tѭӧng vô hѭӟng dùng ÿӇ lѭu trӳ các vӏ trí có ý nghƭa. + Entity node: là các node không nҵm trên cҥnh, nó chӍÿѭӧc liên NӃt vӅ mһt Topology vӟi mһt chӭa nó (ví dө nhѭ thӫÿô). Nó dùng ÿӇ thӇ hiӋn nhӳng ÿһc trѭng riêng biӋt hoһc các ÿLӇm khҧo sát, hay các ÿӕi tѭӧng thӇ hiӋn ӣ mӝt tӍ lӋ nào ÿó. + Connected node: Là các node nҵm ÿҫu mút cӫa cҥnh, nó có thӇ là ÿLӇm ÿҫu hay diӇm cuӕi cӫa cҥnh. Và ÿѭӧc liên kӃt vӅ mһt Topology vӟi các Fҥnh khác. Mӛi node còn có FirstEdge và có mӝt khung bao nhӓ nhҩt (MBR – Minimum Boundary Rectangle) chӭa nó.Các node kӃt nӕi ÿѭӧc sӱ dөng theo 2 hѭӟng: Ĉӏnh nghƭa các cҥnh vӅ mһt Topology: lúc này các node ÿѭӧc xem nhѭ là ÿLӇm ÿҫu và ÿLӇm cuӕi ThӇ hiӋn các ÿһc trѭng ÿLӇm ÿѭӧc tìm thҩy tҥi ÿҫu và cuӕi cҥnh cӫa các ÿһc trѭng tuyӃn tính: chҷng hҥn nhѭ các cây cҫu, các cӱa cӕng cӫa mӝt con kênh, các ÿLӇm truy cұp tiӋn ích trong lòng ÿҩt, vӟi cách này thì các thuӝc tính sӁÿѭӧc kӃt hӧp vӟi các ÿһc trѭng ÿLӇm ÿѭӧc liên hӋ vӟi các node kӃt Qӕi. Tҩt cҧ các node kӃt nӕi ÿѭӧc chӭa trong bҧng node kӃt nӕi. NӃu nhiӅu Fҥnh giao nhau tҥi mӝt node, chӍ mӝt cҥnh sӁ ÿѭӧc duy trì cho mӛi node SV ne t.vn - 53 - trong bҧng node kӃt nӕi; các cҥnh khác ÿѭӧc liên kӃt bҵng cách sӱ dөng thuұt toán tìm cҥnh kӅÿӇ suy ra. Edge: là ÿӕi tѭӧng cѫ sӣ dùng thӇ hiӋn các vӏ trí cӫa các ÿһc trѭng tuyӃn tính nhѭ con ÿѭӡng và các biên cӫa mһt. Cҥnh ÿѭӧc cҩu thành tӯ 2 hay nhiӅu Fһp toҥÿӝ 2 chiӅu (x,y) hay 3 chiӅu (x,y,z) phân biӋt. Hѭӟng cӫa cҥnh có thӇ ÿѭӧc xác ÿӏnh bӣi trұt tӵ các cһp toҥÿӝ. Cҥnh ÿѭӧc ÿӏnh nghƭa tӯ các node ÿҫu cuӕi. Bên cҥnh các node ÿҫu cuӕi thì cҥnh còn chӭa các thông tin nhѭ RightEdge, LeftEdge, RightFace, LeftFace ÿӇ dӉ dàng truy tìm thông tin và Oҩy các ÿһc trѭng. Mӛi cҥnh có mӝt khung bao nhӓ nhҩt (MBR – Minimum Boundary Rectangle) chӭa nó. Face: ÿѭӧc ÿӏnh nghƭa tӯ cҥnh dùng thӇ hiӋn ÿһc trѭng vùng nhѭ các quӕc gia, thành phӕ. Tұp các cҥnh có quan hӋ Topology hình thanh nên biên cӫa Pһt. Mһt có thӇ có biên trong hoһc biên ngoài và có thӇ chӭa mһt nhӓ hѫn trong nó. Quan hӋ này gӗm mӝt tham chiӃu ÿӃn ÿLӇm khӣi ÿҫu cӫa mӝt biên khép kín cӫa các cҥnh, rӗi theo chiӅu kim ÿӗng hӗÿӇ khép kín biên. Mһt có thӇ có nhiӅu biên (rings); có thӇ có mӝt biên ngoài và không có hoһc có mӝt hoһc nhiӅu biên trong. Các mһt không ÿѭӧc chӗng lҩp nhau, và các mһt trong Pӝt lӟp sӱ dөng toàn bӝ vùng mһt phҷng. Mӛi bҧng mһt có mӝt khung chӳ nhұt bao mһt kӃt hӧp (FBR) chӭa hình chӳ nhұt nhӓ nhҩt bao mӛi mһt. 3.4 Các cҩp cӫa Topology: Có 4 cҩp ÿӝ Topology: 0, 1, 2, 3. Ӣ cҩp 3, các kӃt nӕi vӅ mһt Topology hiӋn diӋn mӝt cách tѭӡng minh. SV ne t.vn - 54 - Ӣ cҩp 0, không có thông tin Topology ÿѭӧc thӇ hiӋn mӝt cách tѭӡng minh. Bҧng tәng kӃt sau tәng kӃt các ÿһc tính cӫa 3 cҩp này và cho mӝt ví dө YӅ mӛi cҩp. &ҩp Tên Các ÿӕi tѭӧng Fѫ sӣ Mô tҧ Ví dө 3 Quan hӋ Topology ÿҫy ÿӫ Node kӃt nӕi, node thӵc thӇ, Fҥnh và mһt %Ӆ mһt ÿѭӧc phân chia bӣi Wұp các mһt ÿѭӧc chӑn Nӻ và phҫn chung duy nhҩt. Các Fҥnh chӍ gһp nhau tҥi các node. 2 Ĉӗ thӏ phҷng Node thӵc thӇ, node kӃt nӕi và cҥnh 0ӝt tұp các Fҥnh và các node ӣÿó khi chiӃu vào bӅ Pһt phҷng, các Fҥnh chӍ gһp nhau tҥi các node 1 Ĉӗ thӏ không Node thӵc thӇ, node kӃt nӕi 7ұp các node thӵc thӇ và các SV ne t.vn - 55 - phҷng và cҥnh cҥnh có thӇ Jһp nhau tҥi các node 0 ThӇ hiӋn hình bao Node thӵc thӇ và cҥnh 7ұp các node thӵc thӇ và các Fҥnh. Các cҥnh chӍ chӭa các Wӑa ÿӝ, không phҧi là node Eҳt ÿҫu và node kӃt thúc. %ҧng 3.4-1 Các cҩp Topology trong các lӟp VPF Các cӝt trong các bҧng cҥnh và bҧng node xác ÿӏnh tính kӃt nӕi và tính kӅ cho quan hӋ Topology, tùy thuӝc vào cҩp ÿӝ Topology. %ҧng sau chӍ ra các cӝt bҳt buӝc trong mӛi bҧng cѫ sӣ cho cҩp Topology ÿѭӧc yêu cҫu. Các ÿһc tính cӫa các cӝt này ÿѭӧc chӍ ÿӏnh trong các ÿӏnh nghƭa. &ҩp Topolog y %ҧng cѫ sӣ Các cӝt bҳt buӝc 3 Mһt RING_PTR 3 Bҧng vòng (Ring table) FACE_ID, START_EDGE, START_NODE, END_NODE, SV ne t.vn - 56 - RIGHT_FACE, LEFT_FACE, RIGHT_EDGE, LEFT_EDGE 3 Node thӵc thӇ CONTAINING_FACE 3-1 Node kӃt nӕi FIRST_EDGE 2-1 &ҥnh START_NODE, END_NODE RIGHT_EDGE, LEFT_EDGE 2-0 Node thӵc thӇ (Không có) 0 Cҥnh (Không có) %ҧng 3.4-2 Các cӝt ÿѭӧc yêu cҫu ÿӇÿӏnh nghƭa quan hӋ Topology trong VPF Ba hình sau sӱ dөng biӇu ÿӗ mӕi quan hӋ thӵc thӇ (ER) ÿӇ miêu tҧ các ÿӕi Wѭӧng cѫ sӣ và các mӕi quan hӋ cӫa chúng ӣ mӛi cҩp Topology. Hình 3.4-1 Quan hӋ Topology cҩp 0 SV ne t.vn - 57 - Hình 3.4-2 Quan hӋ Topology cҩp 1 và 2 SV ne t.vn - 58 - Hình 3.4-3 Quan hӋ Topology cҩp 3 SV ne t.vn - 59 - 3.5 MBR – Minimum Bounding Rectangle: 0ӝt khung bao nhӓ nhҩt ÿѭӧc yêu cҫu trong bҧng cҥnh hoһc bҧng mһt. Vì vòng bên ngoài cӫa mһt tәng thӇ không có thӇ hiӋn hình hӑc nào nên bҧng ghi FBR cho mһt 1 luôn có giá trӏ null cho các XMIN, YMIN, XMAX, YMAX. Tên cӝt Mô tҧ Loҥi Fӝt Loҥi khóa Op/Man ID XMIN YMIN XMAX YMAX Id 7ӑa ÿӝ X nhӓ nhҩt 7ӑa ÿӝ Y nhӓ nhҩt Toҥÿӝ X lӟn nhҩt 7ӑa ÿӝ Y lӟn nhҩt I F/R F/R F/R F/R P N N N N M M M M M %ҧng 3.5-1. Ĉӏnh nghƭa khung chӳ nhұt nhӓ nhҩt MBR SV ne t.vn - 60 - CHѬѪNG 4 : Giӟi thiӋu vӅ GIS 4.1 Giӟi thiӋu vӅ các ӭng dөng và giҧi pháp vӅ GIS: GIS (Geography Information System ) là công nghӋ ra ÿӡi vào nhӳng Qăm 60 cӫa thӃ kӍ 20. Công nghӋ GIS cho phép ÿáp ӭng các nhu cҫu liên quan tӟi quҧn lý cNJng nhѭ khai thác và sӱ dөng các thông tin, dӳ liӋu ÿӏa lý. Tӯ giai ÿRҥn ÿҫu ÿѭӧc sӱ dөng trên các hӋ thӕng máy tính lӟn ӣ Mӻ và Canada, ÿӃn nay, công nghӋ GIS ÿã ÿѭӧc áp dөng và triӇn khai hӃt sӭc rӝng rãi trên phҥm vi toàn thӃ giӟi, trên nhӳng hӋ thӕng máy PC và thӡi gian gҫn ÿây là trên cҧ các thiӃt bӏ PDA. 0ӝt sӕ ӭng dөng GIS nәi tiӃng trên thӃ giӟi hiӋn nay ÿang ÿѭӧc ӭng Gөng rӝng rãi nhѭ MapInfo, Arc/Info, Spatial Database Engine (SDE), ArcView GIS...: ÿѭӧc sӱ dөng vӟi mөc ÿích quҧn lý, tích hӧp, quy hoҥch và khai thác các dӳ liӋu bҧn ÿӗ. 7ҥi ViӋt Nam, công nghӋ GIS cNJng ÿã ÿѭӧc nghiên cӭu và có ÿѭӧc mӝt Vӕ sҧn phҭm có kӃt quҧÿáng khích lӋ. Thӡi gian gҫn ÿây, viӋc nghiên cӭu công nghӋ GIS ÿã cho ra hàng loҥt ӭng dөng áp dөng trong thӵc tӃ tҥi Tp.Hӗ Chí Minh, nhѭ StreetFinder cӫa DolSoft, hӋ thӕng GIS trên website Ngân hàng bҧn ÿӗ trӵc tuyӃn cӫa VDC, DMC, Dolsoft (www.basao.com.vn), hӋ thӕng chӍ dүn giao thông cӫa nhóm AMI Group - Ĉҥi hӑc Khoa hӑc Tӵ nhiên Tp.Hӗ Chí Minh. Các giҧi pháp vӅ GIS thѭӡng ÿѭӧc chia làm hai nhóm chính: • Giҧi quyӃt các bài toán phӭc tҥp liên quan ÿӃn mҥng giao thông nhѭ: Các bài toán nhѭ tìm kiӃm ÿѭӡng ÿi tӕi ѭu, ÿLӅu phӕi lӝ trình giao SV ne t.vn - 61 - thông… thѭӡng ÿѭӧc áp dөng trên các hӋ thӕng máy tính lӟn, có cҩu hình Pҥnh. • HiӇn thӏ và tìm kiӃm các thông tin bҧn ÿӗ. Ĉây là dҥng ӭng dөng bҧn ÿӗÿLӋn tӱ, cung cҩp các khҧ năng cho phép ngѭӡi sӱ dөng xem bҧn ÿӗ và tìm kiӃm mӝt sӕ thông tin cҫn thiӃt, thѭӡng ÿѭӧc áp dөng trên các máy tính thông thѭӡng và nhӓ. 4.2 Mô hình dӳ liӋu cӫa thông tin ÿӏa lý: Câu hӓi ÿһt ra là làm sao ÿӇ chuyӇn ÿәi thông tin bҧn ÿӗ vào máy tính và ngѭӧc lҥi? ĈӇ làm ÿѭӧc ÿLӅu ÿó thì GIS phҧi lѭu trӳ thông tin vӅ Geometry (hình dҥng và vӏ trí ÿӕi tѭӧng ) và Attribute (các thuӝc tính cӫa ÿӕi tѭӧng) Hình 4.2-1 Thông tin cҫn lѭu trӳ +Ӌ thӕng thông tin ÿӏa lý là mӝt hӋ thӕng thu thұp, lѭu trӳ và xӱ lý các thông tin dѭӟi dҥng giҩy, ҧnh, sӕ vӅ các hiӋn tѭӧng tӵ nhiên trong thӃ giӟi thӵc. Trong cѫ sӣ dӳ liӋu ÿѭӧc cҩu thành tӯ thông tin, các thông tin thѭӡng không sӱ dөng ÿѭӧc trӵc tiӃp mà phҧi thông qua mӝt hӋ thӕng các công cө truy xuҩt, tái tҥo lҥi ÿӕi tѭӧng thӃ giӟi thӵc mà ngѭӡi dùng quan tâm. Mӝt ÿӕi tѭӧng ÿѭӧc lѭu trӳ trong cѫ sӣ dӳ liӋu dѭӟi dҥng các thӵc thӇ hình hӑc, ngѭӡi dùng sӁ dùng phҧi tái tҥo lҥi ÿӕi tѭӧng ҩy thông qua các dӳ liӋu hình SV ne t.vn - 62 - Kӑc này. Nhѭ vұy dӳ liӋu là rҩt ÿa dҥng, chúng có mang tính không gian, thӡi gian, ÿѭӧc gӑi là dӳ liӋu ÿӏa lý. Tóm lҥi dӳ liӋu ÿӏa lý là các dӳ liӋu sӕ mô tҧ các ÿӕi tѭӧng trong thӃ giӟi thӵc. 'ӳ liӋu ÿLҥ lý ÿѭӧc tә chӭc thành hai nhóm thông tin chính, ÿó là: 1/ Nhóm thông tin vӅ phân bӕ không gian. 2/ Nhóm thông tin vӅ thuӝc tính cӫa ÿӕi tѭӧng. Không giӕng nhѭ các dҥng dӳ liӋu thông dөng khác, dӳ liӋu ÿLҥ lý phӭc Wҥp hѫn, nó bao gӗm các thông tin vӅÿLҥ lý, các quan hӋ Topology và các thuӝc tính phi không gian. Mӑi dӳ liӋu ÿLҥ lý có thӇÿѭӧc mô hình vӟi ba thành phҫn khác nhau theo quan niӋm topology – ÿLӇm, ÿѭӡng, vùng.Bҩt kì Pӝt ÿӕi tѭӧng tӵ nhiên nào ÿӅu có thӇÿѭӧc biӇu diӉn bҵng mӝt trong bao ÿӕi tѭӧng này kèm theo chúng là nhӳng thông tin ÿһc thù riêng. Mô hình dӳ liӋu ÿLҥ lý bao gӗm bӕn thành phҫn sau: + Thành phҫn khoá: là mã sӕ duy nhҩt cho thӵc thӇÿӇ phân biӋt thӵc thӇ này vӟi thӵc thӇ khác. + Ĉӏnh vӏ: ChӍ ra vӏ trí cӫa thӵc thӇ. + Thành phҫn phi không gian: Là nhӳng thuӝc tính riêng cho tӯng thӵc thӇ nhѭ tӹ lӋ, khoҧng, ÿӏnh danh …. + Thành phҫn không gian: Các ÿӕi tѭӧng tѭ nhiên bên ngoài ÿѭӧc chuyӇn vào máy tính ÿӇ quҧn lý theo hai cách sau: Raster và Vector Mô hình vectѫ: tѭӡng ÿѭӧc biӇu diӉn duӟi dҥng ÿLӇm, ÿѭӡng và vùng. Vӏ trí không gian cӫa mӝt thӵc thӇÿѭӧc xác ÿӏnh bӣi mӝt hӋ toҥÿӝ thӕng nhҩt toàn cҫu. Mӝt thӵc thӇÿѭӧc xác ÿӏnh bӣi cһp toҥÿӝ (X,Y) và các thuӝc tính khác nhѭ: kiӇu ÿLӇm, màu, hình dҥng. SV ne t.vn - 63 - Hình 4.2-2 Dӳ liӋu Vector Hình 4.2-3 Các thӵc thӇÿѭӧc thӇ hiӋn trên bҧn ÿӗ Mô hình Raster: Dӳ liӋu Raster ÿѭӧc phân biӋt bҵng ÿѫn vӏ pixel, ÿó là hình ҧnh ÿѫn vӏ nhӓ nhҩt phҧn ánh ÿӕi tѭӧng trong không gian. &ҩu trúc dӳ liӋu ratser 2-D ÿѭӧc xem nhѭ là mӝt ma trұn các ô lѭӟi ÿһc trѭng cho mӝt ô vuông bӅ mһt ÿҩt. Ĉӝ phân giҧi cӫa dӳ liӋu raster phө thuӝc vào kích thѭӟc cӫa nhӳng ô lѭӟi này. Hình 4.2-4 Dӳ liӋu raster SV ne t.vn - 64 - 6͹ khác bi͏t giͷa hai ki͋u dͷ li͏u: Cҧ hai kiӇu dӳ liӋu này ÿӅu rҩt hӳu ích nhѭ nhau, nhѭng chúng cNJng có sӵ khác biӋt quan trӑng. Sau ÿây là bҧng so sánh giӳa hai kiӇu dӳ liӋu này. Vector Raster 'ӳ liӋu hiӇn thӏ ít hѫn, nhanh hѫn, chӍ chӫ yӃu hiӇn thӏ các ÿӕi tѭӧng mà không hiӇn thӏÿһc tính cӫa ÿӕi tѭӧng 'ӳ liӋu nhiӅu hѫn, hiӇn thӏ chұm hѫn, không nhӳng hiӇn thӏÿӕi tѭӧng mà còn hiӇn thӏ cҧÿһc tính cӫa ÿӕi tѭӧng %ҧng 4.2-1 Bҧng so sánh kiӇu dӳ liӋu Raster va Vector Hình 4.2-5 So sánh Raster và Vector 4.3 Thu thұp dӳ liӋu: Có nhiӅu kӻ thuұt ÿӇ thu thұp thông tin tӯ các nguӗn dӳ liӋu. Nó thѭӡng ÿѭӧc thu thұp tӯ viӋc ÿo ÿҥc trӵc tiӃp trên thӃ g iӟ i thӵc . Tuy nhiên, mӝt Vӕ lӟn dӳ liӋu liӋu có thӇ ÿѭӧc chuyӇn ÿәi tӯ bҧn ÿӗ giҩy sang hình thӭc Oѭu trӳ cӫa bҧn ÿӗÿLӋn tӱ. Có ba phѭѫng pháp thѭӡng ÿѭӧc sӱ dөng ÿó là Scanning(phѭѫng pháp quét), Digistsing (phѭѫng pháp sӕ hoá), Vectorisation (phѭѫng pháp vecto hoá). SV ne t.vn - 65 - Phѭѫng pháp quét: Ĉây là kӻ thuұt thông dөng mà lҥi ít tӕn kém, có thӇ ÿѭӧc thӵc hiӋn trên các máy tính cá nhân hay cӫa công ty. Máy quét sӁ lѭu trӳ lҥi các hình ҧnh cӫa bҧn ÿӗ giҩy dѭӟi hình thӭc sӕ và hiӇn thӏ chúng trӣ Oҥi màn hình. ViӋc quét hình ҧnh tӯ bҧn ÿӗ giҩy tѭѫng ÿӕi ÿѫn giҧn và nhanh chóng, tuy nhiên phѭѫng pháp này lҥi không thӇ cung cҩp thuӝc tính cӫa các ÿӕi tѭӧng tӵ nhiên nhѭÿLҥ chӍ cӫa mӝt toà nhà hay ngày thành lұp cuҧ mӝt sân vұn ÿӝng nào ÿó. Dӳ liӋu có ÿѭӧc tӯ nhӳng phѭѫng pháp này thѭӡng Gѭӟi dҥng raster cho kích thѭӟc rҩt lӟn. Hình 4.3-1 Phѭѫng pháp Scanning Phѭѫng pháp sӕ hoá: Kӻ thuұt này ÿòi hӓi phҧi cung cҩp các thiӃt bӏ chuyên ngành. Bҧn ÿӗ nguӗn sӁÿѭӧc trãi bӅ mһt ngang, mӝt con trӓ sӁ xác ÿӏnh tӑa ÿӝ các ÿLӇm tҥo nên hình dҥng bҧn ÿӗ, sau quá trình sӕ hoá, thuӝc tính cӫa các ÿӕi tѭӧng mӟi ÿѭӧc thêm vào. Phѭѫng pháp này ÿòi hӓi nhiӅu thӡi gian và nguӗn dӳ liӋu có ÿѭӧc tӯ kӻ thuұt này dѭӟi hình thӭc Vectѫ. SV ne t.vn - 66 - Hình 4.3-2 Phѭѫng pháp sӕ hoá Phѭѫng pháp Vector hoá: Mӝt vài hӋ thӕng máy tính chuyên nghiӋp có thӇ chuyӇn ÿәi dӳ liӋu Raster sang dҥng dӳ liӋu Vectѫ. Phѭѫng pháp này cho tӕc ÿӝ nhanh do tính tӵÿӝng nhѭng lҥi kém chính xác hѫn so vӟi viӋc sӕ hoá thӫ công. Các kӻ thuұt trên ÿӅu dӵa vào nguӗn dӳ liӋu bҧn ÿӗ giҩy có sҹn. Trên thӵc tӃ, ngѭӡi ta còn dӵa vào các ngành lƭnh vӵc khác nhѭ: viӉn thám, GPS, phân tích ҧnh… ÿӇ thu thұp nguӗn dӳ liӋu cho GIS. 4.4 Các giҧi thuұt nghiên cӭu vӅ GIS: Công nghӋ GIS liên quan trӵc tiӃp tӟi lý thuyӃt ÿӗ thӏ cNJng nhѭ trí tuӋ nhân tҥo trong viӋc ÿѭa ra các giҧi thuұt ÿӇ giҧi quyӃt các bài toán liên quan. Ĉây là nhӳng lƭnh vӵc nghiên cӭu ÿѭӧc ÿҫu tѭ rҩt nhiӅu vӟi các cҧi tiӃn cNJng nhѭÿã ÿѭa ra ÿѭӧc nhiӅu giҧi thuұt tӕt hoһc tӕi ѭu (chҷng hҥn nhѭ các giҧi thuұt clipping, kiӇm tra ÿLӇm trong/ngoài ÿa giác hay các giҧi thuұt tìm kiӃm trên cҩu trúc dӳ liӋu hoһc tìm kiӃm lӝ trình tӕi ѭu...) Các bài toán vӅ GIS hiӋn nay vүn ÿang ÿѭӧc nghiên cӭu và có nhӳng cҧi tiӃn rҩt tӕt, kӇ cҧ trong các bài toán phӭc tҥp.Công nghӋ GIS vӟi nhӳng lӧi thӃ cӫa nó ÿã mang lҥi phѭѫng pháp quҧn lý hiӋu quҧ hѫn, mӑi sӵ vұt, ÿӕi SV ne t.vn - 67 - Wѭӧng, tӯ nhӳng thông tin không gian ÿӃn nhӳng thông tin phi không gian tҩt FҧÿӅu ÿѭӧc quҧn lý mӝt cách thӕng nhҩt trên cùng hӋ thӕng. Mӑi truy xuҩt ÿӅu thӇ hiӋn trӵc quan hѫn trên bҧn ÿӗ sӕ thay cho nhӳng dòng văn bҧn ÿѫn thuҫn. Chính vì thӃ GIS ngày mӝt trӣ nên quen thuӝc hѫn cho ngѭӡi dùng, nó ÿѭӧc ӭng dөng trong nhiӅu lƭnh viӋc tӯÿѫn giҧn ÿӃn phӭc tҥp và chi phí ÿòi hӓi ÿҫu tѭ ngày mӝt thҩp hѫn. Có thӅ nói rҵng GIS ngày mӝt tӵ khҧÿӏnh Wҫm quan trӑng, ÿѭӧc các nѭӟc phát triӇn xem nhѭ mӝt mNJi nhӑn trong lƭnh công nghӋ thông tin. 4.5 Các cҩu trúc dӳ liӋu không gian trong GIS: 4.5.1 Cây tӭ phân (Quad Tree): Quad Tree ÿѭӧc sӱ dөng ÿӇ lұp chӍ sӕ không gian 2D. Mӛi nút trong cӫa cây chia không gian thành 4 vùng không gian con tách biӋt (ÿѭӧc gӑi là NW, NE, SW, SE) tѭѫng ӭng vӟi các trөc tӑa ÿӝ. Mӛi vùng không gian con này ÿѭӧc tách mӝt cách ÿӋ quy cho ÿӃn khi có nhiӅu nhҩt mӝt ÿӕi tѭӧng bên trong mӛi vùng. Hình 4.5.1-1 Cây tӭ phân SV ne t.vn - 68 - Quad Tree không ÿѭӧc cân bҵng và sӵ cân bҵng cӫa nó phө thuӝc vào sӵ phân bӕ cӫa dӳ liӋu và trұt tӵ chèn dӳ liӋu vào cây. 4.5.2 K-d Tree: Phѭѫng pháp này sӱ dөng mӝt cây nhӏ phân ÿӇ chia không gian k chiӅu. Cây này tách không gian thành hai không gian con tѭѫng ӭng vӟi mӝt trong các tӑa ÿӝ cӫa ÿLӇm ÿang tách. Hình 4.5.2-1 K-D Tree *ӑi level(nod) là chiӅu dài cӫa ÿѭӡng ÿi tӯ nút gӕc ÿӃn nút nod và giҧ sӱ các trөc tӑa ÿӝÿѭӧc ÿánh sӕ tӯ 0 ÿӃn k – 1. Tҥi bұc level(nod)ӣ mӛi nút không gian ÿѭӧc tách tѭѫng ӭng vӟi sӕ tӑa ÿӝ (level(nod) mod k). Thao tác thêm và tìm kiӃm tѭѫng tӵ nhѭÿӕi vӟi cây nhӏ phân. Chúng ta chӍ phҧi so sánh các nút tѭѫng ӭng vӟi sӕ tӑa ÿӝ (level(nod) mode k). Cҩu trúc này có mӝt bҩt lӧi là nhҥy cҧm vӟi trұt tӵ mà các ÿӕi tѭӧng ÿѭӧc thêm vào. SV ne t.vn - 69 - 4.5.3 R-Tree: R-Tree là sӵ biӃn cҧi cӫa B-Tree cho dӳ liӋu không gian. R-Tree là cây cân bҵng và chia không gian thành các khung chӳ nhұt có thӇ chӗng lҩp(phӫ) nhau. Mӛi nút ngoҥi trӯ nút gӕc chӭa tӯ mÿӃn M con ( 2/2 Mm ££ ). Nút gӕc có tӕi thiӇu 2 con ngoҥi trӯ nút lá. Hình 4.5.3-1 R-Tree Nút ÿѭӧc thӇ hiӋn bӣi mӝt khung bao nhӓ nhҩt - MBR(minimum bounding rectangle) chӭa tҩt cҧ các ÿӕi tѭӧng cӫa cây con cӫa nó. Mӛi con Fӫa nút ÿѭӧc tách ÿӋ quy. Các con trӓ trӓÿӃn các ÿӕi tѭӧng dӳ liӋu ÿѭӧc lѭu ӣ các nút lá. Vì các MBR có thӇ chӗng lҩp nên có thӇ cҫn phҧi tìm kiӃm trên nhiӅu nhánh cӫa cây. Do ÿó, các khung chӳ nhұt càng tách biӋt càng tӕt. Vҩn ÿӅ này phҧi ÿѭӧc giҧi quyӃt ӣ thao tác INSERT (chèn) có sӱ dөng mӝt sӕ SV ne t.vn - 70 - heuristic. Thao tác này tìm mӝt nút lá sao cho khi chèn ÿӕi tѭӧng mӟi vào nó VӁ gây nhӳng thay ÿәi nhӓ nhѭ có thӇ. Thao tác tách cNJng quan trӑng. Mөc tiêu là làm giҧm xác suҩt sӁ phҧi tìm Fҧ hai nút mӟi. ViӋc kiӇm tra tҩt cҧ các khҧ năng có ÿӝ phӭc tҥp sӕ mNJ, vì thӃ nhӳng thuұt toán cho lӡi giҧi xҩp xӍ thѭӡng ÿѭӧc sӱ dөng. R-Tree là mӝt trong nhӳng cҩu trúc dӳ liӋu không gian ÿѭӧc ÿӅ cұp ÿӃn nhiӅu nhҩt và nó rҩt thѭӡng ÿѭӧc sӱ dөng ÿӇ so sánh vӟi nhӳng cҩu trúc mӟi. Trong các ӭng dөng GIS, R-Tree ÿóng vai trò quan trӑng trong viӋc chӑn Oӵa ÿӕi tѭӧng hiӇn thӏ cNJng nhѭ kích hoҥt nhanh các ÿӕi tѭӧng ÿӗ hӑa. 4.5.4 R*-Tree: R*-Tree là mӝt biӃn cҧi cӫa R-Tree sӱ dөng heuristic khác cho thao tác INSERT. R-Tree cӕ gҳng tӕi thiӇu vùng cӫa tҩt cҧ các nút cӫa cây. R*-Tree NӃt hӧp nhiӅu tiêu chuҭn: vùng bӏ phӫ bӣi khung chӳ nhұt bao, biên cӫa khung chӳ nhұt và sӵ chӗng lҩp giӳa các khung chӳ nhұt. 0өc tiêu làm giҧm vùng bӏ phӫ bӣi khung chӳ nhұt bao là làm giҧm không gian chӃt, có nghƭa là không gian bӏ phӫ bӣi khung chӳ nhұt bao chӭ không phҧi bӣi các khung chӳ nhұt bӏ chӭa. ĈLӅu ÿó làm giҧm sӕ nhánh tìm kiӃm vô ích. Tӕi thiӇu hóa biên (tәng chiӅu dài các cҥnh) cӫa khung chӳ nhұt bao tӕt hѫn là dùng nhӳng khung vuông. Tӕi thiӇu hóa sӵ chӗng lҩp giӳa các khung chӳ nhұt làm giҧm sӕÿѭӡng phҧi tìm kiӃm. Cài ÿһt phѭѫng pháp này thì khó hѫn, nhѭng R*-Tree hiӋu quҧ hѫn R- Tree nhiӅu. SV ne t.vn - 71 - 4.5.5 R+-Tree: R+-Tree là sӵ mӣ rӝng cӫa R-Tree. Khác vӟi R-Tree, các khung bao cӫa các nút tҥi mӝt mӭc không chӗng lҩp trong cҩu trúc này. Ĉһc tính này làm giҧm sӕ lѭӧng nhánh phҧi tìm kiӃm cӫa cây và làm giҧm phí tәn thӡi gian. Hình 4.5.5-1 R+-Tree R+-Tree ÿѭӧc phép tách các ÿӕi tѭӧng dӳ liӋu ÿӇ cho nhӳng phҫn khác nhau cӫa mӝt ÿӕi tѭӧng có thӇÿѭӧc lѭu ӣ nhiӅu nút cӫa mӝt mӭc. NӃu mӝt khung chӳ nhұt chӗng lҩp mӝt khung chӳ nhұt khác, nó sӁ bӏ phân rã thành Pӝt nhóm các khung chӳ nhұt không chӗng lҩp nhau. ĈLӅu này làm gia tăng không gian lѭu trӳ nhѭng cho phép loҥi bӓ sӵ chӗng lҩp giӳa các nút và do ÿó làm giҧm phí tәn thӡi gian tìm kiӃm. SV ne t.vn - 72 - 4.6 Ӭng dөng bҧn ÿӗ: 4.6.1 Các kiӇu bҧn ÿӗ: Hình 4.6.1-1 Các kiӇu bҧn ÿӗ Toppographic là bҧn ÿӗ chӍ bao gӗm các ÿһc tính vұt lý ví dө nhѭÿѭӡng, sông, nhà. Contour (ÿѭӡng viӅn): là bҧn ÿӗ bao gӗm các ÿѭӡng nӕi các vӏ trí ÿLӇm có cùng giá trӏ ví dө nhѭ: ÿӝ sâu cӫa biӇn, ÿѭӡng ÿҷng áp. Choropleth: là bҧn ÿӗÿӏa chí. 4.6.2 Các ÿӕi tѭӧng cӫa bҧn ÿӗ: Công nghӋ GIS cNJng cho phép lѭu trӳ thông tin bҧn ÿӗ trong máy tính theo cách máy tính hoá, nghƭa là lѭu trӳ dѭӟi dҥng tұp tin vӟi các cҩu trúc khác nhau. Và tӯÿó bҧn ÿӗ có thӇÿѭӧc lѭu trӳ, thêm, xoá, sӱa mӝt cách dӉ dàng. Nhìn vào vào mӝt bҧn ÿӗ ta cNJng nhұn thҩy ÿѭӧc các ÿӕi tѭӧng chính Fӫa bҧn ÿӗ, nó bao gӗm: Line(ÿѭӡng), Area (vùng), Point (ÿLӇm), và Text (văn bҧn). SV ne t.vn - 73 - Hình 4.6.2-1 Các ÿӕi tѭӧng chính trong bҧn ÿӗ 4.7 Ӭng dөng GIS trên PocketPC: 6ӵ phát triӇn mҥnh mӁ cӫa Internet, cNJng nhѭ khҧ năng cӫa công nghӋ phҫn cӭng, ÿã dүn ÿӃn sӵ ra ÿӡi cӫa các thiӃt bӏӭng dөng Internet. Theo các nhà nghiên cӭu thӏ trѭӡng, mһc dù PC vүn giӳ vai trò chӫ yӃu trong viӋc xӱ lý và hӛ trӧ công viӋc, nhѭng các thiӃt bӏ Internet hay thiӃt bӏ hӛ trӧ cá nhân VӁ ngày càng khҷng ÿӏnh ÿѭӧc vai trò cӫa nó trên thӏ trѭӡng. Ra ÿӡi vào nhӳng năm 90 cӫa thӃ kӍ 20, Pocket PC là mӝt dҥng thiӃt bӏ Fҫm tay PDA (Personal Digital Assistant) sӱ dөng hӋÿLӅu hành Pocket PC, Pӝt biӃn thӇ cӫa Windows CE, mӝt hӋ ÿLӅu hành nhúng ÿѭӧc Microsoft phát triӇn cho các thiӃt bӏ không là PC (non-PC). Do ÿһc trѭng nhӓ gӑn, ÿѭӧc thiӃt kӃ vӟi mөc ÿích giúp ngѭӡi sӱ dөng Oѭu trӳ các thông tin cá nhân, công viӋc cҫn thiӃt cNJng nhѭ các phҫn mӅm tӕi thiӇu trên mӝt thiӃt bӏ nhӓ gӑn, và sӱ dөng mӝt hӋ ÿLӅu hành hӑ hàng Windows, Pocket PC ÿã ÿѭӧc khá nhiӅu nhà sҧn xuҩt phҫn mӅm quan tâm trong lƭnh vӵc phát triӇn ӭng dөng, trong ÿó có các ӭng dөng GIS. Tuy nhiên, Pocket PC chҥy trên nӅn hӋ ÿLӅu hành nhúng Windows CE, KӋÿLӅu hành chӍ cung cҩp bӝ nhӟ mӝt cách giӟi hҥn cho các ӭng dөng phát SV ne t.vn - 74 - triӇn trên nó. Vì vұy, các ӭng dөng liên quan tӟi hӋ thӕng GIS phát triӇn trên Pocket PC và hӋÿLӅu hành Windows CE gһp phҧi các vҩn ÿӅ vӅ tӕi ѭu hoá Eӝ nhӟ cNJng nhѭ tӕc ÿӝ và thѭӡng có tӕc ÿӝ chұm hѫn nhiӅu so vӟi các ӭng dөng trên PC thông thѭӡng. Ngoài ra, do khҧ năng lѭu trӳ có giӟi hҥn, viӋc ӭng dөng GIS trên môi trѭӡng này cNJng gһp không ít khó khăn. Trên thӏ trѭӡng, mӝt sӕ sҧn phҭm GIS trên Pocket PC ÿã ÿѭӧc phә biӃn Uӝng rãi nhѭ Pocket Street cӫa Microsoft, MapInPocket cӫa Information Technologies India Ltd... SV ne t.vn - 75 - CHѬѪNG 5 : Giӟi thiӋu vӅ chuҭn OpenGIS 5.1 Các kiӇu dӳ liӋu hình hӑc cӫa OpenGIS: Các cҩu trúc chӍ mөc không gian, ví dө R-Tree, ÿѭӧc sӱ dөng trong các hӋ quҧn trӏ cѫ sӣ dӳ liӋu không gian (SDBMS) ÿӇ tăng tӕc quá trình xӱ lý các truy vҩn chҷng hҥn nhѭ các truy vҩn vùng hoһc các truy vҩn các ÿӕi tѭӧng lân cұn gҫn nhҩt. Do ÿó, phҫn cài ÿһt các thao tác tìm kiӃm lân cұn thѭӡng sӱ Gөng R-Tree. Tuy nhiên, nӃu các ÿӕi tѭӧng không gian khá phӭc tҥp, viӋc Oҩy các lân cұn cӫa vài ÿӕi tѭӧng theo cách này vүn tiêu tӕn rҩt nhiӅu thӡi gian vì sӵ phӭc tҥp cӫa ÿánh giá các quan hӋ lân cұn trên các ÿӕi tѭӧng ÿó. Thêm vào ÿó, khi tҥo ra tҩt cҧ các ÿѭӡng lân cұn vӟi mӝt ÿӕi tѭӧng nguӗn ÿѭӧc cho, mӝt sӕ lѭӧng rҩt lӟn các thao tác tìm kiӃm lân cұn phҧi ÿѭӧc thӵc hiӋn. NhiӅu hӋ thӕng quҧn trӏ cѫ sӣ dӳ liӋu không gian là khá tƭnh vì không có nhiӅu cұp nhұt trên các ÿӕi tѭӧng chҷng hҥn nhѭ các bҧn ÿӗÿӏa lý. Cho nên các kiӇu dӳ liӋu hình hӑc cùng vӟi nhiӅu thao tác trên các ÿӕi tѭӧng ÿѭӧc các hӋ quҧn trӏ cѫ sӣ dӳ liӋu sau này hӛ trӧ. SV ne t.vn - 76 - Hình 5.1-1 HӋ phân cҩp các kiӇu dӳ liӋu hình hӑc cӫa OpenGIS. 5.2 OpenGIS Specification (ÿһc tҧ OpenGIS): 5.2.1 Các khái niӋm: Ĉһc tҧ OpenGIS (OpenGIS Specification), mӝt ÿһc tҧ toàn diӋn cӫa mӝt Eӝ khung phҫn mӅm cho các truy cұp phân tán ÿӃn geodata và nhӳng tài nguyên geoprocessing. Ĉһc tҧ này cung cҩp cho các nhà phát triӇn phҫn mӅm trên thӃ giӟi mӝt khuôn mүu giao diӋn chung cһn kӁÿӇ viӃt các phҫn mӅm hoҥt ÿӝng chung vӟi các phҫm mӅm dҥng OpenGIS khác.Bӝ khung OpenGIS (OpenGIS framework) gӗm: - Mӝt cách thӭc chung dҥng sӕ thӇ hiӋn Trái ÿҩt và các hiӋn tѭӧng cӫa nó trên cѫ sӣ toán hӑc và khái niӋm. - Mӝt mô hình chung ÿӇ thӵc hiӋn nhӳng truy nhұp, quҧn lý, thao tác, trình bày, và chia sҿ geodata giӳa nhӳng cӝng ÿӗng thông tin. SV ne t.vn - 77 - - Mӝt bӝ khung ÿӇ sӱ dөng mô hình Open Geodata và mô hình dich vө Open GIS ÿӇ giҧi quyӃt vҩn ÿӅ khҧ năng không hoҥt ÿông kӃt hӧp không chӍ YӅ mһt kƭ thuұt mà cҧ vӅ mһt tә chӭc. Các nhà phát triӇn xây dӵng nhӳng hӋ thӕng có giao diӋn thích ӭng OpenGIS Specification sӁ tҥo ra nhӳng phҫn mӅm trung (middleware), phҫn PӅm bӝ phұn (componentware) và nhӳng ӭng dөng có thӇ kiӇm soát mӝt phҥm vi rӝng các kiӇu geodata và các hàm geoprocessing. Ngѭӡi sӱ dөng các hӋ thӕng này có thӇ chia sҿ mӝt không gian dӳ liӋu tiӅm năng rӝng lӟn qua mҥng, dù dӳ liӋu ÿѭӧc sҧn sinh vào các thӡi ÿLӇm khác nhau bӣi các nhóm không liên quan sӱ dөng các hӋ thӕng sҧn xuҩt khác nhau cho nhӳng Pөc ÿích khác nhau và thұt sӵ có thӇÿang hiӋn hӳu dѭӟi sӵÿLӅu khiӇn chính Fӫa hӋ thӕng ÿѭӧc sӱ dөng cho viӋc sҧn xuҩt cӫa hӑ. Geodata kӃ thӯa (Legacy geodata) ÿѭӧc tә chӭc trong các hӋ thӕng có giao diӋn thích ӭng OpenGIS Specification sӁ có thӇÿѭӧc truy xuҩt bӣi các phҫn mӅm có giao diӋn thích ӭng OpenGIS Specification khác. OpenGIS Specification cung Fҩp mӝt bӝ khung cho nhӳng ngѭӡi phát triӇn phҫn mӅm ÿӇ tҥo ra phҫn mӅm cho phép nhӳng ngѭӡi dùng cӫa hӑ truy nhұp và xӱ lý dӳ liӋu ÿӏa lý tӯ nhӳng nguӗn ÿa dҥng qua mӝt giao diӋn tính toán chung bên trong mӝt nӅn Wҧng công nghӋ thông tin mӣ. Ѭu ÿLӇm: Ĉӕi vӟi ngѭӡi phát triӇn ӭng dөng có thӇ dӉ dàng và linh hoҥt hѫn ÿӇ: ViӃt phҫn mӅm ÿӇ truy cұp geodata.ViӃt phҫn mӅm ÿӇ truy cұp nhӳng tài nguyên geoprocessing.Sӱa ÿәi nhӳng ӭng dөng theo nhu cҫu ngѭӡi dùng cө thӇ, tích Kӧp phi không gian và không gian. Và có thӇ chӑn mӝt môi trѭӡng phát triӇn SV ne t.vn - 78 - hay cung cҩp nhӳng ӭng dөng trên nhӳng nӅn tҧng ÿa dҥng và cNJng có thӇ sӱ Gөng lҥi mã geoprocessing Ĉӕi vӟi nhà quҧn lý thông tin linh hoҥt hѫn trong viӋc Truy cұp và / hoһc phân phӕi geodata, cung cҩp nhӳng khҧ năng geoprocessing tӟi nhӳng khách hàng, tích hӧp Dӳ liӋu ÿӏa lý và sӵ xӱ lý vào mӝt kiӃn trúc tính toán liên hӧp và có thӇ chӑn nhӳng nӅn thích hӧp - kiӇu máy tính cá nhân, kiӇu máy chӫ, và kiӇu nӅn tính toán phân tán (