Tổng quan luận án

Tính cấp thiết và khoảng trống nghiên cứu

Tài liệu XML (eXtensible Markup Language) là định dạng dữ liệu bán cấu trúc phổ biến nhờ khả năng lưu trữ linh hoạt, dễ dàng chia sẻ và sử dụng qua môi trường mạng Internet. Trong lĩnh vực tin sinh học (Bioinformatics) và sinh học tính toán (Computational Biology), sự phát triển của các công nghệ giải trình tự thế hệ mới đã tạo ra các tập dữ liệu có dung lượng rất lớn, đạt quy mô Gigabyte và Terabyte. Các tập dữ liệu này được công khai và cập nhật liên tục từ các trung tâm dữ liệu sinh học lớn như SRA, NCBI Genome, ensembl.org (BioMart), EMBL/EBI và CIB-DDBJ.

Tài liệu XML tin sinh học bao gồm hai thành phần chính: dữ liệu sinh học (trình tự DNA, RNA, Protein, phân loại học, mô hình phân tử) và dữ liệu mô tả cấu trúc được định nghĩa theo các cặp thẻ (tags). Do kích thước vượt quá dung lượng của bộ nhớ chính (RAM), các tài liệu này bắt buộc phải lưu trữ và khai thác trên đĩa cứng hoặc hệ thống lưu trữ phân tán, chỉ có thể nạp từng phần nhỏ lên RAM khi thực hiện phân tích chuyên sâu. Tuy nhiên, tốc độ truy xuất dữ liệu tuần tự trên đĩa cứng chậm hơn truy xuất trên RAM hơn 100.000 lần, trở thành điểm nghẽn chính trong quá trình xử lý.

Các giải pháp đánh chỉ số (indexing) truyền thống đối với dữ liệu văn bản XML bộc lộ nhiều hạn chế khi áp dụng cho dữ liệu tin sinh học quy mô lớn:

  • Kích thước của cây chỉ số văn bản sinh ra thường rất lớn, thậm chí vượt qua kích thước dữ liệu gốc, gây khó khăn cho việc lưu trữ và làm giảm hiệu quả nén cũng như khai thác đồng thời.
  • Tốc độ xử lý các truy vấn XPath và tìm kiếm cấu trúc còn chậm do phải quét dữ liệu tuần tự hoặc duyệt qua quá nhiều nút chỉ số không liên quan.

Để giải quyết vấn đề này, xu hướng nghiên cứu hiện nay tập trung tách tài liệu XML thành hai phần độc lập: đánh chỉ số dữ liệu cấu trúc (hỗ trợ truy vấn XPath) và đánh chỉ số dữ liệu sinh học (hỗ trợ tìm kiếm chuỗi tương đồng), đồng thời chuyển đổi dữ liệu thẻ sang dạng số để giảm kích thước lưu trữ. Luận án lựa chọn giải quyết khoảng trống về phương pháp đánh chỉ số dữ liệu cấu trúc thẻ trên đĩa cứng, tập trung tối ưu hóa số lượng thao tác vào/ra (I/O) đĩa cứng cho các truy vấn XPath đặc thù.

Mục tiêu nghiên cứu

