Extensible Markup Language (XML) is a simple, flexible text format. XML gains international acceptance for its openness. It can conveniently describe semi-structured data, sparse data, hierarchical data, and metadata, some of which cannot be well managed in RDBMS.

For example, when retrieving the mouse homologs of medaka, we care for the attributes of gene ID, transcript ID, chromosome name and so on. We will get the flat table-formatted result as shown in Fig.1. For the same medaka ensemble gene ENSORLG00000000006, we will have to list it three times, because the gene ID has three different transcript IDs, although the other attributes remain completely unchanged. In flat table format, every attribute can only have one value. For multi-attribute records such as gene ENSORLG00000000006, it has to be separated into different rows. In addition, for the chromosome attributes here only have two different values (only 24 different values even for all data) we are forbidden to aggregate them into two groups. It is the same to strand attribute. Another disadvantage of flat format is that there does not exist any index or query language for it. You have to design the query by yourself.

XML provides us a more flexible way to manage these problems, as demonstrated in Fig. 2. The Gene ENSORLG00000000006 occurs only once, because every cell can have multiple transcript ID attributes. We can also group the data by strand by adding a strand level, and then we can differentiate all genes by their strand direction.

The seminal event, the emergence of WWW in the 1990, increases the need of data interchange and also the need to deal with more heterogeneous data, which greatly extends the application of XML, since XML data model facilitates heterogeneous and semi-structured data management.

The morphological database, SCMD, was built to identify the morphological changes in individual mutants. Cells can be grouped into their stage in the cell cycle, which reflects the duration of the phase statistically. According to your research interest, besides the size of the bud, the phase of cells in the cell cycle can also be categorized based on the detailed information on nuclear DNA and actin localization. XML provides a flexible management for any preference. The following figures illustrate a bud size tree structure (Fig.3) and an actin localization tree structure (Fig.4), respectively.

However, traditional XML query processing methods, such as XPath and XQuery, must strictly follow the path-expressions in XML, which is not only error-prone, but fragile to changes in the underlying XML structure because path expressions cannot accommodate structural variations that may occur in designing or updating XML data. In the above example, to retrieve the cell's bud value and mother roundness if its actin localization is at bud, two completely different queries have to be written for these two tree structures:

Q1: //BudSize[Cell[ActinLoc[@ALoc_value="bud"]]]/Bud_value |

//Cell[ActinLoc[@ALoc_value="iso"]]/MotherRoundness

Q2: //ActinLoc[@ALoc_value="bud"]/Cell//Bud_value |

//ActinLoc[@ALoc_value="iso"]/Cell/MotherRoundness

In this cases a query without the path expressions that looks like (cell, BudSize, ALoc_value, where @ ALoc_value ="bud") will be preferable.

Considering the problems of path-based queries mentioned above, schema-free, XRank, relational-style XML query and keyword search have been proposed. All of these previous approaches design their own native XML databases to solve the problem, which not only needs duplicate efforts, lose the portability, but makes the result unreusable for the later queries because of the inherent structural variations of XML. Therefore, we explore the approach of devising path-free XML queries in standard relational database systems with SQL by utilizing their sophisticated data querying and materializing ability.

In this paper, we firstly propose the idea that process path-free XML queries in a pure RDBMS. It is ideal to list all possible structural variations of a given path-free XML query, though it is non-trivial to devise an efficient implementation due to the combinatorial explosion of potential structural variations, nn-1 tree patterns for n queried items. In addition the problems that RDBMS cannot offer an ideal query plan and efficient XML structural join algorithms also pose a big challenge.

By adding XML-specific information to rewrite SQL clauses, we make RDBMS aware of tree structures, thereby accelerating structural joins. In addition we analyze the optimization plan of the original RDBMS and propose a more efficient structural combination execution plan. In particular, we incorporate functional dependencies into our SQL queries to eliminate the unfavorable results and reduce the query space. We design an XML interface module for Saccharomyces Cerevisiae Morphological Database (SCMD), a database of budding yeast mutants, so as to improve the feasibility of the original database.

