Luận án Phương pháp đánh chỉ số cho tài liệu xml tin sinh học dựa trên R - Tree

các entry từ các node có mức cao hơn phải được đặt cao hơn trong cây, vì vậy các lá của các cây con phụ thuộc vào chúng sẽ nằm trên cùng mức như các lá của cây mẹ. h) Cập nhật (Update) Nếu một bộ dữ liệu được cập nhật để cho hình chữ nhật bao phủ nó bị thay đổi, bản ghi chỉ số của nó phải bị xóa, cập nhật và chèn lại, vì vậy nó sẽ phải tìm cách để đặt đúng vị trí trong cây. 38 Một cách tìm kiếm khác so với cách được mô tả ở trên có thể hữu ích hơn, ví dụ để tìm tất cả các đối tượng dữ liệu được chứa hoàn toàn trong một vùng tìm kiếm, hoặc tất cả các đối tượng chứa vùng tìm kiếm. Các bước thực hiện có thể được thực hiện bằng các biến đổi dễ hiểu trên thuật toán đã cho. Tìm một phần tử cụ thể mà nhận dạng của nó đã được biết trước cần đến thuật toán xóa và được thực hiện bằng thuật toán FindLeaf. Các biến đổi của phạm vi xóa, trong phạm vi này, tất cả các đối tượng dữ liệu trên diện tích liên quan được xóa đi, cũng được R-tree cung cấp khá tốt. i) Thuật toán tách node (Node Splitting) Để thêm một phần tử mới, một node chứa đầy M các chỉ số, cần phải phân chia tập hợp của M+1 các phần tử thành 2 node. Sự phân chia nên được thực hiện theo cách làm cho nó không chắc có thể thực hiện được việc phân chia cả hai node mới sẽ cần được kiểm tra trên việc tìm kiếm thứ tự. Khi đó sự quyết định thăm một node phụ thuộc vào hình chữ nhật bao phủ nó có chồng lên diện tích tìm kiếm. Tổng số diện tích của hai hình chữ nhật bao phủ sau khi tách có thể được giảm đến mức tối thiểu. Hình dưới đây minh họa điều này. Diện tích của các hình chữ nhật trong trường hợp “bad split”lớn hơn nhiều so với trường hợp “good split”. Hình 1.13: Trƣờng hợp phân chia node (a) bad split, (b) good split. Cùng tiêu chuẩn đã được dùng trong thủ tục ChooseLeaf để quyết định xem nơi nào có thể chèn một chỉ số mới vào tại mỗi mức trong cây, cây con được chọn 39 là một cây mà hình chữ nhật bao phủ của nó phải được mở rộng ít Bad nhất khi chèn chỉ số mới vào. Chúng ta quay lại thuật toán phân chia tập M+1 phần tử thành hai nhóm cho mỗi node mới. Hình 1.14: Phân chia phần tử thành các nhóm node mới j) Thuật toán A Quadractic Cost Thuật toán này cố gắng tìm một vùng được tách ra có diện tích nhỏ, nhưng không bảo đảm là có thể tìm được một vùng có thể có diện tích nhỏ nhất. Chi phí là bậc 2 theo M và tuyến tính theo số lượng của các chiều. Thuật toán chọn 2 phần tử trong số M+1 phần tử làm phần tử đầu tiên của hai nhóm mới, bằng cách chọn này, hai phần tử mới này có thể làm lãng phí diện tích lớn nhất nếu cả hai được đặt trong cùng một nhóm. Như vậy diện tích hình chữ nhật bao phủ cả hai phần tử, trừ đi diện tích của chính các phần tử, sẽ là lớn nhất. Các phần tử còn lại được gán vào các nhóm cùng lúc. Tại mỗi bước, việc mở rộng diện tích đòi hỏi phải thêm mỗi phần tử còn lại cho mỗi nhóm được tính toán, và phần tử được gán thì sẽ xuất hiện một sự khác biệt lớn nhất giữa hai nhóm. k) Thuật toán Quadratic Split Phân chia một tập M+1 các chỉ số thành hai nhóm. 40 - B1: [chọn phần tử đầu tiên cho mỗi nhóm] Áp dụng thuật toán PickSeeds để chọn hai phần tử làm các phần tử đầu tiên của các nhóm. Gán mỗi phần tử cho một nhóm. - B2: [Kiểm tra nếu đã thực hiện] Nếu tất cả các phần tử đã được gán, ngừng. Nếu một nhóm có một vài phần tử mà tất cả những phần tử còn lại phải được gán vào nó theo thứ tự để cho nhóm này có m nhỏ nhất, gán các phần tử và ngừng. - B3: [Chọn phần tử để gán] Thực hiện thuật toán PickNext để chọn phần tử kế tiếp để gán. Thêm phần tử này vào nhóm mà hình chử nhật bao phủ của nó sẽ phải mở rộng ít nhất để chứa phần tử này. Giải quyết các hạn chế bằng cách thêm phần tử vào nhóm có diện tích nhỏ nhất, khi đó nhóm này có các phần tử ít hơn nhóm khác. Lặp lại B2. l) Thuật toán PickSeeds Chọn hai phần tử làm phần tử đầu tiên của các nhóm. - B1: [Tính toán sự thiếu hiệu quả của việc nhóm các phần tử với nhau] Cho mỗi cặp các phần tử E1 và E2, tạo một hình chữ nhật J bao gồm E1I và E2I Tính d = area(J) – area (E1I) - area(E2I). - B2: [Chọn cặp gây lãng phí nhất] Chọn cặp có d lớn nhất. m) Thuật toán PickNext Chọn một mục còn lại để phân loại vào một nhóm. - B1: [Xác định giá trị của việc đặt mỗi phần tử trong mỗi nhóm] Cho mỗi phần tử E chưa được phân nhóm, tính d1 = diện tích được yêu cầu tăng trong hình chữ nhật bao phủ của nhóm 1 để bao gồm EI, tính toán d2 tương tự như trên cho nhóm 2. - B2: [Tìm phần tử thích hợp nhất cho một nhóm] Chọn bất kỳ phần tử nào có sự khác biệt lớn nhất giữa d1 và d2. 41 n) Thuật toán LinearPickSeeds Chọn hai phần tử làm các phần tử đầu tiên của các nhóm. - B1: [Tìm các hình chữ nhật xa nhất theo tất cả các chiều] Theo mỗi chiều, tìm các phần tử mà hình chữ nhật của nó có cạnh dưới cao nhất và có cạnh trên thấp nhất. Ghi lại việc phân chia. - B2: [Điều chỉnh hình dạng của cụm hình chữ nhật] Chuẩn hóa việc phân chia bằng cách chia chiều rộng của toàn bộ các tập theo chiều tương ứng. - B3: [Chọn cặp cách xa nhất] Chọn cặp có sự phân chia được chuẩn hóa lớn nhất theo bất kỳ chiều nào. 1.4.4. Một số phƣơng pháp cải tiến R-tree đánh chỉ số tài liệu XML  XR-tree [32] XR-tree được thiết kế để xử lý các tài liệu XML có dữ liệu lồng nhau chặt chẽ, hỗ trợ truy vấn tìm tất cả các tổ tiên hoặc hậu duệ của một entry E với chi phí thấp. XR-tree đưa ra 4 định nghĩa trên cây cải tiến với các công thức đi kèm, cấu trúc mới dựa trên các node và các stab list được tạo ra với tham số được tính toán dựa trên các công thức trong các định nghĩa. Hình 1.15: Cấu trúc cây XR-tree Cây XR-tree được thiết kế để đánh chỉ số trên tài liệu XML sau đó kết hợp cùng phép nối có cấu trúc được đề xuất là XR-stack để đưa ra kết quả cuối cùng. Các kết quả tập trung chủ yếu vào trục tổ tiên và hậu duệ. Đây là hạn chể của XR- 42 tree, vì trên thực nghiệm, các truy vấn các trục này thường ít dữ liệu nên cải tiến sẽ không mang nhiều ý nghĩa cho tốc độ truy vấn.  AR*-tree [91] Ý tưởng chính của phương pháp AR*- tree là chia 1 node n-chiều trong R-tree thành n node 1-chiều, n node một chiều này tạo thành một node-group, trong đó mỗi node mới chứa thông tin chỉ số theo 1 chiều (khác với mỗi node trong R-tree chưa thông tin chỉ số cho tất cả các chiều). Tại mỗi node-group tập các entry sẽ có cùng một chỉ số vị trí và phân phối trong các node khác nhau tạo thành một entry of node-group tương ứng với 1 MBR. Mỗi entry của mỗi node trong một node-group tạo thành một cạnh của MBR, trong khi mỗi entry trong các node của R-tree tạo thành 1 MBR. Ví dụ, trong không gian 2 chiều các entry và MBR của phương pháp AR*-tree được biểu diễn như sau: Hình 1.16: Xây dựng MBR trên không gian 2 chiều của phƣơng pháp AR*-tree Kết quả là cải thiện số node cần truy cập trong truy vấn trục Xpath xuống thấp hơn ở tất cả các trục, nhưng không quá nhiều, các thử nghiệm tiến hành trên những file dữ liệu khá nhỏ, từ 5.5 MB đến 113.8 MB. Vấn đề của phương pháp này là làm thay đổi bản chất của các node R-tree, tạo ra nhiều node hơn đáng kể, dẫn đến có thể ảnh hưởng tới nhiều dạng truy vấn khác của R-tree. Hơn nữa, việc tạo ra thành nhiều node hơn sẽ làm tăng kích thước của cây chỉ số, điều này trái với định hướng nghiên cứu là phải giảm kích thước càng nhiều càng tốt. 43 1.5. Các vấn đề còn tồn tại Tác giả thấy rằng, trên thực tế các tài liệu XML tin sinh học thường rất lớn, lớn tới mức không thể xử lý toàn bộ trên bộ nhớ và có thể phải lưu trữ phân tán trên đĩa cứng. Do vậy cần có các phương pháp đánh chỉ số trên đĩa cứng hiệu quả và đồng thời có phương pháp làm giảm kích thước dữ liệu để tăng hiệu quả truy vấn. Các nghiên cứu đánh chỉ số XML kích thước lớn có xu hướng chuyển đổi tài liệu XML về không gian số trước khi áp dụng các phương pháp đánh chỉ số. Đa phần sử dụng B+-tree, lý do chính là B+-tree khá phổ biến trong các CSDL quan hệ ngày nay. Trong khi đó R-tree là phương pháp đánh chỉ số hiệu quả cho không gian đa chiều và cũng rất phổ biến trong các CSDL quan hệ, chưa được tận dụng. R-tree có thể đánh chỉ số với dữ liệu có 2 chiều trở lên, và đặc biệt tốt với dữ liệu phân bố không đều trong không gian. Các truy vấn theo trục Xpath có 46% (6/13 trục) là truy vấn anh em hoặc truy vấn suy dẫn được từ các các truy anh em. Ngoài ra, phân bố dữ liệu sau khi chuyển đổi về không gian Đề các, xu hướng tập trung không đều và lệch hoàn toàn về 1 số vùng không gian chứa các tag anh em (sẽ phân tích ở các chương sau). Chưa có nghiên cứu nào về tối ưu các truy vấn anh em và từ đó tăng hiệu quả các truy vấn khác của Xpath. Từ các vấn đề tồn tại trên, luân án đã chọn nghiên cứu mô hình đánh chỉ số phù hợp với tài liệu XML tin sinh học, với mục tiêu tăng hiệu quả đánh chỉ số dữ liệu XML và đồng thời giảm kích thước dữ liệu để đánh chỉ số và truy vấn. Mô hình trong Hình 1.17, giúp dữ liệu XML được chuyển đổi về không gian đa chiều, từ đó áp dụng các phương pháp đánh chỉ số và truy vấn trong không gian giúp tăng tốc độ xử lý và giảm kích thước dữ liệu khi đánh chỉ số. Có 2 phương pháp chính để đánh chỉ số trong không gian đa chiều là Gridbase và R-tree: - Gridbase phù hợp với dữ liệu phân bố đều 44 - R-tree ứng dụng được trong các dữ liệu phân bố ngẫu nhiên Vì XML tin sinh học trên thực tế rất đa dạng nên R-tree sẽ phù hợp hơn và được lựa chọn làm cơ sở trong luận án này. Hình 1.17: Mô hình quy trình tổng quát Hình 1.18: Mô hình thể hiện quá trình chuyển đổi dữ liệu và đánh chỉ số trên đĩa cứng Phương pháp R-tree hiện còn một số vấn đề khi áp dụng vào xử lý dữ liệu XML tin sinh học như sau: 45 1) Vấn đề chồng chéo trong truy vấn. Đối với kỹ thuật chỉ số dựa trên không gian, không gian tìm kiếm càng lớn thì càng mất nhiều thời gian hơn để nhận được node được trả về. Nhưng điểm yếu của phương pháp dựa trên R-tree là các truy vấn đòi hỏi cửa sổ quét dữ liệu khá lớn, do đó ảnh hưởng đáng kể tới hiệu năng truy vấn. 2) Vấn đề mối liên kết anh em của các tag sau khi chuyển đổi sang không gian, mà được thể hiện như các điểm trong không gian như parent, preceding, sibling, descendant, child, following, v.v theo các trục Xpath. Trong Hình 2.2 biểu diễn việc phân bố dữ liệu trên hệ trục tọa độ, tác giả nhận ra rằng tất cả các dữ liệu phân bố lệch như một hình thang/được chéo thẳng hàng (giống như cánh máy bay). Trong khi đó, tất cả các phương pháp trước đây không quan tâm đến điều đó, nên các truy vấn chưa có cải thiện đáng kể nào khi truy vấn ở vùng dữ liệu cánh máy bay này. 1.6. Kết luận Chương 1 trình bày một số khái niệm nền tảng về tin sinh học và dữ liệu tin sinh học. Dữ liệu tin sinh học ngày càng trở nên khổng lồ do được đóng góp và chia sẻ thường xuyên của cộng đồng nghiên cứu. Do các bài toán phân tích dữ liệu tin sinh học rất đa dạng, các tài liệu lưu trữ thông tin cần cấu trúc dễ thay đổi, linh hoạt, đa dạng và đặc biệt dễ chia sẻ/đóng góp. Hiện nay, tài liệu XML là một chuẩn quan trọng để mô tả và lưu trữ dữ liệu sinh tin học khổng lồ. Tuy nhiên, tài liệu XML có dữ liệu dạng text và bán cấu trúc nên việc khai thác không giống như dữ liệu thông thường. Chương 1 cũng trình bày các nghiên cứu liên quan của bài toán khai thác dữ liệu XML, các phương pháp đánh chỉ số, các thuật toán được đề xuất trong các nghiên cứu trước đây đã được nêu ra, trong đó R-tree đang là thuật toán tỏ ra hiệu quả nhất với các tài liệu XML và truy vấn Xpath. Trên cơ sở đó, chương 1 phân tích và đưa ra các vấn đề nghiên cứu của luận án. 46 Chƣơng 2. PHƢƠNG PHÁP ĐÁNH CHỈ SỐ BIOX-TREE 2.1. Mở đầu Khi thiết kế một phương thức truy cập mới, chúng ta không chỉ phải biết được bản chất của dữ liệu mà còn phải biết các kiểu truy vấn và phương thức sẽ được sử dụng [16][42]. Việc truy vấn Xpath quét toàn bộ dữ liệu XML sẽ làm giảm hiệu suất đáng kể. Các phương pháp lập chỉ số đã được phát triển trong những năm gần đây để khắc phục vấn đề này. Các phương pháp xử lý truy vấn và lập chỉ số dữ liệu XML khác nhau đã được đề xuất để hỗ trợ các truy vấn Xpath. Bài viết [2] phân loại các chỉ số dữ liệu XML thành ba loại. - Đầu tiên là các chỉ số dựa trên đường dẫn, chúng nhóm các node trong cây dữ liệu theo độ tương tự cục bộ và có cấu trúc chỉ số có thể điều chỉnh theo khối lượng công việc truy vấn. Hạn chế của các chỉ số này là kích thước chỉ số rất lớn vì chúng lưu trữ các đường dẫn tiến và lùi để thiết lập một lớp hỗ trợ [17][35]. - Thứ hai là các chỉ số dựa trên dãy, chúng đánh giá các truy vấn bằng cách ghép dãy sau khi chuyển đổi cả dữ liệu XML và truy vấn thành dãy. Tuy nhiên, nhược điểm của chúng là xuất hiện dương tính giả gây ra bởi việc ghép dãy thay vì ghép cây [64][79]. - Thứ ba là các chỉ số dựa trên node, chúng sử dụng các giá trị duyệt cây theo thứ tự trước cùng với các giá trị duyệt cây theo thứ tự sau của một tag name trên cây XML làm tọa độ của node trên không gian. Kết quả sau đó được sử dụng để xác định mối quan hệ giữa các node cây. Trong luận án này, tác giả tập trung vào loại thứ ba vì các chỉ số dựa trên node có thể được phân loại thành chỉ số dựa trên đánh số và chỉ số dựa trên đa chiều. Đây 47 là tiền đề để tác giả đề xuất cây BioX-tree và mở rộng BioX+-tree với mục tiêu cải thiện hiệu suất tốt hơn so với phương pháp trước đây. Cũng như mô hình dữ liệu có cấu trúc, mô hình dữ liệu bán cấu trúc XML cũng có các ngôn ngữ truy vấn riêng, phổ biến nhất là Xpath và Xquery. Trong đó, Xpath là dạng đơn giản và cơ bản của Xquery. Cơ chế hoạt động của truy vấn XPath thường phân ra 2 dạng: Tuần tự và đánh chỉ số. Với dạng tuần tự, dữ liệu XML sẽ không được tiền xử lý trước khi truy vấn. Mỗi truy vấn sẽ thực hiện đọc toàn bộ dữ liệu. Dạng đánh chỉ số sẽ tiền xử lý dữ liệu XML để xây dựng cấu trúc dữ liệu khác mà mỗi lần truy vấn không đòi hỏi quét toàn bộ dữ liệu. Chỉ số dựa trên đánh chỉ số sử dụng các tag name XML ghi nhãn để thể hiện vị trí của các tag trong tài liệu. Trong [37] trình bày chỉ số cây con dựa trên phạm vi, và ghi nhãn dựa trên tiền tố. Chỉ số cây con dựa trên phạm vi được sử dụng để xác định mối quan hệ tổ tiên - con cháu giữa bất kỳ cặp tag XML nào. Hạn chế của nó là việc tính toán lại toàn bộ thứ tự của các node được yêu cầu bất cứ khi nào có node mới được chèn, xem [21][47] và hiệu quả truy vấn kém. Chỉ số cây con dựa trên phạm vi sử dụng các cặp (giá trị duyệt cây theo thứ tự trước, giá trị duyệt cây theo thứ tự sau) của các chuỗi con của dữ liệu XML được tính từ khi bắt đầu tài liệu XML duyệt theo chiều sâu. Hạn chế của nó là không thể xử lý các cập nhật thường xuyên của dữ liệu XML vì người ta cho rằng các vị trí node không bao giờ thay đổi một khi chúng được gán, xem [95] . Chỉ số dựa trên tiền tố là để chỉ chính xác tổ tiên của một node trên đường dẫn của nó. Hạn chế của nó là khi chiều cao của cây tăng lên, kích thước của nhãn tăng nhanh, xem [55][78]. Trong chỉ số dựa trên đa chiều trong ánh xạ [27][28] mọi node sẽ được đưa lên mặt phẳng hai chiều, sử dụng xếp hạng duyệt cây theo thứ tự trước trên trục x và xếp hạng duyệt cây theo thứ tự sau trên trục y. Node bối cảnh và bốn trục chính của các đường dẫn XPath (accestor, preceding, following, descendant), chia không gian hai chiều thành bốn vùng, mỗi vùng tương ứng với một trục chính. 48 Với một node bối cảnh, quá trình truy vấn tìm kiếm một trong các trục của nó có thể được đơn giản hóa như các node phân vùng trên mặt phẳng hai chiều và truy xuất các node rơi vào vùng tương ứng với trục cụ thể trong truy vấn. Một cấu trúc chỉ số, XPath Accelerator, đã được đề xuất để hỗ trợ phương pháp tiếp cận đa chiều. Bằng cách sử dụng một hệ thống cơ sở dữ liệu quan hệ, sẽ có lợi rất nhiều nếu cơ sở dữ liệu hỗ trợ các kỹ thuật lập chỉ số không gian như R-tree [30]. Tập hợp các node của bốn trục chính sẽ được kết hợp để hỗ trợ tất cả các trục biểu thức đường dẫn. Tối ưu hóa có thể được thực hiện để giảm thêm kích thước của vùng tài liệu trong truy vấn, mặc dù pre order và post order trong một số trường hợp chèn node phải được tính lại. Các phương pháp đưa ra ở trên trong việc đánh chỉ số trong không gian dựa trên R-tree đang gặp các vấn đề: Thứ nhất, đó là vấn đề chồng chéo. Đối với kỹ thuật chỉ số dựa trên không gian, không gian tìm kiếm càng lớn thì càng mất nhiều thời gian hơn để nhận được node được trả về. Nhưng yếu điểm của phương pháp dựa trên R-tree là các truy vấn đòi hỏi cửa sổ quét dữ liệu khá lớn, do đó ảnh hưởng đáng kể tới hiệu năng truy vấn. 49 Hình 2.1: Phạm vi quét thứ tự duyệt cây theo thứ tự trƣớc và sau ban đầu (vùng xám) và thu nhỏ (vùng trắng) cho truy vấn con cháu đƣợc thực hiện theo truy vấn mẫu Hình 2.1 minh họa một thể hiện của tài liệu XML với một số điểm nhỏ biểu thị dữ liệu XML theo mặt phẳng. Giả sử rằng, từ node bối cảnh E, chúng ta muốn lấy tất cả các node con cháu của nó bằng cách sử dụng cửa sổ truy vấn {pre(E), ; 0, post(E)} [36]. Cửa sổ thực sự cần thiết để tìm kiếm là màu trắng được xác định bởi giá trị duyệt cây theo thứ tự trước của node con cháu bên trái và giá trị duyệt cây theo thứ tự sau của node con cháu bên phải của node E. Kết quả là, phạm vi thừa được đánh dấu màu xám trong cửa sổ truy vấn tương ứng với trục con cháu sẽ gây ra ảnh hưởng đáng kể đến hiệu suất thực hiện các truy vấn, mà phạm vi này lại có thể rất lớn trong nhiều trường hợp. Thứ hai, đó là vấn đề mối liên kết anh em của các tag sau khi chuyển đổi sang không gian, mà được thể hiện như các điểm trong không gian như parent, preceding, sibling, descendant, child, following, v.v theo các trục Xpath. Trong Hình 2.2 biểu diễn việc phân bố dữ liệu trên hệ trục tọa độ, với dữ liệu DNA gạo kiểm thử trên 1000 node (Hình 2.2a), với dữ liệu Swissprot kiểm thử trên khoảng 20.000 node (Hình 2.2b), tác giả nhận ra rằng tất cả các dữ liệu dữ liệu phân bố lệch như một hình thang/được chéo thẳng hàng (giống như cánh máy bay). Tác giả đã thử 50 nghiệm trên nhiều tài liệu XML khác nhau với từ vài trăm node đến vài trăm nghìn node cũng ra kết quả tương tự. (a) (b) Hình 2.2: Ví dụ về phân phối các điểm quy đổi cho một tài liệu XML Đây là đặc thù theo cách chuyển đổi lên không gian theo phương pháp giá trị duyệt cây theo thứ tự trước – sau. Trong khi đó, tất cả các phương pháp trước đây không quan tâm đến điều đó, chúng chỉ tập trung vào xử lý mối quan hệ giữa cha mẹ/con cái hoặc tổ tiên/con cháu và bỏ qua các trục khác mà chúng cũng là phần 51 quan trọng trong xử lý truy vấn, đặc biệt là xử lý luồng truy vấn XPath với các vị từ. Các truy vấn chưa có cải thiện đáng kể nào khi truy vấn ở vùng dữ liệu cánh máy bay này. Một số ví dụ về truy vấn với các tham số vị từ: q1= descendant[2]/preceding-sibling[3] q2= parent[3]/following-sibling[7] q3= parent/preceding-sibling[3]/child[2] Tác giả nghiên cứu truy vấn q1, được hiểu là node cần tìm ở vị trí thứ ba của anh em trước của con cháu thứ hai của node bối cảnh. Phương pháp lập chỉ số dựa trên R-tree mất nhiều thời gian hoặc thậm chí khó giải quyết loại truy vấn đó. Để xử lý truy vấn trên, đầu tiên chúng ta phải lấy tất cả các anh em trước của node bối cảnh, sau đó chọn node thứ ba cho các bước tiếp theo. Trong khi đó, với Bộ tăng tốc XPath, tập các node trả về sẽ là tất cả các node nằm ở góc dưới bên trái của mặt phẳng từ node bối cảnh. Các node có mối quan hệ với những node khác (cha mẹ- con cái, tổ tiên-con cháu) và nằm ngẫu nhiên trong node lá do hạn chế về không gian; dẫn đến thật khó để xác định đâu là node thứ ba từ node bối cảnh. Và bước tiếp theo không thể được thực hiện như là kết quả của các bước trước đó. Khi thực thi thuật toán cũng sẽ đòi hỏi nhiều tài nguyên và thời gian để có được kết quả trả về. Đó là nhược điểm của phương pháp Bộ tăng tốc Xpath. Thông thường, phương pháp lập chỉ số dựa trên R-tree đã giải quyết hầu hết các trường hợp câu truy vấn đơn giản nhưng với những câu truy vấn có vị từ phức tạp đặc biệt là tham số vị từ chỉ vị trí thì R-tree không đưa ra được một cấu trúc chỉ số tối ưu có khả năng truy vấn nhanh tất cả các trục. Cấu trúc của R-tree cũng không quan tâm đến cấu trúc phân bố dữ liệu cánh may bay nên đã để các node anh em bị nằm rải rác trên cây là nguyên nhân chính. Từ đó, tác giả đi sâu nghiên cứu phương pháp đánh chỉ số mới, được cải tiến từ R-tree giúp các truy vấn Xpath chạy hiệu quả hơn trong một số trục. Trong bài 52 toán này, mục tiêu của tác giả là tập trung vào một cấu trúc lập chỉ số có đủ khả năng thực hiện tất cả các loại truy vấn dựa trên cấu trúc, đặc biệt tập trung vào giải quyết các truy vấn vị từ vị trí. Ngoài ra, nó có thể đưa ra một khả năng để mở rộng các trục tồn tại trên tài liệu XML nhưng không được sử dụng trong phương pháp cũ thành các trục linh hoạt và hiệu quả hơn. Tuy nhiên, tác giả không đi sâu vào vấn đề đó mà vẫn cố gắng sử dụng các trục tương tự như các tài liệu nghiên cứu liên quan. Dựa theo mô hình đã lựa chọn trong chương 1, tác giả sẽ có những đề xuất cải tiến trong các thành phần: chuyển đổi, đánh chỉ số, module xử lý truy vấn. Hình 2.3: Các thành phần đƣợc đề xuất cải tiến trong phƣơng pháp BioX-tree Với các thử nghiệm trong chương 2 và 3, tác giả sẽ chứng minh bằng kết quả cụ thể phương pháp đề xuất được cải thiện so với các phương pháp gốc. Các kết quả trong chương này được công bố trong các công trình 1, 2, 3, 4 phần “Danh mục các công trình của tác giả”. 2.2. Phƣơng pháp đánh chỉ số cải tiến BioX-tree 2.2.1. Chuyển đổi tài liệu XML Dựa theo cách đánh chỉ số trên lược đồ của của Dietz đã nêu ở chương 1, khi chuyển đổi tài liệu XML, các tag name sẽ biến đổi sao cho biểu diễn được trong không gian với hệ trục tọa độ Đề các. Bước đầu tiên là tài liệu XML sẽ được xây dựng lên dạng cây với quan hệ phân cấp cha con (như Hình 2.6), sau đó các node tương ứng sẽ được đánh 2 chỉ số theo quy tắc duyệt cây theo thứ tự trước, duyệt cây 53 theo thứ tự sau (cặp giá trị này sẽ tạo thành NodeID) và đánh số thứ tự cho từng tag name của tài liệu XML [22][63]. Tương ứng như vậy khi gắn lên hệ trục tọa độ ta được thể hiện như Hình 2.4; thứ tự pre của các tag name sẽ là Bioseq-set_descr < Seqdesc_source < BioSource_genome < BioSource_org < < Date-pub_month < Date-pub_day, và do đó pre(Bioseq-set_descr) = 1, pre(Seqdesc_source) = 2 ,. . . , pre(Date-pub_day) = 31; còn post(BioSource_genome) = 1, post(BioSource_org) = 2 ,. . . , post(Bioseq-set_descr) = 31. Hình 2.4: Ví dụ về biểu diễn điểm dựa trên cặp giá trị (duyệt cây theo thứ tự trƣớc, duyệt cây theo thứ tự sau) Vẫn tuân thủ theo nguyên tắc chung đó trong phân tích và chuyển đổi tài liệu XML, tác giả đã xây dựng một chương trình riêng để thực hiện để đảm bảo độ chính xác khi so sánh với phương pháp dựa R-tree của các nghiên cứu trước. Trong tài liệu [20], trình chuyển đổi được triển khai bằng hai thủ tục startEuity (t, a, att) và endEuity (t). Ở đây, tác giả đã thêm một tham số mới theo cách riêng của tác giả để tăng hiệu quả tìm kiếm lên, bên cạnh việc vẫn sử dụng tham số duyệt cây theo thứ tự trước và duyệt cây theo thứ tự sau. Đó là tham số được sử dụng để chỉ cấp độ l (level) của từng node, tác giả sẽ sử dụng tham số này cho các truy vấn con cháu. 54 Bất cứ khi nào thủ tục phân tích cú pháp startEuity (t, a, atts) gặp thẻ mở XML (dấu <) tham số l (đây là biến toàn cục, giá trị mặc định ban đầu là -1) sẽ được cộng thêm 1 đơn vị. Khi thủ tục endEuity (t) được gọi, l trừ đi 1 đơn vị. Hai thủ tục trên được sửa đổi với tên mới startElement và endElement, trình bày trong Thuật toán 2.1. Thuật toán ConvertXMLDocument(XMLdoc) Đầu vào: tài liệu XML cần chuyển đổi. Đầu ra: file txt chứa các giá trị trên không gian của một node(E) = {pre (E), post (E), par (E), att (E), tag (E)}. Begin l = -1; startElement(t, a, atts) l ← l +1; v ← (pre = gpre, post = _, par = (S.top()).pre, level= l, att = a, tag = t) S.push(v); Gpre ← gpre + 1; for v’ IN atts do startElement(v’, true, nil ); endElement(v’); endElement(t) v ← S.pop(); v.post ← gpost; gpost ← gpost +1; chèn v vào bảng kết quả; l ← l-1; End Thuật toán 2.1: Hai thuật toán sửa đổi trong chuyển đổi tài liệu XML 2.2.2. Cấu trúc chỉ số trên cây BioX-tree BioX-tree áp dụng chiến lược chèn/tách khác nhau để đạt được các mối quan hệ anh em của dữ liệu XML một cách dễ dàng hơn, trong khi không gây ảnh hưởng đến khả năng phân biệt không gian của chỉ số quá nhiều. 55 Tác giả thiết kế cấu trúc cây BioX-tree duy trì nghiêm ngặt quỹ đạo liên kết anh em, các tag anh em với nhau sẽ có cùng cấp độ và có cùng cha mẹ. Như vậy, cấu trúc BioX-tree thực chất là cây có mỗi node lá sẽ chứa nhiều tag con của cùng một tag cha mẹ, được tổ chức theo cấu trúc phân cấp cây cân bằng về chiều cao. Bên trong các node chứa các phần tử (được gọi là ent