里仁学院论文模板2013

第3章 Index Lookup Eager算法原理与实现

} }

}

} }

if(a == i-1) { return true; } else return false;

3.4本章小结

在本章中着重介绍了XML数据及其树结构，SLCA的定义及涉及到的一些概念，Index Lookup Eager算法的原理，以及算法的具体实现。

27

燕山大学本科生毕业设计（论文）

第4章 SLCA查询系统的实现 4.1 数据库的实现

4.1.1解析XML文档

从3.3.1节中可以知道XML文档的结构，要使得文档可带入程序中进行计算必须对文档进行解析。解析程序由C++语言实现，这里不再列出具体算法通过解析程序对XML文档解析后可得到对应的倒排表形式文件。

解析钱文档的形式：

图4-1 XML文档

28

第4章 SLCA查询系统的实现

解析后的倒排表形式：

图4-2 XML文档解析后倒排表

4.1.2数据库的设计

根据解析后的倒排表可以得到关键字对应节点的个数各节点的编码。在本系统中涉及到的对象是关键字，根据用户的需求，使用实体—联系图来建立数据模型。本系统设计的主要实体及其属性为：（下划线部分为主键）

关键字索引表：（关键字名称，节点个数，节点编码） ID索引表：（ID号，关键字名称）

E-R模型的联系用于刻画实体间的关联。一种完整的方式是，对局部结构中任意两个实体类型，依据需求分析的结果，考察局部结构中任意两个实体类型之间是否存在联系。若有联系，进一步确定是1:1,1:N,还是M:N。还要考察一个实体类型内部是否存在联系，等等。为了使E-R图表示的更加清晰，先将E-R图分成实体及其属性图和实体及其联系图。

关键字信息：

29

燕山大学本科生毕业设计（论文）

节点个数 关键字名称 节点编码

图4-1关键字信息实体图

ID号信息：

ID号 关键字名称

图4-2 ID信息实体图

E-R图如图4-3所示

节点个数 节点编码 关键字名称 图4-2 E-R图

关键字名称 查找 ID号 本系统采用MySQL数据库，在其中新建名称为library的数据库。本系统主要通过关键字名称来查询关键字对应的所有节点编码带入算法中进行计算关键字的SLCA。计算得出结果为节点的编码，于是需要通过编码的ID号来查询节点所对应的关键字。本系统数据库各个表的结构如下所示。

Keyword_name表用于记录关键字的信息，当用户输入关键字时可以通过关键字的名称到数据中提取相应的节点编码。

30