Luận án xác định hai mục tiêu thực hiện cụ thể:

  1. Nghiên cứu phương pháp đánh chỉ số dựa trên cấu trúc R-tree nhằm tăng hiệu quả thực thi các truy vấn XPath trên dữ liệu XML, thông qua dữ liệu trung gian được chuyển đổi về dạng tọa độ số của các thẻ (tags) từ tài liệu XML tin sinh học.
  2. Sử dụng phương pháp chuyển đổi dữ liệu văn bản có cấu trúc XML về dữ liệu dạng số biểu diễn trên không gian 2 chiều (có khả năng mở rộng lên nhiều chiều) nhằm giảm kích thước dữ liệu gốc và tạo điều kiện áp dụng phương pháp đánh chỉ số đề xuất. Ngoài ra, luận án thực hiện khảo sát các phương pháp đánh chỉ số cho dữ liệu sinh học (chuỗi DNA) nhằm định hướng cho các nghiên cứu tiếp theo.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Cấu trúc dữ liệu bán cấu trúc XML tin sinh học; các phương pháp chuyển đổi tài liệu XML sang không gian số tọa độ Đề-các; cấu trúc cây chỉ số không gian R-tree và các giải thuật biến thể (BioX-tree, BioX+-tree); các biểu thức đường dẫn và phép truy vấn theo 13 trục XPath.
  • Phạm vi dữ liệu: Các tập dữ liệu XML tin sinh học trích xuất từ các ngân hàng gen và cơ sở dữ liệu sinh học quốc tế (NCBI, EMBL/EBI, DDBJ), bao gồm dữ liệu bộ gen (DNA lúa/gạo quy mô 1.000 nút), dữ liệu protein (Swissprot quy mô khoảng 20.000 nút) và các tập tài liệu thử nghiệm có quy mô từ vài trăm đến hàng trăm nghìn nút.
  • Phạm vi kỹ thuật: Đánh chỉ số dữ liệu cấu trúc thẻ trên mô hình bộ nhớ ngoài (External Memory Model) nhằm tối thiểu hóa số lần đọc/ghi block đĩa cứng ($I/O$), tối ưu hóa nhóm truy vấn trục anh em ($sibling$) và các trục dẫn xuất trong XPath.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu đánh chỉ số dữ liệu sinh học

Các phương pháp đánh chỉ số cho cơ sở dữ liệu sinh học được tổng hợp và phân loại thành hai nhóm chính:

Nhóm phương pháp Kỹ thuật tiếp cận chính Các thuật toán và công trình tiêu biểu
Nhóm 1: So sánh tương đồng qua chuỗi đại diện So sánh các phân đoạn trong chuỗi với chuỗi ban đầu, tối ưu hóa độ tương đồng cục bộ hoặc toàn cục (độ phức tạp $O(mn)$ với $m, n$ là độ dài chuỗi con). Smith - Waterman [41]; BLAST [3][6][69][74][88]; Flash [13]; PatternHunter [41]; BLAT [88]; Piers [14][88]; Twee-Hee Ong [41][56]; FASTA [59]; Paper [44][45] (Similar multi-step, filter and refine); Suffix array scans [65]; RAMdb [24]; Dynamic programming [54][69][77].
Nhóm 2: Biến đổi cấu trúc chỉ số Can thiệp vào cấu trúc chỉ số thông qua véc-tơ, không gian mêtric, phân tích ma trận, phép biến đổi Wavelet và thống kê tần số bộ gen. ProperSearch tool [88]; CAFE [86][87]; Metric space indexing [88]; Kahveci and Singh [41][74]; Williams & Zobel [41]; Ozturk and Ferhatosmanoglu [41]; Jeong [41]; Jiang [41]; BIS (Bitmap Indexing Structure) [57]; IDC (Incrementally Decreasing Cover) [46].

Các phương pháp đánh chỉ số tài liệu XML và xử lý truy vấn XPath

Văn bản điểm lại các kỹ thuật đánh chỉ số cho dữ liệu bán cấu trúc XML theo ba nhóm:

