An Efficient XML Index for Keyword Query with Semantic Path in Database

Abstract

With the wide adoption of XML in many applications, people begin to manage thousands of XML documents in database. In many applications which backend data source powered by a XML database management system, keyword search is important to query XML data with a regular structure if the user does not know the structure or only knows the structure partially. Essentially, many keyword search can be rewritten to XPath query Q=[//|/]e₁[//|/]e₂[//|/]…[//|/]e_m[text()=str]-suppose there is a keyword search [books William] on XML data about publishing, the result could be the union of the results of the two queries after database system rewriting based on meta data: //books//chapters//authors[text()=”William”]   and //books//authors[text()=”William”]. We propose an XML index structure BTP-Index, composed of XML structure index mechanism which backbone is a Suffix tree, for evaluation of path ([//|/]e₁[//|/]e₂[//|/]…[//|/]e_m) of Q, and XML content index mechanism which is based on Tries & Patricia tree, for the evaluation of [text()=str], filtering part of query Q. Using BTP-Index, we can process query Q efficiently. We have proven the effectiveness of BTP index in our Relation-XML dual engine database management system.