Experiments carried out on SQL Server have proven orders of magnitude improvement over the naive implementation, demonstrating the feasibility of path-free XML query processing using a pure RDBMS kernel. Retaining the portability, our RDBMS implementation is as fast as the previous native XML implementation.

At last, we introduce potential applications of our proposed approach to data integration. Utilizing the unique characteristics of our method serves as a unified platform for XML data and relational data. Indeed, we can take advantage of the flexibility of XML, and also the powerful ability of relational database. Dealing with XML query in a pure RDBMS efficiently bridges the semantic gap between XML and relational database.

Fig. 1 Fragment of flat table data, mouse homologs of medaka's

Fig. 2 XML model for mouse homologs of medaka's

Fig. 3 XML model for morphological data: group by budsize

Fig. 4 An alternative XML model for morphological data: group by actin localization

生物学が取り扱うデータは、構造化/階層化して扱うと都合の良いデータが多い。たとえば、組織→細胞→オルガネラ、DNA→エキソン・イントロン構造→タンパク質コード領域、Gene Ontologyにおける遺伝子の機能階層などは典型的な例である。このような構造化/階層化をそのまま自然に記述することができる点で、半構造化データ記述言語XMLは相性がよい。そのため多くの生物学的データベースがXMLにより記述されている。

一方、XMLで生物データを記述する際の問題点として、構造化/階層化の記述方式の自由度が大きいため、同じデータを記述するにしても、設計者により大幅に異なるデータ構造が作られる傾向にあることが挙げられる。そのため、データを問い合わせる際には、各データベースの構造化の仕方に忠実に問合せを作成しなければならない。たとえばXMLデータベース問合せ言語 XPathやXQueryでは、必要なデータへアクセスするためのパスを明示的に記述しなければ所望のデータを抽出することができない。プログラミングに近い作業となるため、一般のユーザー、特に生物学者ユーザーにとっては大きな負担となる。

この問題を解決するためにパスを明示的に記述せず、データの属性だけを宣言的に記述するだけで、システム側がパスを推定して計算するようなパスフリー問合せ言語がいくつか提案されている。パスフリー言語は初心者ユーザーにとっては福音である。しかし、計算時間や計算資源を最適化するデータアクセスパスを推定することは自明でなく、難しい問題である。

そこで本研究ではXML用パスフリー言語の要となる演算として近年注目されている Amoeba Joinを研究対象として最適化技法を提案している。最適化技法が普及することを意識して、関係データベースシステム RDBMS上に実装できるように工夫している。最適化の柱は、(1)木構造を区間木としてRDBMS上に効率よく実装した点、(2) データ間の関数従属性(Functional Dependency)を考慮した最適化技法である。これらについては第2章で詳細に述べられている。

最適化技法の有効性は第3章で詳細に検討されている。処理速度の高速化を実証するために、区間木最適化法を利用した場合の高速化率、関数従属性を考慮した最適化の高速化率は、どちらも模擬データを使って実証されている。またデータ数を増やした場合のScalabilityも良好であることが示されている。

第4章では現実のデータベースを使ってその有効性を議論している。利用したのは出芽酵母のすべての非必須遺伝子を破壊した株の、遺伝子型と表現型を格納したデータベース SCMDである。ゲノム、遺伝子、表現型画像、Gene Ontologyという生物学における主要なデータ要素をSCMDは含んでおり、解析対象として適切な選択である。典型的なデータ抽出が現実的な時間で処理できており、当初の研究目標を達成できている。

まとめると、呉紅艶は、構造化した生物学データベースへのデータ問合せをパスフリー言語により現実的な時間で処理することができるシステムを、幅広く普及しているRDBMS上で実装できる方式を提案することに成功している。情報生命科学の観点から高い貢献である。なお、本論文は、斉藤太郎、森下真一との共同研究であるが、論文提出者が主体となって分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。