半结构化索引(数据库)

时间：2022-12-12 10:30:02 | 来源：信息时代

时间：2022-12-12 10:30:02 来源：信息时代

    半结构化索引 : 对主要是XML数据的半结构化数据所建立的索引。结构汇总(structural summary)类索引,以XML-树结构中结点的路径信息为基础,采取某种化简方式,使得化简后的树结构只维护不同的路径信息,而不会存在具有相同路径的两个结点。该类索引仍然采取标签有向图的结构。当基于结构汇总进行XML查询处理时,避免了对XML中标签路径相同的结点需要重新遍历所有相同路径的缺陷。
T-索引(T-index): 即模板索引(template index),它是一个通用的用于半结构化数据的索引结构。T-索引具有以下特点: ①允许在空间与通用性之间进行权衡。②索引构建效率比较高。③索引本身占用空间不是很大。④具有很好的推广性。
T-索引的关键思想在于,将数据库对象按等价类(equivalence class)进行分组,每个类包含与路径模板(path template)定义相同的路径。由于计算完全的等价关系代价很高,因此T-索引只考虑计算效率较高的半双拟(bisimulation)或双拟(simulation)关系,为便于描述,本索引中所提到的等价关系均指这种半双拟或双拟等价关系。
如果存在一个半双拟关系～,即v～u,则两个结点v和u是半相似(bisimilar)的,写为v≈_bu。同样的,如果存在两个双拟关系≤,即v≤u和u≤v,则两个结点v和u是相似(similar)的,写为v≈_su。实际上,有一个简单的判断相互半相似的推论。如果两个结点是相互半相似的,则进入它们的输入边(in-coming path)是相同的。
基于上述这种等价关系,利用非确定性自动机(non-deterministic automaton)可以构建一个T-索引,自动机中的状态代表等价类,状态迁移对应于类中对象间的边。在T-索引中,半结构化数据被建模成一个边带有标记的图(labeled graph),图中结点对应数据库中的对象,边对应对象的属性。标记图用DB=(V,E,R)形式化表示,其中V表示图的顶点,是有限的顶点集合; E表示图中相邻结点之间的边,是带标记的边集合;R是根结点集合,从R中某个根结点r_i出发可达V中以r_i为根的所有相关顶点。
一个路径模板t具有T₁x₁T₂x₂…T_nx_n表达形式,其中每个T或者是一个正则路径表达式(regular path expression),或者是P和F二个占位符之一。P可用正则路径表达式来替换,F可用公式替换。一个查询由一条查询路径和一组变量集合构成,其表示形式为“select x_i1,x_i2,…,x_ik from P₁x₁P₂x₂…P_nx_n”,查询路径就是对路径模板的实例化。比如,一个真实的查询具有形式“select x from(*.Restaurant) x(Menu.*.Dinner.*.Lasagna) y” ,其中(*.Restaurant)和(Menu.*.Dinner.*.Lasagna)就是路径模板实例。如果令t=Px₁Px₂…Px_k,那么t₁＝Px就是1-索引,t₂＝^*x₁Px₂就是2-索引。
实际上,有一个简单的判断1-索引和2-索引的推论。1-索引就是从根结点root进入某个结点v的所有路径均相同。2-索引就是一对结点(对应一条标记路径的起始点和终止点)具有相同的标记路径。图1和图2给出了1-索引和2-索引。在图1中,(a)为数据图;(b)为该数据图对应的1-索引;(c)为数据图对应的强数据向导(data guide)。

图1 1-索引

图2 2-索引

A(K)索引(A(K)index):由于1-索引和DataGuide要对XML数据图中的所有路径进行编码,包括长的和复杂的路径,因此,即使当两个结点局部相似时,它们也必须被存储成不同的实例。针对该问题,一种利用局部相似性(local similarity)来构建索引的机制被提出,这就是A(K)索引。A(K)索引的基本思想是: 该索引放弃了索引的绝对准确性,而是将在一起的相似数据进行分组,以便一次更新操作对索引占据空间大小和索引最大范围所产生的影响可以通过一个参数k来控制。
A(K)索引是一种近似的结构汇总(approximate structural summary)索引,是基于k-相互半相似性(k-bisimilarity)来构建的,它具有这样的性质: 如果两个结点u和v是k-相互半相似的,则进入它们的长为k的标记路径集合是相同的。k-相互半相似性≈^k的递归定义如下:
(1)对于任意两个结点u和v,如果u和v具有相同的标记,则u≈⁰v。
(2)对于u的每个父结点u′,都存在一个v的父结点v′,使得u≈^k-1v,则u≈^kv。
k-相互半相似性定义了图中结点的等价关系。通过为每个等价类建立一个索引结点,并将数据结点与索引结点相关联,然后将索引结点用边连接起来,这样就形成了一个索引图。A(K)索引的创建过程是一个逐渐细化的过程:k阶索引的建立是在(k-1)阶索引的基础上实现的,随着k的增加,通过分裂某一指定的等价类,会进一步细化由原等价关系所引入的部分,直至到达最大的双相似性,即获得了1-索引为止。
图3解释了A(k)索引的整个构建过程。首先给出了一个数据图G,以及基于0-半相似性、1-半相似性和2-半相似性的A(0)索引、A(1)索引以及A(2)索引。在当前情况下,2-半相似性索引就是基于最大半相似性的1-索引。

图3 一系列A(K)索引

从图中可以看出,A(0)索引就是将结点标记相同的结点实例合并在一起的索引,如G中标记为D的结点实例{4,5}在A(0)索引中被合并成一个D结点,同样的还有具有两个实例{6,7}的E结点。A(1)索引是将到G中任意一个结点的长度为1的输入边相同的结点合并到一起的索引,如G中结点标记为E的两个实例结点{6,7},由于它们具有相同的长度为1的输入边,因此在A(1)索引中它们被合并成一个E结点。类似地,A(2)索引就是将到G中任意一个结点的长度为2的输入边相同的结点合并到一起的索引,由于G中所有长为2的输入边均不相同,因此,A(2)索引中没有合并结点的存在。同时,在该例中,由于A(2)索引具有最大的半相似性,因此A(2)索引与1-索引相同。