hexstore：语义网数据管理六元索引

1、hexastore：语义网数据管理中的六元组索引cathrin weiss panagiotis karras abraham bernsteun摘要尽管人们对于实现语义网z梦v分热衷，大多数 已存在的rdf数据管理模式都在效率及规模上存在看制 约。另外，rdf格式的日益流行也使得克服这些缺陷变得 尤为迫切。从关系数据库的角度看來，这些制约都是因为 rdf数据模型的本性一基于三元组格式。近來的研究已尝 试通过为每个属性构造两个独立列表的垂直划分方法来 减小其制约性。然而，此类方法在未绑定rdf属性值的 査询值上仍存在规模的制约。木文中我们提出一种将三元 组作为一种优势的存储模式。这种模式强化了

2、垂直划分思 想并将其作为一种逻辑上的结论。rdf数据以六种可能方 式被索引，每种对应一种三元组三个元素的顺序。毎个 rdf元素实例都和两个向量相关联：毎个向量的元素是山 其他类型小的一个构成，同时还包含附于每个向量元素的 第三种类型资源的农单。因而产生了 sexmple模式。这种 格式允许快速和规模化的查询处理，相比z前的rdf数 据管理方法尤其重要优势（高达五个数量），代价就是在 索引所占空间的最坏悄形的五倍。我们通过现实世界和合 成数据的实际査询证实了该方法的优势。1.导论语义网的前呆是希架让每个人能像发布网页那样方 便的发布互联的机器可处理的信息。其基础是称为资源 描述框架的标准逻辑数据

3、模型。rdf数据是状态的集 合，称为三元组，形式为<s,p,o>, s表示标题，p是断言, o代指对象；每个三元组描述了 s与o z间的联系。一 个三元组集合可以表示为直接典型的图，图中节点代表 s, o,边代表断言，连接起s, oo网络上i i益增加的rdf数据要求开发出高效的系统 并对这些数据做冇效管理。因而在rdf数据的存储和查 询方面人们已作岀很多颇见成效的努力。然而，大多数现存三元组存储方法耍么是有着规模 受限的缺陷要么存在对于特殊类熨査询要求特殊的结构 这样的缺陷。传统方法要么限制在基于内存的存储，要 么映射基于三元组的格式到一个关系数据库，于是他们 没能关注基于图的三

4、元组存储，检索，更新的优化。尤其因为rdf三元组历来存储在一个大的三元组 表屮，这带來了 了严重的规模问题。一些其他方法试图 通过类关系表來缓解这些问题，这些类关系表将许多三 元组特性集合作为其属性。然而，此类方法还是不能克 服规模化弊端。最近为解决这一问题的努力是关注于克 服规模问题，产生了乖直划分法出现。在该方法中一个 三元组农（一个三列的关系农，每列代衣-种资源）被 写到n个两列表格中，其中n是数据中独立特性的数h。 在特性表现如同已绑定的变量的查询情形下，该方法有 明显优势。然而，垂直划分法是严格特性导向的。另外，特性绑定的査询在rdf数据检索表达中并非 一定使用。因而在未绑定特性查询

5、情形下，方法是对一 般化杳询找到局部锻优。这样该模型的特性导向将不再 适用。在本文屮，我们捉出高效的存储模式应该既能满足 数据管理上的规模要求又要在存储，处理及表达方面做 到一般化。未达到这两个目标，我们提出rdf数据管理 新方法。我们的工作框架是基于rdf多索引框架思想。 毎个rdf数据元素（例如subject）有两个向量相关联, 这两个向量与另外两个元素分别对应。另外，第三个 rdf元素的列表也附加在两个向量中。总共冇六种联系 來索引rdf数据，包括了 rdf数据三元素所冇可能排 列顺序。事实上，我们的方法釆用了垂直划分理念和多 索引系统，并进一步得出其逻辑结论。这种模式既允许 基于特性的

