Native XML数据库的结构连接算法研究

A new structural join algorithm in Native XML database

Native XML数据库的快速查询,可以通过基于XML文档编码的结构连接算法实现。在对现有结构连接算法进行综述的前提下,提出一种新的Native XML数据库的结构连接算法---基于深度均匀划分的结构连接算法(DRIAM)。该算法不要求输入数据AList和DList有序或在其节点编码上建有索引,避免了排序和索引所增加的额外开销;不需要输入数据AList和Dlist全部加载到内存中,可以适应不同内存大小限制的情况,并且该算法时间复杂度非常低。

Structural join operation is the main solution to Native XML database query. Based on the survey of existing structural join algorithms, a new structural join algorithm, depth partition based structural join algorithm （DRIAM） was proposed. In DRIAM, input data sets AList and DList were not necessary to.be ordered or indexed so that the additional cost was avoided. AList and DList were not necessary to be loaded in the memory. Besides, the time-complexity of DRIAM was very low.