无数据的查询转换评估

t1(q) =t2(q) =t3(q) =t4(q) =qR =SELECT ?x ?yWHERE {?x p ?y .?z q ?y .}15990无数据的查询转换评估0简短论文0Jérôme David Univ. GrenobleAlpes，Inria，CNRS，Grenoble INP，LIGGrenoble，法国Jerome.David@univ-grenoble-alpes.fr0Jérôme Euzenat Univ. GrenobleAlpes，Inria，CNRS，Grenoble INP，LIGGrenoble，法国 Jerome.Euzenat@inria.fr0Pierre Genevès Univ. GrenobleAlpes，Inria，CNRS，Grenoble INP，LIGGrenoble，法国 Pierre.Geneves@cnrs.fr0Nabil Layaïda Univ. GrenobleAlpes，Inria，CNRS，Grenoble INP，LIGGrenoble，法国 Nabil.Layaida@inria.fr0摘要0查询转换在语义Web查询处理中无处不在。对于任何未经构造证明正确的转换情况，必须评估这些转换的质量。通常的评估指标要么过于句法化且信息不够丰富——结果为：正确或不正确——要么依赖于评估来源。此外，这两种方法不一定产生相同的结果。我们建议将评估基于查询包含性，以实现与数据无关的评估，比通常的句法评估更具信息量。此外，这种评估方式可以考虑本体、对齐或不同的查询语言，只要它们与查询评估相关。0CCS概念0• 信息系统 → 语义Web描述语言；• 计算理论 →逻辑和验证；数据库查询处理和优化（理论）；0关键词0SPARQL查询转换；查询包含性；转换评估0ACM参考格式：Jérôme David，Jérôme Euzenat，Pierre Genevès和NabilLayaïda。2018年。无数据的查询转换评估：简短论文。在WWW'18Companion：2018年Web会议伴侣，2018年4月23日至27日，法国里昂。ACM，美国纽约，4页。https://doi.org/10.1145/3184558.31916170随着RDF和OWL等标准Web知识表示语言的可用性，SPARQL查询变得无处不在以访问数据。与之前的SQL一样，该语言允许在评估之前进行操作。SPARQL查询可能0©  2018 IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACMISBN 978-1-4503-5640-4/18/04。0SELECT ?x ?yWHERE { ?x p?y . ?z q ?y .?z r ?x . }0SELECT ?v ?wWHERE { ?b q?w . ?v p ?w . }0SELECT ?x ?yWHERE { ?x p?y . }0SELECT ?x ?yWHERE { ?x p?y . ?y q ?z . }0图1：由转换产生的示例查询（省略了from子句；由于我们使用集合语义，可以添加distinct进行评估）。0被转换以优化其评估，以处理异构词汇或使用更受限制的查询语言。特别是，查询转换是本体基础数据访问（OBDA）[10]和联合查询[15, 12,14]的核心。一些转换在理论上通过构造证明是正确的（这是某些OBDA的情况）[3,1]，然而其他一些转换，特别是当它们连接在不同本体中表示的数据源时，可能需要手动设计[9]或使用临时规则[5, 12, 7, 17,16]。在这种情况下，必须评估这些转换的质量。01 评估转换后的查询0查询转换方法将查询q转换为替代查询t(q)。它们可以用于对相同的数据源（即数据库或RDF图）或使用不同的数据模型对不同的数据源进行查询评估。对这些转换的质量评估是通过计算一个在[0,1]区间内的值来衡量的。通常有两种不同的模式进行评估。在第一种模式[7]中，给定一个初始查询q和它预期转换为的查询qR（参考查询），然后进行评估。0本文根据知识共享署名4.0国际许可发布。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW '18 Companion，2018年4月23日至27日，法国里昂 © 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5640-4/18/04。0Track: 数据推理 WWW 2018，2018年4月23日至27日，法国里昂tqRm(t)˜p(t)˜r(t)p(t)f (t)r(t)D1.1.1.G1t1qR0101..67.5G21.1.1.G1t2qR1111.1.1.G21.1.1.G1t3qR001.57.731.Gr(t) =Dabcdefgpqrqpprqqqr⟨a,p,c⟩ ⟨b,q,c⟩⟨f ,r,a⟩ ⟨f ,q,c⟩⟨c,p,e⟩ ⟨f ,p,d⟩⟨д,r, f ⟩ ⟨д,q,d⟩⟨д,q,e⟩ ⟨d,q,e⟩⟨d,r,c⟩Figure 2: Data set G1.with a query which is not the expected one. Table 2 shows that,though the syntactic comparison determines that t1 and t3 do notyield the reference query, the use of the data set G1 does not allowto discriminate them. Conversely, though the use of precision andrecall with respect to G2 correctly determines that t1 returns in-complete results and t3 returns incorrect results, this informationis not available by using the syntactic measure which grants themthe same value, 0, as t4.(2) Precision and recall are highly dependent on the selecteddata set. This is obvious from Table 2 as G1 finds the result oftransformation t1, t2 and t3 equally perfect, though G2 identifiestrue negatives in t1 and false positives in t3. In addition, obtainingRD, on large data sources may be a resource-consuming task, sobenchmarks are not easy to build.(3) The syntactic measure is very rough as it only tells if thequery is the expected one or not. This does not allow to discriminatequeries, though precision, recall and F-measure may permit to rankthem on a more precise scale. The information that t1 only providescorrect answers and that t3 always provides all answers, is notavailable by using the syntactic measure which grants them 0.The apparent added-value of precision and recall is, in fact, verydependent on the data set. Indeed, as soon as its value is not neces-sarily 1. it is always possible to tune the data set to obtain a differentvalue —through adding and suppressing triples that will generatemore true positive or more false positive. Hence, one may arguethat the finer grain provided by these measures is misleading andthat there is actually only three values, for either precision andrecall: it is necessarily 1. or not (necessarily 0. is only obtained bythe empty query).Checking what is necessary does not depend on the data set andis prone to static analysis. Hence, we suggest here that by usingquery containment instead of syntactic equality, it is possible toimprove such methods without resorting to data sets.3CONTAINMENT-BASED TESTSIn order to better qualify the quality of transformations, a contain-ment test can replace the equality test. A query q is contained inanother q′, noted q ⊑ q′ if, for any RDF graph G, eval(q, D) ⊆eval(q′, D) [2, 11]. The evaluation measures can then be defined as:˜p(t) =�1if t(q) ⊑ qR0otherwiseand˜r(t) =�1if t(q) ⊒ qR0otherwisethis has the advantage of benefiting from well-understood defini-tions that go beyond the implementation of the equality predicate.It also splits the measure in two different meaningful ways in theTrack: Reasoning on Data WWW 2018, April 23-27, 2018, Lyon, France16000查询  G 1 G 2 q R � a , c � � f  , d � � c , e � � a , c � � b , c � � c , e � � д , e � t 1 (q ) � a , c � � f  , d � � c , e � � a , c � � c , e � t 2 ( q ) � a , c � � f  , d � � c , e � � a , c� � b , c � � c , e � � д , e � t 3 ( q ) � a , c � � f  , d � � c , e � � a , c � � b , c � � c , e � � f , d � � д ,  f  � � д , d � � д , e � t 4 ( q ) � f  , d � � f  , d � � д , d � � д ,  f  � Table1: 查询对数据集G 1和G2的评估结果（使用集合语义而不是标准的多重集语义进行查询评估）。01. .50 .33 G 1 t 4 q R 0 0 0 0. 0. 0. G 2 Table 2:转换评估指标（灰色单元格说明第3节的含义）。0m(t)的计算方式为：0m(t) =0� 如果t(q) � qR，则为1，否则为00等式谓词(�)通常不是严格的语法相等，而是可以通过交换性和变量重命名来判断——这是在比较图1中的t 2(q)和qR时的情况——或者是相对于正常形式的查询的相等。在第二种模式[9, 17, 16]中，给定一个初始查询q和对数据源D的预期评估结果RD，往往是R D = eval(q R, D)对于某个参考查询q R。然后将RD与eval(t(q),D)的结果进行比较。然后可以根据这组答案定义经典的度量，如精确率(p(t))和召回率(r(t))：0p(t) = | eval(t(q), D) ∩ R D|0| R D0F-度量通常以精确率和召回率的调和平均数的方式计算。通常，评估是针对涉及各种测试的基准进行的，其结果被聚合或平均。表1显示了针对图1中的查询q R，t 1，t 2，t 3和t 4对图2和图3的数据集G1和G2进行评估的结果。从这些结果中，可以计算出表2中报告的度量m，p，f和r。当度量m(t)为1时，精确率和召回率都为100%。然而，它们也可以在m(t)=0时达到100%。02 问题0这些评估指标存在三个问题。(1)这两个指标之间存在差距。特别是，在精确率和召回率方面，可能会得到100%的正确结果。abcdefgpprqpppppqr⟨a,p,c⟩ ⟨b,p,c⟩⟨f ,r,a⟩ ⟨f ,q,c⟩⟨c,p,e⟩ ⟨f ,p,d⟩⟨д,p, f ⟩ ⟨д,p,d⟩⟨д,p,e⟩ ⟨d,q,e⟩⟨d,r,c⟩t1(q)t4(q)t3(q)⊑⊑⊑⊑If the data sources are expressed in a particular schema or ontologyO, it is possible to use containment modulo schema ⊑O [4, 3] inorder to perform the test. This can still be achieved independentlyfrom any data set.In addition, if the query evaluation mechanism can take suchontologies into account under a particular entailment regime reд,then the previous inequalities may be rendered as:t(q) ⊑reдOqR ⇒ evalreд(t(q), D ∪ O) ⊆ evalreд(qR, D ∪ O)Figure 5 shows a genuine SPARQL query t5(q) using the OWLproperty rdfs:subPropertyOf. If considered as simple SPARQLqueries, there is no containment relation between t5(q) and qR.However, if the OWL-entailment regime is used, t5(q) ≡ qR becausethe triple pattern ?z q ?y in qR will match all triples which entailit, including those involving a subproperty of q.This also applies for queries in SPARQL variants: the contain-ment test must be defined with respect to the specific variant tot5(q) =SELECT ?x ?yWHERE {?x p ?y .?z ?r ?y .?r sPO q .}t6(q) =SELECT ?x ?yWHERE {?x p ?y .?z ?r ?y .?r sPO∗ q .}Figure 5: Queries expressed with respect to ontological ex-pressions (sPO stands for rdfs:subPropertyOf).Track: Reasoning on Data WWW 2018, April 23-27, 2018, Lyon, France16010图3：数据集 G2。0这意味着它可以用来确定是否可以期望完全正确或完全完整的结果。因此，这比度量m更具信息性。特别是，如果R D = eval(q R,D)，我们知道：0t ( q ) � q R � eval ( t ( q ) , D ) � eval ( q R , D )0或者˜ p ( t ) = 1 � p ( t ) =1。 ，以及0t ( q ) � q R � eval ( t ( q ) , D ) � eval ( q R , D )0或者˜ r ( t ) = 1 � r ( t ) = 1。，对于任何D都是如此。因此，这对于所有数据集都是正确的。仍然可以按照通常的方式计算F-measure˜f，根据精确度表示纠正和召回度表示完整性的直觉。然而，这个度量会丢失信息，因为它只有两个值，0和1（实际上，如果˜m是用语义等价计算的m，那么˜ f将是˜ m）。这也可以组合为：0t ( q ) ≡ q R � eval ( t ( q ) , D ) = eval ( q R , D0或者˜ m ( t ) = 1 � f ( t ) =1。这种基于包含关系的测试不能提供错过或错误结果的比例的细粒度度量。然而，它们可以告诉我们是否没有错过答案和没有错误答案，并且对于所有数据源都是有效的。如果有人对不错过答案的转换（选择t 3 ）或不返回无关答案的转换（选择t 1）感兴趣，这可能是重要的信息。因此，基于包含的度量通过提供两个布尔值而不仅仅是一个布尔值来解决问题（1），这两个布尔值在两种度量类型之间是中间的。该方法通过简单地取两个值的合取来检索˜m（可以认为比m更好）。它还通过独立于数据源来处理问题（2），并通过提供关于查询行为更精确的信息来处理问题（3），保持与精确度和召回度的联系，指示某些答案可能是不正确或缺失的。它也可以用于整个测试台而不仅仅是单个测试。在这种情况下，可以对结果进行平均（成功的包含测试比例）。04 转换比较0尽管返回一对布尔值的结果可能看起来粗糙，但它们可以用于比较不同转换的优点。实际上，包含是一个偏序关系0这是一种可以用来比较多个转换的关系。因此，可以将由转换得到的所有查询相对于彼此进行定位，并观察一个查询是否比另一个更接近参考查询（尽管在图4的示例中并非如此）。0q R ≡ t 2 (q )0图4：由图1中的查询包含引起的转换顺序。0这适用于一个查询。可以通过在每个图中将查询替换为转换来考虑一组查询，保留单个qR节点，用两个�和�边替换≡，最后相交这些图，即它们的边集。如果一个转换总是返回比另一个或参考查询少的答案，它们应该通过�边相关联。还可以取这些图的并集，并根据它们出现在的图的数量给边赋权重。05 本体和查询语言match the corresponding evaluation operation. This has alreadybeen done for PSPARQL [2], a variant of SPARQL 1.0 extended withproperty path expressions, now included in SPARQL 1.1.Figure 5 shows a PSPARQL query t6(q) using a property path ofan undefined number of rdfs:subPropertyOf properties (aimingat implementing the transitivity of this relation). If qR is evaluatedas a PSPARQL query, then qR ⊑ t6(q) because ?z q ?y in qRonly matches those triples with the q property, but t6(q) will matchthese and in addition all those properties related to it by a chain ofrdfs:subPropertyOf in the data.6ALIGNMENTS16020当一个查询以词汇表 O 表达时，转换为以词汇表 O ′表达的查询的这种评估方式非常方便，因为它不依赖于任何对齐：转换 t 可能涉及对齐，也可能不涉及，但查询 t ( q ) 和 q R 都以词汇表O ′ 表达，因此可以在 O ′的模块或非模块下进行包含性测试。我们已经定义了用于评估本体对齐的度量标准，考虑到用户可能希望对查询给出精确答案，或者相反，对查询给出完整答案[6]。这导致了依赖于转换的方向和用户期望的属性（正确性或完整性）的度量标准，这些度量标准通过容忍返回比相应的类更精确或更一般的类来放宽语法精确性和召回率。这不直接转化为相对于特定SPARQL查询的更好的精确性和召回率，因为使用了减法等操作，这需要反转方向。基于包含性的转换评估实际上提供了一种在查询评估的背景下比较本体对齐的新方法。实际上，如果认为转换 t 是由对齐 A [5] 参数化的，那么 t A 的评估就是对 A的评估。这个过程已经在使用具有可用参考结果的特定数据集的本体对齐评估活动中使用过[8]。使用基于包含性的评估，可以从一组参考查询中获得相同的结果，而无需依赖数据集：可以在这个基准上比较由不同匹配器提供的多个对齐，以评估它们在转换查询能力方面的能力。这也提供了一种以定向方式评估对齐的替代方法，与其在查询处理中的使用相关，因为结果将与所需的精确性和召回率相关。07 结论0查询转换质量通常通过两种类型的度量来评估，具有其质量（易于定义/细粒度）和缺陷（粗糙/数据集相关+难以定义）。我们提出了一种中间类型的度量，基于查询包含，它与第一种一样容易定义，但在结果上更精确，并且其结果对于任何数据集都是有效的。这样的度量具有优势，它们可以基于查询包含而不是包含来对不同的转换进行有力基础上的排序。这也可以使用查询子sumption[11]来定义，而不是包含。这将0结果可能导致有效的度量，但与初始度量的关系可能不直接成立。该方法可以针对任何类型的包含关系进行定义，依赖于不同的查询语言、本体或推理制度。它也可以被看作是一种对齐评估度量。查询包含可能计算成本高昂（带有可选项的定义良好的模式是Πp2-完全的[11]，许多已知的过程在ExpTime[4]中），在某些情况下是不可判定的（包含包含选择和可选项的包含语义或完整的SPARQL[13]）。然而，当它是可行的时，它只取决于查询的大小，而不是通常更大的数据集的大小。因此，我们期望这对于评估任务是可以接受的。0参考文献0[1] Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, VladislavRyzhikov, and Michael Zakharyaschev. 2017. 基于OWL2QL和有界树宽查询的本体数据访问的复杂性.在第36届数据库系统原理研讨会（PODS）中，芝加哥（美国），201–216页。[2] MelisachewWudage Chekol, Jérôme Euzenat, Pierre Genevès和Nabil Layaïda. 2011.PSPARQL查询包含性. 在第13届国际数据库编程语言研讨会（DBPL）中，西雅图（美国）。[3]Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès和Nabil Layaïda. 2012.RDFS蕴涵制度下的SPARQL查询包含性.在第6届国际联合自动推理会议（IJCAR）中，曼彻斯特（英国），134–148页。[4] MelisachewWudage Chekol, Jérôme Euzenat, Pierre Genevès和Nabil Layaïda. 2012.SHI公理下的SPARQL查询包含性.在第26届AAAI人工智能大会中，多伦多（加拿大），10–16页。[5] Gianluca Correndo, ManuelSalvadores, Ian Millard, Hugh Glaser和Nigel Shadbolt. 2010.用于实现链接数据上数据集成的SPARQL查询重写. 在EDBT/ICDTWorkshops中，洛桑（瑞士）。[6] Marc Ehrig和Jérôme Euzenat. 2005.本体匹配的宽松精确度和召回率. 在K-CAP集成本体研讨会中，班夫（加拿大），25–32页。[7]Pascal Gillet, Cássia Trojahn dos Santos, Ollivier Haemmerlé和Camille Pradel. 2013.查询模式重写的复杂对应关系.在第8届本体匹配研讨会（OM）中，悉尼（澳大利亚），49–60页。[8] Antoine Isaac,Shenghui Wang, Claus Zinn, Henk Matthezing, Lourens van der Meij和Stefan Schlobach.2009. 评估图书馆领域语义互操作性的词库对齐. 《IEEE智能系统》，24，2，76–86页。[9]Prateek Jain, Peter Yeh, Kunal Verma, Cory Henson和Amit Sheth. 2009.使用基于部分关系的变换规则对SPARQL查询进行重写.在第3届地理语义学国际会议（GeoS）中，墨西哥（墨西哥），140–158页。[10] RomanKontchakov, Mariano Rodriguez-Muro和Michael Zakharyaschev. 2013.带有数据库的本体数据访问：一个简短的课程.在第9届国际推理Web暑期学校中，曼海姆（德国），194–229页。[11] Andrés Letelier, JorgePérez, Reinhard Pichler和Sebastian Skritek. 2013. 语义Web查询的静态分析和优化.《ACM数据库系统交易》，38，4，25:1–25:45页。[12] Konstantinos Makris, NektariosGioldasis, Nikos Bikakis和Stavros Christodoulakis. 2010.用于查询联合RDF数据源的本体映射和SPARQL重写. 在On the Move to Meaningful InternetSystems（OTM）中，赫尔松索斯（希腊），1108–1117页。[13] Reinhard Pichler和SebastianSkritek. 2014. 设计良好的SPARQL的包含和等价性.在第33届数据库系统原理研讨会（PODS）中，Snowbird（美国犹他州），39–50页。[14] EricPrud’hommeaux和Carlos Buil-Aranda. 2013. SPARQL 1.1联合查询. 推荐。W3C。[15]Bastian Quilitz和Ulf Leser. 2008. 使用SPARQL查询分布式RDF数据源.在第5届欧洲语义Web会议（ESWC）中，特内里费（西班牙），524–538页。[16] ÉlodieThiéblin, Fabien Amarger, Ollivier Haemmerlé, Nathalie Hernandez和Cássia Trojahn dosSantos. 2016. 从1：n复杂对应关系重写SELECT SPARQL查询.在第11届本体匹配研讨会（OM）中，神户（日本），49–60页。[17] Ana Isabel Torre Bastida,Jesús Bermúdez和Arantza Illarramendi. 2015. 在数据集不完全对齐的情况下进行查询近似.在软件工程和数据库的第20届会议（JISBD）中，桑坦德（西班牙）。0跟踪：数据推理WWW 2018，2018年4月23日至27日，法国里昂