（计算机软件与理论专业论文）半结构化数据查询中路径表达式的快速匹配方案.pdf

半结构化数据查询中路径表达式的快速匹配方案 摘要 摘要 f f 在w e b 迅猛发展和半结构化信息急剧膨胀的今天，数据查询尤其是半结 构化数据查询日益成为信息技术领域一个重要的研究发展方向。半结构化数据查 询在数据库检索、模式匹配和其他涉及大规模结构化信息处理领域，诸如数字图 书馆和因特网搜索引擎等，都有着广泛的应用。半结构化查询中的核心技术之一 是利用路径表达式来表达和检索用户所指定的结构模式扣怔文首先介绍了半结构 化数据的基本概念和相关的存储及查询技术，然后介绍路径表达式计算方法的研 究进展，并提出了一种最新的路径匹配方案利用文档结构的位置信息进行路 径匹配，详述了该方案的具体算法和实现，最后给出在原型系统上的实验结果和 性态分析，同时指出该方案的发展方向以及应用前景。 本文提出的利用文档结构的位置信息进行路径表达式的快速匹配方案( 简称 快速路径匹配方案) ，取得了以下的成果：突破了传统路径查询中的确定模式 限制，为每个满足用户查询要求的结构指定匹配值，并将查询路径确定化，为后 继的各类操作提供了广阔的互动空间：在表达能力与查询效率问作出相应的折 t h 加速最经常使用的操作，基本解决了结构匹配与数值匹配的性能鸿沟；将 结构查询和数值查询分离，利用符号信息描述文档结构并处理相关的查询。 关键字：x m i ，、半结构化数据、路径表达式、半结构化查询 u 7 v 复旦大学硕士学位论文 ! ! ! ! 竺! ! 型! ：! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ：! ! ! 竖! ! ! ! ! ! ! ! ! ! ! ： 竺墨竺二 a b s t r a c t w it ht h er a p i dd e v e l o p m e n to fw e ba n dl a r g ev o l u m es e m i s t r u c t u r ed a t a ， d a t aq u e r y ，e s p e c i a l l ys e m i s t r u c t u r ed a t aq u e r y ，h a sb e e nm o r ea n dm o r e i m p o r t a n tt h e s ed a y s s e m i s t r u c t u r ed a t aq u e r yh a sb e e nu s e dw i d e l y i n t h ef i e l d so fd a t a b a s eq u e r y ，p a t t e r nr e c o g n i t i o na n do t h e rf i e l d st h a t r e l a t et o l a r g ev o l u m es e m i s t r u c t u r ed a t am a n a g e m e n t ，s u c ha sd i g i t a l 1i b r a r ya n di n t e r n e ts e a r c he n g i n e o n eo ft h ek e r n e lt e c h n i q u e si su s i n g p a t ht oe x p r e s sa n dq u e r yu s e rd e f i n e ds t r u c t u r e sa n dd a t a t h i sp a p e r i n t r o d u c e ss o m eb a s i c c o n c e p t s a b o u ts e m i s t r u c t u r ed a t a a n dit s m a n a g e m e n t ：t h e nt a l k sa b o u tr e l a t e dw o r k sa b o u tp a t he v a l u a t i o n a tl a s t ， t h is p a p e rp r e s e n t s an e wf a s tm e t h o df o rp a t hm a t c h i n g ，w h i c hi st h e b o t t l e n e c ko fp a t he v a l u a t i o n b e s i d e st h ea l g o r i t h m ，t h i sp a p e ra l s o g i y e ss o m es y s t e mi m p l e m e n t a t i o nc o n s i d e r a t i o n s a n dd e t a i l e x p e r i m e n t r e s u lt s t h ef a s tp a t hm a t c h i n gm e t h o d ，w h i c hi si n t r o d u c e di nt h isp a p e r ，u s e s s t r u c t u r en o d ep o s i t i o ni n f o r m a t i o nt oj u d g et w on o d e s r e l a t i o na n dt h e n t om a t c ht h eu s e rd e f in e dq u e r yp a t h sw i t hs t f u c t u r e sind a t a b a s e t h e m a in c o n t r i b u t i o n so ft h i s p a p e r a r e ：( 1 ) n o tr e s t r i c t e di nfix c d s e m i s t r u c t u r es c h e m ab u ta u t o m a t i c a l l ym a t c ha l lq u a l i f i e ds t r u c t u r e s int h ed a t a b a s e ( 2 ) e n h a n c et h em o s tu s e do p e r a ti o n sa n dq u e r ye x p r e s sio n s i no r d e rt og a i ns a t i s f y i n gp e r f o r m a n c ec o m p a r e dw i t ho t h e rm e t h o d s ( 3 ) s e p e r a t et h es t r u c t u r e d a t am a t c h i n gp r o c e s sa n d u s es y m b o lt oe n c o d e d o c u m e n t s s t r u c t u r ein f o m a tio n k e y w o r d s ：x m l 、s e m i s t r u c t u r ed a t a 、p a t he x p r e s s i o n 、s e m i s t r u c t u r eq u e r y 复旦大学硕士学位论文 半结掘化数据查询中路径表达式的抉遽匹配方寰第l 贾 第一章引言 1 1 研究背景 w e b 是一种臣大的异构信息资源库。据统计，目前垒球已有4 亿多网页，并 且还以巨大的速度增长着。x m l 是种扩展的文本标记语言，能表达元素、元素 间嵌套和引用等概念。由于x m l 标准的制定以及基于x m l 的网页、网站和应用开 发工具的大鼙涌现，作为种全新通用的数据表示和交换标准，x m l 受到了越来 越广泛的关注，并将逐渐成为w e b 上信息的主要表示和交换工具之一。如何在 w e b 这种异构环境中利用相关技术处理以x m l 文档为代表的海量半结构化数据， 戒了警今各相关领域的研究热点。 髦缝整毽鏊耄霉蕉楚l 垒楚毫弯塑窟：丕窭篓塞迅速变化的数据。由于x m l 文 一 秽一般都遵献某个d t d ，丽d t d 对于其体的x m l 文档却不是必须的，因此越来越 多的入将x m l 视为一种鬓要的半结构化建模语言，并将大量的半结构亿数据的研 究残采巍灞予x m l 领域 i ，2 。本文的研究主要两向x m l 文档，相关的研究成采 溺祥可醣方篌地液焉于半结构纯数据。 涟着w e b 土戳掰l 为代表的半结构纯数据的遂速增长和用户对异稽数据避行 统一访闰要求的蠢益离涨，数据综合系统 3 ，4 ，5 ，6 ，7 ，8 的辑究程渐广泛和 深入。这样戆系统能为焉户爨 共访溺备季孛异橡数据滚的统一途径，两不强知道冀 确切斡模式。 尽管嚣熬成熬的褒用鼹终援索弓| 擎，诸如g o o g l ej 手鞋l y c o s 等，能撬供簦予 关键字憝全文查询，但却基本上怨略了文档内部豹逻辑结梅。匿此，在传统的全 文检索基础上，加入对结构僚息的查询处理，垮会极大遗丰富和扩展搜索引攀静 检索能力和应用领域，w 3 q s 系统 1 9 】馒 乍出了这样款尝试秘努力。 出上可知，无论从何葶孛应用角度惩砉，迫切篱要秘能处理w e b 上大量半结 构化数据的方案。显然结构傣息的有效存贮靼查询是其中的核心问题，穗查询又 是所有工作的出发点靼归宿。查询效率、痊询语轰的表达能力和空间占用将是评 价查询方案优劣的重要标准。因此，本文提出的利用文档结构的位置信息进行路 径表达式的快速旺配方案，就综合性能而言，具有相当的优势和先j 性。 1 2 全文结构 论文正文共6 章，第l 章是引言，第6 章是小结。主要研究内容从第2 章到 第5 章。 第2 章介绍栩关的基本概念，如率结构化数据、半绪构化查询和路径表达式 等，并介绍了路径表达式计算的研究进戚以及所面临的机遇和挑战。 美旦大学硬士学位论文 半结构化数据查询中路径表达式的快速匹配方案 第2 页 第3 章具体介绍本文提出的快速路径匹配方案，并指出其应用价值和理论意 义。 第4 章具体讲述快速路径匹配方案的实现技术，包括相关重要算法的实现考 虑和对分布式架构的一些设想。 第5 章给出基于原型系统的实验结果及相关的性态分析。 复旦大学磺士学位论文 半结构化数据查询中路径表达式的快速匹配方案 第3 页 第二章综述 2 1 重要的半结构化数据一x i 】l 扩展的标记语言( x m l ) 是一种迅速崛起的数据交换规范，与h t m l 一样，也 是s g m l 的一个子集。但和h t m l 标记主要用来描述数据的显示格式不同，x m l 标 记是用来描述数据本身，也就是说，x m l 文档是自描述的。这就允许不同的应用 程序以自己的方式来解释甚至筛选相关数据。 近来，关于x m l 的研究在w e b 应用与电子商务潮流的带动下，吸引了各界人 士的广泛关注，人们普遍将其视为一种通用的可查询的数据格式。几乎所有的数 据管理系统都加入了对x m l 数据的支持：能导出、导入及浏览相关的x m l 数据； x m l 数据的查询与综合也正处于研究的热潮中。x m l 文档存贮器如o b j e c t d e s i g n se x c e l o n 9 和s o f t w a r e a g st a m i n o 1 0 已经问世，而x m l 数据的发布 功能也已经加入o r a c l e ，i b m 和m i c r o s o f t 最新版本的d b m s 中。 随着x m l 标准的发展与相关应用与研究的深入，它的作用已经超越了原有的 作为保留语义信息的半结构化文档标准的功能，成为一种异构数据平台间的通用 数据交换规范。各种异构数据源可以通过x m l 来发布自己的数据，而其它系统则 可以直接导入或查询这些异构数据。 简单的说，x m l 文档是一种层次化的结构描述，从根结点开始，包含了一系 列的嵌套元素，每个元素都可以拥有自己的属性( 值) 、数据与予元素。具体的 x m l 信息可以参考 1 2 ，1 3 。 文档类型描述( d t d ) 1 4 描述了相关x m l 文档所遵循的结构信息，它的作 用类似于x m l 文档的模式。d t d 通过给出元素的名称、属性和相互包含关系来具 体定义x m l 文档的结构。同时，元素构造允许复杂的正则操作如“+ ”、“十”、“? ” 和“i ”。所有的元素数据一般都被视为字符串类型，除非指定为a n y 类型( 表示 任意合法的x m i 。片断) ，而i d 类型是一种特殊的类型，要求在相关的x m l 文档中 保证其唯一出现。 t h es e l f is ig e n e ! e l e 咂mb o o k ( b o o k t i t le a u t h o 件) ) f i r s t n a m e ) r i c h a r d ( ! e l e 姬n t 1 a m e ( f i r s t n a m e 7 1 a s t l a 日m e ) ( a d d r e s s ( ! e l e 娅mf i r s t n a l r * ( # p c d a t a ) t i m b u k t u ( c i t y ( z id 9 9 9 9 9 x m l - o l 查询 图2 3 ) m - 0 l 查询及其对应的l o r e l 查询 如上图所示，对于图2 1 中右图描述的d t d ，两种不同的查询语言都能查询 书名为“t h es e l f i s hg e n e ”的作者的姓是什么。显然，图2 1 中左图满足查询 要求，因此返回的结果中必然有“d a w k i n s ”。 2 3 半结构数据处理应用领域 2 3 1 数据发布与信息交换 x m l 作为统一的数据交换标准，已经得到广泛地应用。但如今多数数据却并 不符合x m l 标准，因此有必要建立一种与x m l 数据相互转换的映射机制，将x m l 作为一种视图映射的定义语言。 由于x m l 主要用于w e b 与商业应用领域，而绝大多数的商业应用数据却是存 贮于关系数据库中，因此x m l 与关系数据库的映射机制就尤为重要 4 4 。此种映 射机制的研究却相当有挑战性：首先，x m l 数据本质上是层次和嵌套的，而关系 模型却是平坦和规范化的( 3 n f ) ：其次，对应于x m l 的查询，相关的底层关系数 据库可能需要经历多次的嵌套查询、索引联接和结果合并，甚至可能通过不同的 数据库进行数据综合与和查询调度。 2 3 2 网络搜索引擎 目前越来越流行的观点是将w e b 看成一个巨大的x m l 文件库，因此就需要 种能支持在w e b 范围内查询相关x m l 数据的工具。目前的搜索引擎只提供基于关 键字的文本查询方式，而对x m l 数据而言极为重要的结构信息，却被无情地忽略， 这就对传统的搜索方式提出了新的要求。 和目前流行的局限于指定具体模式( d t d ) 的x m l 查询不同，基于w e b 范围 的x m l 查询提出了新的要求与内容，它要求系统做到： 能处理海量数据而性能影响甚微 在各个不同数据源问做自动的模式综合与匹配查询 当要求分配到不同的数据源计算时，尽量减少传输与通讯的代价。 基于w e b 的x m l 搜索引擎一般具有两种工作模式 3 5 。一种是松耦合地与各 查询处理系统连接，该引擎将用户请求解析后路由到具体的查询处理系统，结果 复童大学硕士学位论文 半结构化数据查询中路径表达式的快速匹配方案 第7 页 经过综合后返回给最终用户。在此类系统中，需要中间件位于搜索引擎与各查询 系统间处理相关的控制、加锁和恢复工作；另一种工作模式是利用数据库作为索 引缓冲空间并且独立处理相关的用户查询。2 0 多年的关系数据库技术对于查询 优化与执行、可扩展性和并发控制能力使此方案看上去具有极大的优势，但是时 间和空间消耗过大却是其最大的缺点。 目前直接对应于以上两种类型的基于w e b 的x m l 数据查询系统主要有 n i a g a r ai n t e r n e tq u e r ys y s t e m 3 2 与x y l e m e 3 3 。n i a g a r a 允许用户在网上 用传统的路径表达式查找满足相关条件的所有x m l 文档。和n i a g a r a 这种利用松 耦合技术实现的搜索引擎系统不同，x y l e m e 的方案是为网络上的x m l 文档建立 索引和缓冲，统一处理查询和相关维护。 2 3 3 数据综合 企业对异构数据源统一访问能力的日益关注和网络半结构化数据的迅速增 加使数据综合成为研究的热点之一。数据综合系统简而言之就是提供多个( 异构) 数据源的统一访问模式。利用异构数据源间数据交换的x m l 规范，数据综合的任 务重点研究将多个相关的d t d 结构综合匹配，从而为用户提供一个统一的访问界 面 3 5 。 2 4 路径表达式计算 目前涌现出不少针对x m l 之类的半结构化数据的查询语言，其共同特征是路 径表达式。它们所定义的路径表达式能够让用户指定相关结构中符合一定条件的 任意路径，这也是其与关系数据库查询系统的一个重要差异。 2 4 1 路径表达式及其计算 路径表达式是由结点与结点间的关系约束依次间隔构成的有限长度的列表。 表达式的表达能力是衡量和划分表达式的重要指标。对表达式表达能力的鉴定司+ 以从以下若干方面进行。 ( 1 ) 结点名： 结点名是否是由确定的字符组成：是否允许通配符“”与“一”匹配0 个至多个或任意单个字符；是否允许用户使用正则操作“+ ”、“$ ”、“? ”和 “i ”来表达更为复杂的概念。 ( 2 ) 结点构造： 结点是否允许嵌套递归，即允许结点由其它的一条子路径或结点构造组 成；结点是否允许正则操作；结点是否允许为其附加相应的谓词约束。 复旦大学硕士学位论文 半结构化数据查询中路径表达式的快速匹配方案 第8 页 ( 3 ) 结点间的关系约束： 结点间的关系约束是固定的直接连接，还是允许用户指定其在数据中的具 体表现形式，如后继和祖先关系、同祖先的兄辈关系等等。 根据各项指标的符合程度，我们可将路径表达式按表达能力由强至弱划分为 以下四类： 复杂路径表达式：允许所有的正则操作和通配符，结点允许嵌套，谓词 可以附加于结点； 正则路径表达式：允许所有正则操作和通配符，结点允许嵌套，谓词不 可以附加于结点： 普通路径表达式：结点可以含有正则操作，但结点名只允许含有通配符， 不允许结点嵌套与谓词约束： 简单路径表达式：无正则操作，无通配符，无谓词约束与结点嵌套。 随着表达能力由强到弱的排列次序，计算复杂度也由强到弱排列。 2 1 指出 计算路径表达式基本上有三种模式，一种是结构顶端开始，一一展开匹配，这称 为自顶向下计算方案。另一种是从用户指定的条件开始，一步步向结构顶端逆向 联接查找，这就是自底向上计算。介于两者之间，同时执行到某一中间层次再将 结果联接合并的称为混合计算方案。即便如此，验证一条简单的路径是否满足正 则路径表达式现证明是n p 完全的 3 6 ，因此需要更好的计算方法和相关辅助索 1 技术。 2 4 2 研究进展 对于表达式计算的研究，主要着重点在于计算效率的提高，目前，许多学者 在此方面做了大量的研究并取得了显著的成果。 针对表达式的优化基本上可以分为两大类 3 7 ，一种是基于语义的查询优 化，另一种是基于执行代价的查询优化。在语义优化方面， 3 6 研究了利用约束 信息对正则路径表达式进行优化。而谓词消除和联接选择主要是基于代价的查询 优化的考虑范围。 4 0 研究了用于估计查询代价和路径联接次序的统计模型及相 关算法。 至于利用索引技术加快数据的查询，自然是研究的重要方向之一。 4 1 ，4 2 ， 3 5 研究了将结构信息转换成相关的符号信息，利用后者的比较和查询优势执行 相关结构查询。 3 4 采用边表的方法加速路径的查找；为了节约空间， 4 0 研究 了利用统计信息压缩结构树与相关的边表。 4 2 将索引信息通过b 树形式存放， 将用户完整的查询路径表达式作为输入，一次查询得解； 4 1 则是将查询路径表 达式分段计算后按不同的结点间关系约束依次联接。 复里大学硕士学位论文 半结构化数据查询中路径表达式的快速匹配方案第9 页 由于x m l 数据目前大多存放于r d b m s ，并提供了至关系数据库的相应视图映 射，因此 1 l ，4 3 ，4 4 ，4 5 主要研究了将相关的x m l 查询通过视图映射转换成一 组有效的s q l 执行语句，最后依赖关系数据库选择具体的优化方案执行。 最后， 3 8 提出扩展的路径表达式模型，试图支持更为复杂的计算语义与查 询语句间的相互构造。而 3 9 则利用模式识别中的树匹配概念，试图将半结构化 的查询结构通过模式匹配，一次计算得出结果。 2 4 3 评价标准 对于表达式计算的评价，可以从以下若干方面进行比较 数据模型：被查询的半结构化数据符合图模型还是树模型。用于查询的 表达式是线形表达式还是半结构化查询树； 表达能力：主要是指查询表达式的表达能力如何( 见上节介绍) ； 处理效率：主要是指执行用户查询的平均耗时与首次响应时间是多少； 空间代价：主要是指如果使用索引结构，索引空间与存贮数据之间的比 例是多少。 可以看出上述的四条标准是相互矛盾的，研究设计者的任务在于从中找出一 种适合具体应用需求、综合性能较好的设计方案。 2 4 4 机遇与挑战 e 如前面章节所述，x m l 处理技术在数据综合、数据交换与发前i ，尤其是网 络数据结构化查询方面，有着远大的应用前景。但由于目前的路径表达式定义与 计算的若干不足，使相关应用的推广受到了一定程度的阻碍。 首先，查询的效率不理想。即使利用了索引信息处理相关的优化查询，子查 询结果的联接及其联接次序仍然依赖相关的统计信息。但在缺乏固定模式的前提 下，保留和维护全部路径的查询统计信息变得相当困难与复杂。再者，当查询复 杂度增加后，x m l 到s q l 的查询映射会形成大量的嵌套s q l 查询语句，从而导致 关系数据库自身优化框架的失效。 其次，路径表达式过于复杂。比如，结点构造允许嵌套、结点名与结点构造 允许正则表达式，实际上大多用户无法掌握此类复杂的语法，他们的查询需求其 实很简单。但正是那些并不常用的复杂操作，徒增了系统的复杂性，降低了执行 的有效性与处理性能，而这才是用户最关心的问题。 最后，路径表达式过于确定化，严重依赖于用户对目标d t d 的准确掌握，而 这在多数情况下并不现实，因为他们只清楚自己所需数据的内容和大致符合的关 系( 结构) 。 复旦大学磺士学位论文 半结构化数据查询中路径表达式的快速匹配方案 第l o 页 因此，本文认为首先是减少并不常用的路径表达式的操作，通过部分降低路 径表达式的表达能力来换取性能的大幅改善( 即加速最常用的操作) ；其次是减 少查询对用户明确掌握相关结构模式和正则表达式的依赖，允许更为宽松的结点 间关系和更为柔性的表达式操作。 正是基于以上理由，本文提出了利用文档结构的位置信息进行路径表达式的 快速匹配( 简称快速路径匹配方案或快速匹配方案) ，并实现了相关的原型系统。 下面三章分别介绍快速匹配方案的算法，实现及实验结果。 复旦大学硕士学位论文 半结构化数据查询中路径表达式的快速匹配方案 第1 1 页 第三章路径表达式的快速匹配 3 1 问题提出和解决思路 3 1 1 问题提出和解决思路 近来对路径表达式计算的研究方兴未艾，已有多种计算方案，总的来说可分 为以下三种类型：自顶向下计算、自底向上计算与混合计算。自顶向下计算是先 确定结构，再验证其子结点包含的值是否满足用户要求。当用户指定的叶结点数 据比较稀疏时，上述方案的有效性便产生了问题。自底向上计算是先选择包含用 户指定数据的叶结点，再验证其结构是否为用户所需，当叶结点数据相对密集时， 上述方法也不适用。混合计算是综合上述两种方法的优势，同时将自底向上与自 顶向下计算到某层次，然后利用联接操作，获得相应的结果。 同时，随着w e b 上x m l 数据的日益膨胀，用户迫切需要一种统一的结构化查 询界面，而且不必指定相关的x m l 数据所遵循的d t d 。因此就有必要先将用户的 查询请求与数据库中登记的结构信息进行匹配，再执行具体的数值查询操作。 无论何种应用，路径表达式匹配将是重要的核心技术之一。因为对于数值的 存贮与查询经过2 0 多年的研究，关系数据库辅以全文索引技术的方案已为大家 所认可，但对于结构的访问与匹配，却仍具有极大的研究价值。 尽管如今已有多种关于路径表达式计算与匹配的研究结果，但仍有各自的不 足： 用户需要指定相关x m l 文档所遵从的d t d ： 要求用户对其查询结构非常清楚与了解，能写出明确的j 下则路径表达式； 将结构索引与数值索引混合在一起，系统的扩展性不佳； 结构查询与数值查询的效率严重失配，无法充分利用混合查询的优势； 路径表达式过于复杂，用户无法确切掌握，引入太多并不常 j 的正则计 算与嵌套语义，尽管提高了表达能力，但严重影响了计算的性能。 由上述分析，本文提出了路径表达式的快速匹配方案，并取得了以下研究成 果： 突破了传统路径查询中的确定模式限制，为每个满足用户查询要求的结 构指定匹配值，并将查询路径确定化； 在表达能力与查询效率间作出相应的折中，加速最经常使用的操作，基 本解决了结构匹配与数值匹配的性能鸿沟： 将结构查询和数值查询分离，利用符号信息描述文档结构并处理相关的 查询。 复且大学硕士学位论文 半结构化数据查询中路径表达式的快速匹配方案第1 2 页 3 1 2 理论意义和实践价值 ( 1 ) 多模式动态支持 解决了以往查询中过多依赖模式信息的不足，采用匹配技术动态地在所 有相关结构中执行查找，使用户不必提供相关x m l 文件所遵从的d t d 结构便 可执行相关查询。对w e b 这样的异构数据环境，尤其有价值。 ( 2 ) 表达能力与性能的折中 目前一般有两种关于结构信息的存贮管理方式，一种是将结构信息映射 成相关的符号信息，利用符号特征执行查询，从而快速地匹配结构；另一种 则采用精巧的数据存贮布局来模拟相应的文档结构，如链接树等。前者虽然 执行速度较快，但是表达能力较弱，无法支持复杂的表达式操作，如正则表 达式等；后者虽然表达能力很强，能支持所有的操作，但查询效率却不尽如 人意。 系统在表达能力与查询效率问作出相应的折中方案，加速用户常用操作 的计算，忽略罕见的费时查询表达，将查询路径分割为简单路径与复杂路径， 利用符号映射方法进行计算，同时利用结点名进行结构预筛选和按查询复杂 程度有序地匹配查询路径，有效地解决了空间、时间与表达能力之间的矛盾。 ( 3 ) 可扩展性 由于快速路径匹配算法并不涉及数值匹配的概念，而且在匹配的同时将 查询路径确定化，并给出相关的匹配值，为后继操作提供了广阔的互动空问。 再者，绝大多数的数据与应用系统都建立在关系数据库上，与我们采用的存 贮介质同源，因此在互操作与兼容性上的优势是显而易见的。 ( 4 ) 关系数据库的优势 关系数据库自问世以来经过2 0 多年的历史，相关技术可谓是炉火纯青。 系统采用关系数据库作为存贮介质，其可靠性、可维护性、并发控制能力将 是采用其他存贮介质的系统所不能比拟的。 3 2 数据模型和相关定义 3 2 1 文档结构 系统所处理的数据源模型属于以x m l - q l 代表的树模型。每个结点由结点名 和结点编号组成。结点名对应着具体半结构数据中的标记，而结点编号由系统在 装入数据库时根据结构实例统一分配，由0 开始。这样便解决了结点重名的问题， 如下图中结点( n a m e ：0 ) 和( n a m e ：1 ) ，分别与s t u d e n t 结点和t e a c h e r 结点 相连。结点分为两种类型，一种是只起连接作用不含数值的内部结点；一种是可 复旦大学硕士学位论文 半结构化数据查询中路径表达式的快速匹配方案第1 3 页 能包含数值的结点。 结点和结点间的有向关系称为 边，具体对应成半结构化数据文档 中的包含关系。边上标有相关的序 号，表示其指向的目标结点在源结 点的子结点集中按结点名字母升序 排列后的序号，同样由0 开始。 同时，合法的模型实例必须要 符合一定的约束： 无回路约束：无含回路； 数值约束：每一个叶 结点必须含有数值，反之却 不必然； 可达性约束：每个结点都至少含有一条从根结点开始的( 有向) 路径； 单包含约束：每个结点必须只被一个结点直接包含。 由此可知，模型实例是一棵结点和边附加了属性和标记的层次树，而模型可 用如下的三元组形式化描述： ( r o o t n o d e s e t ，n o d e s e t = n o d e ) ，e d g e s e t = ( c o n t a i n ) ) 3 2 2 路径表达式 硝三堕至炎萌廷主：、 、。一图3 2 模糊路径表达式一个实例 由上图可知，模糊路径表达式可以看成是由查询结点( 或经过某些构造) 按 一定的关系约束依次连接而成的有序列表，支持常见的通配符和正则表达式操 作，同时为了增强用户对结点问关系的查询需求，允许用户自由指定结点间关系 约束。 查询结点由结点名和结点谓词约束组成。结点名一般是有效的英文单词或通 配符“”( 匹配0 个至多个字符) 和“一”( 匹配单个字符) 组成。结点谓词约束 是可选的，一般是对结点数值进行限制。这样查询结点就可以写为 n a m e c o n s t r a i n t 或n a m e ，比如，t e a c h 和s c h o o l = “f u d a n ” 都是合法有效 的查询结点，而n a m e = ? 就是需要求值的查询目标。 查询结点允许正则表达式“女”( 匹配0 个至多个结点) 、“? ”( 结点可选) 、“+ ” 复旦大学礤士学位论文 半结构化数据查询中路径表达式的快速匹配方案第1 4 页 ( 匹配1 个至多个结点) 和“| ”( 至少匹配其中1 个结点) 的构造，但只允许单 个结点执行正则操作( 即经过正则构造后的结点和路径表达式不能参与结点构 造) ，而且带有正则操作的结点不能附加谓词约束。这样，查询结点可以如下表 示：n a m e s 、n a m e ? 、n a m e + 和( n a m e i l n a m e 2 l n a m e 3 ) ，比如( t e a c h ) ? 就是合法 的结点构造。 结点间的关系约束可以是祖先后继( 记为“ ”) 、后继祖先( 记为“ n a m e = ? 借鉴模式匹配的概念，每个查询路径经过处理后得到一个匹配值，匹配值越 大表示匹配程度就越小，若值为0 则完全匹配，而值为一1 则为不匹配。这样就 为用户和后继操作提供相关的选择信息。 比如，要完全匹配上述查询要求，可以写成如下的形式： d e p t = “c s ” ( t e a c h ) 7 s c h o o l = “f u d a n ” s t u d e n t 一 n a m e = ? = o 3 2 3 结构的位置信息 对于结构而言，最重要的信息是结点所属的层次与各结点间的包含关系。因 此构造相关的信息便成为结构查询的首要任务。我们形式化递归定义结构中任意 结点n o d e 的位置信息p o s i t i o n ，如下所述： p o s i t i o n ( r o o t ) = “0 ”； p o s i t i o n ( n o d e ) = p o s i t i o n ( p a r e n t ) + o r d e r ( p a r e n t ，n o d e ) i ( p a r e n t ，n o d e ) e d g e s e t 。 由上述定义可知，位置信 息是一个字符串。由右图所 示，图中结点t e a c h e r 的位置 信息“0 2 ”便是由其父结点 s c h o o l 的位置信息“0 ”附加 上边s c h o o l 到t e a c h e r 的序 号“2 ”而得到的。 由直观观察可知( 证明 略) ，位置信息具有下列良好 特性： 位置信息的长度表 示结点所处的层次； 复旦大学确士学位论文 图33 某结构实例的位置信息 半结构化数据查询中路径表达式的快速匹配方案 第1 5 页 一个合法的位置信息可以唯一确定具体结点，而任何结点的位置信息 是唯一的： 通过比较不同结点的位置信息可以确定结点间的关系； 通过比较不同结点的各自位置信息可以确定结点间的增广路径( 即无 向路径) 。 正是由于上述的良好特性，因而避免了路径表达式计算中频繁执行数据库联 接、索引查找以及大量的i o 操作，为快速路径表达式计算打下坚实的基础。 3 2 4 结构的增广路径 增广路径是不考虑结构中边的方向( 即认为所有边允许双向连接) 的所有路 径( 无回路) 。由直观可知( 证明略) ，任何结点间的增广路径必然是唯一确定的。 l 0 e a d ( 盈) n o r m a le d e t e t t e n dp a t b _ 图3 4 丑s t u d e n t 为起点的长度为2 的所有增广路径 如左图，给出了以s t u d e n t 为开始结点的所有长度为2 的5 条增广路径，记为s t u d e n t c i t y ，s t u d e n t c o u r s e ， s t u d e n t a b s t r a c t ，s t u d e n t t e a c h e r ，s t u d e n t s t r e e t 。 由于增广路径的数目大约为 结构边数的指数级范围，因此记 录所有结构的所有增广路径，对 存储的空间复杂度而言，即不现 实，也不可能。 3 3 路径表达式的快速匹配 下面重点介绍路径表达式快速匹配方案，比较了两种不同的增广路径计算方 法：利用位置信息推算结点间的增广路径和利用数据库联接计算全部的增广路 径。 3 3 1 利用位置信息计算结点间相对于指定关系约束的匹配值 由于同一路径上不同结点间的位置信息具有一定的特性，即祖先结点的位置 信息必然在后继结点的位置信息中重复，因此通过比较位置信息可以快速地推算 出任意结点间的彼此联系、距离和相对于指定约束的匹配值。具体的步骤如下所 示： 复且大学硕士学位论文 半结构化数攒查询中路径表达式的快速匹配方案第埔贾 p o s 泌n a e p o s 狂l o 挺酾d e 砖f o s i t i b e p o s m o n ( n o d e b ) l e n g t h a 爿p o s i t i o n a l , l e n g t h b = lp o s i t i o n b l r e l a t i o n ( p o s i t i o n a , p o s i t i o n b = d i s t a n c e ( p o s i t i o n a , p o s i t i o n b ) = u p p e r 3 c 0 ，l f t * n g t h a = p o s i t i o n a l = l e n g t h a 墨 p o s ；t i o n l l l ：l e n 。血匀 7 i 譬 i： g 血棚l d o w n ：3 c 地船篆慧篙! & 舶撵：湖l 。i r e c t ：l l e n g t h a 蛳=