6、两列表，也支持基于rdf资源和特性重要性 顺序的表示。本文提纲第二章介绍了 rdf存储相关工作，讨论了z前一些方 法的弊端。第三章概括了研究目的。第四章介绍了我们的语义网数据管理方法，hexstore。第五章介绍实验结果第六章讨论了结果并提出未來研究方向第七章对结论做了概插。2.背景及相关工作木章我们对rdf现存数据管理方法进行概述。21传统方法人们提出了很多存储和查询海虽：rdf元数据的构 架方案。然而诸如 forth rdf suite , redland ,sesame ,3store jena .dldb ,kaon ,rstar, oracle及rdfdb的系统采用传统关系型数据库b

7、erkeley db作为其基本的永久数据存储。在这些系统中，rdf数据被分解成大疑单一的状态, 以直接存储到关系或哈希表中。这些系统对简单的基于状 态的查询能够得到较理想的结果。但是这种基于状态缺少 了三元组的一部分或是两个部分，其结果是完善了缺失部 分的-组资源，而且也不能代表查询rdf数据最重要的 方式。一些更复杂的査询，比如包含很多过滤步骤的，相 比來讲更重要些。但是传统方法对此无法胜任。另外,jena系统尝试在从rdf数据创建出类关系的特 性农，这些表将一列主题上的诸多特性倍息搜集到一起， 但是这种模式在那些无法从一张表中得出结果需要多张 表联合的悄形上表现不佳，进一步來说，就是这些表

8、把类 关系结构强加于半结构化的rdf数据z上。这些并非自 然存在的强加结构导致了衣屮许多null值的稀疏农达。 处理这样的稀疏表，不同于一般较稠密的表，需要较高的 计算代价。目前的研究集中在构建规模化的rdf元数据 发布系统以及在其上的连续査询。2.2.非传统的rdf数据存储模式其他一些论文小提出了不同于传统的rdf数据存储 模式。2.2.1以图方式存储rdf数据一些人致力于研究以图来农示rdf数据的可能性。然 而这些研究的最终结论并为充分考虑规模问题。其屮一项 研究就是提出了基于路径的rdf数据存储，然而这种基 于路径方法最终还是在关系数据库棊础z上：它是将子图 存储在不同关系农中的。因而此

9、类系统无法提供海虽:rdf 数据查询的规模需要。另外一些研究则关注于衡量语义网 内部的相似性并使用冇选择性的佔计方法來优化rdf数 据查询；这些方法基于内存的图实现，仍存在着规模上的 限制。2.2.2多索引方案harth与dexker提出基多索引存储rdf数据，该方 法要考虑数据上下文。在s,p,o,c)形式的小块的十六种可 访问模式上，建立六种索引将z覆盖，其中c代表上下文。 这-模式允许对小块做快速检索，适用于s,poc任意为变 量或是貝体值的情形。因此，此法也是定位于简单某于状 态查询，不适用于更复杂查询的高效处理。wood在kowari系统屮提出另一种类似方案。kowari 也是以四方

10、块存储数据，前三块存储的是三元组，第四个 是元数据，用來描述状态出现在哪个模型。kowari也区分 四种节点可组织的六种排序，这样一到四个节点的任意集 合可被用来找出与之匹配的状态或状态组。这样-来，每 个序列都表现为一个复合索引，都包含了 rdf的所有状 态。kowari使用avl树存储及排列这些索引的元素。然而其仍打算使用简单状态查询，其所考虑的六种序 列遵循同一周期序列，没右考虑四个小块的十六种可能排 列，也没考虑到三元组中三元素的六种排序。因而若忽略 元节点，所需索引数目将减小到3,由以下三个循环序列 (spo)(pos)osp)o这些索引不足以提供给定特性的有序主 题列表。因而kow