Phân loại chỉ số XML (theo [2])

  1. Phương pháp nén và đánh nhãn:

    • XGrind [82] (Tolani và Haritsa): Nén bằng cách thay thế tên phần tử và thuộc tính bằng ký tự duy nhất.
    • Xpress [52] (Min et al.): Sử dụng hàm toán học nghịch đảo mã hóa đường dẫn nhãn thành các đoạn riêng biệt.
    • XQzip [15] (Cheng and NG): Sử dụng cây chỉ số cấu trúc SIT (Structure Index Tree).
    • XQueC [7] (Arion et al.): Sử dụng cây tóm tắt cấu trúc (Structure Summary Tree).
    • Arroyuelo et al. [8]: Tạo cây đánh nhãn kết hợp chỉ số mảng bit (Bit Array) để nén dữ liệu.
    • Qian et al. [62]: Tách rời cấu trúc và nội dung để nén độc lập.

  2. Phương pháp đánh số trên lược đồ và cây B+-tree:

    • XISS (XML Indexing and Storage System) [61][63] (Li and Moon): Phát triển từ sơ đồ đánh số Dietz, gán cho mỗi nút một cặp giá trị $\langle order; size \rangle$. Cấu trúc sử dụng B+-tree để đánh chỉ số theo tên (Name Index) và thực thi các thuật toán nối cấu trúc: EA-Join (Element-Attribute), EE-Join (Element-Element) và KC-Join (Kleene Closure).

  3. Phương pháp ánh xạ không gian đa chiều và R-tree:

    • MDX (Multidimensional Approach to Indexing XML) [37][51]: Mô hình hóa cây XML thành các véc-tơ trong không gian đa chiều, phân biệt đường dẫn tuần tự (PID) và đường dẫn gắn nhãn (LPID), quản lý qua 3 bảng chỉ số: Term, Labeled Path và Path.
    • Ánh xạ sang CSDL quan hệ: Chuyển đổi tài liệu XML thành các bảng quan hệ đảm bảo tính chất ACID [80], tuy nhiên việc tìm thứ tự gán nhãn tối ưu quy về bài toán tìm đường đi Hamilton (NP-đầy đủ), phải sử dụng giải thuật Heuristic.
    • XPath Accelerator [36]: Biểu diễn mỗi nút $E$ trong không gian 5 chiều: $entry(E) = {pre(E); post(E); par(E); att(E); tag(E)}$, dịch các trục XPath thành truy vấn cửa sổ và ánh xạ sang câu lệnh SQL.
    • XR-tree [32]: Cải tiến R-tree bằng danh sách stab list và giải thuật XR-stack, tập trung giải quyết quan hệ tổ tiên - con cháu.
    • AR*-tree: Gom nhóm các phần tử thành các nút nhóm (node-group) để xây dựng MBR 2 chiều.

Khoảng trống nghiên cứu được luận án lựa chọn

Mặc dù các phương pháp tiếp cận không gian đa chiều dựa trên R-tree mang lại tiềm năng lớn, các nghiên cứu trước đây tồn tại hai hạn chế lớn:

  • Vấn đề cửa sổ truy vấn dư thừa: Khi ánh xạ cây XML sang mặt phẳng 2 chiều bằng thứ tự duyệt trước (pre-order) và duyệt sau (post-order), các truy vấn trục con cháu ($descendant$) hoặc tổ tiên ($ancestor$) đòi hỏi cửa sổ tìm kiếm hình chữ nhật chứa diện tích dư thừa rất lớn (vùng xám), làm tăng số lượng nút cần duyệt.
  • Bỏ sót đặc thù phân bố dữ liệu và quan hệ anh em ($sibling$): Sau khi chuyển đổi tọa độ, dữ liệu XML không phân bố ngẫu nhiên mà tập trung lệch thành dải chéo/hình thang thẳng hàng (dạng cánh máy bay). Trong khi đó, các trục truy vấn quan hệ anh em và các trục suy dẫn từ anh em chiếm tới 46% (6/13 trục XPath), nhưng các cấu trúc như XR-tree chỉ tập trung tối ưu cho trục tổ tiên/con cháu mà không khai thác cấu trúc phân bố dải chéo này.

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

