Path Match Graph - An Indexing System for Semi-structured Data*

摘要

Indexing on semi-structured data introduces new challenges to the database researchers. Unlike the relational data, semi-structured data do not have fixed schema. Thus, it is difficult to develop an indexing system that can efficiently locate the data. Due to this special nature of the new type of data, an intuitive and straightforward indexing system which implements the indices as a tree may take as much space as the source data itself. This would also incur as much cost searching the index as searching the data. Therefore, employing a regular tree-like indexing system does not provide much performance gain. To cope with these problems, we build an indexing system, called Path Match Graph (or PMG), to index the semi-structured data With the tools provided in our research, the system can be easily maintained and the data can be accessed efficiently through the indices.