一种用于存储与查询半结构化数据的新方法

第３２卷　第１９期　Ｉ１ｏ１．３２　・计算机工程　２００６年１Ｏ月　Ｏｃｔｏｂｅｒ　２００６　№１９　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　软件技术与数据库・　一文章编号：１００　一４２８（２００６）ｌ　＿＿０ｏ９１—＿ｏ３　文献标识码；Ａ　中圈分类号：ＴＰ３１１　种用于存储与查询半结构化数据的新方法　叶飞跃，蒙德龙，员红娟　（上海大学计算机工程与科学学院，上海２０００７２）　摘要：由于半结构化数据缺乏模式信息，因而半结构化数据的存储与查询将是一个十分重要且具有挑战性的研究课题。利用关系数据库　存储半结构化数据可以重用数据库的查询优化器和事务处理机制，能够保证半结构化数据的一致性和完整性。该文提出一种实现半结构化　数据存储与查询的新方法，该方法使用关系数据库系统来实现半结构化数据的存储与查询。给出了把基于半结构化数据的查询重写为基于　关系的查询的算法，同时介绍一个可视化查询程序。　关健词：半结构化数据；查询重写；ＯＥＭ　Ｎｅｗ　Ａｐｐｒｏａｃｈ　ｆｏｒ　Ｓｔｏｒｉｎｇ　ａｎｄ　Ｑｕｅｒｙｉｎｇ　Ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　Ｄａｔａ　ＹＥ　Ｆｅｉｙｕｅ，ＭＥＮＧ　Ｄｅｌｏｎｇ，ＹＵＡＮ　Ｈｏｎｇｊｏａｎ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｓｃｉｅｎｃｅ，Ｓｈａｎｇｈａｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０００７２１　［Ａｂｓｔｒａｃｔ］Ｓｔｏｒｉｎｇ　ａｎｄ　ｑｕｅｒｙｉｎｇ　ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ　ｗｉｌｌ　ｂｅ　ａ　ｖｅｒｙ　ｉｍｐｏｒｔａｎｔ　ａｎｄ　ｃｈａｌｌｅｎｇｉｎｇ　ｒｅｓｅａｒｃｈ　ｂｅｃａｕｓｅ　ｉｔ　ｌａｃｋｓ　ｓｃｈｅｍａ　ｉｎｆｏｒｍａｔｉｏｎ．Ｕｓｉｎｇ　ＲＤＢＭＳ　ｔｏ　ｓｔｏｒｅ　ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ　ｃａｎ　ｒｅｕｓｅ　ｄａｔａｂａｓｅ’Ｓ　ｑｕｅｒｙ　ｏｐｔｉｍｉｚｅｒ　ａｎｄ　ｔｒａｎｓａｃｔｉｏｎ　ｍａｎａｇｅｒ，ｗｈｉｃｈ　ｃａｎ　ｅｎｓｕｒｅ　ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ’Ｓ　ｃｏｎｓｉｓｔｅｎｃｙ　ａｎｄ　ｉｎｔｅｇｒａｌｉｔｙ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｎｅｗ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｓｔｏｒｉｎｇ　ａｎｄ　ｑｕｅｒｙｉｎｇ　ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ．Ａｎ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｇｉｖｅｎ　ｔｏ　ｒｅｗｒｉｔｅ　ｆｒｏｍ　ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ—ｂａｓｅｄ　ｑｕｅｒｙ　ｔｏ　ｒｅｌａｔｉｏｎ—ｂａｓｅｄ　ｏｎｅ．ａｎｄ　ａ　ｖｉｓｕａｌ　ｑｕｅｒｙ　ｐｒｏｇｒａｍ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ．　［Ｋｅｙ　ｗａｒｄｓ］Ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　ｄａｔａ；Ｑｕｅｒｙ　ｒｅｗｒｉｔｉｎｇ；ＯＥＭ　半结构化数据是指那些结构隐含或无规则、不严谨的自　我描述型数据…。这样的数据介于严格结构化数据（如关系数　据库和对象数据库中的数据）和完全无结构的数据（如声音、　图像文件）之间　。半结构化数据的来源主要是：互联网和数　据集成。传统的数据存储、处理、查询技术不能直接应用于　这种数据类型，本文提出了一种基于关系的半结构　化数据的存储方法，并在此基础上给出了一种半结　构化数据的查询语言，且给出了把这种查询语言重　写为ＳＱＬ语句的算法。为了克服直接输入半结构化　数据查询语句容易出错的缺点，我们还编写了一个　可视化查询程序，用于半结构化数据的可视化查询。　半结构化数据的模式描述方法很多，有基于图　的描述形式和基于逻辑的描述形式　】。在这里采用　的是比较有代表性的基于图的ＯＥＭ（Ｏｂｊｅｃｔ　Ｅｘｃｈａｎｇｅ　Ｍｏｄｅ１）模型。　及算法。ＯＥＭ模型可以用一个带根有向图Ｇ（ｒ，Ｖ，Ｅ）来表示，　其中ｒ表示根结点；Ｖ表示对象集；Ｅ是有向边的集合，边　上的标签表示对象之间的关系，记作＜Ｏｉ，ｌａｂｅｌ，Ｏｊ＞，如＜ｌ，Ｐｌａ　ｙｅｒ，１　４＞，＜０，Ｃｌｕｂ，２０＞等。若图Ｇ中存在＜０　ｌ，ｌ　Ｉ，Ｏ２＞，＜０２，ｌ２，Ｏ３　＞，…，＜０　，ｌ　，ＯＩ＞，则称ＯＥＭ模型图Ｇ中存在环路。　１基本概念　１．１ＯＥＭ模型　ＯＥＭ是斯坦福大学（Ｓｔａｎｄｆｏｒｄ　ｕｎｉｖｅｒｓｉ【ｙ）Ｐａｐａｋｏ　ｎｓｔａｔｉｎｏｎ等人提出的用来描述半结构化数据的数据　模型　。ＯＥＭ模型的主要特征是自描述性。该模型　由表示对象的结点和带标签（１ａｂｅ１）的有向边构成。每　个ＯＥＭ对象可以用一个４元组来表示：（ｏｌｄ，ｌａｂｅｌ，ｔ　ｙｐｅ，ｖａｌｕｅ）。其中ｏｉｄ是对象标识。ｌａｂｅｌ是对象的标　签描述，表示对象之间的关系。ｔｙｐｅ是对象类型，　对象类型有两类：原子对象和复杂对象。原子对象是不可再　分的基本类型，如ｉｎｔ，ｓｔｒｉｎｇ，ｒｅａｌ等。复杂对象是对象引用　作者筒介：叶飞跃（１９５９一），男，教授，主研方向：数据库；蒙德龙、　员红娟，硕士　图１　ＯＥＭ模星　的集合，每一个对象引用指向另一个对象。不失一般性，借　用文献【４　Ｊ中的ＯＥＭ模型图来举例说明文中用到的相关概念　收稿日期：２００５一ｌ２—２４　Ｅ－ｍａｉｌ：ｍｅｎｇｄｌ２００４＠１６３．ｃｏｒｎ　－９ｌ一　维普资讯 http://www.cqvip.com