Khung lý thuyết và mô hình tính toán

  1. Mô hình bộ nhớ ngoài (External Memory Model):

    • Đĩa cứng được tổ chức vật lý gồm các đĩa từ, trục quay, track và sector. Các sector vật lý được ánh xạ thành các block logic có kích thước cố định là $B$ (dung lượng một lần đọc/ghi $I/O$).
    • Với cơ sở dữ liệu có $N$ đối tượng, số lượng block tối thiểu cần để lưu trữ là $n = \lceil N/B \rceil$.
    • Một câu truy vấn trả về $K$ đối tượng đòi hỏi tối thiểu $k = \lceil K/B \rceil$ thao tác $I/O$.
    • Thuật toán đạt không gian tuyến tính nếu sử dụng $O(n)$ block và đạt thời gian logarit nếu chi phí truy vấn là $(\log_B n + k)$ lần $I/O$.

  2. Mô hình tài liệu XML, DOM và ngôn ngữ XPath:

    • Chuẩn DOM (Document Object Model) phân chia thành Core DOM, XML DOM và HTML DOM để truy cập cây đối tượng.
    • Đặc tả XPath [11] định nghĩa 13 trục điều hướng quan hệ: self, parent, child, ancestor, ancestor-or-self, descendant, descendant-or-self, following, following-sibling, preceding, preceding-sibling, attribute, namespace.
    • Vị từ (predicate) đặt trong dấu ngoặc vuông [...] đóng vai trò lọc điều kiện logic hoặc vị trí số học (ví dụ: /a/b[3] tương đương /a/b[position()=3]).

  3. Cơ chế đánh số thứ tự cây (Tree Order Numbering):

    • Ánh xạ mỗi nút $x$ thành cặp tọa độ số: thứ tự duyệt trước $pre(x)$ (đánh số tăng dần từ trên xuống dưới) và thứ tự duyệt sau $post(x)$ (đánh số tăng dần từ trái qua phải).
    • Điều kiện xác định quan hệ tổ tiên - con cháu (Ancestor - Descendant, A-D): $$\forall x, y \in T: x = ancestor(y) \iff pre(x) < pre(y) \land post(x) > post(y)$$

  4. Cấu trúc cây R-tree và các giải thuật cơ bản:

    • Cây R-tree [30] là cây cân bằng đa chiều. Nút lá chứa các mục $(MBR, object_ptr)$, nút trong chứa $(MBR, child_ptr)$, trong đó MBR (Minimum Bounding Rectangle) là hình chữ nhật biên nhỏ nhất $n$-chiều bao bọc dữ liệu.
    • Bậc của nút được kiểm soát bởi số lượng mục vào tối thiểu $m$ và tối đa $M$ ($m \le M/2$).
    • Các thuật toán chuẩn trên R-tree:
      • Tìm kiếm (Search): Duyệt từ gốc, kiểm tra sự giao cắt MBR giữa nút chỉ số $E_I$ và vùng tìm kiếm $S$.
      • Chèn (Insert): Sử dụng ChooseLeaf để chọn nút lá có độ mở rộng diện tích MBR nhỏ nhất; nếu nút tràn ($M+1$ mục), kích hoạt thuật toán tách nút SplitNode và lan truyền lên nút gốc bằng AdjustTree.
      • Tách nút (SplitNode): Bao gồm thuật toán chi phí bậc hai (Quadratic Split) sử dụng PickSeeds (chọn cặp phần tử gây lãng phí diện tích lớn nhất khi gộp chung) và PickNext (chọn phần tử có hiệu số gia tăng diện tích lớn nhất giữa hai nhóm); hoặc giải thuật tuyến tính (LinearPickSeeds).
      • Xóa (Delete): Sử dụng FindLeaf định vị phần tử, kích hoạt CondenseTree để loại bỏ các nút không đủ số lượng tối thiểu $m$ mục và thực hiện chèn lại (re-insertion).
      • Cập nhật (Update): Thực hiện tuần tự thao tác xóa, hiệu chỉnh MBR và chèn lại phần tử.
Quy trình chèn phần tử vào cây R-tree
          Kiểm tra sức chứa nút lá L
                    AdjustTree (điều chỉnh MBR lên nút cha)