11、ari也不适用于更复杂查询的高效处理。 然而在我们看來,这种多索引方法是个值得进一步深入研 究的思路。在第四章介绍我们的方法时我们还会对其进行 探讨。2.2.3垂直划分方案abadi ®近提出了垂直划分方案，提岀将三元组重写 到n个两列表中，每个表记录一个特性，n即为rdf中 特性个数。每个表包含了上题和对象列。多值的标题(标 题通过同一特性与多个对彖札【关).通过农屮同标题不同 对彖的多行来表现。每个表都是按主题排序的，这样可以 快速定位，并可以川快速合并连接来重建主体子集的特性 信息。该法伴随列向的dbms (即专为垂直划分实例设计 的dbms,较z行向的在压缩性和表现上冇其优势

12、)。接 下來他讨论了将特性作为绑定变量的优势，认为在规模语 义网数据管理方而达到了人师级。abadi还指出，表中的对象列也可以做选择性索引, 或是在该列上做一份聚集拷贝。以此也提岀了可在数据管 理上的一种多索引。但是这种多索引限制于特性导向的架 构上。另外，论文系统屮也耒将这一提议实现为基准的一 部分。事实上，该垂直划分模型意图完成特性未绑定的杳 询，否则搜索就限制于儿个特性上。尽管abadi等人不赞 成特性表的方案，他们的基于特性的二列表方法却存在特 性表的多数缺陷。二列表无非是特性表的特殊变形。二列 衣与多指属性衣很柑近，也就是说，后者也是存储了主题 和对彖。这样看來，其绘人创新z处在于将

13、二列表整合到 列向dbms中。另外，wilkinson也注意到了特性表在碰 到未知特性査询时的不足。以此，不论是一般的特性表还 是特殊的列向的特性表都在存在来知特性或是特性须在 运行绑定的情形下都表现不佳。abadi确实注意到特性未绑定的情形，然而却没能有 效解决该问题。其他方案诸如未严格限制特性值或是在执 行时才绑定特性的缺点也都在abadi等的研究中有所体 现：所冇的二列表都将被資询到，并且结果会冇复杂的联 合语句或是连接。于是对于不确定特性值的查询都会对该 rdf架构带來问题。在研究中典型地皋于如下假设：在所研究的图卩馆目 录集的221个独立特性中的28个构成的集合是感兴趣的 地方；没冇

14、特性绑定的查询只能在这个被限制集上。不幸 的是，这种假设在现实世界中很难实现。因而我们需要不依赖对数据的特性数目或所执行得査询本性(特性绑定 的)作出假设的规模化的语义网数据管理。作为一个实例，图一中的原始数据表展示了 lubm 式的三元组实例，该三元组表存储了一个四人小组的学术 信息。值得注織的是，并非所有屈性都对应表中所有主题。 一种可能的有趣的査询是询问如杲有人与mit有关，这 种关系是什么；另一个冇意思、的査询则是寻找这样一些 人，他们与斯坦福间的关系与某人和耶鲁的z间关系相 同。更进一步，还可以查询人们相关的一所大学所涉及的 其他学校，或是查询从某所大学获取的任懣类型的学位那 些人，

15、或是与两所大学都相关的人，等等。所有这些查询 都菲特性绑定的；而是需要从多个特性屮搜集信息。此外, 还冇一些需要在涉及到儿种特性的同某一对彖相关的主 题列表上做复杂连接。这样的杳询既不是來自于主题，也 不是特性，而是对象(比如某个大学)。3动机事实上，属性值上的绑定的査询并非最受关注的，也 不是现实语义网应用小的常见查询。多数情形下，具体属 性往往是查询语句中的未知部分。我们可以不指定而是去 查询资源间的关系(比如随社会网络兴起产生的应丿u)。正如所见，己存的rdf数据存储的设计并未将这类 查询考虑在内。而是围绕如何将具冇相同属性或是相同主 题的三元组聚集在一起。另一些给出了对于不同属性的对

