基于属性相关性的SPARQL查询优化方法.pdf

计算机研究与发展 I S S N1 0 0 0 1 2 3 9 C N1 1 1 7 7 7 T P J o u r n a lo fC o m p u t e rR e s e a r c ha n dD e v e l o p m e n t4 6 S u p p l 1 1 9 1 2 5 2 0 0 9 基于属性相关性的S P A R Q L 查询优化方法 吕彬杜小勇王琰 教育部数据工程与知识工程重点实验室北京1 0 0 8 7 2 中国人民大学信息学院北京1 0 0 8 7 2 1 v b i n r u c e d u e n S P A R Q LQ u e r yO p t i m i z a t i o nB a s e do nP r o p e r t yC o r r e l a t i o n s L aB i n D uX i a o y o n g a n dW a n gY a n K e yL a b o r a t o r yo fD a t aE n g i n e e r i n ga n dK n o w l e d g eE n g i n e e r i n go fM i n i s t r yo fE d u c a t i o n B e i j i n g1 0 0 8 7 2 S c h o o lo fI n f o r m a t i o n R e n m i nU n i v e r s i t yo fC h i n a B e i j i n g1 0 0 8 7 2 A b s t r a c t N o w a d a y st h em a i n s t r e a mR D Fr e p o s i t o r ys y s t e m sa r eb a s e do nR D B M S T h eS P A R Q L q u e r ye n g i n et r a n s l a t e saS P A R Q Lq u e r yi n t oaS Q Lo n e a n dt h e nt h eR D B M Se x e c u t e st h eS Q L q u e r y H o w e v e r t h eR D B M So p t i m i z e r s w h i c hu s u a l l ya s s u m e t h a tc o l u m n sa r es t a t i s t i c a l l y i n d e p e n d e n t o f t e nu n d e r e s t i m a t et h es e l e c t i v i t yo fe o n ju n c t i v ep r e d i c a t e sa n dc h o o s eab a dq u e r y e x e c u t i o np l a n I ti si m p o r t a n tf o rq u e r yo p t i m i z e r st od e t e c tc o r r e l a t i o n sa m o n gp r o p e r t i e s Am e t h o d o fc o m p u t i n gp r o p e r t yc o r r e l a t i o n sb a s e do no n t o l o g yi t s e l fi s p r o p o s e di no r d e rt oi m p r o v et h e e x e c u t i o np e r f o r m a n c eo ft h eS Q Lt r a n s l a t e df r o mS P A R Q Ls t a t e m e n tq u e r i e s K e yw o r d so n t o l o g y S P A R Q L S Q L p r o p e r t yc o r r e l a t i o n q u e r yo p t i m i z a t i o n 摘要目前主流的R D F 存储系统都是基于关系数据库的 其查询引擎都是将S P A R Q L 转换为S Q L 然后由数据库的查询引擎来执行查询 但是 目前的数据库查询优化器对于连接查询的选择度估计都是 基于属性独立假设的 这往往导致估计错误而选择了效率低的执行计划 所以属性相关性信息对于 S P A R Q L 查询优化器能否找到效率高的执行计划是非常重要的 针对S P A R Q L 转换为S Q L 后 因连 接操作没有优化导致查询效率不高的问题 提出了利用本体信息自动计算属性相关性的方法 从而调整 连接操作的选择度估计值 调整连接顺序 提高S P A R Q L 查询中基本图模式的连接查询效率 关键词本体 S P A R Q L S Q L 属性相关 查询优化 中图法分类号T P l 8 2 R D F 是W 3 C 组织推荐的资源描述语言标准 采用三元组T s P o 来描述W e b 信息 其中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 W 3 C 数据访问工作小组 D A W G 已 将S P A R Q L c l J s i m p l ep r o t o c o la n dR D Fq u e r y l a n g u a g e 推荐为R D F 查询语言标准 它是基于图 模型的查询语言和数据访问协议 它的操作类似于 收稿日期 2 0 0 9 0 6 1 9 基金项目 国家自然科学基金项目 6 0 8 7 3 0 1 7 6 0 5 7 3 0 9 2 6 0 4 9 6 3 2 5 关系代数的连接 合并 选择 投影和左外连接等 如今 R D F 在语义网和W e b 2 0 中得到广泛的 应用 互联网上的R D F 数据越来越多 支持大规模 R D F 数据的存储系统已开始出现 其中多数都是建 立在关系数据库上的 它们的存储模式大体可以分 为3 类 第1 类是三元组存储 即用1 张单表来存储 R D F 三元组 此表有主 谓 宾3 列 分别存储R D F 万方数据 1 2 0计算机研究与发展2 0 0 9 4 6 增刊 三元组中的 S P O 此类的代表性系统包括 J e n a E 引 s e s a m e 3 3 s t o r e t 4 3 等 第2 类是二元组模 式 即利用R D F 模式信息生成属性表或类表 这样 同一属性的实例存在l 张表中 或同一类的实例存 在1 张表中 如D L D B L5 R D F S u i t e 6 第3 类是混 合模式 即将R D F 模式信息按照一定的分类存到若 干张表中 而实例信息存成三元组 如C O D E 引 S O R t 8 3 等 为了有效地查询R D F 数据 这些系统都有自己 的S P A R Q L 查询引擎 例如J e n a 的s p a r q l 2 s q l E 9 A R CS P A R Q I 2 S Q I R e w r i t e r L 加3 等 它们将S P A R Q L 查询转换为等价的S Q L 查询 然后将S Q L 直接交 给数据库查询优化器处理 但是转换后的S Q I 语句 太过复杂或者不够合理 导致关系数据库的查询优 化器无法找到最优的执行计划 严重影响整个R D F 存储系统的查询效率 虽然一些研究者也提出了一 些查询优化方法 但都是比较简单的或者是针对 S P A R Q L 到S Q L 转换方法的一些优化问题 本文主要针对S P A R Q L 中的基本图模式 b a s i c g r a p hp a t t e r n 的连接查询进行优化 基本图模式是 S P A R Q L 查询的基本单位 定义如下 1 定义1 基本图模式是1 组三元组模式 可以理 解为一个有向图 B G P N E 其中N 是点的集 合 代表主语和宾语 E 是边的集合 代表谓语 每条 边从主语节点指向宾语节点 由变量名或U R I 标 示 每个节点由变量名或U R I 或空节点或字符串来 标示 例1 一个S P A R Q L 基本图模式查询及其等价 的S Q L 查询返回所有院长所在学院 电话信息 邮 件地址和名字 S P A R Q L 基本图模式查询 S E L E C T c o l l e g e t e l e m a i l n a m e W H E R E f s o m e o n er d f t y p e D e a n s o m e o n e h e a d O f c o l l e g e s o m e o n e T e l e p h o n e t e l s o m e o n e E m a i l A d d r e s s e m a i l s o m e o n e N a m e n a m e 等价的S Q L 以三元组存储为例 S e l e c tb O C O d O e o F r o mt r i p l ea t r i p l eb t r i p l eC t r i p l ed t r i p l ee W h e r ea p 一 r d f t y p e a n da o D e a n a n da s b Sa n db P h e a d O f a n da s c sa n dC P 一 T e l e p h o n e a n da s d Sa n dd D E m a i l A d d r e s s a n da s e sa n de p N a m e 本文研究S P A R Q L 查询中两类常见的连接 类型 1 串型连接 c h a i n j o i n 主语和宾语进行 连接 如图1 a 所示 2 星型连接 s t a r j o i n 主语和主语连接 如图1 b 所示 或宾语和宾语连接 如图1 c 所示 a 串型连接 b 主语星型连接 c 宾语星型连接 图1 连接类型 这两种连接都非常耗时 原因是数据库很难获 取详细的统计信息 包括属性相关信息 例如三元组 存储 所有的属性都存于一列 数据库很难获得各个 属性的统计信息 更别说属性连接的选择度了 这样 查询优化器无法选择较优的连接顺序 只能按照用 户输入的连接顺序进行连接 如果先执行中间结果 集大的连接 则效率非常低下 对于属性表和类表这 两种存储方式 各个属性的统计信息相对容易获得 但是属性连接的选择度都是基于属性独立假设的 经常会发生选择度估计偏差很大的情况 导致优化 器很可能选择性能比较差的执行计划 但是如果知 道属性间的相关关系 就有利于查询优化器正确地 估计属性连接的选择度 从而选择效率较高的连接 顺序 图2 图3 对比了不同规模下 不同的连接顺 序对性能的影响 一个是用户输入的连接查询 一个 是经人工调整连接顺序后的查询 对于星型查询优 化效果很明显 效率提高了9 0 以上 最大提高了 9 9 对串型连接的效率也提高了1 5 2 0 图2 星型连接效果对比图 万方数据 吕彬等 基于属性相关性的S P A R Q L 查询优化方法 1 2 1 P l P 2I Ic r 5I Id I 十I 盯 I 其中t 2 S P o 表示任一三元组 kI 指集合盯 包含元素的个数 1 以一 t J lt P P l t J P P 2At s t S 2 c r o 岛 It p P lAt j P P zAt i 0 岛 0 3 c r c t j It p P lAt j P P zAt o 1 0 一4 三元组个数 i s 图3 串型连接效果对比图 1 2属性相关性发现方法 我们可以把R D F s 本体分为两部分 一部分 R D F s 用三元组T 一 s P o 来描述本体 属性 是描述属性之间 类之间以及属性和类之间的相互 相关性发现方法D P C d e t e c t i n gp r o p e r t yc o r r e l a t i o n 关系 称之为模式信息 另一部分则是实例信息 如 a l g o r i t h m 主要是用R D F 本体的模式信息来发 果我们可以利用模式信息快速地获取属性相关信 现属性间的相关性 具体来讲 方法主要发现以下3 息 从而调整连接顺序 就可以加快S P A R Q L 的查 种关系 询效率 本文将讨论如何利用本体模式信息自动获 1 函数依赖 f u n c t i o n a ld e p e n d e n c i e s 属性 P 取属性相关性 并将其运用于S P A R Q I 一连接查询优 和P 满足函数依赖的判定条件 如果三元组T 一 化 运用启发式规则最大程度地发现属性相关关系 P P P 的属性P 为r d f s s u b P r o p e r t y O f 如图 减少处理空间 使属性相关性发现方法具有计算量 4 所示 则P 函数依赖于P 相关关系p F D S I 属性相关性发现及查询优化 1 1 定义 首先引入一些记号 D o r a P C 表示属性P 的 定义域为类C R a n g e P C 表示属性P 的值域为 类C S u b P r o p e r t y f P 1 P 2 表示属性P 1 是属性 P 2 的子属性 S u b C l a s s o f C C 表示类C 是类 C 2 的子类 其中P P P 为属性 C C C 为类 定义2 本文中属性P P 2 的相关关系 c o r r e l a t i o n 有以下3 类 函数依赖 F D S 相关 C o R 独立 I N D 定义3 选择度 s e l e c t i v i e t y 属性P P 的选择度 T 手T b P 1 与P 2 独立 几 反丌订 1 习2 似业 r 南 P 与P 相关 r 瓦11 P z 函数依赖于P 其中 P I P 2 P r o p e r t y IP l1 指属性P l 的d i s t i n c t 值个数 I P P I 指属性P 和P 的联合d i s t i n c t 值 对个数 本文用此定义来计算属性P P 连接时的 选择度估计值 调整查询连接顺序 d o c t o r a l D e g r e z F r o mm a s t e r s D e g r e e F r o mu n d e r g r a d u a t e D e g r e e F r o m 二 r d f s s u b P r o 兹鬣 哪 研 r d I s s u b P r o p e r t y u O l d e g r e e F r o m 图4 父子属性的函数依赖关系 2 相关 c o r r e l a t i o n 当满足以下判定条件之 一时 属性P 和P 相关 p 一 C O R R a n g e P 1 D o r a P 2 如图5 所示 P l p u b l i c a t i o n A u t h o r P 2 a d v i s o r R a n g e P 1 一 D o m P 2 P e r s o n 所以P 1 和P 2 相关 图5 属性相关关系例1 R a n g e P 1 s u p e r C l a s s D o r a P 2 即 s u b C l a s s O f D o r a P 2 R a n g e P 1 如图6 所示 P 1 A d v i s o r P 2 h e a d O f R a n g e P 1 P r o f e s s o r D o r a P 2 一 D e a n s u p e r C l a s s D o r a P 2 P r o f e s s o r 所以P l 和P 2 相关 在方法中 s u p e r C l a s s C 计算的是类C 的所有父类 万方数据 1 2 2计算机研究与发展2 0 0 9 4 6 增刊 图6 属性相关关系例2 R a n g e P 1 一a u b e r C l a s s D o m P 2 即 s u b C l a s s O f R a n g e P 1 D o m P 2 如图7 所示 P 1 A d v i s o r P 2 一 W o r k f o r R a n g e P 1 一 P r o f e s s o r D o m P 2 E m p l o y e e s u b e r C l a s s D o m P 2 P r o f e s s o r 所以P 1 和P 2 相关 在 方法中s u b e r C l a s s C 计算的是类C 的所有子类 图7 属性相关关系例3 其他属性相关性 之前3 种关系可以从本体 的模式信息快速地获取 但有些本体可能没有明确 定义属性的定义域和值域 而是在实例信息中体现 属性间的相关关系 所以需要将这部分补充进来 我 们运用3 个启发式规则简单而有效地减少计算空 间 提高相关性发现的效率 i 去掉所有数据类型属性 i i 去掉lP l 是的属性 点是参数 如果属性 的d i s t i n c t 值很少 与其他属性进行连接对查询性 能影响不会很大 可以忽略以减少相关性计算搜索 空间 i i i 从该本体的所有属性集中除去父子属性 对以及之前发现的3 种相关属性对 这对剩余属性计算两两间的选择度 如果 P l P zl 一0 则 D I N D 如果IP 1 P 2I IP 1l 则l D F D S 如果lP I IP P I IP I IP l 则p C O R 3 独立 i n d e p e n d e n t 本体所有属性之间除了 之前判定为函数依赖和相关的 剩余属性对 P P z 如果IP P zI 0 则认为是独立的 p I N D 1 3 调整查询连接顺序 得到相关关系后 针对查询中涉及的属性重新 调整它们的连接估计值 进行顺序重组 当然这里还 涉及到找到查询顺序最优解的问题 这个我们是用 动态规划算法结合左深树连接策略得到的 具体步 骤如下 1 按照定义3 计算属性对的选择度估计值 2 根据调整后的选择度估计值 用动态规划算 法结合左深树连接策略重新计算最优的连接顺序 3 重写S P A R Q L 转换后的S Q L 2 实验结果分析 我们做了以下实验来验证D P C 方法的可行性 和对查询性能的改进效果 1 在三元组 属性表 类 表3 种存储方案下 对星型连接和串行连接两种连 接类型的性能改进情况 2 比较D P C 方法与数据库 已有方法的执行效率 3 参数k 对发现属性间相关 关系的正确性和执行效率的影响 实验平台为P e n t i u m DC P U2 2 8 G H z 内存 1G B 硬盘1 6 0 G B 使用的数据库为某商业数据库 2 1 查询优化效果分析 目前基于关系数据库的R D F 存储系统大体分 为3 种存储方式 三元组 属性表 类表 所以实验分 别在这3 种存储方式上运用D P C 方法发现的属性 相关性 分析D P C 方法对星型连接和串行连接这两 种连接类型的效率改进情况 其中对于三元组的星 型连接分为主语星型连接和宾语星型连接 而类表 存储模式下同一个实例的属性值存于同一元祖 所 以只分析了宾语星型连接的情况 属性表存储模式 也只分析了主语星型连接的情况 实验使用的是人 造数据集 它有固定的3 2 个属性 并根据参数生成 不同规模的R D F 本体 实验中生成了由小到大3 个 规模的本体 它们的三元组数和实例数分别为 8 2 4 1 5 1 7 1 7 4 5 1 6 1 1 6 1 0 2 3 6 8 1 0 5 2 8 9 5 2 0 7 4 2 6 每个查询均为冷启动执行 分别执行了1 0 遍取平均值 优化前后的执行时间如图8 1 0 所示 实验用D P C 方法获得属性的相关关系 重新计 算连接的选择度估计值 优化前是指按照用户输入 的S P A R Q L 查询中的连接顺序转换成对应的 S Q L 交给数据库中执行的情况 优化后是指 S P A R Q L 转换成S Q L 时根据重新计算后的选择度 估计值改变连接顺序 使数据库按照调整后的顺序 万方数据 吕 彬等 基于属性相关性的S P A R Q L 查询优化方法 1 2 3 执行的情况 从实验结果来看 D P C 方法获得的属 性相关性信息对3 种存储模式下的星型连接和串行 连接效率都有明显的改善 从连接类型来看 主语星 型连接的改进效果最为明显 最少的提高了7 3 4 8 最多的提高了9 7 1 宾语星型连接平均提高了 2 8 9 串型连接平均提高了3 3 8 从存储方式 来看 三元组存储方式的主语星型连接改进效果最 明显 平均提高了9 2 1 8 宾语星型连接和串型连 接大概改进了1 0 2 0 属性表存储的串行连接平 均提高了5 4 7 主语星型连接平均提高了8 1 2 而对于类表存储方式 星型连接改进的效果比串行 连接来的明显 至于中间规模的数据集的改进效果 时高时低 是因为实验数据是随机生成的 如果在这 个数据集上的中间结果集比较大 则选择到好的执 行计划就能大幅减少执行时问 如果中间结果集较 小 则改进的效果不会太好 图8主语星型连接执行时间比较 图9 宾语星型连接执行时间比较 图1 0 串型连接执行时间比较 2 2 属性相关性发现方法执行效率比较 本实验在三元组规模最大的数据集上执行 有 1 0 5 万条三元组 3 2 个属性 比较D P C 方法和基于 熵的属性相关度计算方法C O C A 1 1 1 的执行效率 执 行D P C 方法的时间是2 4 6s 这个时间包括选择度 的计算时间 而C O C A 方法需要对每个属性对计算 相关度 最后所有属性对的相关度计算1 遍的时间 超过了1 天 如表1 所示 一般D P C 方法用于预处 理 所以这个时间是可以接受的 如果本体有新增的 属性 可以增量计算新增属性与已有属性间的关系 万方数据 1 2 4计算机研究与发展2 0 0 9 4 6 增刊 表1 执行时间比较 图1 1 是不同IP l IP I 规模下C O C A 方法和 D P C 方法在执行时间上的比较 由于C O C A 方法需 要计算属性对的每个不同值对 所以它的计算时间 与lP I lP I 的大小相关 其他数据库方面的属性 相关性发现方法也是类似的 都需要考虑属性值的 分布 而D P C 方法不需要考虑属性的值分布 所以计 算时间要远小于它们 可以用于实际系统 易于维护 3 0 g 2 0 要1 0 O 一基于熵的方法j D P C 算法 厂 厂 卜 1 53 06 Z 1 3 0 2 2 5 4 5 0 5 6 0 9 3 01 0 5 0 1 8 6 02 0 8 0 l l l f 2 I 图1 1属性相关度方法执行时间对比 2 3 参数七取值对正确性和执行效率的影响 在计算隐藏在实例信息中的属性相关性时 可 以设置参数k 以减少计算量 如果k 取值太小就对 D P C 计算时间影响不大 起不到想要的效果 如果k 取值太大则会影响正确率 所以我们来分析k 对 D P C 方法正确性和执行效率的影响 期望找到比较 合适的k 值 当然 不同的数据分布最合适的k 取值 也是不同的 实验结果如图1 2 和图1 3 所示 1 0 0 毋 妻 8 0 嘏4 0 靛2 0 蒙 O 3 0 0 芝2 0 0 垦 莒1 0 0 0 相关 一 0O 0 0 0 1 0 0 0 0 50 0 0 1 00 0 0 1 5 0 0 0 2 0 7 图1 2 正确性比较 D P C 算法 7 0 0 0 0 0 10 0 0 0 50 0 0 1 00 0 0 1 50 0 0 2 0 叩 图1 3D P C 方法执行效率比较 其中 绝对误差率A e I 估计值一正确值I 正 确值 7 k m a x 1P I P 是数据集中d i s t i n c t 值最 多的属性 I P I 是P 的d i s t i n c t 值个数 从实验结果 中可以发现随着k 值的不断增大 执行时间变短 错 误率增大 所以 最合适的k 值应该是在应用环境允 许的时间内取绝对误差率最低的k 值 在实际应用 中 可以根据自己对时间的要求取到符合条件的最 小k 值 然后将其应用于属性相关性方法 3相关工作 在S P A R Q L 转换为S Q I 的查询优化方面 也 有考虑选择度来改进查询效率的工作 文献 1 2 3 引 入依赖属性的概念 用概率的方法来计算三元组连 接后的结果集大小 它是在图模型上作连接查询估 计 所以需要考虑整个查询路径的匹配 而且是根据 具体的属性值来作连接估计 这个计算量是比较大 的 另一个问题是它没考虑如父子属性这类语义关 系 而本文的方法是在关系模型上作连接查询估计 充分运用本体的语义关系 考虑到父子关系 不需要 匹配整个查询路径 不需要根据具体属性值来作估 计 计算量很小 而且主要依据的是本体模式信息 可扩展性高 另外 本文的方法是基于关系数据库的 可以处 理海量本体 而文献 1 3 也是解决S P A R Q L 查询 中基本图模式 b a s i cg r a p hp a t t e r n 的优化问题 但 是它也是基于内存的S P A R Q L 查询引擎上的 不 适用于大规模本体的情况 虽然属性相关性发现方面的研究在语义网查询 优化领域的丁作非常少 但在关系数据库领域的研 究还是比较多的 这可以为S P A R Q L 查询优化提供 借鉴 例如文献 1 4 介绍了基于样本的概率的方法 自动发现属性间模糊函数依赖 并利用发现出来的 代数约束将查询改写 以便优化器能找到更有效的 执行路径 文献E 1 5 3 则用卡方检验的方法分析样本 确定相关性和弱函数依赖关系 并为优化器推荐列 集合以维护多维直方图统计值 由于文献 1 5 3 为了 克服卡方检验的局限性用了一些有损耗的方法 所 以文献 1 1 提出了基于熵的相关因子 可以提高属 性相关性的准确度 并能给出相关系数 还针对不同 类型的相关性设计了多维直方图方案 与之相比 D P C 方法由于应用于本体存储系 统 而本体本身就富含语义信息 这就可以利用更多 的语义关系来快速地发现属性间的相关关系 之前 介绍的数据库方面的计算属性相关性发现方法是非 常耗时的 即使利用采样技术也没有D P C 方法效率 万方数据 吕彬等 基于属性相关性的S P A R Q I 查询优化方法 1 2 5 高 其次 文献 1 4 1 5 只能发现定义了主外键关系 的属性对之间相关性 且需要对数据类型进行约束 而D P C 方法无此限制 这样可以发现更多相关的属 性对 而且无需对数据类型进行约束 另外 文献 1 5 只能运用于整个数据库 无法获得单个属性 对是否相关 而D P C 方法既可以运用于整个本体库 的属性相关性发现 也可以运用于单个属性对 非常 灵活 4 结语 本文利用本体本身固有的语义信息计算属性间 的相关关系 并利用该信息优化S P A R Q L 查询中基 本图模式的连接顺序 解决关系数据库查询优化器 因为属性独立假设而选择效率低的执行计划的问 题 从而加快在此基础上的S P A R Q L 基本图模式的 查询效率 本文的属性相关性发现方法D P C 利用本 体模式信息和启发式规则最大程度地发现属性相关 关系 减少处理空间 并运用动态规划算法结合左深 树策略得到调整后的连接顺序 而且 实验也证明此 方法运用于各类存储模式均有比较好的效果 所以 具有计算量小 可扩展性高 通用性强的优点 下一 步计划将此方法推广到含O P T I O N 和U N I O N 的 S P A R Q L 复杂模式查询中 提高S P A R Q L 查询的 整体效率 参考文献 1 P r u d h o m m e a u xE S e a b o r n eA S P A R Q Lq u e r yl a n g u a g ef o r R D F W 3 C W D 2 0 0 8 2 0 0 8 0 1 1 5 h t t p w w w w 3 o r g T R r d f s p a r q l q u e r y f 2 W i l k i n s o nK S a y e r sC K u n oH e ta 1 E f f i c i e n tR D F s t o r a g ea n dr e t r i e v a li nJ e n a 2 P r o eo fS W D B 0 3 S a n F r a n c i s c o M o r g a nK a u f m a n n 2 0 0 3 1 3 1 1 5 0 3 3B r o e k s t r aJ K a m p m a nA H a r m e l e nF S e s a m e Ag e n e r i c a r c h i t e c t u r ef o rs t o r i n ga n dq u e r y i n gR D Fa n dR D Fs c h e m a L N C S2 3 2 4 P r o co ft h e1s tI n tS a m a n t i cW e bC o n f B e r l i n S p r i n g e r 2 0 0 2 4 H a r r i sS S h a d b o l tN S P A R Q Lq u e r yp r o c e s s i n gw i t h c o n v e n t i o n a lr e l a t i o n a ld a t a b a s es y s t e m s L N C S3 8 0 7 P r o e o ft h eI n tW o r k s h o po nS e a l a b l eS e m a n t i cW e bK n o w l e d g e B a s eS y s t e m s S S W S N e wY o r k S p r i n g e r 2 0 0 5 5 P a nZ h e n g x i a n g H e f l i nJ D L D B E x t e n d i n gr e l a t i o n a l d a t a b a s e st os u p p o r ts e m a n t i cW e bq u e r i e s 2 0 0 8 0 4 一l o h t t p w w w e e c s 1 e h i g h c d u h e f l i n p u b s p s s s 0 3 一p o s t e r p d f 6 A l e x a k iS C h r i s t o p h i d e sV K a r v o u n a r a k i s G e ta 1 O n s t o r i n gv o l u m i n o u sR D Fd e s c r i p t i o n s T h ec a s eo fW e b p o r t a lc a t a l o g s P r o co ft h eI n tW o r k s h o po nt h eW e ba n d D a t a b a s e s N e wY o r k A C M 2 0 0 1 7 李曼 本体库管理系统研究 北京 中国人民大学 2 0 0 6 8 L uJ i n g M aL i Z h a n gL e i e ta 1 S O R Ap r a c t i c a ls y s t e m f o rO W Lo n t o l o g ys t o r a g e r e a s o n i n ga n ds e a r c h 2 0 0 8 0 4 1 0 h t t p w w w v l d b o r g e o n f 2 0 0 7 p a p e r s d e m o p 1 4 0 2 一 l u p d f 9 s p a r q l 2 s q laq u e r ye n g i n ef o rS P A R Q I o v e rJ e n at r i p l e s t o r e s 2 0 0 7 1 1 1 0 h t t p I l j e n a s o u r c e f o r g e n e t s p a r q l 2 2 1 1 0 A R CS P A R Q L 2 S Q LR e w r i t e r 2 0 0 7 一1 1 一I O h t t p w w w a p p m o s p h e r e c o m p a g e s e n a r cs p a r q l 2 s q lr e w r i t e r 11 3 C a oW e i Q i nX i o n g p a i S h a nW a n g a A M o r es c u r a t e m u l t i d i m e n s i o n a lh i s t o g r a m so u to fm o r es c u r a t ec o r r e l a t i o n s d e t e c t i o n z o o s 一0 4 一i o h t t p i e e e x p l o r e i e e e o r g x p l f r e e a b s a 1 1 j s p a r n u m b e r 4 5 9 7 0 4 4 1 2 P a t r i c kS h i r o n o s h i t aE M i c h a e lTR y a n M a n s u rRK a b u k a C a r d i n a l i t ye s t i m a t i o nf o rt h eo p t i m i z a t i o no fq u e r i e so n o n t o l o g i e s S I G M O DR e c o r d 2 0 0 7 3 6 2 1 3 1 8 1 3 M a r k u sS t o e k e r A n d yS e a b o r n e A b r a h a mB e r n s t e i n e ta 1 S P A R Q Lb a s i cg r a p hp a t t e r no p t i m i z a t i o nu s i n gs e l e c t i v i t y e s t i m a t i o n T h e17 t hI n tW o r l dW i d eW e bC o n f N e wY o r k A C M 2 0 0 8 1 4 B r o w nPG H a a sPJ B H U N T A u t o m a t i cd i s c o v e r yo f f u z z ya l g e b r a i cc o n s t r a i n t si nr e l a t i o n a ld a t a P r o co ft h e 2 9 t hV I D BC o n f S a nF r a n c i s c o M o r g a nK a u f m a n n 2 0 0 3 6 6 8 6 7 9 1 5 3l l y a sIF M a r k lV e ta l C O R D S A u t o m a t i cd i s c o v e r yo f c o r r e l a t i o n sa n ds o f tf u n c t i o n a ld e p e n d e n c i e s P r o co fS M S l G M O D2 0 0 4 N e wY o r k A C M 2 0 0 4 6 4 7 6 5 8 吕彬女 1 9 8 1 年生 硕士研究生 主要研究方向为 语义W e b 高性能数据库 杜小勇男 1 9 6 3 年生 教授 博士生导师 主要研究方 向为智能信息检索 高性能数据库 知识工程 王琰男 1 9 7 7 年生 博士研究生 主要研究方向为 语义W e b 高性能数据库 万方数据 基于属性相关性的SPARQL查询优化方法基于属性相关性的SPARQL查询优化方法 作者 吕彬 杜小勇 王琰 L Bin Du Xiaoyong Wang Yan 作者单位 刊名 计算机研究与发展 英文刊名 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT 年 卷 期 2009 46 z2 被引用次数 0次 参考文献 15条 参考文献 15条 1 Prudhommeaux E Seaborne A SPARQL query language for RDF W3CWD 2008 2 Wilkinson K Sayers C Kuno H Efficient RDF storage and retrieval in Jena2 2003 3 Broekstra J Kampman A Harmelen F Sesame A generic architecture for storing and querying RDF and RDF schema 2002 4 Harris S Shadbolt N SPARQL query processing with conventional relational database systems 2005 5 Pan Zhengxiang Heflin J DLDB Extending relational databases to support semantic Web queries 2008 6 Alexaki S Christophides V Karvounarakis G On storing voluminous RDF descriptions The case of Web portal catalogs 2001 7 李曼 本体库管理系统研究 2006 8 Lu Jing Ma Li Zhang Lei SOR A practical system for OWL ontology storage reasoning and search 2008 9 sparql2sql a query engine for SPARQL over Jena triple stores 2007 10 ARC SPARQL2SQL Rewriter 2007 11 Cao Wei Qin Xiongpai Shan Wang COCA More scurate multidimensional histograms out of more scurate correlations detection 2008 12 Patrick Shironoshita E Michael T Ryan Mansur R Kabuka Cardinality estimation for the optimization of queries on ontologies 2007 2 13 Markus Stocker Andy Seaborne Abraham Bernstein SPARQL basic graph pattern optimization using selectivity estimation 2008 14 Brown P G Haas P J BHUNT Automatic discovery of fuzzy algebraic constraints in relational data 2003 15 llyas I F Markl V CORDS Automatic discovery of correlations and soft functional dependencies 2004 相似文献 10条 相似文献 10条 1 期刊论文 张宗仁 杨天奇 ZHANG Zong ren YANG Tian qi 基于自然语言理解的SPARQL本体查询 计算机应用 2010 30 12 为了用户能够方便地获取本体知识 提出了基于自然语言理解的SPARQL本体查询 利用Stanford Parser分析用户的自然语言查询 根据语法构建查询 三元组 与关键词的方法相比 有效地减少了组合的个数 结合用户词典 能较准确地把查询三元组的词汇映射到本体实体 分值计算时除了考虑词语的形式 相似和语义相似外 还考虑了概念的模糊性 尽量返回具体的概念 利用本体推理获取隐藏在本体中的信息 对查询进行过滤和限制 提高了准确率 用户通 过图形交互界面和系统进行交互 选择需要的结果 最后返回树形查询结果 并能看到相关的信息 实验结果表明 该方法达到了预期的效果 2 学位论文 许德山 本体驱动的中文语义检索系统的设计与实现 2008 传统的信息组织方式以人类用户的阅读习惯进行设计 使得检索结果不能够精确定位到用户的需求 因此语义网 SemanticWeb 和本体 ontology 技 术逐渐发展起来 成为当前信息检索领域研究的热点 语义网用一种机器容易处理的方式组织信息 它具备更好的灵活性 集成性 自动性和自适应性 尤其是本体技术的应用 使语义网更加智能化 在知识组织和服务中本体技术也得到了广泛的应用 围绕着语义网的建设和应用 出现了各种工具和 实验性应用项目 与此同时国际语义网联盟 W3C 也推出了面向语义检索的标准查询语言SPARQL 用来完成对本体的各种检索 但SPARQL不是自然语言 需要了解本体知识库的组织方式并学会用SPARQL的语法来表达自己的查询意图 这种方式为普通用户带来了不便 为此笔者提出了一种较为理想的方 式是 用户只需用自然语言来表达自己的查询意图 系统自动完成问题到SPARQL的转换和概念推理并执行相应的查询 返回查询结果 本文首先分析了传统信息检索手段的不足 简要地介绍了语义检索的实现的背景 结合知识组织介绍了本体的概念 分析了本体的优势及SPARQL检 索本体的方式 接下来 对问题进行分析和归类 提出一种中文自然语言问句到SPARQL语言的转化方案 随后 讨论了本体推