Phương pháp nghiên cứu thực nghiệm

  • Chuyển đổi dữ liệu sang không gian 2 chiều: Ánh xạ các thẻ XML thành tọa độ $(pre, post)$, phân chia không gian thành 4 góc phần tư tương ứng với 4 trục XPath chính quanh nút bối cảnh: con cháu ($descendant$), tổ tiên ($ancestor$), nút trước ($preceding$), nút sau ($following$).
  • Cải tiến cấu trúc chỉ số: Phát triển cấu trúc BioX-tree và BioX+-tree dựa trên nền tảng R-tree, hiệu chỉnh giải thuật phân tách nút và duyệt cây nhằm giảm số bước duyệt dư thừa trên đĩa cứng đối với vùng phân bố dải chéo.
  • Tiền xử lý dữ liệu lớn: Kết hợp công nghệ Hadoop/MapReduce với kho dữ liệu truyền thống (Data Warehouse/Data Mart) để trích xuất dữ liệu XML thô thành các trường có cấu trúc trước khi lập chỉ số.
  • Nguồn dữ liệu thực nghiệm:
    • NCBI: GenBank (dung lượng vượt 100 Terabyte, chứa 53.161 bản ghi WGS tại thời điểm 8/2005), PubMed (>15.000 tóm tắt y sinh), MMDB (3D Domains), Taxonomy, Cancer Chromosomes.
    • EMBL/EBI (1980/1992): Medline, OMIM, Patent Abstracts, ArrayExpress, MIAME, ASD, ATD, IPD.
    • CIB-DDBJ: Dữ liệu từ Trung tâm Thông tin Sinh học, Viện Di truyền Quốc gia Nhật Bản (tích hợp các công cụ SRS, FASTA BLAST, ClustalW, GTOP LIBRA).
    • Các nguồn bổ trợ: SRA, ensembl.org (BioMart), dữ liệu 231 hệ gen hoàn chỉnh, CSDL dược học và hệ gen người (Homo sapiens).

Nội dung chính theo từng chương

Chương 1: Tổng quan về tin sinh học và các phương pháp đánh chỉ số

Chương 1 thiết lập cơ sở lý luận và khảo sát bức tranh toàn cảnh về dữ liệu tin sinh học cũng như các giải pháp kỹ thuật quản trị dữ liệu bán cấu trúc:

  • Đặc thù dữ liệu tin sinh học: Phân tích sự bùng nổ dữ liệu từ các dự án giải mã bộ gen, cấu trúc phức tạp của các tệp XML (chứa dữ liệu trình tự DNA/Protein kết hợp siêu dữ liệu phân loài, phản ứng sinh hóa). Phân tích kiến trúc kết hợp giữa Hadoop (lưu trữ phân tán dữ liệu thô) và kho dữ liệu (lưu trữ thông tin trích xuất có cấu trúc) để phục vụ phân tích trên các nền tảng ứng dụng (.NET, PHP, Java).
  • Mô hình bộ nhớ ngoài và nút thắt cổ chai: Trình bày chi tiết cơ chế đọc/ghi đĩa từ theo sector/block $B$ và chứng minh khoảng cách tốc độ hơn 100.000 lần giữa RAM và đĩa cứng, đặt ra yêu cầu giảm thiểu số phép toán $I/O$.
  • Hệ thống hóa các thuật toán đánh chỉ số: Khảo sát toàn diện hai nhóm giải thuật đánh chỉ số sinh học (so sánh chuỗi đại diện và biến đổi cấu trúc/véc-tơ), cùng các phương pháp đánh chỉ số XML (XGrind, Xpress, XISS, MDX, XPath Accelerator, XR-tree, AR*-tree).
  • Phát hiện vấn đề nghiên cứu:
    1. Chỉ ra rằng 46% (6 trong số 13) trục XPath là các truy vấn quan hệ anh em (following-sibling, preceding-sibling) hoặc các truy vấn suy dẫn trực tiếp từ quan hệ anh em.
    2. Phát hiện hiện tượng phân bố dữ liệu sau chuyển đổi tọa độ $(pre, post)$ luôn bị lệch thành dạng hình thang/dải chéo thẳng hàng (dạng cánh máy bay), được kiểm chứng đồng nhất trên tập dữ liệu DNA lúa (1.000 nút) và Swissprot (khoảng 20.000 nút).
    3. Kết luận cấu trúc R-tree phù hợp hơn Grid-based đối với dữ liệu XML tin sinh học phân bố không đều, làm tiền đề đề xuất cải tiến cấu trúc chỉ số trong các chương tiếp theo.

Chương 2: Phương pháp đánh chỉ số BioX-tree

