XML多值依赖问题的研究

摘要

XML凭借着众多优势已经成为Web上数据表示与交换的标准。但XML模式所能表示的语义信息却相对有限。同关系数据库相似，设计不好的XML数据模式也会引起更新异常。而Internet的开放性使XML数据更新异常的危害性要远远大于关系数据。因此，完善XML数据库规范化理论已成为必要。本文在对国内外研究现状进行综合分析的基础上，基于DTD，在模式一级对XML中多值依赖进行规范化研究。主要内容如下。 首先，在分析XML文档DTD设计的基础上，对XML多值依赖约束进行研究，基于路径表达式和树元组提出了XML多值依赖的形式化定义。 其次，研究XML多值依赖的推理规则集问题。提出了XML路径集闭包、路径依赖基等基本概念，给出了XML多值依赖的一个有效且完备的推理规则集，并对其有效性和完备性进行了证明。 再次，对XML多值依赖的成员籍问题进行了研究。给出了求解路径依赖基的算法。并基于求解路径依赖基，给出了解决XML多值依赖成员籍问题的算法，并对两个算法的可终止性、正确性进行了证明，对时间复杂度进行了分析。 然后，对XML多值依赖下的范式及其规范化问题进行研究。提出了在XML多值依赖下的范式MXNF的定义，并证明满足MXNF的DTD消除了数据冗余。在此基础上，提出了将任意DTD转换为满足MXNF的DTD的算法，并对算法的正确性、可终止性和时间复杂性进行证明分析。 最后，对XML文档对给定多值依赖集的满足性的检测问题进行了研究。通过定义栈结构和值元组等，定义了文档的控制结构。给出了计算支持元素的算法。给出了文档的分析算法。最后给出了检测XML文档对给定多值依赖集的满足性的XMVD检测算法。并对算法进行了分析。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究背景

1.2研究现状

1.3研究的理论和实际意义

1.4本文主要研究内容

1.5本文组织结构

第2章基本定义及符号

2.1引言

2.2 XML简介

2.2.1 SGML、XML与HTML

2.2.2 XML特性

2.2.3 XML的模式

2.2.4 XML约束

2.3 DTD

2.4 XML树和树元组

2.5其它定义

2.5本章小结

第3章XML多值依赖及其推理规则集

3.1引言

3.2关系数据库中的多值依赖

3.3 XML多值依赖

3.4 XML多值依赖推理规则集

3.4.1 XMVD推理规则集

3.4.2 XMVD推理规则集的有效性

3.4.3 XMVD推理规则集的完备性

3.5本章小结

第4章XML多值依赖的成员籍问题

4.1引言

4.2 XML多值依赖的成员籍问题

4.3路径依赖基求解算法

4.3.1算法描述

4.3.2算法分析

4.4成员籍算法

4.4.1算法描述

4.4.2算法分析

4.5本章小结

第5章XML多值依赖下的范式及其规范化

5.1引言

5.2 XML多值依赖下的范式

5.2.1键和冗余

5.2.2范式XMNF

5.3 XML文档规范化设计与算法

5.3.1规范化设计与算法

5.3.2算法应用举例

5.4本章小结

第6章XML文档对多值依赖满足性的检测

6.1引言

6.2文档控制结构

6.3文档分析

6.4 XMVD检测

6.5本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务和主要成果

致谢

作者简介