（计算机软件与理论专业论文）基于语义网的软件工程数据查询处理技术研究.pdf

2 0l lm a s t e rd e g r e et h e s i s u n i v e r s i t yc o d e ： l0 2 6 9 s t u d e n ti d ：5 1 0 8 1 5 0 0 0 0 2 ea s tch i nan o r m a l u n i v e r s i t y r e s e a r c ho nse m a n t i c e n g m e e n n g w a r e d a t a q u e i yp r o c e s s i n g d e p a r t m e n t ：s q 鱼迎垦! 星星照g i 卫星星煎堕gi 垒曼! i 地! 曼 m a j o r ：q 堡p 丛l 曼s q 鱼巡旦! 里垦坠鱼坠曼q ! x d o m a i n ： s 坌堡垒n ! i 坌鳖坠q 垒! 垒丛鱼堕旦g 垒也星堕! s u p e r v i s o r ：q q 垒gx 坠曼g i 坠g a p p l i c a n t ：垦q ：! 堕y i 2 0 1 1 5 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文基于语义网的软件工程数据查询处理技术研究， 是在华东师范大学攻读移垒博士( 请勾选) 学位期间，在导师的指导下进行的研究工作 及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意。 作者签名：叟厦易日期：加年厂月2 7 日 华东师范大学学位论文著作权使用声明 基于语义网的软件工程数据查询处理技术研究系本人在华东师范大学攻读学位 期间在导师指导下完成的硕左博士( 请勾选) 学位论文，本论文的研究成果归华东师范 大学所有。本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门 和相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学 位论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采 用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部”或“涉密 学位论文母， 于年，月日解密，解密后适用上述授权。 ( 2 不保密，适用上述授权。 导师签名 本人签名整垦星 加1 1 年箩月2 7 日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范人学研究生申请学位论文“涉密”审批表方为有效) ，未经上述 部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上 述授权) 。 萱屋易硕士学位论文答辩委员会成员名单 姓名职称单位备注 周水庚教授复旦大学主席 王晓玲教授华东师范大学 钱卫宁副教授华东师范大学 摘要 在软件系统的丌发过程中通常会产生了大量结构复杂、语义丰富的数据，而建立一 个灵活的语义模型是对各类软件工程数据进行统一管理的基础。在管理大量软件工程数 据的过程中，如何对其进行高效的查询无论对项目管理人员还是科研人员都是一个挑 战。近年来随着语义网技术的兴起，为解决这些问题提供了契机。r d f 与o w l 是语义 网的重要组成部分，具有对复杂数据进行描述和建模的能力。软件工程数据互相关联结 构各异的特点使得它们能较好地被r d f 与o w l 表示。同时语义网研究中关于r d f 数 据的查询优化也是一个热点领域。本文围绕如何利用语义网技术对软件工程数据进行表 示和查询展开研究工作。本文的主要研究工作有以下几点。 首先，本文在对软件工程数据的特点和管理现状进行详细分析的基础上，提出利用 语义网技术对软件工程数据进行管理的思路和方法，对于软件工程数据的查询需求本文 进行了分类和总结，并给出了一些典型的查询应用场景。 其次，本文为软件工程数据定义了本体来完整地描述此类数据，基于该本体，本文 收集了一些软件工程数据的语义数据，以后的研究及实验都可围绕该本体和这些语义数 据展丌。建模和数据收集的工作可用于将来进一步的研究，为实现高效的数据管理打下 了基础。 最后，本文总结了现有的语义网数据查询优化技术，提出了一种利用数据集本体的 统计信息来优化语义网数据查询的方法，该方法能减少查询执行时连接操作的代价，从 而提高查询速度。实验证明了该方法较同类方法具有更好的性能。 本文的研究工作为如何高效管理软件工程数据提供了一个新的思路，也是实现一个 海量软件工程数据存储和检索平台的关键支撑技术。本文的工作为实现这一平台打下了 基础。 关键词：语义网、软件工程数据、数据建模、查询处理 ab s t r a c t t h ed e v e l o p m e n to fs o j f t w a r eb r i n g sh u g e锄o u n to fd a t aw h i c hh a sc o m p l i c a t e d s t m c t u r ea 1 1 dr i c hs e m a n t i c s b u i l d i n gan e x i b l es e m a n t i cm o d e li st h ef o u n d a t i o no ft h e m a n a g e m e n to nv 撕o u st y p e so fs o 胁a r ee n 昏n e 丽n gd a t a i nt h ep r 0 蓼e s so fs u c h m a n a g e m e n t ，h o wt om a k eh i 曲p e r f o n i l a i l c eq u e 拶i sab i gc h a l l e n g e 旬rm a n yp r o j e c t a d m i n i s t r a t o r sa n dr e s e a r c hp e o p l e t h er i s eo fs e m a n t i cw e bt e c i l n o l o g yp m v i d e san e wi d e a t or e s o l v es u c hp r o b l e m s r d fa n do w la r em ei m p o r t a n tp a r t so ft h es e m a n t i cw e b 、】l ，h i c h h a v es t r o n ga b i l i t yo nd e s 嘶b i n ga r l dm o d e l i n gc o m p l e xd a t a s i n c es o 觚a r ee n 昏n e e r i n gd a t a h a sr e l a t e da n dh 劬e r o g e n e o u ss t m c 彻e ，i tc a i lb ed e n o t e de a s i l yw i t hr d fa n do w l i i lt h e f i e l do fs e m a n t i cw 曲，r d fq u e 叮o p t i m i z a t i o ni sa l s oah o ts p o t w ef o c u sh o wt od e n o t e 锄d q u e 叮 s o 胁a r ee n 百n e e r i n gd a t a u s i n gs e m a n t i cw e bt e c 量l i l o l o 夥 1 1 1 e n o v e l t ya n d c o n t r i b u t i o n so ft h i sd i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w i n g ： w ed i s c u s st h em a n a g e m e n ts t r a t e g yo fs o f t w a r ee n 百n e e r i n gd a t ai ns e m a n t i cw e b e n v i r o m e n t w em a k eac l a s s i 6 c a t i o nf o rm eq u e r i e so ns o r w a r ec n 西n e e i i i n gd a t a 锄d 西v e s o m er 印r e s e n t a t i v eq u e 巧s c e n e w ed e f i n ea 1 1o n t 0 1 0 9 ym o d e lf o rs o 脚a r ee n 百n e 舐n gd a t at o 舀v ea i li n t e 孕a t e d d e s c p t i o no ns u c hd a t a w ec o l l e c ta n u m b e ro fs o f t w a r ec 1 1 百n e 甜n gd a t aa c c o r d i n gt ot h e o n t o l o g y t h e s ed a t ac a nb eu s e do n 如t l l r er e s e a r c h 砒l de x p e r i m e n t w es u m m 撕z ee x i s t i n gt e c h l l i q u e so fs e m a n t i cw e bq u e r y o p t i m i z a t i o n ；p r o p o s ean o v e l o p t i m i z a t i o nm e t h o du s i n go n t o l o g ys t a t i s t i c a ld a t a t h em e t h o di m p m v e sq u e r yp e r f i o m a n c e b yr e d u c i n gm ec o s to f j o i no p e r a t i o ni i lq u e e x p 舐m e n t a lr e 叭l t sc o n f i 姗t h a tt h em e t h o d h a sb e t t c rp e r f o n n a l l c em a ne x i s t i n ga p p r o a c h t h ew o r ko f “sd i s s e r t a t i o np r e s t san e wi d e af o rm a l l a 舀n gs o 脚a r ce n 西n e e r i n gd a t a e 伍c i e n n y i ti sa l s o t h ec o r ct e c h i l i q u e so fd e v e l o p i n gas t o m g e 锄ds e 删lp l a t f o n nf o r m a s s i v es o 胁a r ec i l 百n e e r i n gd a t a k e y w o r d s ：s e m a n t i cw 曲，s o 胁a r ee n 酉n e 嘶n gd a _ t a d a t am o d d i n 岛q u e r yp r o c e s s i n g 目录 l 绪论1 1 1 研究i ：作的背景。l 1 2本文的研究内容2 1 3 本文的主要贡献3 1 4 章霄安排4 2背景知识和相关工作5 2 1 语义网一5 2 1 1 资源描述框架( r d f ) 7 2 1 2 r d f 的奄洵语言( s p a r q l ) 9 2 1 3 网络本体语言( o w l ) lo 2 2 r d f 数据夯询处理技术l2 2 3 软件一r 程数据应用现状1 4 2 4 本章小结1 5 3软件工程数据的查询与本体1 6 3 1 查询需求与场景1 6 3 1 1 关键字杏询1 6 3 1 2 关联查询18 3 1 3 相似性奄询1 8 3 2 软件工程数据的本体模型1 9 3 2 1 源代码1 9 3 2 2 需求2 2 3 2 3 测试2 3 3 2 4 缺陷2 4 3 2 5 版本2 6 3 2 6 数据间的关联2 7 3 3 实例分析2 9 3 4 本章小结3l 4基于本体统计信息的查询代价估算3 2 4 1 选择率3 2 4 2 启发式规则3 3 4 3 利用本体统计信息的优化方法3 4 4 4 本章小结3 9 5实验数据与实验分析4 0 5 1软件+ l ：样语义数据集4 0 5 2实验与分析4 2 5 3 本章小结4 9 6总结与展望5 0 参考文献5 2 致谢5 8 攻读学位期间主要研究成果5 9 皋十语义刚的软件i i 干口数据阿处j ! ! ! 技术研究 1 绪论 1 1 研究工作的背景 绪论 随着信息技术的发展，软件系统变得越来越庞大和复杂。在大型软件系统的开发、 部署及维护过程中会产生海量的、结构各异的数据，如软件规格说明书、代码、注释、 版本信息、测试数据、错误报告和运行同志等，这些数据可以被统称为软件工程数据。 软件工程数据不仅仅是软件开发过程的产物，同时也是开发和维护软件系统的重要基 础。通过对海量的软件工程数据进行有效管理和综合分析，能够在需求挖掘、代码重用、 错误调试、运行维护等多方面帮助丌发人员快速、高效地构建和维护软件系统。 数据管理一般分为存储和查询两部分。目前的软件工程数据大多采用文件的形式存 储 1 】【2 】 3 【4 】，仅能实现对部分数据的分析和重用，且效率低下。不止是存储，在查询 上目前的方法也存在问题。目前对于软件工程数据通常采用基于关键字的查询方式 5 】， 这种方式所能应付的查询场景较有限，且无法利用数据中的许多重要信息。如果能够建 立一个对海量软件工程数据进行存储和检索的平台，开发人员就可以在构建和维护软件 系统的不同阶段，通过该平台获取有用的信息，用以帮助改进软件开发的过程，提高开 发效率和软件系统的质量。 语义网 6 】( s e m a n t i cw 曲) 的兴起为解决这个问题提供了契机。语义网是w 3 c 7 组织提出的关于下一代互联网的一系列实现技术，主要包括资源描述框架( r e s o u r c e d e s 嘶p t i o nf r 锄e w o r k ，i m f ) 【8 】、和网络本体语言( o n t o l o g y w 曲l a n g u a g e ，o w l ) 9 】。 其中o w l 具有对复杂数据进行语义描述和建模的能力，其最早被用来描述w e b 数据。 而软件工程数据和w e b 数据一样，具有互相关联和结构各异的特点，因此适合使用 o w l 来对其进行表示。 与其他数据一样，语义网数据也需要管理平台，目前使用传统关系型数据库对其进 行管理是一种常用的手段【1 0 】【1 l 】。然而语义网数据作为半结构化数据，比关系型数据 库中的数据更灵活，关系型数据库的模式一旦定义就几乎不会改变，而语义网数据随着 新加入数据源的不同模式可能经常发生变化。因此，传统关系型数据库的存储和查询方 皋- j 二语义州的软件t 程数据台询处理技术研究 式必须做出变化以适应语义网数据模式不稳定的特点。 1 2 本文的研究内容 绪论 本文针对使用r d f 进行描述和存储的软件工程语义数据，研究和实现相应的查询处 理策略和查询优化技术。上文提到，建立一个软件工程数据存储与检索平台能够改善软 件工程数据的管理情况。图1 1 给出了该平台的基本架构，该架构主要分为如下几个部 分： 图1 1 ：软件t 程数据存储与检索平台的基本架构 用户查询界面：最终用户提交查询条件的界面。由于使用r d f 数据，用户提交的查 询可以不限于关键字查询。界面应成分利用r d f 的特点，使用户的查询类型更丰富。 查询处理与优化模块：根据用户输入的查询条件，生成相应的r d f 查询语言，并在 优化后生成执行计划，按照执行计划访问r d f 数据存储器，取得结果并封装后返回 给用户。 数据采集与标注：包括从网上获取原始软件工程数据的爬虫以及从这些数据中提取 语义信息的语义标注模块。 本文研究的目的是为最终实现一个软件工程数据管理平台所做的技术准备。参考该 平台各部分的功能，本文的主要研究内容有以下几个部分： 首先，本文对常见的软件工程数据查询进行总结和分类，并给出典型的查询需求。 目前通常使用的关键字查询不能很好地对数据中的语义进行查询，这使得关键字查询的 2 堆十语义删的软件t 程数据盘洵处理技术研究绪论 应用场景较为有限，无法满足用户的需求。在引入r d f 数据后，查询的利，类除了关键 字查询外，还可对本体的类型进行查询，或在有上下文的环境中查询，甚至可以比较两 个实体的语义相似度。这些额外的查洵类型为软件工程数据管理平台提供了丰富的应用 场景。 其次，本文定义了一个软件工程数据的本体，并从一些丌源软件社区( 如s o u r c e f o 玛e 1 2 】) 收集了一些软件工程数据，通过预处理提取其语义信息。这些本体和语义数 据为本文的实验提供了依据，也可作为将来软件工程数据语义检索研究方面的测试数据 集。 基于该测试数据集以及其他一些r d f 标准测试集，本文深入研究和分析了r d f 数 据的查询优化方法。设计和实现了一种利用数据本体的统计信息来对l m f 查询进行优 化的方案。在r d f 查询处理中，连接操作的代价较大，许多优化方法都是针对如何减 少连接操作来进行的。一种方法是建立索引，通过索引可以提高表的扫描速度，也可以 记录部分连接操作的结果，从而减少执行时的连接操作：另一种是利用数据集统计信息， 根据数据集的特点事先计算一些关键统计信息也可以帮助减少连接操作的代价。 1 3 本文的主要贡献 本篇论文主要对软件工程数据语义查询处理技术展丌研究工作，论文的主要贡献可 以总结为如下几点： 本文在对软件工程数据的特点和管理现状进行详细分析的基础上，提出利用语义 w e b 技术对软件工程数据进行管理的方法和思路。本文对于软件工程数据的查询需求 进行了分类和总结，给出了一些典型的查询应用场景。 本文为软件工程数据定义了本体，该模型不仅能够对源代码、需求、测试、版本和 缺陷数据进行描述，同时还对这些数据之间的语义关联进行了描述。在该本体的基础上 本文收集了一些软件工程数据的语义数据，以后的研究及实验都可围绕该本体和这些语 义数据展开。建模和数据收集的工作为实现高效的数据管理打下了基础。 本文总结了现有的语义w e b 数据管理技术，提出了一种利用本体和数据集本身信 息统计的方法，根据估计的选择率来生成查询策略，该方法能有效减少查询执行时中间 结果的大小，从而提高查询速度。实验证明该优化方法较一般r d f 查询引擎执行效率 3 皋十语义悯的软件。l ? 程数据企询处理妓术研究 有较大提高。 1 4 章节安排 绪论 本论文共分为六章。第l 章主要对论文研究工作的背景、研究内容等进行概要性的 介绍，给读者一个整体的印象。第2 章到第5 章是本文的核心内容，对本文研究工作的 背景知识、相关工作、主要技术、和实验情况进行了详尽的介绍。为了方便读者理解， 在第2 章中首先介绍语义w e b 及其核心技术r d f 和o w l ，以及r d f 的标准查询语言 s p a r q l ；然后会从存储组织、查询处理及优化等方面介绍语义w e b 数据管理的研究 现状；最后介绍了软件工程数据管理与研究的现状。论文的第3 章研究了语义网环境下 的软件工程数据查询场景，提出了针对软件工程数据的本体模型。首先对软件工程数据 的查询进行总结和分类，然后在此基础上分别对软件工程中的源代码、需求、测试、缺 陷、版本等数据进行本体建模，最后结合一些实际应用场景对该本体模型的应用做了分 析。利用本体统计信息对s p a r q l 查询进行优化是本文另一个重要研究工作，第4 章中 论文对这部分内容进行了详尽的介绍。本文总结了优化中需要统计的数据集信息和本体 信息，并给出了如何利用它们估算出s p a r q l 三元组模式的选择率，并根据选择率对三 元组模式进行排序的方法。在第5 章中，本文介绍了在收集的软件工程语义数据的方法 与收集到的语义数据集，并按照第4 章中的方法实现了一个优化器，通过实验与分析验 证了该方法的有效性。最后，在第6 章中对论文的研究工作进行了总结，并就技术的改 进和将来的研究方向进行了讨论。 4 皋十语义m 的软件t 程数据金1 j 处理技术研究 2 背景知识和相关工作 背景知识和相关t 作 本文在第1 章绪论中，对研究工作的应用背景、内容和主要贡献进行了阐述。本章 主要介绍与文中研究工作相关的背景知识，以及在相关领域中已有的研究工作和成果。 首先，本章对语义网进行了一个概要性的介绍，并结合一些实例对语义网的两大技术： r d f 和o w l 进行深入介绍；其次，介绍了用于对r d f 数据进行查询的s p a r o l 语言； 然后，本文会从存储组织、查询处理及优化等方面对现有的语义w e b 数据管理工作进 行综述；最后本章将从研究与应用的角度介绍了软件工程数据管理的现状。 2 1 语义网 语义网是w 3 c 组织的主席t i mb e m c r s l e e 于1 9 9 8 年提出的一个概念。语义网技术j 通过为互联网上的数据添加元数据或结构化描述等一系列方法来使得计算机能够理解 互联网上的各种资源，从而实现计算机之间语义信息的交换。语义网是互联网的扩展， 也是下一代互联网的发展方向。在自然语言处理研究尚不成熟的情况下，语义网的研究 开始逐渐成为热点。目前语义网还没有一个正式的定义，人们提到语义网，主要指的是 w 3 c 提出的相关模型及技术标准，包括描述互联网资源的“资源描述框架( r d f ) 以 及定义本体或词汇概念的“i m f s 1 3 】”和“网络本体语言( o w l ) 等。 t i mb e m e r s l e e 提出了语义网的体系结构框架 1 4 】。如图2 1 所示，该框架由七层组 成，自下而上分别是：编码定位层、x m l 层、资源描述层、本体层、逻辑层、证明层 和信任层。该体系结构以现有的互联网为基础，自下而上功能逐渐增强，为语义网的实 现提供了基本的思路与方法。 5 果十语义刚的软件t 程数据询处理技术研究背景知识和相关丁作 幽2 1 ：语义网体系结构框架幽 编码定位层( u n i c o d e + u r l ) ：位于体系机构的底层，是语义网的基础。其中u n i c o d e 对资源进行编码，u r i 对资源进行标识。资源只有在被编码和标识的情况下才可作 进一步处理。 x m l 层( x m l + n s + x m ls c h e m a ) ：想要描述互联网资源，必须为其添加元数 据，元数据对于机器间的信息交换是至关重要的。为了显式地表示元数据，必须对 数据进行标记。为此，w 3 c 组织提出了可扩展标记语言( e x t e n s i b l em 咖 l a i l g l l a g e ) 【1 5 】，即) ( m l 。x m l 具有简单灵活的特点，再加上命名空间( n s ) 和 x m ls c h e m a 提供的数据确定性和多数据类型检验机制，x m l 成为了语义网体系结 构的重要组成部分。该层负责从语法上表示数据和结构，并将数据的内容和结构分 离。但x m l 仍有其局限性，其只能表达数据的语法，而不能将数据表示成机器所 能理解的形式。 资源描述层( r d f + i m fs c h e m a ) ：资源描述框架( r e s o u r c ed e s c r i p t i o n f r 锄e w o r k ) ，简称r d f ，是w 3 c 组织推荐的用于描述互联网资源的规范。r d f 十 分善于描述资源及其之间关系，具有简单、易扩展、开放性、易交换和易综合等特 点。r d f 有向图的特性使其能比x m l 更灵活地表达网上的资源信息。在砌) f 中可 定义词汇，并可表达机器可理解的形式化语义。r d f 可以说是一种元数据语义描述 规范。但r d f 在定义词汇时无法解决一词多义的问题，同时其推理能力也不够。 本体层( o n t o l o 科v o c a b u l a r y ) ：在语义网中，本体指关于领域知识的概念化、形式 化的规范。在资源描述层的基础上，本体层能够对领域知识进行统一的理解和描述， 6 笨一j ：语义刚的软件厂程数据金询处删技术研究背景知识和相关t 作 并支持逻辑推理。本体层弥补了资源捕述层的不足，同时也足逻辑层及以上各层的 基础。在w 3 c 规范中，网络本体语言( o n t o l o g yw 曲l a n g u a g e ，即o w l ) 是最常 用的描述本体的一种形式。 逻辑层( l o 西c ) 、证明层( p r o o f ) 和信任层( t r u s t ) ：引入语义网的最终目的是要 利用其中的语义信息，使程序的智能和自动化程度大大提高，要实现这一目的离不 丌推理和验证。在语义网体系结构中本体层以上的各层统称为规则层，它们都是为 程序如何利用语义信息而服务的。具体说来，逻辑层的主要任务是定义一套强大而 高效的推理系统；证明层是为保证代理工作的可靠性而提供的一种验证机制；信任 层位于体系结构的顶层，通过建立信任关系来确保语义网的可靠性。 2 1 1 资源描述框架( 1 m f ) 如前文所述，r d f 是一种描述互联网上资源及其关系的一种规范。虽然有多种表现 形式( 如r d f l 1 6 】、n 3 1 7 】、t u r t l e 1 8 、n - 嘶p l e s 1 9 】) ，但其本质都三元组。具 体来说，r d f 是以( s ，p ，o ) 的三元组形式来表示网络资源的，其中s 代表主语( s u b j e c t ) ， p 代表谓语( p r e d i c a t e ) ，o 代表宾语( o b j e c t ) 。这样主语和宾语就由谓语建立起了关联， 从而使数据带有语义信息。例如，l l t t p ：s o m e 、h e r e p e r s o n l 表示互联网上一个独一无二 的资源， “j o h i ls m i m 是一个普通的字符串，两者通过 h t t p ： r 、 ，、) l ，w 3 o 增7 2 0 0 0 1 0 s w a p p i m c o n t a c t 撑m l l n a m e 这个谓词连结，该谓词也是一个资 源。这样组成的三元组所表示的语义为“一个资源的姓名是j o l l i ls m i t h 。 图2 2 ：一个) ) ( m l 文档示例 7 基十语义删的软件t 程数据食洵处理技术研究 背景知识和相天t 作 由于r d f 有多种表现形式，这旱以比较常见的r d f x m l 为例进行说明。图2 2 给 出了一个描述个人信息的r d f 文档示例。可以看到，其语法是基于x m l 规范的。该文 档描述了一个u r i 为h t t p ：，、】v w w 3 o 叫p e o p l e e m c o n t a c t 群m e 的资源，它的名字叫“e r i c m i l l e r ”，邮箱地址为“锄 w 3 o r g ”，头衔为“d r ”。这些语义由4 条三元组组成，分别 是： ( h t t p ：v n 删w 3 o i p e o p l e e h 嗄c o n t a c t m e ， h t t p ：、) l ，w w w 3 o r 2 0 0 0 1o s w a p p i m c o n t a c t 群m 1 1 n 锄e ， ”e r i c m i l l e r ) ( h t t p ：b ，w w w 3 o r p e o p l e e m c o n t a c t 挣m e ， h t t p ：、硎哪w 3 o r g 2 0 0 0 1o s w a p p i m c o n t a c t f p e r s o n a l t i t l e ， d r ) ( h t t p ：州哪w 3 o 吲p e o p l e e m c o n t a c t 枷e ， h t 巾：m v w w 3 o 叫l9 9 9 0 2 2 2 一r d s ”t a x - n s “y p e ， h t t p ：、幅啊w 3 o r 2 0 0 0 l0 s w a p p i m c o n t a c t 撑p e r s o n ) ； ( h t t p ：w w w w 3 o 叫p e o p l e e m c o n t a c t j f i m e ， h t t p ：w w w w 3 o 叫2 0 0 0 1o s w a p p i l l l c o n t a c t 枷a i l b o x ，e m w 3 o r g ) 。 图2 3r d f 图的三种链式结构 8 皋于语义m 的软件门军数据询处胖技术研究7 7 景知识和相关丁作 r d f 主要有两种数据类型，u r l 和“t e r a l 。u r i 表示资源，每一个u r i 都是互联网 上一个独一无二的标识；“t e r a l 指字符串等数据，这些数据在互联网中不具有唯一性。 三元组中的主语和谓语一定是u r i ，而宾语既可以是u r l 也可以是“t e r a l ，如果是u r i 则表示该节点是下一个三元组的主语或宾语，从而两个三元组f h j 彤成了一个链式结构， 如图2 3 所示。如果把三元组中的主语看作节点，谓语看作有向线段，则r d f 数据就可 以表示成带标签的有向图的形式。比起x m l 的树形结构，r d f 的有向图形式更为灵活， 而且作为一种知识表现形式，有向图也较传统的关系模型显得更加自然。虽然在实际应 用中，相当一部分r d f 数据存储在关系型数据库中。 2 1 2r d f 的查询语言( s p a r q l ) 由于r d f 层作为语义网中数据交换的媒介，是语义网的重要组成部分，语义网的大 部分应用都涉及到对r d f 数据的查询。w 3 c 组织为r d f 设计了一些查询语言，如 雀二 s p a r q l 2 0 】、o w l - q l 【21 】、r q l 【2 2 】和r d q l 2 3 等。其中s p a r q l 是目前最流行的 r d f 查询语言。 s p a r q l 的语法格式与s q l 2 4 】较为相似，按查询目的划分共有4 种查询方式： s e l e c t 、c o n s t r u c t 、a s k 和d e s c r i b e 。s e l e c t 方式用于从待查询r d f 文档 中抽取原始数据，结果以表格形式反馈；c o n s t r u c t 方式用于把查询的结果重构成 r d f 文档的形式；a s k 方式用于仅对查询结果作真假判断；d e s c 融b e 方式用于在待 查询文档中抽取r d f 子图。一个s p a r q l 查询不管采用哪种方式，通常都有w h e r e 模块来描述查询条件( 在c o n s t r u c t 方式下w h e r e 是可选的) 。 前面讲过，r d f 可以表示成有向图的形式，而s p a r o l 即根据查询的模式在待查询 的r d f 图中进行图模式匹配。s p a r q l 支持4 种匹配方式：三元组模式( 嘣p l ep a t t e n l s ) 、 值约束( v a l u ec o n s t r a i n t s ) 、可选图模式( o p t i o n a lg r a p hp a t t c m s ) 和替代图模式 ( a l t 锄a t i v eg r a p hp a t t 锄) 。其中三元组模式又称基本图模式( b a s i c 胁p hp a t t e n l ) ， 是s p a r q l 中最常见的匹配方式，与r d f 的三元组类似，但三元组的任意一个或几个， 都可以由查询变量代替；值约束是在三元组模式的基础上过滤出一些满足特定条件的子 图，s p a r q l 中的关键字为f i l t e r ；可选图模式用于在结果集中增加一些满足部分条 9 皋十语义刚的软件t 程数据仓i 旬处理技术研究 背景知识和相关t 作 件的子图，s p a r q l 中的关键字为0 p t l 0 n ；替代图模式用于两个子图的联合查询，类 似s q l 中的u n i o n 。 例2 1 ：p r e f i xd c ： p r e f i xn s ： s e l e c t ? t i t l e ? p c e w h e r e ? x d c ：t i t l e ? t i t l e o p t i o n a l ? xn s ：p r i c e ? p r i c e f i i j e r ? p r i c e 3 0 ) ) 例2 1 给出了一个s p a r q l 的例子。其中p r e f i x 定义了名空间，s e l e c t 后的内容表示待查询的变量，在s p a r q l 中，“? ”后接变量名表示一个变量。w h e r e 中包含了满足查询条件的图模式，这个例子中包含3 种匹配模式：基本图模式、可选图 模式和图约束。该查询返回数据集中所有的t i t l e 和p r i c e 小于3 0 的值。如果给定数据集 如例2 2 所示( 三元组形式) ，则该查询的结果在表2 1 中显示。 在信息科学中，本体是指 娃f 语义i q 的软件t 程数据洵处删技术研究背景知识和相天一i i 作 相关领域中实体的推理或描述该领域。 o w l 用于对本体进行语义描述，是山w 3 c 推荐的用来描述语义网中本体的标准语 言，其语法遵循x m l 规范。o w l 分为三种【2 6 】，按照语义表达能力从低到高分别为： o w l “t e 、o w ld l 和o w lf u l l 。o w l 本体的主要元素是与类( c l a s s e s ) 、属性 ( p r o p 酣i e s ) 、类的个体( i n d i v i d u a l s ) ( 实例) 以及这些个体之间的关系，其中个体是 类的具体实现。 o w l 中的类提供了使具有相同特性的资源聚集在一起的抽象机制。在本体中，它用 来代表不同的概念之间的层次结构。在描述一个本体时，类通常都带有层次结构，以一 些领域中的基本类为基础，向下扩展其他类，即其他类都是这些基本类的子类 ( r d f s ：s u b c l a s s o f ) 然而，所有用户定义的类都是o w l 中一个隐含类o w l ：t h i n g 的子类， 即o w l ：1 1 1 i n g 是整个o w l 树形结构的根( r o o t ) 。 o w l 中的属性用于描述类或个体之间的关系或个体带有的特征。o w l 中的属性分 两种：对象属性( o w l ：c i b j e c t p r o p e n y ) 和数据属性( o w l ：o b j e c t p r o p e n y ) 。对象属性定义 两个类的个体之间的关系，而数据属性定义类的个体和数掘类型的关系；换句话说，对 象属性连接两个类的个体，数据属性连接个体和数据值。与类一样，属性也可以有其子 属性( o w l ：s u b p r o p e n y o f ) ，表示带有其父属性的类或个体也同样带有该子属性。在定义 属性时可以指明它的定义域( d o m a i n ) 和值域( r a n g e ) 。和r d f 一样，一个本体结构也 可看作有向图，一个属性和其两端的节点形成了一个三元组。借用r d f 的概念，定义 域指的是三元组“主语”的类型，值域指的是“宾语”的类型。对象属性的值域可以是 类，也可以是数据类型；数据属性的值域只可以是数据类型。上文的数据类型，指的是 r d fl i t e r a l s 和v i ls c h e m ad a t at y p e s 。其中x m ls c h e m ad a t at y p e s 具体在文献 2 7 】中 定义，w 3 c 推荐的在0 w l 中使用的类型有3 5 种【2 6 】。 为了方便推理，o w l 为属性引入了谓词逻辑中一些性质，包括传递性 ( t r 柚s i t i v e p r o p e r t y ) 、对称性( s ) ，i 】：蚰e t r i c p r o p e r t y ) 、函数性( f u n c t i o n a l p r o p e r t y ) 、逆 属性( i i l v e r s e o f ) 、反函数性( i n v e r s e f u n c t i o n a l p r o p e n y ) 等 2 6 】。这些属于o w l 的高 级特性，不在本文的研究范围内，故不做讨论。 与传统的x m l 和r d f 相比，o w l 相当于一个框架，一旦框架定义完成，其下的 x m l 和r d f 数据都不应超出此框架的范围。o w l 提供了扩展的词汇表，并允许设计 者自定义词汇，这一特性使得o w l 能够表示各种异构的数据。同时，o w l 的对象属 性能很好地体现各种数据之间的关系。o w l 的这些特性已被应用于描述多个领域中复 幕十语义叫的软件丁程数据哟处胖披术研究 杂数据 2 8 】 2 9 】。 2 2r d f 数据查询处理技术 背景知识和栩关t 作 随着语义网逐渐成为研究热点，近年来在r d f 数据管理方面已经有大量的研究工作 和成果被发表，一些组织也设计丌发了一些对r d f 数据进行管理的工具或原型系统。 数据查询处理与优化是数据管理的一大基本任务。本小节从r d f 的查询处理技术与查 询优化技术分别加以讨论。 在查询处理方面，目前通常的做法是将s p a r q l 映射到s q l 的方式来实现，因为 s q l 的查询处理技术己较为成熟。但s p a r q l 与s q l 在结构上仍存在差异，人们对如 何将s p a r q l 完整转换为s q l 的问题上做了一系列工作。【3 0 】提出了一套模式无关的 转换算法；【3 l 】【3 2 提出了基本查询、嵌套查询、并行查询的转换算法； 3 3 】提出了将 o p t i o n a l 算子匹配到s q l 的算法；【3 4 解决了f i l t e r 表达式的转换问题。 在r d f 的查询优化上，目前的工作主要分为构建索引和建立统计信息两部分。由于 r d f 数据是一种图数据，它的索引分为两种：路径索引和分块索引。路径索引指的是根 据r d f 图中两个节点间的距离而建的索引，又可分为单步索引、双步索引和多步索引。 单