Chương 2 tập trung phân tích các khiếm khuyết nội tại của mô hình chỉ số không gian hiện hành và xây dựng giải pháp BioX-tree:

  • Phân loại chỉ số XML theo [2]: Phân tích ưu nhược điểm của ba nhóm: chỉ số dựa trên đường dẫn (kích thước chỉ số lớn do lưu cả đường dẫn tiến và lùi), chỉ số dựa trên dãy (dễ phát sinh lỗi dương tính giả do ghép chuỗi thay vì ghép cây), và chỉ số dựa trên nút (gồm chỉ số đánh số và chỉ số đa chiều). Luận án lựa chọn hướng tiếp cận chỉ số dựa trên nút đa chiều.
  • Phân tích nhược điểm của các chỉ số đánh số truyền thống:
    • Chỉ số cây con dựa trên phạm vi: Đòi hỏi tính toán lại toàn bộ thứ tự nút khi có thao tác chèn mới, hiệu quả truy vấn thấp và không hỗ trợ tốt việc cập nhật thường xuyên.
    • Chỉ số dựa trên tiền tố: Kích thước nhãn tăng nhanh theo chiều cao của cây XML.
  • Bản chất vấn đề chồng chéo (Overlapping) trên R-tree:
    • Khi thực hiện truy vấn con cháu cho nút bối cảnh $E$ với cửa sổ lý thuyết ${pre(E), 0; post(E)}$, vùng tìm kiếm thực sự (vùng trắng) được giới hạn bởi $pre$ của nút con ngoài cùng bên trái và $post$ của nút con ngoài cùng bên phải.
    • Cửa sổ quét mặc định tạo ra một diện tích dư thừa rất lớn (vùng xám), buộc hệ thống phải truy cập nhiều nút chỉ số không chứa dữ liệu kết quả, gây lãng phí nghiêm trọng số lần $I/O$ đĩa cứng.
  • Đề xuất cấu trúc BioX-tree và BioX+-tree:
    • Tác giả đổi tên phương pháp từ XR-tree (tên trong các bài báo công bố ban đầu của tác giả) thành BioX-tree trong luận án để tránh trùng lặp với công trình của nhóm tác giả khác. Đồng thời phát triển phiên bản mở rộng BioX+-tree.
    • Thiết kế cấu trúc chỉ số cải tiến nhằm thu hẹp cửa sổ quét và tái cấu trúc các nút MBR theo hướng bám sát dải phân bố cánh máy bay của dữ liệu tọa độ $(pre, post)$.
    • Tối ưu hóa thuật toán duyệt cây nhằm loại bỏ các nhánh cây chỉ số không chứa các nút có quan hệ anh em, giảm thiểu tối đa các bước duyệt dư thừa trên đĩa cứng.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và cấu trúc dữ liệu

  • Luận án đã đề xuất phương pháp đánh chỉ số BioX-tree và phương pháp mở rộng BioX+-tree (cải tiến từ cấu trúc R-tree). Các phương pháp này khắc phục nhược điểm của cấu trúc R-tree gốc khi áp dụng cho dữ liệu chuyển đổi từ tài liệu bán cấu trúc XML.
  • Về mặt lý thuyết và mô hình giải thuật, cấu trúc đề xuất chứng minh khả năng cắt tỉa các nhánh duyệt dư thừa trên cây chỉ số lưu trữ trên đĩa cứng. Nhờ đó, hệ thống giảm thiểu trực tiếp số lượng thao tác truy xuất $I/O$ đĩa cứng để nạp dữ liệu lên RAM trong quá trình xử lý truy vấn XPath.
  • Tối ưu hóa đặc thù cho các truy vấn trục anh em ($sibling$) và các truy vấn phức hợp tận dụng quan hệ anh em trong thuật toán thực thi.