１．２标签路径、｜ｌ【据路径和路径实例　标签路径１ｐ是以符号‘．’分隔开的标签序列，记作ｌｐ＝　Ｉ１．１２…ｌｎ，ｎ是１ｐ的长度。如ｌｐｌ＝Ｃｌｕｂ．Ｎａｍｅ．Ｏｆｆｉｃｉａｌ是一　条长度为３的标签路径。　数据路径ｄｐ是以符号‘．’分隔开的对象和标签交替出现　的序列，记作ｄｐ＝Ｏｏ．Ｉｌ＿Ｏｌ＿１２…Ｉｎ，Ｏ　，ｎ是ｄｐ的长度。　例如：ｄｐｌ＝０．Ｃｌｕｂ．１．Ｎａｍｅ．２．Ｏｆｆｉｃｉａ１．３。　称数据路径ｄｐ＝Ｏｏ．１１．Ｏ１．Ｉ２…Ｉｎ，Ｏ　为对应于标签路径　ｌｐ＝ｌ１．１２…１　的路径实例。对于同一标签路径可能存在多个路　径实例。图１中有４条数据路径是标签路径ｌｐ２＝Ｃｌｕｂ．Ｐｌａｙｅｒ　．Ｎａｍｅ的路径实例。它们分别是：　ｄｐＩ＝０．Ｃｌｕｂ．１．Ｐｌａｙｅｒ．５．Ｎａｍｅ．６　ｄｐ２＝０．Ｃｌｕｂ．１．Ｐｌａｙｅｒ．１４．Ｎａｍｅ．１５　ｄｐ３＝０．Ｃｌｕｂ．２０．Ｐｌａｙｅｒ．２２．Ｎａｍｅ．２３　ｄｐ４＝０．Ｃｌｕｂ．２４．Ｐｌａｙｅｒ．２８．Ｎａｍｅ．２９　１．３同类对象　所谓同类对象是指那些对应于同一标签路径的所有路径　实例中的最后一个对象。由同类对象组成的集合称为同类对　象集。例如对应于标签路径ｌｐ２的同类对象集是｛６，１５，２３，２９｝。　２半结构化数据的存储　目前提出并实现了半结构化数据的存储技术主要有：文　本文件方式，ＲＤＢ方式及ＯＯＤＢ等方式　ｌ。文本文件存储方　式的缺点是存储难度较大，不利于数据的检索和管理。对于　ＯＯＤＢ方式，如果在事先不知道数据的类型信息时，数据加　载的代价可能是很高的；如果类型发生了变化，将导致代价　极高的模式更新。而半结构化数据的数据类型和模式是不固　定的，它随着数据的更新而发生变化。　利用ＲＤＢＭＳ来存储半结构化数据具有如下的优点：当　前的关系数据库技术已十分成熟，商用的关系数据库都具有　高性能的查询引擎、良好的可扩展性、安全性和健壮性。利　用关系数据库存储半结构化数据可以重用数据库的查询优化　器和事务处理机制，能够保证半结构化数据的一致性和完整　性。但是，由于数据模型上的差异，因此利用关系数据库来　存储半结构化数据也给数据库技术带来了许多新的挑战。　半结构化数据模型本质上是基于带根有向图　ｌ，用关系　表来存储半结构化数据必须保证不破坏或丢失原来数据的结　构信息和数据信息，因此，除了存储对象值之外，还要存储　对象之间的关系。本文提出一种基于边的半结构化数据存储　方法，使用３个关系表存储半结构化数据，半结构化数据的　结构信息蕴涵在关系表中。表结构及其意义表示如下（下划线　表示主键）：　ｒｏｏｔ（ｒＯＩＤ，ｃｈＯＩ—Ｄ　ｌａｂｅ１）。这个表存储ＯＥＭ的根结点ＩＤ、　根结点的子结点ＩＤ以及根对象名。　ｅｄｇｅｓ（ｐＯＩＤ，ｃｈＯＩＤ，ｌａｂｅｌ，ｌｆａｇ）。这个表存储ＯＥＭ中的边，　ｌｆａｇ字段用于表示ｃｈＯＩＤ的对象类型，如果是原子对象则用　ｌｅａｆ表示，否则用ｒｅｆ表示。　ｖａｌｕｅｓ（Ｑ　，ｔｙｐｅ，Ｖａｌ—ｉｎｔ，Ｖａｌ—ｓｔｒｉｎｇ，Ｖａｌ—ｆｌｏａｔ…．）。这个表　存储原子对象的类型和对象值。　图１所示的半结构化数据用关系数据库存储表示，如表　１～表３所示。　表１　ｒｏｏｔ表　ｒＯＩＤ　ｃｈ０ＩＤ　ｌａｂｅ　Ｊ　０　ｌ　ｐｒｅｍｉｅｒｓｈｉｐ　０　２０　ｐｒｅｍｉｅｒｓｈｉｐ　０　２４　ｐｒｅｍｉｅｒｓｈｉｐ　表２　ｅｄｇｅｓ表　ｐＯ１Ｄ　ｃｈ０ｌＤ　ｌａｂｅｌ　ｌｆａｇ　０　１　Ｃｌｕｂ　ｒｅｆ　０　２０　Ｃｌｕｂ　ｒｅｆ　表３　ｖａｌｕｅｓ表　０ＩＤ　ｔｙｐｅ　Ｖａｌｉｎｔ　Ｖａｌｓｔｒｉｎｇ　Ｖａｌ　ｆｌｏａｔ　３　Ｓｔｒｌｎｇ　Ｍａｎｃｈｅｘｔｅｒ　Ｕｎｉｔｅｄ　４　ｓｔｒｌｎｇ　Ｒｅｄ　Ｄｅｖｉｌｓ　这种存储方法只用３个关系表就把基于图结构的半结构　化数据信息和结构信息全部存储下来，对于半结构化数据的　标签路径、数据路径都蕴涵在关系表中，对半结构化数据的　查询就可以转化为对关系表的查询。　３查询　半结构化数据的特点是数据的结构不规则或不完整，其　模型都基于带根有向图，因此，半结构化数据的查询过程本　质上可以看作是从根结点开始对图的搜索过程　ｌ。由于我们　采用的是基于关系的存储方式，因此对图的搜索过程要转化　为对关系表的查询过程，转化过程由后面的查询重写来实现。　３．１查询语言　在用于异构数据源集成的丛模型（ＰＭ）系统中，使用的查　询语言可以看作是Ｌｏｒｅｌ的一个子集，查询类似于ＳＱＬ语句　的结构，即　ＳＥＬＥＣＴ　ｓｅｌｅｃｔ，ｌｉｓｔ　ＦＲ０Ｍ　ｆｒｏｍ，ｌｉｓｔ　ＷＨＥＲＥ　ｃｏｎｄｉｔｉｏｎ　例如，考虑查找运动员“Ｒｏｂｂｉｃ　Ｆｏｗｌｅｒ”的国籍的查询，　查询可以表示如下：　Ｑ　１：ＳＥＬＥＣＴ　ｘ．ｎａｔｉｏｎａｌｉｔｙ　ＦＲＯＭ　ｐｒｅｍｉｅｒｓｈｉｐ．ｃｌｕｂ．ｐｌａｙｅｒ　ｘ　ＷＨＥＲＥ　ｘ．ｎａｍｅ＝“Ｒｏｂｂｉｃ　Ｆｏｗｌｅｒ”　上面的查询语句不能直接用于ＲＤＢＭＳ，必须把它改写　为ＲＤＢＭＳ能够识别的ＳＱＬ语句。　３．２查询重写　查询重写就是要把基于路径的半结构化数据查询改写为　基于关系表的ＳＱＬ查询。结合前面介绍的半结构化数据的存　储方法，提出使用ＩＮ子句的查询重写方法，其基本思想是利　用ＩＮ子句对标签路径的同类对象集进行集合查找和集合交　操作。算法由下面３部分组成：（１）查询得到满足Ｑ１中ｆｒｏｍ　子句的同类对象集；（２）在满足第１步的同类对象集中查询满　足ｗｈｅｒｅ子句的对象集；（３）在满足第２步的对象集中查询满　足整个查询的结果集。算法如下：　输入：半结构化数据查询语句Ｑ　输出：基于关系的ＳＱＬ查询语句　Ｓ１＝“ｓｅｌｅｃｔ　ＤＩＳＴＩＮＣＴ　ｒＯ１Ｄ　ｆｒｏｍ　Ｒｏｏｔ’’：　ｌｐ＝ｇｅｔＦｒｏｍＬｐ（Ｑ）；／／取ｆｒｏｍ子句中的标签路径　ｆｏｒ　ｌａｂｅｌ∈ｌｐ　Ｓ　ｌ＝“ｓｅｌｅｃｔ　ｃｈＯ１Ｄ　ｆｒｏｍ　ｅｄｇｅｓ　ｗｈｅｒｅ　ｐＯ１Ｄ　１Ｎ　ｒ．．　＋ｓ　１＋“）ＡＮＤ（１ａｂｅｌ＝”＋ｌａｂｅｌ＋“）”：　ｒｐ＝ｇｅｔＷｈｅｒｅＬｐ（Ｑ）；／／取ｗｈｅｒｅ子句中的标签路径　ｓ２＝“ｓｅｌｅｃｔ　ＯｌＤ　ｆｒｏｍ　ｖａｌｕｅｓ　ｗｈｅｒｅ　ｖａｌｓｔｒｉｎｇ”＋ｗｈｅｒｅＣｏｎｄｉｔｉｏｎ；　ｏｆｒｌａｂｅｌ∈ｒｐ　ｓ２＝“ｓｅｌｅｃｔ　ｐＯ１Ｄ　ｆｒｏｍ　ｅｄｇｅｓ　ｗｈｅｒｅ　ｃｈＯ１Ｄ　１Ｎ　Ｃ＋ｓ２＋“）”　＋“ＡＮＤ（１ａｂｅｌ＝”＋ｌａｂｅｌ＋“）”：　ｓ３＝“ｓｅｌｅｃｔ　ＤＩＳＴＩＮＣＴ　ｐＯ１Ｄ　ｆｒｏｍ　ｅｄｇｅｓ　ｗｈｅｒｅ　ｐＯ１Ｄ　１Ｎ（．．　＋ｓ１＋¨）ＡＮＤ　ｐＯ１Ｄ　１Ｎ　Ｃ＋ｓ２＋¨）”；／／查询交集　ｒｐ：ｇｅｔｓｅｌｅｃｔＬｐ（Ｑ）；／／取ｓｅｌｅｃｔ子句中的标签路径　维普资讯 http://www.cqvip.com