16、彖-主题哈希关键字。就是没有一种能做到根据对象找出 其一列相关主题或属性。我们认为这一功能不仅仅是必耍 的，而且山于rdf数据的三元组特性，它也是能够实现 的。也就是说，一个六(3!)索引集将覆盖rdf査询所 需的所冇访问模式。尽管这样的多索引会导致普通关系表 的组合性增长，在rdf数据中确实实际可行的。下一章 我们将定义hexstore,实现这-想法。4. hexstore：六元组语义网数据索引本章屮将讨论一种方法，该法不对特性这一属性特姝 化，而是将rdf各元素同等对待。4.1.关于hexstore的描述为克服前面说提及到的困难，我们将垂直划分法作 进一步硏究，得出其整个逻辑结论。结论未将

17、任何rdf 数据元素区别对待。这样每个元素都術在其上构建其专门 的索引结构。进一步地，三个元素在一个索引模式中的每 种可能的优先顺序都要加以实现。结果懣味着一种六元索 引模式ohexstore中的每个索引都用绕于一个rdf元素并 定义了在另外两元素上的优先顺序。这样，相当于二列特 性衣的hexstore可以通过卞题索引，允许每个主题对应多 个对象条目，反之亦然。这样特性p关联于主题向最s(p) 及对象向量0 (p)；在前者中，关联对象os (p)的列表 附于向量屮的各主题条目z后，后者中，关联主题so(p) 附于向虽中的各对象条hz厉。此外，hexsiore不把三个三元组屈性任懣优先顺序 看作

18、是理所应当的。rdf三元组并为假设存在一个有特性 构建的宇审。因而，hcxstorc不仅创建了特性主导的划分， 也创建了主题及对彖主导的划分。在前者中，一个给定的 主题条n s关联于一个特性向量和一个向量。一列关联 对象op (s)附于特性向量条目之后，相似地，一列关联 特性p。(s)附于对象向量之后。有趣的是，对于给定的 主题与属性sx与py,在这一主题主导的索引中的对象 列农opy (sx)不同于特性主导索引中的对彖列衣osx (py),因而在索引架构中只需要该列别表的单拷贝。对 于对象主导的划分也有致的结论。总而言之，数据屮毎个三元组<s,p,o>的信息都可山 六种方式表达，