Đóng góp về mặt thực tiễn và giải pháp kỹ thuật

  • Chứng minh bằng thực nghiệm tính hiệu quả của phương pháp chuyển đổi dữ liệu XML tin sinh học (DNA, Protein, cây phân loài) về không gian số đa chiều trong việc giảm kích thước dữ liệu lưu trữ gốc.
  • Cung cấp giải pháp kỹ thuật hoàn chỉnh cho việc quản trị, lập chỉ số và truy vấn các tệp XML tin sinh học dung lượng lớn trên hệ thống lưu trữ thứ cấp, giải quyết bài toán nút thắt cổ chai về tốc độ truy xuất trên đĩa cứng.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế được chỉ ra trong văn bản

  • Hiệu quả nén không đồng đều: Tỷ lệ nén dữ liệu khi chuyển đổi tài liệu XML sang không gian số phụ thuộc vào cấu trúc từng loại dữ liệu, không đạt kết quả tốt đồng đều giữa các dạng tài liệu XML DNA, Protein và cây phân loài.
  • Suy yếu cấu trúc tối ưu không gian tổng quát: Việc điều chỉnh cấu trúc cây R-tree để tối ưu hóa riêng cho các truy vấn XPath đã làm suy giảm tính tối ưu về mặt hình học không gian của R-tree gốc.
  • Hiệu năng không ổn định trên một số trục truy vấn: Các phép truy vấn không gian thông thường (truy vấn phạm vi thuần túy không phải XPath) cũng như hai loại truy vấn XPath tìm toàn bộ các thẻ đứng trước (preceding) và đứng sau (following) của một thẻ bất kỳ cho kết quả thực thi không tốt, có độ dao động thất thường và khó dự đoán (mặc dù hai trục truy vấn này ít mang ý nghĩa thực tiễn trong các ứng dụng XPath thông thường).

Hướng nghiên cứu tiếp theo

  • Tiếp tục nghiên cứu hoàn thiện cấu trúc BioX-tree và BioX+-tree nhằm mở rộng phạm vi áp dụng, khắc phục sự suy giảm hiệu năng đối với các truy vấn phạm vi tổng quát và các trục preceding, following.
  • Mở rộng nghiên cứu bài toán đánh chỉ số cho phần dữ liệu sinh học (như các đoạn chuỗi DNA) phục vụ các truy vấn tìm kiếm tương đồng xấp xỉ, kết hợp đồng bộ với giải pháp chỉ số cấu trúc đã hoàn thiện.

Giá trị tham khảo

Luận án mang lại giá trị tham khảo chuyên môn cho các nhóm đối tượng:

  • Nghiên cứu sinh, học viên cao học và giảng viên ngành Khoa học máy tính, Hệ thống thông tin và Tin sinh học: Cung cấp tài liệu hệ thống hóa chi tiết về các giải thuật đánh chỉ số sinh học (Smith-Waterman, BLAST, Wavelet, ma trận...), các mô hình nén/đánh chỉ số XML (XGrind, Xpress, XISS, MDX, XPath Accelerator) và toàn bộ các thuật toán vận hành cấu trúc R-tree (ChooseLeaf, AdjustTree, CondenseTree, Quadratic Split...).
  • Kỹ sư phát triển phần mềm và kiến trúc sư cơ sở dữ liệu: Tham khảo quy trình thiết kế hệ thống xử lý dữ liệu lớn kết hợp Hadoop và kho dữ liệu, cũng như phương pháp ánh xạ tài liệu bán cấu trúc XML sang không gian tọa độ số 2 chiều $(pre, post)$ để tối ưu hóa chi phí $I/O$ đĩa cứng.

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

1. Tại sao thao tác $I/O$ trên đĩa cứng lại là điểm nghẽn chính trong khai thác dữ liệu XML tin sinh học và mô hình bộ nhớ ngoài được tính toán như thế nào?

Dữ liệu XML tin sinh học có kích thước từ Gigabyte đến Terabyte nên không thể nạp toàn bộ vào RAM mà phải lưu trên đĩa cứng. Truy xuất đĩa cứng là tuần tự và có tốc độ chậm hơn RAM hơn 100.000 lần. Theo mô hình bộ nhớ ngoài, đĩa đọc/ghi theo từng block logic kích thước $B$. Nếu cơ sở dữ liệu có $N$ đối tượng thì cần tối thiểu $n = \lceil N/B \rceil$ block để lưu trữ, và câu truy vấn trả về $K$ kết quả cần tối thiểu $k = \lceil K/B \rceil$ lần $I/O$. Thuật toán tối ưu phải đạt số lần $I/O$ xấp xỉ mức logarit $(\log_B n + k)$.

2. Hiện tượng phân bố dữ liệu dạng "cánh máy bay" khi chuyển đổi tài liệu XML sang không gian 2 chiều là gì?

