XML多值依赖成员籍问题研究.pdfVIP

XML多值依赖的成员籍问题研究+l onthe Problem forXML Research ofMultivalued Membership Dependency 荣凌燕聂俊岚刘国华 (燕山大学信惠科学与工程学院秦皇岛066004) 扩展的哈希算法来检测XML文档对给定XMVD 1 引言 集的满足性，并给出了算法的性能分析。 同关系数据库相似，XML数据的冗余也会引起 以上方法对ⅪⅡL多值依赖问题虽有涉及，但 更新异常。而由于Internet的开放性，Ⅺm。数据更对其研究仅仅停留在文档一级，脱离了模式的定义。 新异常的危害性远远大于关系数据。因此，对引起 而关于XML多值依赖的成员籍等问题还尚未给出 XML数据更新异常的原因及消除更新异常的方法 有效的解决方法。这样就无法解决XML数据中多 进行研究具有重要的意义。 值依赖的蕴涵问题，直接影响着规范化算法的有效 虽然有关XML数据模式设计的研究已经取得性和完备性。 了一些初步成果，但还没有形成统一的规范和完整 本文基于DTD给出了XML多值依赖的形式 Li 的理论体系。MongLee等人在文[1]中提出 化定义，给出了求解路径依赖基的算法，并基于求解 XIVlL函数依赖的概念，丰富了XML语义，但没有 路径依赖基，给出了XML多值依赖的成员籍算法。 Buneman等人在 从理论上给出完整的证明。Peter 本文的工作增强了XML数据的语义表现力，为进 文[23中讨论了Ⅺ订L绝对键和相对键以及它们相一步完善XML数据库模式设计奠定了基础。 关判定性问题，并在多项式时间里给出键的可推理 性和可判定性。但其都是在有限情况下成立。 2 DTD和XML树 Mareelo Arenas等人引入XML函数依赖表达语 本文采用文[3]中关于DTD及DTD路径的定 义，定义了XML范式——xNF，并提出把DTD 义。用P口￡胁(D)表示D中所有路径的集合。 (DocumentDefinition)转换为XNF的无损连 Type 为统一比较结点“值相等”，本文重新给出XML 接算法o】。但文章模型中的“相等”有二义性。文 树的定义，这是在文[3]基础上修改得到的。 [43基于路径、路径表达式的方法，在不存在DTD 定义1(xML树)一棵xML树定义为丁一 的情况下提出一组XML函数依赖的推理规则，证 (V，lab，ele，att，val，root)，其中 明是正确的，并在一元函数依赖的前提下证明是完 (1)y表示T中结点的有限集； 备的[5]。文[6]在存在DTD的情况下提出一组正 ．(2)lab：V到EfUAttU{S)的函数； 确并完备的函数依赖推理规则集。文[7]初步研究 s(3)ele：从、，到一系列V结点的偏序函数，使得 了XML中的多值依赖(xMvD)，基于路径表达式 给出了多值依赖的定义