19、每一种代表了三元素的一种可能的优先顺 序。我们一个顺序中三元素的首字母來命名这六种排序。 那么，spo就代表如f含义：该索引是s主导的划分，带 有p向量组并且毎个向量都带有一列o。我们采用字典编码的方法。我们使用简化后的字串 或是关键字而菲整个字串或uri來进行存储。我们将字串 映射为幣数标识。这样一來，除去六个索引里对于rdf 元素使用标识，hexsiore也存储包含了一个将关键字映射 剑相关串的映射表。这些映射组成了字串的字典编码。对于上述讨论，六个索引中有三对有着同样的末端 列表。spo与pso就冇着同样的对彖列。事实上留个索 引较z三元纟(i衣所占空间的最坏悄形并非变为其六倍，而 是五

20、倍。这是因为三元组中的每个资源都出现在两个头组 和两个向量组中，但只出现在一个后续列表里。比如s出 现在spo和sop的头，出现于pso, osp的向量,但对 于ops和pos,两者共用同一个s列表。在最坏情形中， 假设存在三元m<si,pj,ok>, si,pj,ok中的每个在给定数据 集终止出现i次，然而在hexstore索引中每个资源的关键 字都要有五个新条目。因而最坏情形是原来五倍。在实际 应用屮，由于大多数rdf资源并非只出现一次，因此还 有可能将此代价减小。4.2.论证hexstore较z较早的rdf数据管理主要优势概括如 下：对多值资源简明而有效的处理在rdf的关系化

21、翻译中表现为多值属性的任何资源 都是为hcxstorc所能接受的。即出现在hcxstorc索引末端 条目中的列衣可以包含多值的条目，该方法比使用二列多只特性表的方法更加简明。若一个主题经山同一特性与多 个对象相关，则特性的的各个值都列在表的后续行中。这 种类型的特性衣叫多值特性衣，用來存储特性最人成员数 多于i或未知。对于同一主题用多行并非绘简明的办法。 hexstore用了最简明方案，注懣到了对于任何基于关系的 体系要包含多值资源是困难的，因而提出了基于运行长度 编码的方案。考虑语义网数据的的半结构化特性，专为多 值情形设计的方法是必要的。hexstore提供了这样一种方 法。空值的避免只冇

22、与特定的其他元索相关的那些rdf元素需要存 储在特定的索引中。比如，并非为特定对彖oi所定义的 特性无需出现在01的索引ops中。这样对于rdf数据翻 译到关系时就不会有空值的空间浪费。hexstore也充分的 考虑到这点。无需特别选择比如判定那些特性一起存储在同一表中，在关系模式 中哪条路径衣达式需要衣示出來。hexstore回避了这种特 殊判定。hexstore的体系结构是独有的茄汁取决丁手边的 rdf数据，没有必耍做会影响其表现特别判定。降低的i/o代价根据査询中的绑定元素,可制定出一个通常高效的计 算策略；该策略只访问与查询冇关的内容。其它存储方案 则会去访问许多跟查询无关的农；比如，

23、基丁特性的方法 在进行未确定特性的查询时将访问所有的特性农；另外， 进行对象绑定的查询对多数目询已存存储也存在若问题。 由于hcxstorc的六索引，消除了不必要的数据访问。所有第一步的成对连接都是快速合并连接hexstore使用的所有向量和列农中的资源的关键字都 是有序的。这样实现了与一个或-对资源相关的所有资源 的排序。因而在查询处理第一步中的成对连接都是一种快 速线性时间的介并。其他方案则要付出大量计算代价。 减少联合与连接为了获取在两个指定对彖上存在任何相同特性的主 题列表，传统方法将需要多个联合和连接操作（比如查询 参与两个学校项目的人员）。比如，受限的多索引法不能 提供对结果的快速

24、访问，而是需要分别访问为两个对象定 义的所冇状态并对标题列衣结果做交叉连接。相似地，特 性导向方案需要访4所冇特性來区别匹配两个对彖的 subject,object对的实例，联合各对彖的结果，并连接。 hexstore则直接以线性合并连接osp索引中的两个主题 向疑來直接提供出结果。在其它査询处理惜形下也会这样 简单。hexstore的主要缺陷在于存储空间的利用上；尽管 已经捉到的简洁的优点，相较于三元组表其也仍有最坏多 达五倍的空间的增加。初看起來这五倍看起來是兀余的。 然而，我们认为用其换取查询处理时间上的高效是值得 的。此外，所增加存储量至多只有五倍。不会取决于任意 参数，例如资源的出度

25、或是在体系上的特殊选择。这样， 数据引藥可以指果hexstore的可预测的存储盂求。进一步來说，我们认为rdf数据的五倍规模的表达 冇着更为重耍的理由；即首先这说明了 rdf是一种数据 模型。特别是颠覆了从关系数据库管理系统的观点反対 rdf的论点。即通常认为rdf有着内在的欠缺，限制了 自身作为一种数据模型。然而，将rdf翻译成六元映射 使得其具备了关系数据库所没冇的性能上的提升。即在 rdbms屮查询过程屮执行的很多连接都不是合并连接。 这产牛较高的了性能代价。然而，在hexstore中通过使用 符合的索引，所有第-步的成对连接都是合并连接。这样 hexstore不仅允许半结构化数据高效稱

26、简的表达，避免了 任何关系导向方案都存在的稀疏化或空值问题，而且在某 些情形下能做到比rdbms更高效。此外，讲关系型数据库转换为许多类似rdf六索引 的表示会带来存储的激增。即一个n屈性表需耍n!的转 换数据。这样，我们的六索引在rdf数据模熨三元组特 性乙上创造了的优势；三元组特性常被认为是rdf的不 足。模型的负成了其特色。最坏五倍的代价在我们看來 是值得为其性能买单的。另外，这种需求也在存储技术的 容量增加幅度之内。hexstore在处理更新和插入时会存在些问题；这些 操作会影响六个索引，因为降低了速度。然而，现存的 rdf应用不涉及人量数据更新。4.3 讨论路径表达式问题abadi已

27、注意到查询路径表达式，作为rdf中的常见 操作，可能是代价较大且低效的。这种低效是因为路径农 达式査询需要主题一对象连接，因为每个路径屮心节点n 都在n,p,o中作为主题，又在另一三元纠.vs,p：n中作为 对彖。在乖玄划分方案里，特性的二列衣涉及到了謂要连 接的路径表达式。这些连接发牛在一个二列表的主题列和 另一个的对象列。然而这种实现里特性表只按主题排序。 这表明还可以有按值列排序的另一个拷贝表，却并为这样 实现。于是，s0连接不是合并连接，因而代价较高。一种解决办法是将选择出的路径衣达式存储在不同 的关系表中。这种方法是基于某些路径是提前选择好这样 的假设之上的，没有-般化的解决问题。a

28、badi则提岀使 用他们的二列特性表，将选择的路径表达的结果当做附加 的常规特性。这样对于那些以实现的路径表达式就避免了 连接，但此法也存在不具-般化的缺点。实现所冇路径衣达式并不是可行的方案。在一个n长度的路径上，将有 (n-1) (n-2) /2=o(n2)»j能的待计算的附加特性。从图论的观点看，计算所冇路径可能是传递闭包的 一个实例，此问题上做了很多研究，却鲜冇能在人规模数 据管理上的可用的规模算法。hexsiore对这个问题也做了 有效地解决，不用提前计算和具体化选择路径表达式。宙 于它包含的pso和pos的索引，长为n的路径的第一次 的n1个连接实线性的介并连接，余下的n

29、2是排序介并 连接，即需要对每个进行排序。这样路径衣达式查询过程 序的数冃大大减少。5. 试验评价在我们的实验研究小，我们将我们的hcxstorc方法 同列向垂直划分法(covp)在性能上作比较。我们通过 我们的pso索引来表示covp方法,该方法和比纯垂直划 分方案有了提高，也就是pso索引将经由唯一特性与同一 主题相关的多个对象集合放到小组屮。然而，在纯垂直划 分中则是对特性p的二列特性表中的每个对象都冇一个 独立的主题条目vsqp,另外我们采用了二建议创建了按 对彖排序的拷贝特性表。事实上，这个建议在工并未被采 川，只是在对象列上使用postgre实现的垂直划分体系创 建了非聚集的b*索

30、引，然而当同样的垂直划分体系实现在 为工提供最好性能的列向dbms时，这样的树状索引不 会被创建。此外，工也未对对象列进行排序。创建按对彖 排序的拷贝特性表的建议就相当丁我们的同时具有的pso 和pos索引，为了让结论更加完整，我们也在这种两个索 引的特性导向存储上进行了实验。为了区分，把单索引的 特:性导向心储称为covp1,两个索引的叫covp2,后者 衣明了较z单索引使用第二个索引的两人优势，也存在着 较z hexstore方法的限制z处。此外，正如我们在2.2.3中讨论那样，二是基于假设: 所研究的图书目录集221条现存特性中只有一个大小为 28的预选集是研究所需的。七个査询中冇三个为

31、绑定特性 值。特性导向体系应该在此类查询上显露缺陷。同样地， 工中四个杳询只在提前选择好的28个特性集合当中进行。 我们的实验中演示了有无假设两种情形下的结果。为区分 起见，在限制于预选集的方法前加上后缀28,于是， covp2 28就是限制在28个特性上的二索引，covp2就 是无限制的。系统配置为amd速龙双核2.8g处理器， 16g主存，linux操作系统。使用python2.5來实现我们的 索引模式原型，在主存中存储索引和进行查询。5.1.数据描述性能评佔时我们使用了两组公开数据集。第一组是真 实数据，第二组是人工数据。5.1.1 barton 数据集我们的第一个数据集，也是二所使用的

32、，収自公共 mit barton图书馆数据集，冇mit的simile项目所提供， 该项11力图在数字资源，模式，词农，方法论，元数据及 服务等方面的交互能力的提升。该数据包含了一堆m1t barton图书馆的目录的记录。这些记录是从1口的图书馆格 式标准marc (机读目录)转换到rdf的。由于数据來 源的多样性，以及目录本身的多样特性，数据结构是非常 不规则的。和5样，我们将barton的原來的rdf/xm1 转换为三元组并且去掉重复项。在数据清洗之后，总共余 下61233949个三元组，有285个独立特性。大多数特性 是不常见的。总z, barton集是rdf半结构化本质的很 好的实例。5

33、.1.2 lumb数据集lumb是一个用于综合性研究的人工基准。使用 在学术资源用到的信息建模。其生成在23中有介绍。我 们创建了一个有十八个不同特性的十所窩校的数据集，得 到了 6865225个三元组。5.2.查询描述我们的实验在barton数据集上进行了七个杳询， 在lumb上完成了五个。我们高水准的描述这些查询并 给出covp 1,covp2,hexstore的各种实现细节。5.2.1 barton 査询在我们使用barton数据集的实验屮，目的是评估 多索引方案较z单索引二列模式(fflcovpl來表示)的 优势。同时也关注增加了第二个基于特性的索引到covp1 中的covp2方案，也

34、关注hexstore的表现。为了进行公 证的比较，我们使用了与【5】相同的数据集，相应地， 我们采用了 6屮的描述。这些查询都是基于典型的使 用rdf数据探测的longwell浏览器得浏览对话。因而是 真实世界查询的农现。我们将在下面描述这些查询的以图 以及实现细节。query 1 (bq1)该查询耍计算出rdf数据上各个type的数目。这涉 及到type这一特性的所有三元组以及每个对象值的数h。 hexstore和covp2只需要报告出type的关对象的pos 索引的主题的数目，然而covp1不具备这样的索引，所 以在对彖上用pso索引需要做自连接集合。querv2 (bq2)该查询耍列出为

35、资源type： texl界定的特性，以及该 资源的毎个特性的出现频率。使用covp1处理时需要从 type的pso索引中选出所有带有对象值text的subject, 这些subject在临时表t排序，然后与每个特性的subject向量做连接。在连接时，在对象集上会计数，以此來计算 每个特性在t的subject中的频率ac0vp2屮操作也类似, 不过由于pos索引的存在,type：text选择是直接得到的。 hexstore包含了该优势，并在第二步中也有优势。即， hexstore只需在spo索引上合并(里的subject的排好序的 特性向量并合计出频率。query3 (bq3)与bq2相同,该

36、查询要列出为资源type： text界定的 特性。然而，还需耍报告某一特定property的object值出 现多于次的情况。需要在predicate-object对的集合上 做计数，选出多于一个object的结果。covp1的表现较 之.bq2中多了步分别去计数每个property的object。 c0vp2在最后使用pos索引，來检索与各property的t 的标题和关的各objecto hexstore因为spo索引的使用有 其优势，但在最后它无法直接在spo进行各property的 object集的计数，而是盂要同covp2 样使用pos索引。query4 (bq4)同3类似，不过还要考虑language： france,查询过程 差不多，但前期选择不一样。c0vp1从type和language 的pso索引中联合选出subjectso而c0vp2和hexastore 需耍用pos索引来检索和合并连接type： text与 language： france 的 subjects