Extensible Markup Language (XML) is emerging as a dominant standard for data representation and data exchange over the Internet. As XML is gaining widespread adoption, it is expected that more and more information will be formatted as XML documents. Managing a large amount of XML documents raises a number of challenges. One of the most important issues is the query evaluations against XML documents by which a database will be retrieved to find all those documents that satisfy a given searching condition. The purpose of this thesis is to develop an efficient method for evaluating path-oriented queries in document databases. Path-oriented queries are the queries submitted for retrieving XML documents from databases. Many traditional query evaluation methods often use some types of index structures, such as path indexes, to evaluate path-oriented queries. These methods fail to recognize that the problem of path-oriented query evaluation is in fact a tree inclusion problem. Therefore, they often perform well on simple queries but fail to do so in case of large and complex queries. In this thesis, I propose a new query evaluation method to eliminate this deficiency. The new approach combines a top-down tree inclusion algorithm with the signature technique to achieve high efficiency.
展开▼