Khi ánh xạ các nút của cây XML sang mặt phẳng 2 chiều với trục hoành là thứ tự duyệt trước ($pre$) và trục tung là thứ tự duyệt sau ($post$), các điểm tọa độ không phân bố rải rác ngẫu nhiên mà tập trung lệch hẳn thành một đường chéo/hình thang thẳng hàng giống như cánh máy bay. Hiện tượng này xuất hiện đồng nhất trên mọi tập dữ liệu thử nghiệm từ vài trăm nút đến hàng trăm nghìn nút (đã kiểm thử trên dữ liệu DNA lúa 1.000 nút và dữ liệu Swissprot 20.000 nút).

3. Vấn đề cửa sổ truy vấn dư thừa (vùng xám) trên R-tree xảy ra như thế nào đối với truy vấn con cháu ($descendant$)?

Đối với nút bối cảnh $E$, cửa sổ truy vấn lý thuyết trên R-tree bao phủ phạm vi ${pre(E), 0; post(E)}$. Tuy nhiên, vùng thực sự chứa các nút con cháu chỉ là vùng giới hạn bởi giá trị $pre$ của nút con ngoài cùng bên trái và giá trị $post$ của nút con ngoài cùng bên phải của $E$ (vùng trắng). Phần diện tích chênh lệch giữa hai vùng (vùng xám) là phạm vi quét dư thừa, khiến R-tree phải duyệt qua nhiều nút chỉ số không liên quan trên đĩa cứng.

4. Hệ thống XISS giải quyết bài toán kiểm tra quan hệ tổ tiên - con cháu và các biểu thức đường dẫn bằng cơ chế nào?

XISS sử dụng sơ đồ đánh số gán cho mỗi nút một cặp giá trị $\langle order; size \rangle$. Nút $x$ là tổ tiên của nút $y$ khi và chỉ khi $order(x) < order(y) \le order(x) + size(x)$. Để xử lý các biểu thức đường dẫn phức tạp, XISS phân rã biểu thức thành các biểu thức con và áp dụng 3 thuật toán nối (join): EA-Join (nối phần tử với thuộc tính), EE-Join (nối hai danh sách phần tử) và KC-Join (xử lý bao đóng Kleene $+$, $*$ bằng cách lặp lại EE-Join).

5. Vì sao tác giả đổi tên cấu trúc đề xuất từ XR-tree thành BioX-tree trong văn bản luận án?

Trong các công bố khoa học ban đầu, nghiên cứu sinh đã đặt tên cho phương pháp cải tiến là XR-tree. Tuy nhiên, sau đó tác giả phát hiện tên gọi này bị trùng lặp với một phương pháp chỉ số XML đã được công bố trong một bài báo khác của nhóm tác giả khác. Do đó, trong văn bản luận án chính thức, nghiên cứu sinh đã đổi tên cấu trúc đề xuất thành BioX-tree và phiên bản mở rộng là BioX+-tree.

Kết luận

Luận án giải quyết bài toán tối ưu hóa truy vấn XPath trên các tài liệu XML tin sinh học quy mô lớn thông qua việc chuyển đổi cấu trúc thẻ sang không gian tọa độ số 2 chiều $(pre, post)$ và đề xuất cấu trúc cây chỉ số BioX-tree cùng phiên bản mở rộng BioX+-tree (cải tiến từ R-tree). Bằng việc khai thác đặc thù phân bố dữ liệu dạng dải chéo cánh máy bay và tối ưu hóa nhóm truy vấn quan hệ anh em (chiếm 46% các trục XPath), nghiên cứu đã chứng minh khả năng cắt giảm các bước duyệt cây dư thừa và giảm thiểu số lượng thao tác đọc/ghi $I/O$ trên đĩa cứng. Mặc dù còn hạn chế về hiệu năng trên các trục truy vấn preceding/following và tỷ lệ nén chưa đồng đều giữa các loại dữ liệu sinh học, luận án đã thiết lập một giải pháp kỹ thuật có giá trị thực tiễn cao cho việc lưu trữ và khai thác dữ liệu bán cấu trúc trong tin sinh học.