半结构化数据的动态树存储模型研究

第２８卷第５期　２０１１年５月　计算机应用与软件　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｖｏ１．２８　Ｎｏ．５　Ｍａｖ　２０１１　半结构化数据的动态树存储模型研究　张雨佳　苏中滨ｈ　吴华瑞　’（东北农业大学工程学院朱华吉　北京１０００９７）　陶　勇　黑龙江哈尔滨１５００３０）　（国家农业信息化工程技术研究中心软件工程部。（农业部农业信息技术重点开放实验室北京１０００９７）　摘要　为了克服半结构化数据存储的不确定性，基于半结构化数据的结构信息可由其模式来描述的思想，提出一种动态树存储　模型。在对对象交换模型ＯＥＭ（Ｏｂｊｅｃｔ　Ｅｘｃｈａｎｇｅ　Ｍｏｄｅ１）进行深度优先遍历，找出所有最大简单路径表达式基础上，采用累加计数原　则将得到的最大路径表达式依次添加到一个动态树中，从而生成存储模型。最后将此模型映射到关系表中，实现了半结构化数据在　关系数据库中的存储与查询。以村镇土地审批处理系统为实例来说明这种存储模型的有效性。　关键词　对象交换模型　半结构化数据模式抽取　动态树　ＲＥＳＥＡＲＣＨ　ｏＮ　ＤＹＮＡＭＩＣ　ＴＲＥＥ　ＳＴｏＲＡＧＥ　ＭｏＤＥＬ　ｏＦ　ＳＥＭＩ．ＳＴＲＵＣＴＵＲＥＤ　ＤＡＴＡ　Ｚｈａｎｇ　Ｙｕｊｉａ　・　Ｓｕ　Ｚｈｏｎｇｂｉｎ　Ｗｕ　Ｈｕａｒｕｉ　’　Ｚｈｕ　Ｈｕａｊｉ　，　Ｔａｏ　Ｙｏｎｇ　（Ｓｃｈｏｏｌ　ｏｆＥｎｇｉｎｅｅｒｉｎｇ，Ｎｏ．ｂｅａｓｔ　Ａｇｒｉｃｕｌｔｕｒａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ　１５００３０，Ｈｅｉｌｏｎｇｆｉａｎｇ，Ｃｈｉｎａ）　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆＳｏｔｆｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎａｔｉｏｎａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｒｅｓｅａｒｃｈ　Ｃｅｎｔｅｒｆｏｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　ｉｎ　Ａｇｒｉｃｕｌｔｕｒｅ，Ｂｅｉｊｉｎｇ　１０００９７，Ｃｈｉｎａ）　（Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙｆｏｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｉｅｓ　ｉｎ　Ａｇｒｉｃｕｌｔｕｒｅ，Ｍｉｎｉｓｔｒｙ　ｏｆＡｇｒｉｃｕｌｔｕｒｅ，Ｂｅｉｊｉｎｇ　１０００９７，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ　Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｏｖｅｒｅｏｍｅ　ｔｈｅ　ｕｎｃｅｒｔａｉｎｔｙ　ｏｆ　ｓｅｍｉ—ｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ　ｓｔｏｒａｇｅ，ａ　ｄｙｎａｍｉｃ　ｔｒｅｅ　ｓｔｏｒａｇｅ　ｍｏｄｅｌ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｄｅａ　ｔｈａｔ　ｔｈｅ　ｓｔｒｕｃｔｕｒｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｏｆ　ｓｅｍｉ—ｓｔｕｃｔｕｒｅｄ　ｄａｔａ　ｃａｎ　ｂｅ　ｄｅｓｃｒｉｒｂｅｄ　ｂｙ　ｉｔｓ　ｍｏｄｅ１．Ｆｉｒｓｔ，ａｌｌ　ｂｉｇｇｅｓｔ　ｓｉｍｐｌｅ　ｐａｔｈ　ｅｘｐｒｅｓｓｉｏｎｓ　ｗｅｒｅ　ｆｏｕｎｄ　ｂｙ　ｃａｒｒｙｉｎｇ　ｏｕｔ　ｔｈｅ　ＯＥＭ　ｄｅｐｔｈ—ｆｉｒｓｔ　ｔｒａｖｅｒｓａ１．Ｔｈｅｎ，ｔｈｅｓｅ　ｅｘｐｒｅｓｓｉｏｎｓ　ｗｅｒｅ　ａｄｄｅｄ　ｉｎ　ｔｕｎａ　ｔｏ　ａ　ｄｙｎａｍｉｃ　ｔｒｅｅ　ｔｏ　ｇｅｎｅｒａｔｅ　ｔｈｅ　ｓｔｏｒａｇｅ　ｍｏｄｅｌ　ａｃｃｏｒｄｉｎｇｌｙ　ｂｙ　ａｄｏｐｔｉｎｇ　ｔｈｅ　ｐｒｉｎｃｉｐｌｅ　ｏｆ　ｃｕｍｕｌａｔｉｖｅ　ｃｏｕｎｔ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｓｅｍｉ－ｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ　ｓｔｏｒａｇｅ　ａｎｄ　ｑｕｅｒｙ　ｉｎ　ｒｅｌａｔｉｏｎａｌ　ｄａｔａｂａｓｅｓ　ｗａｓ　ａｃｈｉｅｖｅｄ　ａｆｔｅｒ　ｍａｐｐｉｎｇ　ｔｈｅ　ｍｏｄｅｌ　ｔｏ　ｒｅｌａｔｉｏｎｓｈｉｐ　ｔａｂｌｅ．Ｔｈｅ　ｔｒｅａｔｍｅｎｔ　ｓｙｓｔｅｍ　ｏｆ　ｌａｎｄ　ｅｘａｍｉｎｉｎｇ　ａｎｄ　ａｐｐｒｏｖｉｎｇ　ｉｎ　ｖｉｌｌａｇｅ—ｔｏｗｎ　ｗａｓ　ｔａｋｅｎ　ａｓ　ｔｈｅ　ｅｘａｍｐｌｅ　ｔｏ　ｉｌｌｕｓｔｒａｔｅ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｉｓ　ｍｏｄｅ１．　Ｋｅｙｗｏｒｄｓ　Ｏｂｊｅｃｔ　ｅｘｃｈａｎｇｅ　ｍｏｄｅｌ（ＯＥＭ）　Ｓｅｍｉ－ｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ　Ｍｏｄｅ　ａｂｓｔｒａｃｔｉｏｎ　Ｄｙｎａｍｉｃ　ｔｒｅｅ　半结构化数据存储模型，以有效解决半结构化数据类型和模式　０引　言　半结构化数据是指那些结构隐含或无规则、不严谨的自我　描述型数据，介于严格结构化数据（如关系数据库和对象数据　库中的数据）和完全无结构的数据（如声音、图像文件）之间－－　。　由于半结构化数据缺乏类型信息，只有有效地将其存储之后，才　不断变化的问题，并将此模型映射到关系表中，实现了半结构化　数据在关系数据库中的存储与查询。　１　半结构化数据描述模型　在将半结构化数据存储之前，首先要找到一个高度灵活的　数据模型，它能够表达不同类型数据，并对半结构化数据的模式　进行描述。而对此目前已经提出了多种描述形式，有基于图的　能对其进行索引及查询处理，从而方便管理，因此，半结构化数　据存储策略将是一个十分重要的研究课题。　近年来大量国内外相关研究机构致力于半结构化数据的存　储与查询处理的研究。目前，提出并实现了的存储技术主要有：　文本文件方式、ＲＤＢ方式及ＯＯＤＢ等方式。其中，文本文件的　描述形式和基于逻辑的描述形式。在这里采用比较有代表性的　基于图的ＯＥＭ模型。　ＯＥＭ是斯坦福大学Ｓｅｒｇｅ　Ａｂｉｔｅｂｏｕｌ教授等提出的用来描述　半结构化数据的描述模型。该模型中所有的实体均为对象，由　表示对象的结点和带标签（１ａｂｅ１）的有向边构成　。每个ＯＥＭ　存储方式存储难度较大，不利于数据的检索和管理。ＲＤＢ存储　方式运算效率低，即使一个非常简单的查询也将会产生较多的　联结。ＯＯＤＢ存储方式在事先不知道数据的类型信息时，数据　加载的代价可能会很高，并且一旦类型发生了变化，将会导致代　价更高的模式更新，而半结构化数据正是一种缺乏类型信息，并　且数据类型和模式不固定的数据，因此也不适合用ＯＯＤＢ方式　存储。　针对以上各种方式的局限性，本文提出～种动态树结构的　收稿日期：２００９—１２—２９。“９４８”项目（２００６一Ｇ６３）；国家科技支撑　计划（２００６ＢＡＪ０９Ｂ０５）；国家高技术研究发展计划项目（２００７ＡＡ０１　Ｚ１７９）；国家科技支撑计划子课题（２００６ＢＡＪ０９　Ｂ０７０２）；黑龙江省教育厅　自然科学重点项目（１１５４ｚｉ０１１）。张雨佳，硕士生，主研领域：计算机决　策支持系统。　第５期　张雨佳等：半结构化数据的动态树存储模型研究　２．１模式的定义　８７　对象都可用一个４元组表示：（ｏｉｄ，ｌａｂｅｌ，ｔｙｐｅ，ｖａｌｕｅ）。其中ｏｌｄ　是对象的唯一标识。ｌａｂｅｌ是对象的标签描述，为一字符串表达　对象的含义。ｔｙｐｅ是对象类型，ＯＥＭ对象类型有两类：原子对　象和复杂对象。原子对象是不可再分的基本类型，具有ｉｎｔｅｇｅｒ、　模式定义的提出需要引入一些ＯＥＭ相关概念知识，现结合　图１给出几个定义和符号表示如下：　定义１　简单路径表达式ｓｐｅ令ｌｉ是对象引用中的一个　标签，其中ｉ＝１，…，ｎ（ｎ≥１），则ｓｐｅ＝ｌｌ，１２，…，　就是一个长　度为ｎ的简单路径表达式。　定义２　最大简单路径表达式ｎａｐｅ若有一个简单路径表　ｓｔｒｉｎｇ等类型的值。复杂对象是对象引用的集合，每一个对象引　用指向另一个对象，不失一般性。　现结合村镇土地审批流程处理中的相关数据，在分析了流　程数据具有半结构性的基础上，构造出一个有关宅基地的ＯＥＭ　描述模型。　达式集合｛ｓｐｅｌ，ｓｐｅ２，…，ｓｐｅｎ｝，对于某个ｓｐｅｉ在集合中不存在任　何ｓｐｅｉ的超集，则称ｓｐｅｉ是该集合中的最大印ｅ，记作ｒｏｐｅ。　由于村镇土地流转业务复杂、审批处理流程标准不统一，会　使相同的土地审批处理在各村镇问有着各异的流程，甚至因为　某项政策的改变，同一个村镇的某项审批处理流程也会随之发　生变动。比如同样一个关于宅基地申请的处理流程，有的村镇　只需“农民申请”、“村委审议”和“乡镇政府审批”三个业务点　组成，有的村镇还需“实地调查审核”这个业务点，即相同的流　程数据可能具有不规则的结构，并可能随时处于变化之中，从而　说明土地审批处理中涉及的流程数据具有半结构性。为简单起　见，在一定程度上简化了对宅基地的描述，只对其部分主要属性　进行了ＯＥＭ模型表达，如图１所示，认为它由用户标识符、所有　者、面积、宅基地申请审批流程以及宅基地建房审批流程描述，　并且每个流程业务点也只列出其中比较重要的几个属性，例如　规划主体（Ｓｕｂｊｅｃｔ）、规划操作（Ｏｐｅｒａｔｉｏｎ）、规划客体（Ｏｂｊｅｃｔ）　等。其中，用户标识符由用户根据其不同的含义进行定义，例如　此块宅基地记为ｚｊｄ１。　图１宅基地的ＯＥＭ描述模型　２半结构化数据的动态树存储模型　半结构化数据的模式是用于描述数据结构信息的，而不是　对数据结构进行强制约束　，但由于半结构化数据的模式与数　据是混淆在一起的，为此模式抽取就成为找到半结构化数据中　的结构，发现数据对象间关系，从而将其存储到关系数据系统中　的首要步骤。基于这样的思想，本研究提出一种动态树存储模　型，此模型可体现半结构化数据的模式信息，方便我们发现半结　构化数据的结构。下面仍以图１为例，首先对半结构化数据的　模式进行定义，明确模式抽取的目标对象。然后详细介绍如何利　用层次结构思想和累加计数原则，生成具有半结构化数据模式　的动态树存储模型。　例：ＳｈｅｎｇＱ．ＰｌａｎＰｏｉｎｔ．Ｓｕｂｊｅｃｔ是一个长度为３的简单路径　表达式；集合Ｓ＝｛ｓｐｅｌ＝ＳｈｅｎｇＱ．ＰｌａｎＰｏｉｎｔ；ｓｐｅ２＝ＳｈｅｎｇＱ．　ＰｌａｎＰｏｉｎｔ．Ｓｕｂｊｅｃｔ｝，则ｓｐｅ２即为该集合的ｒｏｐｅ，ＳｈｅｎｇＱ为ｓｐｅｌ与　ｓｐｅ２的共享前缀。　定义３频繁简单路径表达式ｆｏｅ　ｓｐｅ出现在ＯＥＭ模型中　的个数，称作ｓｐｅ的支持度计数，记作ｓｕｐ（　ｅ）。当ｓｕｐ（ｓｐｅ）≥　ａｒｉｎ＿ｓｕｐ（最小支持度阈值）时，ｓｐｅ就为频繁的ｓｐｅ，记作ｆｐｅ。　定义４数据路径表达式ｄｐ令０　是一个对象ｉ：０，１，　…，ｎ，对象０　和标签ｌｉ以逗号为间隔并交替出现的序列，即　＝０。，ｚ。，０。，ｚ　，…，ｚ　，０　，和就称为一个源于００的止于０　的长度为ｎ的数据路径表达式。　例：　＝｛１．ＳｈｅｎｇＱ．４．ＰｌａｎＰｏｉｎｔ．６．Ｓｕｂｊｅｃｔ．１７｝，是一个源　于１的止于ｌ７的长度为３的数据路径表达式。　半结构化数据的模式抽取是为了找到数据中的结构，发现　数据对象问关系，因此对ＯＥＭ模型中的连接对象要比对象本身　更感兴趣。而根据上面的概念可知，ｓｐｅ要比　更能反映半结　构化数据的一般结构。为此，将待抽取的数据模式定义为ＯＥＭ　中所有频繁的最大简单路径表达式（ｍｐｅ）　。　２．２　生成具有层次结构的最大简单路径表达式集合　为了找到ＯＥＭ中所有频繁的ｍｐｅ，本文需首先试图生成一　个由所有ｍｐｅ构成的集合。由于ＯＥＭ模型具有层次性，所以可　充分利用深度优先遍历的优势，对图１中的ＯＥＭ模型进行深度　优先遍历，找出所有ｍｐｅ并生成集合。借鉴文献［４］提出的分　层结构的思想，可有效解决ＯＥＭ模型的分支问题。因此本文同　样采用此思想，将遍历得到的ｒａｐｅ添加层次标记，从而生成…・个　具有层次结构的ｍｐｅ集合，记作ｓ。这样，图１中的ＯＥＭ模型　经深度优先遍历之后，即可生成集合５｛ｕｉｄ．．．，Ａｒｅａ　，Ｏｗｎ—　ｅｌ＂】３，ＳｈｅｎｇＱ１—４．ＰｌａｎＰｏｉｎｔ　２一１．Ｓｕｔ＃ｃｔ　３一ｌ・－…・｝。　２．３构造动态树结构的存储模型　得到集合Ｓ之后，便期望从中找到所有频繁的ｍｐｅ，即提取　出半结构化数据的模式。为此本研究提出一种累加计数原则，　将Ｓ中各个元素ｍｐｅ依次作为树的分支，最终生成一个动态树。　由于通过此原则生成的树可方便地对数据的模式进行提取，找　到半结构化数据的隐含结构，发现对象问的关系，从而将半结构　化数据进行存储，于是本文提出将此树结构作为半结构化数据　的存储模型。　根据ＯＥＭ模型的基本特点并结合图１，可对树的结构进行　如下定义：　＃ｄｅｆｉｎｅ　ＭＡＸ—．ＴＲＥＥ—．ＳＩＺＥ　５００　ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　Ｎｏｄｅ｛　，７　谗缝　ｓｔｉｒｎｇ　ｌａｂｅｌ；　／／ｍｐｅ的共享前缀　ｓｔｒｉｎｇ　ｌｅｖｅｌ—ｃｏｄｅ；　／／ｌａｂｅｌ的层次标记　ｉｎｔｅｇｅｒ　ｉｄ；　／／节点在ＯＥＭ中的ｏｉｄ　８８　ｍｔｅｇｅｒ　ｃｏｕｎｔ；　计算机应用与软件　／／计数器，记录节点在ＯＥＭ中出现的次数　ｃｈｉｌｄ　２０１１血　根据累加计数原则可知，通过此树各节点的ｃｏｕｎｔ值即可方　便地找出所有频繁的ｍｐｅ，抽取出半结构化数据的模式，发现数　据的结构。　该存储模型除了可方便我们提取数据的结构信息以外，还　有着动态性，可随时方便地进行更新，以适应半结构化数据的高　度灵活扩展和不规则性。比如从图２可以看出，此时的宅基地　建房审批流程是由“农民申请宅基地使用权”、“村委会对农民　提交材料复核”、“镇土地管理所现场勘测宅基地”以及最终的　“县级政府正式批准宅基地建房”这４个业务点组成。但若某　ｓｔｒｕｃｔ　Ｎｏｄｅ　／／一个指向子节点的指针　，／＿Ｉ《遗锗　｝Ｎｏｄｅ；　ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　Ｔｒｅｅ｛　Ｎｏｄｅ　ｎｏｄｅｓ［ＭＡＸ—ＴＲＥＥ—ＳＩＺＥ］；　ｉｎｔ　ｒ，ｎ；　｝Ｔｒｅｅ；　／／根的位置和节点数　接下来，根据上述结构定义，开始构造动态树。其中根节点　的ｌｅｖｅｌ—ｃｏｄｅ和ｃｏｕｎｔ都为０，ｌａｂｅｌ记为“ＺＪＤ”，ｉｄ记录该宅基地　的ｏｉｄ信息。而在将集合Ｓ中的各个元素ｍｐｅ作为分支依次添　村镇的宅基地建房申请审批处理中，又规定建设单位或个人必　加到树中时，需依据累加计数原则，以便日后提取数据的模式信　息。即：添加ｍｐｅ元素时，判断此元素所含的节点与当前树中的　前一个节点之间是否有共享前缀，即它们的ｌａｂｅｌ是否相同。若　无共享前缀（１ａｂｅｌ不同），则创建新的分支，即直接将此元素添　加到树中；若有共享前缀（１ａｂｅｌ相同），则需再进一步判断它们　的ｌｅｖｅｌ—ｃｏｄｅ的值是否相同。若ｌｅｖｅｌ—ｃｏｄｅ的值相同，则说明此时　在添加的是ＯＥＭ模型中的一个分支，即只需在原有节点下添加　一个分支即可。例如：在添加元素ＳｈｅｎｇＱ１—３．ＰｌａｎＰｏｉｎｔ２—１．Ｏｂ一　ｃｔ３－３时，因为当前树中的前一个元素为ＳｈｅｎｇＱ１—３．ＰｌａｎＰｏｉｎｔ２—　１．Ｏｐｅｒａｔｉｏｎ３—２，判断出它们的ｌａｂｅｌ（ＳｈｅｎｇＱ．ＰｌａｎＰｏｉｎｔ）以及　一　ｅｌ—ｃｏｄｅ（１－３和２—１）值都相同，说明此时添加的是ＰｌａｎＰｏｉｎｔ节　点的一个分支，只需在原有节点ＰｌａｎＰｏｉｎｔ：２—１：１６：１下添加　Ｏｂｊｅｃｔ：３—３：１９：１这一分支。若判断它们的ｌｅｖｅｌ—ｃｏｄｅ值不同，　则说明此时添加的元素与之前节点不是兄弟节点，则ｃｏｕｎｔ值加　１，并将此元素涉及到的每个节点添加一条新纪录，记录保存着　ｌａｂｅｌ、ｌｅｖｅｌ—ｃｏｄｅ、ｉｄ和ｃｏｕｎｔ的新值，进而转入开始处理新的分　支。例如：在添加元素ＳｈｅｎｇＱ１—３．ＰｌａｎＰｏｉｎｔ２—２．Ｓｕｂｊｅｃｔ３－４时，判　断出其与当前树中的前一个元素ＳｈｅｎｇＱ１—３．ＰｌａｎＰｏｉｎｔ２—１．Ｏｂ一　ｃｔ３，３的ｌａｂｅｌ值相同，但ｌｅｖｅｌ—ｃｏｄｅ值不同，因此说明此时在添　加的是一个新的分支，需要为ＰｌａｎＰｏｉｎｔ节点添加一条Ｐｌａｎ—　Ｐｏｉｎｔ：２－２：７：２的新纪录。依此类推，直至集合Ｓ中的所有元素　添加完毕，此时一个由ｍｐｅ构成的树就构造完成。　为了节省空间，对构造出的树又做了进一步的改进：将每个　结构节点的定义信息ｌｅｖｅｌ—ｃｏｄｅ、ｉｄ以及ｃｏｕｎｔ等作为一个元素依　次链成一个以各相应节点ｌａｂｅｌ为名字的队列。具体改进过的　树结构如图２所示。　一　｝ｚＪＤ　００：Ｏｌ　ＩＦＩＩ￣：５：Ｉｉ　￣１１４：１：１ｊ胁｛　２：ｌｌ　Ｏｗｎｅｒ［１．８：３：ｌ｝　碉１舭ｌ　Ｉ２吨９：ｌ：　２４：６：１　２矗１Ｏ：２：　２－２：７：２；　２－６：１１：３；　∞１２：４｝　３４：２２：２；　Ⅲ　１：３７：　图２动态树结构的半结构化数据存储模型　须在用地经批准后，要由镇土地管理所现场验线，核实无误后方　可施工，为此需要对宅基地建房申请审批流程增加“镇土地管　理所现场验线”这个业务点，则只需在图２所示的树结构基础　上，对ＪｉａｎＦ下的ＰｌａｎＰｏｉｎｔ节点及其分支节点各添加一条记　录：｝ＰｌａｎＰｏｉｎｔ：２—８：３８：５；Ｓｕｂｊｅｃｔ：３—２２：３９：５；Ｏｐｅｒａｔｉｏｎ：３—２３：４０：　５；Ｏｂｊｅｃｔ：３－２４：４１：５｝，而无需改变整个树结构。　由此可见，借助此动态树的存储模型，即可方便地发现半结　构化数据的结构，又可实现半结构化数据的动态存储，解决其往　往不规则，并且经常处于变化之中的问题。　３　半结构化数据的存储与查询　３．１半结构化数据的存储　生成存储模型后，下一步需要解决的问题就是半结构化数　据如何进行物理存储。由于关系数据库技术已发展成为一种成　熟的数据库技术，所以若能利用关系数据库来存储半结构化数　据，就可重用关系数据库的查询优化器和事务处理机制，以保证　半结构化数据的一致性和完整性　Ｊ。为此，本研究继续提出将　生成的动态树存储模型映射到关系表中，以实现半结构化数据　的存储。　首先，根据存储模型中节点的性质，将各节点划分为两类：　模式节点和数据节点，对这两类节点将分别采用不同的方式映　射到关系数据库中。为此，需要对存储模型中各节点的属性数　据所具有的结构程度进行简单的判断，即根据节点出现的数目　决定将该节点转化数据节点或模式节点。当节点数目大于某个　阈值ｎ时，则将其定义为模式节点；否则，视为数据节点。阈值　１的确定必须合理，如果ｎ的取值太小，有可能形成大量元组　数目较小的关系，从而影响数据存储和处理的效率；ｎ的取值　过大，则不能充分地发挥出这种存储模型的优势。　判断出节点类型后，就可对这两类节点将分别采用不同的　方式映射到关系数据库中。其中，由于数据节点和ＯＥＭ描述模　型中的数据节点类似，用来表示源数据中结构松散的数据。所　谓“松散”是指这类节点常以属性值的形式出现在ＯＥＭ描述模　型中，而在存储模型中，也表现为叶节点，用来描述模式节点，因　此它们大多数可以作为属性保存在对应模式节点的主关系　表中。　根据节点划分规则可知，模式节点可理解为ＯＥＭ描述模型　中由类型相近的数据节点组成的集合，对于模式节点的存储是　本研究存储映射工作中的难点和重点。每个模式节点都有一个　对应的主关系表和从属关系表，用来保存集合中各源数据节点　的相关信息。　在模式节点主关系表中，由于源数据节点在主关系表中唯　一对应一个元组，因此可以用源数据节点的本身　作为主键。　第５期　张雨佳等：半结构化数据的动态树存储模型研究　８９　而该表中的其他属性域用来保存集合中多数节点的共有属性值，　即某属性出现的次数较频繁，就将其作为一个属性域，这样可以　保证表中大多数的元组具有该属性域，避免存储的浪费。为此，　８　ｆ　乡镇政府　Ｉ　审批　ｆ　宅基地　表３建房业务点主关系表（Ｙｅｗｕ＿ＪＦ＿ｍａｉｎ）　ＩＤ　Ｓｕｂｊｅｃｔ　Ｏｐｅｒａｔｉｏｎ　Ｏｂｉｅｃｔ　本研究设定一个阈值　，并设定／２＝０．５，如果具有某属性值的　节点数目与总的节点数目的比值较大（大于　），即该集合中有　过半的节点都有该属性，则在主关系表中添加此属性域；而对于　９　ｌＯ　ｌ１　ｉ２　农民　村委会　镇土地管理所　县级政府　申请　复核　现场勘测　审批　宅基地　那些少量节点独有的属性域则需要创建单独的属性从属关系表。　在该属性从属关系表中除了要保存那些少量节点的值和类型信　宅基地　宅基地　息以外，还要根据节点队列中保存的ｃｈｉｌｄ指针所指向的节点，保　存这些节点的父节点　。　模式节点从属关系表，用来保存模式节点之间的从属关系，　即该表的属性域为连接模式节点的边的开始节点　和目标节点　。通常情况下，主关系表中的一个节点可对应其他主关系表中　的多个节点，因此，在模式节点从属关系表中，源数据节点的　是该表的外键。节点　作为主关系表和从属关系表的主键和外　键，在数据查询时，经常用来确定关系元组，因此可在主关系表和　从属关系表的ＩＤ属性域上建立哈希索引。　根据以上的映射思想，并结合图２生成的存储模型，具体的　映射过程及生成的表结构如下：　（１）节点类型的划分宽度优先遍历图２的存储模型，根据　规则找出模式节点ＺＪＤ（宅基地）、Ｙｅｗｕ＿ＳＱ（申请业务点）和Ｙｅｗｕ　一，Ｆ（建房业务点），其他节点视为数据节点。如表１、表２和表３　所示。　（２）模式节点主关系表和属性从属关系表的生成　分别对　ＺＪＤ、Ｙｅｗｕ＿ＳＱ和Ｙｅｗｕ一，Ｆ这三个模式节点生成各自的主关系表：　ＺＪＤ＿ｍａｉｎ、Ｙｅｗｕ＿ＳＱ＿ｍａｉｎ以及Ｙｅｗｕ一，Ｆ—ｍａｉｎ。在生成模式节点　主关系表时，关键的步骤就是确定关系表的属性域，以Ｙｅｗｕ—ＪＦ　模式节点为例简略说明Ｙｅｗｕ＿ＪＦ＿ｍａｉｎ属性域的确定过程。由于　ＪｉａｎＦ分支下的ＰｌａｎＰｏｉｎｔ模式节点的总节点数目为４，而Ｏｂｊｅｃｔ　的ｃｏｕｎｔ为３，判断具有此属性值的节点数目与总的节点数目的　比值，显然３／４大于本研究设定的阀值　（７２＝０．５），则将Ｏｂｊｅｃｔ　添加到ＰｌａｎＰｏｉｎｔ的主关系表的属性域中。而对于Ｄａｔｅ属性，其　ｃｏｕｎｔ为１，由于１／４小于０．５，则Ｄａｔｅ的值将保存在ＰｌａｎＰｏｉｎｔ的　属性从属关系表Ｙｅｗｕ一，　ｔｔＳｕｂ中，并根据图２中节点ＰｌａｎＰｏｉｎｔ　和Ｄａｔｅ保存的ｃｈｉｌｄ指针，存储属性域Ｙｕａｎｌｄ和　的值，以便　日后能够对少量节点独有的属性进行查询。如表７所示。　（３）模式节点从属关系表的生成结合图２生成的存储模　型，确定三个模式节点ＺＪＤ、Ｙｅｗｕ—ＳＱ和Ｙｅｗｕ—ＪＦ之间的从属关　系，从而生成模式节点从属关系表ＺＪＤ—Ｓｕｂ、ＳＱ—Ｓｕｂ以及　一　Ｓｕｂ。如表４、表５和表６所示。　（４）建立索引　分别在ＺＪＤ、Ｙｅｗｕ—ｓｑ和Ｙｅｗｕ一，Ｆ的主关系　表和从属关系表的ＩＤ属性域上建立哈希索引，方便数据的查询。　表１宅基地主关系表（ＺＪＤ　＿ｍａｉｎ　）表２申请业务点主关系表（Ｙｅｗｕ—ＳＱ＿ｍａｉｎ）　ＩＤ　Ｓｕｂｉｅｃｔ　Ｏｐｅｒａｔｉｏｎ　Ｏｂｊｅｏｔ　６　农民　申请　宅基地　７　村委　审议　宅基地　表４宅基地从属关系表（ＺＪＤ＿Ｓｕｂ）　ＩＤ　ＳｕｂＩｄ　００　４　００　５　表６建房审批从属关系表（ＪＦ—Ｓｕｂ）　ＩＤ　ＳｕｂＩｄ　５　９　５　１０　５　ｌ１　５　１２　表７　建房业务点属性从属表（ＹｅｗｕｊＦ—ＡｔｔＳｕｂ）　ＹｕａｎＩｄ　１　Ｉｄ　ＶａｌＨｅ　１Ｏ　３１　２ｏｏ３—９　用关系表来存储半结构化数据必须保证不破坏或丢失原来　数据的结构信息和数据信息，因此，除了要存储节点对象值之外，　还要存储对象之间的关系。本研究在上述的存储映射规则中也　注意了这方面的内容。从上面的存储映射规则可以看出，其中，　模式节点的主关系表就是用来对节点对象的存储，而模式节点从　属关系表和属性从属关系表都是对对象间关系的存储。　综上所述，本研究提出的这种存储方法将半结构化数据在很　大程度上转化为关系数据，在转化的过程中既保证了半结构化数　据的完整性，又没有对半结构化数据结构复杂、灵活易变的特点　进行过多的限制，为利用半结构化数据的结构信息提供了有效　途径。　３．２半结构化数据的查询　通过上面的存储映射，已将半结构化数据存储到关系数据库　中，因此日后对半结构化数据的查询就可转化为我们所熟知的关　系表的查询，同时，也可应用传统的关系查询优化的思想和查询　技术来选择具体的查询执行计划。　例如，要查询此块宅基地（ｕｉｄ为ｚｊｄ１）建房的流程，只需写基　于关系的ＳＱＬ查询语句：ｓｅｌｅｃｔ　Ｓｕｂｊｅｃｔ，Ｏｐｅｒａｔｉｏｎ，Ｏｂｊｅｃｔｆｒｏｍ　Ｙｅｗｕ—　ＪＦ＿ｍａｉｎ　ｗｈｅｒｅ　１１）ｉｎ（ｓｅｌｅｃｔ　Ｓｕｂｌｄｆｒｏｍ　ＪＦ—Ｓｕｂ　ｗｈｅｒｅ　ＩＤ　ｉｎ（ｓｅｌｅｃｔ　ＳｕｂｌｄｆｒｏｍＺＪＤ＿ＳｕｂｗｈｅｒｅＩＤｉｎ（ｓｅｌｅｃｔＩＯｆｒｏｍＺＪＤ＿ｍａｉｎｗｈｅｒｅ　ｕｉｄ　＝ｚｊｄ１）））即可查询到此块宅基地的所有建房流程。同样，也可　以对宅基地的其他属性信息进行查询。　由此可见，将此动态树结构的存储模型映射到关系表中之　计算机应用与软件　２０１１皇　后，即可利用关系数据库系统对半结构化数据实现查询与分析　处理。　４应用实现　将本研究提出的动态树存储模型应用到村镇土地审批处　理系统中，可有效地对土地审批处理过程中涉及的各流程数　据进行动态存储，实现流程的动态定制。该实例系统的具体　实现技术路线包括以下几步：首先，借助ＯＥＭ模型针对不同　村镇的实际情况进行流程数据的动态定义，以解决流程数据　的描述问题。然后，利用本研究提出的思想，生成一个具有流　程数据模式信息的动态存储模型。最后，将模型映射到关系　表中，实现流程数据的动态存储。以此技术路线为准则，制定　了系统流程图，如图３所示。　囤一（　一ｊ　［至　～囤～　图３实例系统流程图　５结束语　本研究遵循着从概念模型到逻辑模型，再到具体物理存储　的思路，逐步研讨如何实现半结构化数据的存储与查询。首先　借助ＯＥＭ模型（概念模型），并结合模式的定义，构造出半结构　化数据的动态树存储模型（逻辑模型），然后根据一定的映射规　则，将生成的存储模型映射到关系数据库中，实现了半结构化数　据在计算机内部的物理存储。该存储模型不仅能够体现半结构　化数据的模式信息，方便抽取数据结构，还可针对半结构化数据　类型信息缺乏、描述结构不严格且不断变化等特点，随时灵活地　进行更新，克服了半结构化数据存储的不确定性。另外，将此模　型应用到村镇土地审批处理系统中，有效解决了个性化流程数　据的动态存储问题，实现了审批处理流程的灵活定制，通过实践　证明此模型的可行性和有效性。下一步工作的重点将是半结构　化数据的增量更新。　参考文献　［１］Ｓｔｅｆａｎｋｉｓ　Ｅ．Ｍｏｄｅｌｌｉｎｇ　ｓｅｍｉ—ｓｔｒｕｃｔｕｒｅｄ　ｇｅｏｇｒａｐｈｉｃａｌ　ｄａｔａ［Ｊ］．Ｉｎｔｅｒｕａ－　ｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆＧｅｏｇｒａｐｈｉｃａｌＩｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，２００３，１７（６）：５１７—　５４６．　［２］Ａｂｉｔｅｂｏｕｌ　Ｓ．Ｑｕｅｒｙｉｎｇ　Ｓｅｍｉ—ｓｔｕｒｃｔｕｒｅｄ　Ｄａｔａ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＩＣＤＴ　Ｄｅｌ－　ｐｈｉ，Ｇｒｅｅｃｅ：［Ｓ，ｎ．］，１９９７．　［３］吕橙，魏楚元，张瀚韬．基于ＯＥＭ模型的半结构化数据的模式发现　［Ｊ］．计算机工程与应用，２００６，３４：１６２—１６５，１８１．　［４］叶飞跃，蒙德龙，员红娟．一种用于存储与查询半结构化数据的新　方法［Ｊ］．计算机工程，２００６，３２（１９）：９１—９３．　［５］冯建华，王钦克，周立柱，等．半结构数据的存储模型和查询执行　［Ｊ］．计算机科学，２００２，２９（１０）：６—１０．　（上接第７４页）　图７联邦门户的协作页面　从以上案例可知，在传统的联邦门户环境中，消费者门户虽　然可以订阅生产者门户的Ｐｏｒｔｌｅｔ，但不能针对远程Ｐｏｒｄｅｔ的协　作特性进行二次开发，因为远程Ｐｏｒｔｌｅｔ和本地Ｐｏｒｔｌｅｔ不具备协　作能力，这样就为Ｐｏｒｔｌｅｔ的再利用增加了额外的迁移和开发负　担。而联邦协作框架增强了异构门户的互操作性，能够支持远　程Ｐｏｒｔｌｅｔ和本地Ｐｏｒｔｌｅｔ的协作，使得Ｐｏｒｔｌｅｔ开发人员能够复用　远程Ｐｏｒｔｌｅｔ的协作能力，促进Ｐｏｒｔｌｅｔ的再利用，从而达到减少工　作量、充分整合遗留ＩＴ资源的目的。　５　结论　随着联邦门户系统的出现，要求门户能提供一个通用的　Ｐｏｒｔｌｅｔ协作框架，但ＪＳＲ２８６和ＷＳＲＰ２．０的协作都存在对规范　的依赖，使得门户开发人员在门户构建中不能有效使用可协作　的远程Ｐｏｒｔｌｅｔ构建业务页面。本文通过引入了协作信息转换机　制和服务注册机制，消除依赖关系。文中给出了协作信息转换　和服务注册的原理，同时对联邦门户系统中的Ｐｏｒｔｌｅｔ容器和代　理容器进行扩展以支持远程Ｐｏｒｔｌｅｔ和本地Ｐｏｒｔｌｅｔ的协作。该方　法已在门户中间件ＯｎｃｅＰｏｒｔａｌ中实现，并很好地解决了联邦门　户系统中协作的问题。　参考文献　［１］Ｗｅｇｅ　Ｃ．Ｐｏｒｔａｌ　ｓｅｒｖｅｒ　ｔｅｃｈｎｏｌｏｇｙ［Ｊ］．ＩＥＥＥ　Ｉｎｔｅｒｎｅｔ　Ｃｏｍｐｕｔｉｎｇ，２００２　（６）：７３—７７．　［２］ＪＳＲＩ６８　Ｐｏｒｔｌｅｔ　Ｓｐｅｃｉｆｉｃａｔｉｏｎ１．０［Ｓ］．Ｊａｖａ　Ｃｏｍｍｕｎｉｔｙ　Ｐｒｏｃｅｓｓ，２００３．　［３］ＷＳＲＰ　ｖ１．０　Ｗｅｂ　Ｓｅｒｖｉｃｅｓ　ｆｏｒ　Ｒｅｍｏｔｅ　Ｐｏｒｔｌｅｔｓ　Ｓｐｅｃｉｉｆｃａｔｉｏｎ　ｖ１．ｏ［ｓ］．Ｏｒ－　ｇａｎｉｚａｔｉｏｎ　ｆｏｒ　ｔｈｅ　Ａｄｖａｎｃｅｍｅｎｔ　ｏｆ　Ｓｔｒｕｃｔｕｒｅｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｔａｎｄａｒｄｓ，２ＯＯ３．　［４］ＪＳＲ２６８　Ｐｏｒｔｌｅｔ　Ｓｐｅｃｉｆｉｃａｔｉｏｎ２．０［Ｓ］．Ｊａｖａ　Ｃｏｍｍｕｎｉｔｙ　Ｐｒｏｃｅｓｓ，２００８．　［５］ＷＳＲＰ　ｖ２．０　Ｗｅｂ　Ｓｅｒｖｉｃｅｓ　ｆｏｒ　Ｒｅｍｏｔｅ　Ｐｏｒｔｌｅｔｓ　Ｓｐｅｃｉｉｆｃａｔｉｏｎ　ｖ２．０［ｓ］．　Ｏｒｇａｎｉｚａｔｉｏｎ　ｆｏｒ　ｔｈｅ　Ａｄｖａｎｃｅｍｅｎｔ　ｏｆ　Ｓｔｕｒｃｔｕｒｅｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｔａｎｄａｒｄｓ，　２ｏ０８．　［６］Ｐａｕｌ　Ｃ，Ｆｅｌｉｘ　Ｂ，Ｌｅｎ　Ｂ．Ｄｏｃｕｍｅｎｔｉｎｇ　Ｓｏｆｔｗａｒｅ　Ａｒｃｈｉｔｅｃｔｕｒｅｓ：Ｖｉｅｗｓ　ａｎｄ　Ｂｅｙｏｎｄ［Ｍ］．Ｂｏｓｔｏｎ：Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ，２００２．　［７］Ｒａｄｅｓｔｏｃｋ　Ｍ，Ｅｉｓｅｎｂａｃｈ　Ｓ．Ｃｏｍｐｏｎｅｎｔ　Ｃｏｏｒｄｉｎａｔｉｏｎ　ｉｎ　Ｍｉｄｄｌｅｗａｒｅ　ｓｙｓｔｅｒｎｓ　［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ　Ｈａｆｆｏｒｍｓ　ｎａｄ　Ｏｐｅｎ　Ｄｉｓｔｉｒｂｕｔｅｄ　Ｐｒｏｃｅｓｓｉｎｇ（Ｍｉｄｄｌｅｗａｒｅ＇９８）．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，１９９８．　［８］Ｇｒｅｇｏｒ　Ｈ，Ｂｏｂｂｙ　Ｗ．Ｅｎｔｅｒｐｒｉｓｅ　Ｉｎｔｅｇｒａｔｉｏｎ　Ｐａｔｔｅｒｎｓ：Ｄｅｓｉｇｎｉｎｇ，Ｂｕｉｌｄ—　ｉｎｇ，ａｎｄ　Ｄｅｐｌｏｙｉｎｇ　Ｍｅｓｓａｇｉｎｇ［Ｍ］．Ｂｏｓｔｏｎ：Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ，２００３．　［９］Ｍａｍｍａ　Ｅ，Ｈｅｌｍ　Ｒ，Ｊｏｈｎｓｏｎ　Ｒ，ｅｔ　ａ１．Ｄｅｓｉｇｎ　Ｐａｔｔｅｒｎｓ：Ｅｌｅｍｅｎｔｓ　ｏｆ　Ｒｅ—　ｕｓａｂｌｅ　Ｏｂｊｅｃｔ—Ｏｒｉｅｎｔｅｄ　ｓｏｆｔｗ＆ｒｅ［Ｍ］．Ｂｏｓｔｏｎ：Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ，１９９４．　［１０］中科院软件所．网驰平台门户中间件（ＯｎｃｅＰｏｒｔ１ａ）［ＥＢ／ＯＬ］．　２００７．ｈｔｔｐ：／／ｗｗｗ．ｏｎｃｅ．ｏｒｇ．ｃｎ．