ｓ４＝“ｓｅｌｅｃｔ　ｐＯＩＤ　ｆｒｏｍ　ｅｄｇｅｓ　ｗｈｅｒｅ　ｐＯＩＤ　ＩＮ　Ｃ＋ｓ３＋“ｒ：　ｆｏｒｌａｂｅｌ∈ｒｐ　ｓ４＝“ｓｅｌｅｃｔ　ｃｈＯＩＤ　ｆｒｏｍ　ｅｄｇｅｓ　ｗｈｅｒｅ　ｐＯＩＤ　ＩＮ　ｒ’　＋ｓ４＋“）ＡＮＤ（１ａｂｅｌ＝”＋ｌａｂｅｌ＋“）”：　ｓｑｌ＝“ｓｅｌｅｃｔ　Ｖａｌ—ｓｔｒｉｎｇ　ｆｒｏｍ　ｖａｌｕｅｓ　ｗｈｅｒｅ　ＯＩＤ　ＩＮ”＋ｓ４：　／／在对象值表上查询　ｒｅｔｕｒｎ　ｓｑｌ　例：上面的Ｑ１查询使用重写算法改写后，得到如下所　示的ＳＱＬ查询，其中左边一列是语句行号，右边的语句是改　写后得到的基于关系的ＳＱＬ查询。　１　ｓｅｌｅｃｔ　Ｖａｌ　ｓｔｒｉｎｇ　ｆｒｏｍ　ｖａｌｕｅｓ　２　ｗｈｅｒｅＯＩＤＩＮ　３（ｓｅｌｅｃｔ　ｃｈＯＩＤ　ｆｒｏｍ　ｅｄｇｅｓ　４　ｗｈｅｒｅ　ｐＯＩＤＩＮ　５　（＇ｓｅｌｅｃｔ　ＤＩＳＴＩＮＣＴ　ｐＯＩＤ　ｆｒｏｍ　ｅｄｇｅｓ　６　ｗｈｅｒｅ　ｐＯＩＤＩＮ　７（ｓｅｌｅｃｔ　ｃｈＯＩＤ　ｆｒｏｍ　ｅｄｇｅｓ　８　ｗｈｅｒｅ　ｐＯＩＤＩＮ　９（ｓｅｌｅｃｔ　ｃｈＯＩＤ　ｆｒｏｍ　ｅｄｇｅｓ　１０　ｗｈｅｒｅ　ｐＯＩＤＩＮ　１　１（ｓｅｌｅｃｔ　ＤＩＳＴＩＮＣＴ　ｒＯＩＤ　ｆｒｏｍ　ｒｏｏｔ）　１　２　ＡＮＤ　ｆｌａｂｅｌ＝　Ｃｌｕｂ’）　１３　）　１　４　ＡＮＤ（１ａｂｅｌ＝’Ｐｌａｙｅｒ　）　ｌ５　１　１６　ＡＮＤ　ｐＯＩＤＩＮ　１　７（ｓｅｌｅｃｔ　ｐＯＩＤ　ｆｒｏｍ　ｅｄｇｅｓ　ｌ８　ｗｈｅｒｅ　ｃｈＯＩＤ　ＩＮ　１　９　ｆｓｅｌｅｃｔ　ＯＩＤ　ｆｒｏｍ　ｖａｌｕｅｓ　２０　ｗｈｅｒｅ　ｖａｌ—ｓｔｒｉｎｇ＝　Ｒｏｂｂｉｃ　Ｆｏｗｌｅｒ　２１　）　２２　）　２３　）　２４　ＡＮＤ（１ａｂｅｌ＝　Ｎａｔｉｏｎａｌｉｔｙ　）　２５　）　说明：　（１）７～１５行查询得到满足查询Ｏ１中ｆｒｏｍ子句的同类对象集，即　（５，１４，２２，２８｝；　（２）１７－２２行查询得到满足Ｏ１中ｗｈｅｒｅ条件子句ｘ．ｎａｍｅ＝”Ｒｏｂｂｉｃ　Ｐｏｗｌｅｒ”的对象，即（２２｝；　（３）第５行和１６行实现（１）和（２）两步的交集，得到查询Ｏ１中满　足条件的对象集，即（５，ｌ４，２２，２８｝ｎ（２２｝＝（２２｝；　（４）３～２５行查询得到满足第（３）步的ｘ．Ｎａｔｉｏｎａｌｉｔｙ的对象集（１９｝；　（５）最后通过第１、２两行在关系表ｖａｌｕｅｓ中查询得到满足条件　的运动员的国籍”Ｅｎｇｌｉｓｈ”。　３．３可视化查询界面　半结构化数据没有固定的模式，随着数据的变化模式也　会发生变化，这使得书写半结构化数据的查询语句非常不方　便，而且容易出错。为了克服这个缺点，我们编写了一个可　视化查询程序，程序界面见图２。　在可视化查询界面上，左边的面板显示半结构化数据的　模式图，用鼠标点击模式图中的标签名，对应的标签名就会　出现在右边的ｌａｂｅｌ文本框中，然后再点击Ａｄｄ按钮，就可　以把相应的标签添加到对应的查询子句中去。重复以上过程，　直到所需的标签路径和查询条件全部生成为止。最后点击界　面下方的Ｃｒｅａｔｅ按钮，程序就会按要求生成一条完整的查询　语句。如果要执行这个查询，则只要点一下Ｑｕｅｒｙ按钮即可。　可见使用这个可视化查询界面，用户几乎不用输入什么内容，　只要用鼠标在这个界面上点几下就可以生成一条半结构化数　据查询语句，非常方便。　图２可视化查询界面　４性能分析　查询重写过程就是把对路径的搜索改写为对关系表的查　询。查询的路径长度决定重写后ＳＱＬ查询的嵌套层数，路径　越长，重写后得到的查询语句的嵌套层数就越多。在ＤＢＭＳ　中，嵌套查询语句的执行是从最内层ｓｅｌｅｃｔ查询开始的，并　逐层向外执行。查询主要是在表ｅｇｄｅｓ上进行，为简化分析，　假定每一层ｓｅｌｅｃｔ查询的时间开销为ｔ，则嵌套ｍ层的查询　的时间开销为ｍｔ。设有如下查询语句：　ＳＥＬＥＣＴ　ｘ．１ｒｐ　ＦＲＯＭｌｐ　ｘ　ＷＨＥＲＥ　ｘ．ｃｒｐ　令１ｒｐ的路径长度为ｎ１，ｌｐ的路径长度为ｎ２，ｃｒｐ的路　径长度为ｎ３。则重写后的查询语句的ｓｅｌｅｃｔ嵌套层数为　（１＋ｎ２）＋（１＋ｎ３）＋１＋ｎ１－－ｎ１＋ｎ２＋ｎ３＋３　对于上面的查询Ｑ１，ｎ１＝１，ｎ２＝３，ｎ３＝１，重写后的查　询语句的ｓｅｌｅｃｔ嵌套层数等于８，查询开销为８ｔ。可见，查询　的时问开销与查询语句中的ｓｅｌｅｃｔ、ｆｒｏｍ及ｗｈｅｒｅ子句中的　标签路径的长度之和成正比。通过在关系表中建立索引，可　以减少查询中的ｔ值，从而加快查询速度。　５结束语　半结构化数据的存储与查询及相关技术是异构数据源集　成和网络资源共享的一个研究重点。本文提出的半结构化数　据的存储与查询方法已经应用到我们的丛结构模型系统中，　实践证明该方法是可行和有效的。在下一步工作中，我们的　工作重点将是半结构化数据的查询优化。　参考文献　１　Ａｂｉｔｅｂｏｕｌ　Ｓ．Ｑｕｅｒｙｉｎｇ　Ｓｅｍｉ—ｓｔｒｕｃｔｕｒｅｄ　Ｄａｔａ［Ｃ］．Ｐｒｏｃ．ｏｆ　ＩＣＤＴ　Ｄｅｌｐｈｉ　Ｇｒｅｅｃｅ，ｌ　９９７．　２王静，孟小峰．半结构化数据的模式研究综述…　计算机科学．　２００１．２８（２　：６　１０　３　Ｐａｐａｋｏｎｓ【ａｎｎ【ｉｎｏｕ　Ｙ　Ｇａｒｉｃａ　Ｍ　Ｈ，Ｗｉｄｏｍ　Ｊ．Ｏｂｊｅｃｔ　Ｅｘｃｈａｎｇｅ户ｃｒｏｓｓ　Ｈｅｔｅｒｏｇｅｎｅｏｕｓ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｏｕｒｃｅｓ［Ｃ］．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＩＥＥＥ　ＩＣＤＦ．　ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｐｒｅｓｓ．１９９５：２５　ｌ一２６０　４　Ｓｖｅｔｌｏｚａｒ　Ｎ，Ｊｅｆｆｒｅｙ　Ｕ．Ｊａｎｅｔ　ｗ．Ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　Ｏｂｊｅｃｔｓ：Ｃｏｎｃｉｓｅ　ＲｅＤｒｅｓｅｎｔａｔｉｏｎｓ　ｏｆ　Ｓｅｍｉｓｔｕｒｃｔｕｒｅｄ．Ｈｉｅｒａｒｃｈｉｃａｌ　Ｄａｔａ［Ｃ］．Ｐｒｏｃ．ｏｆ　ＩＣＤＥ．１９９７：７９　９０　５聂培尧，李战怀，胡正国　一种基于ＸＭＬ的半结构数据的ＯＲＤＢ　存储方法…．计算机工程与应用，２００３，３９（１４）：１９０—１９３，１９９．　６陈滢，王能斌．半结构化数据查询的处理和优化…．软件学报．　１９９９，１Ｏ（８）：８８３—８９０　９　—