半结构化Web数据的数据库技术

语义丰富的半结构化Web数据的数据库技术朱利安·勒布莱引用此版本：朱利安·勒布莱。用于语义丰富的半结构化Web数据的数据库技术。其他[cs.OH]。南巴黎大学-巴黎第十一大学，2013年。英语。NNT编号：2013PA112193。电话：00872883HAL ID：电话：00872883https://theses.hal.science/tel-00872883提交日期：2013年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire语义Web中半结构化数据的优化技术巴黎南部计算机科学博士学院博士论文提交人：Julien LEBLAY支持日期：2013年9月27日获得学位：南巴黎大学博士学位学科/专业：计算机科学/数据T Hesa 领导者：M. G OASDOUÉ弗朗西斯大学。巴黎南部夫人。M. Anolescu IoanaInria SaclayR报告员M. 在曼恩贝恩德大学皮埃尔和玛丽居里M. CERI Stefano米兰理工大学和XAMINATERSM. GROSS-雷恩大卫大学1夫人。克里斯汀·罗德沃大学巴黎南部ii.iii摘要RDF和SPARQL已经成为描述和查询Web上数据的标准数据模型和查询语言。现在有大量的RDF数据可用，无论是作为半结构化文档（尤其是XML）的数据集还是元数据。RDF和XML之间日益增长的共存性和虽然许多工作涵盖了半结构化数据的注释的手动或自动生成和发布本文为XML-RDF混合数据管理奠定了基础我们介绍XR，一个适应XML结构方面和RDF语义的数据模型该模型足够通用，可以表示独立或相互连接的数据，其中每个XML节点都可能是RDF资源。我们介绍了XRQ语言，它结合了XQuery和SPARQL语言的主要特性该语言允许我们介绍了XRQ语言中的查询组合问题，并对可能的查询求值技术进行了详尽的研究。我们开发了XRP平台，实现了查询评估算法，并通过我们提出了一个基于该平台的应用程序，用于在Web上找到的页面的自动和手动注释。最后，我们提出了一种在RDF（和XR）数据管理系统中进行RDFS推理的技术关键词：语义网，XML，RDF，链接数据，数据模型，查询语言，查询组合，查询响应，查询ivv摘要自语义网诞生以来，RDF和SPARQL已经成为描述Web上资源的标准数据模型和查询语言。大量的RDF数据现在既可以作为独立的数据集，也可以作为半结构化文档（通常是XML）上的元数据。在XML数据上应用RDF注释的能力强调了同时表示和查询数据和元数据的需要。虽然在手动或自动生成和发布注释方面投入了大量精力，但在利用这些数据方面却投入了很少的精力。本文旨在为混合XML- RDF数据的管理奠定数据库基础。我们提出了一个数据模型，它捕获了XML数据的结构方面和RDF的语义。我们的模型通常足以描述纯XML或RDF数据集，以及RDF注释的XML数据，其中任何XML节点都可以充当资源。我们还介绍了结合了XPS和SPARQL特性的XRQ查询语言XRQ不仅允许查询文档的结构及其注释的语义，还允许生成带注释的半结构化数据。我们介绍了XRQ中的查询组合问题，并对XR数据的查询评估技术进行了详尽的研究，以证明这种数据管理设置的可行性我们已经为XML和RDF开发了一个基于众所周知的数据管理系统的XR平台。该平台采用了几种查询处理算法，并对这些算法的性能进行了实验比较。这是一个基于XR平台的应用程序。该应用程序提供手动和自动注释工具，以及用于同时查询注释网页和公开可用的XML和RDF数据集的接口。作为RDF和SPARQL的推广，XR和XRQ启用了RDFS类型的查询响应。在这方面，我们提出了一种在RDF（并通过扩展XR）数据管理系统中支持RDF的技术。关键词：语义Web、XML、RDF、链接数据、数据模型、查询语言、查询组合、查询回答、查询优化vivii论文摘要（法文）简介十多年来，XML [www 08 c]（eXtensible Markup Lan- guage）已成为在Web上发布数据的绝大多数现代网页都是XHTML文件，这是XML格式的众多化身之一。它也常用于XML文档在概念上可以看作是一棵树，其节点是有标签的、有序的和无限的有几种语言可以查询XML数据，其中包括W3C自2007年以来推荐的Xpress和XPS[WEB与XML同时开发的它在几个方面不同于XML。首先，RDF数据实例是一个有向图，具有标记边和无序边，其节点根据其类型进行不同的标记。RDF图中的一个节点，资源可以由URI1（通用资源标识符）标识，也可以是匿名的，在这种情况下，我们称之为空白节点。节点也可以是文字。在这种情况下，它由一个值（常量）标记，并可能伴随RDF数据集也可以被看作是一组事实（主语、谓词、宾语）。RDF模型是语义网的底层，语义网是一个允许在Web上发布可由机器明确操作的数据的概念。它的语义是根据推理规则来定义的，允许从现有事实中推导出新的事实例如，事实自2006年以来，随着链接开放数据运动[www06b]的出现，该模型得到了巨大的发展大量1. httpwww.w3.org/TR/2001/NOTE-uri-clarification-20010921/viii许多机构现在以RDF [wwwh]格式向公众提供重要的数据集。到目前为止，除了一些旨在将数据从一个模型转换到另一个模型的研究之外，很少有工作由于RDF和XML模型特别适合于不同的应用程序，我们假设，如果我们利用这两种模型各自的特性，即在Web上联合管理和查询文档的结构和语义，则可以出现新的解决方案来解决实际问题，特别是在数据新闻和在线事实检查的最新领域本论文旨在通过为将XML和RDF数据组合到一个公共实例中的工具奠定基础，使这种类型我们提出了一个数据模型及其查询语言，并提出了一个实现这些想法的平台它使我们本文的主要贡献如下：– 注释XML文档的数据模型。虽然到目前为止的大多数工作仅限于将RDF模型中的数据表示为XML格式，反之亦然，但XR模型提供了一种表示互连的XML和RDF数据的方法，即– 就组成而言，它是一种封闭的查询语言。我们引入了一种查询语言，用于该语言有两种形式：（i）返回元组集的简单形式，（ii）在组合方面封闭的扩展形式。换句话说，XR查询的结果是XR数据的实例，– 对查询评估和优化策略的详尽研究我们正在详细研究有效评估XR数据查询的可能技术，特别是考虑到现有数据管理系统的技术限制;– 一个数据管理平台XML和RDF数据之间的这种清晰分离消除了管理员的任何转换，并允许将数据存储在单独的子系统中。我们已经开发了一个数据存储和查询系统，– 一项实验研究。我们提出了一系列– 这是一个数据新闻工具。XR数据模型为最近在Web上出现的一组应用程序提供了坚实的基础。ix互联网，就像数据新闻一样。为了证明该模型及其语言对这类应用程序的有用性，我们开发了FactMinder，这是一个帮助在Web上验证事实的工具。L’outil se présente sous la forme- 响应查询的替代方法。如前所述，RDF的语义要求我们考虑查询响应中隐含的事实。由于我们的数据模型是RDF模型的超集，因此它保留了RDF模型的语义。然而，用于响应RDF请求的现有技术具有缺点。我们引入了一种基于本论文的结构如下。首先，在第2章中，我们概述了第3章正式介绍了数据模型、语言和详细的属性。第4章研究了该模型的查询评估和优化技术，介绍了数据管理平台，并进行了一系列实验来验证我们的技术。第5章介绍了我们在Web上的验证工具第6章最后，第7章通过讨论这项工作可能导致的方向来结束这一论点最新技术水平注释数据管理的研究集中在两个方面：一方面是结构化数据注释工具的设计，另一方面是XML和RDF模型组合的Web数据的注释工具。从RDF模型一开始，就提出了许多解决方案来促进网页的注释，无论这些注释是由用户手动创建[ Yee02，HS02]还是自动和半自动创建[VVMD + 02，DEG + 03]。在本节中，[RH05]概述了迄今为止这项工作主要针对带注释文档的存储和查询，不考虑对其结构和语义的关于这些解决方案，包括W3C的微格式2、eRDF3和RDFa42. http：microformats.org/3. http：research.talis.com/2005/erdf/wiki/Main/RdfInHtml4. http：www.w3.org/TR/xhtml-rdfa-primer/x没有数据查询问题的解决方案。此外，它们假定希望注释文档的用户具有对该文档的写访问权限，这大大降低了它们的有用性。我们提出的模型允许您创建和管理语义注释，而不会影响文档的结构或内容关于这一主题的第二个观点涵盖了混合数据模型。在这种情况下，已经提到的最常见的解决方案是将RDF模型的数据转换为XML格式，以便仅使用XPS语言进行查询，或者执行转换以将interrog转换为lan g age S P ARQL [RG N + 01，PSS02，DFG + 07]。还设想将一个语言时代的功能作为另一个语言时代的外部组件[CKK C + 09]，例如可从SPARQL环境访问的X P ath提取一些研究建议从一个更通用的框架（如基于规则的系统）开始，将几种语言建模为一种语言[FBB05]。最后，如W3C 5的GRDDL建议中所述，已经设计了混合语言来从XML文档中提取几乎没有的注释虽然这些解决方案允许同时查询XML和RDF数据，但它们通常依赖于预处理原则，在预处理原则中，数据或查询必须转换为其中一种模型。然而，这种替代方法也有缺点：（a）重写可能导致复杂且难以优化的查询，（b）数据转换通常是昂贵的，无论是在查询执行之前还是在数据集的上游执行，以及（c）先前的方法都没有将XML节点视为RDF资源本身C’est pour pallier ces manques que nous avons orienté notre travail sur une solutionqui respecte les formats dans lesquels les données sont initialement使用示例。让我们用下面的例子来说明我们的观点，在这个例子中，注释起着核心作用在竞选期间罗伯特在他的网站上发表了他的演讲稿，在演讲稿中他分享了他对土耳其和日本局势的看法，特别是引用了： 2012 年 7 月 的 每 月 失 业 率 为 8% 。 通 过 使 用 开 放 数 据 集 （ 如http://data.gouv.fr），它变得非常有用。可以半自动地检查所引用的数字此外，通过存档候选人的演讲，它将能够确定，例如，5. http：www.w3.org/TR/grddl/xiBN}ULL\（\）\（\）\（\）→ U在提到这个国家的其他地方如果这样的查询太模糊而不能从基于自然语言处理的技术获得可操作的结果，则它们可以用查询语言（例如SPARQL）正式地表示为带注释的半结构化数据的管理XR数据模型XR数据模型设计用于表示带注释的文档。为了保持标准XML和RDF数据模型的属性，XR数据实例包括两个子实例：（a）由XML树组成的L’association这些URI可以出现在RDF三元组中。形式上，考虑以简化是最后，是未定义的文字或URI，如我们所述-然后是罗恩。定义（XML树）。XML树是一棵树，T=（N，E），有限的，有标签的，无序的，无限元数的，其中N是节点，E是边，每个节点n N与一个标签λ（n）相关联，和类型τ（n）文档、属性、元素、文本。元素类型的节点不能有两个同名的子属性。属性类型节点必须是元素类型节点的子节点，它具有属于文字集的值，并且没有子节点。文本节点没有子节点。最后，XML树最多有一个文档节点。文档节点是树的分支，正好有一个子节点，并且标记为。定义（XML实例）。 XML I X实例是一组有限的XML树。现在，我们假设URI分配函数是连接XML和RDF子实例的实际上，可以在RDF子实例中引用分配给XML子实例的节点的标识符。在第4节中，我们将介绍在实践中实现此功能的几种可能方法简而言之，xiiUN考虑一个函数，该函数为第一次呈现的任何输入返回一个新值，并在随后对该输入的RDF子实例被定义为一组三元组，这些三元组可以引用XML节点的URI。定义（RDF实例）。 RDFIR实例是一组三元组，其形式为（s，p，o），其中s（U = B），p（U），o（L = U = B）。形式上，对于给定的RDFIR 我们将在第3.2.2节和第6章中讨论这一主题。现在，我们可以定义XR实例，如下所示：定义（XR实例）。XR实例是一对（I X，I R），其中I X和I R分别是XML子实例和RDF子实例，它们构建在同一组URI上。由于XML和RDF实例是在同一组URI上形成的，因此RDF三元组可用于注释任何 XML 节 点 L’exemple suivant illustre cette interconnexion entre les deux sous-instances duXRQ查询语言XR实例的用户必须能够查询数据的结构（在XML实例中描述）以及语义（在RDF实例中描述）。这就是XRQ的目标，XRQ是一种允许从这两个角度访问数据的语言。在3.2节中，我们首先建立语言的语法，然后在3.2.2节中详细介绍语义。最后，第3.2.3节和第3.2.4节介绍了该语言的扩展，该扩展提供了构建复杂结果的方法，生成XR实例，从而使XRQ成为一种封闭的语言与我们在下面定义这两种类型的动机。请注意，在树模式中使用的变量定义（树模式）。树模式是一个有限的、有序的、无界的和标记的树，它有两种类型的边：子边和后代边。树中的每个节点最多可以追加一个变量uri、一个变量xiiiQQQQ1 2 3 4R R R（$X，：authorOf，$Y），（$Y，owl：sameAs，$A），（$B，：about，$A），（$X，rdf：type，：MemberOfCongress）$CA，$X ：-微博blogtitleval：$VC消息htmldiv正文URI：$A=#205内容：$CAH2URI：$C值：$V CdivURI：$B内容：1 2X XF图 1val和变量cont。一个节点也可以用[t= c ]形式的等价谓词来标记，其中c奏效，t是{ uri，val，cont }中的一个类型。树模式这些变量有两个目的：（i）指示树模式（或三元组）之间的连接。(ii)指示查询的哪些元素将成为结果的一部分（类似于连接查询）。类型指定将XML节点中的哪些信息分配给变量。当树模式中的n t个节点与XML树中的n d个节点匹配时定义（三元组的模式）。三 元 模式是形式为（s，p，o）的三元，其中s，p是URI或变量，而o是URI、文字或变量。通过组合树模式定义（XRQ查询）。XRQ请求由标头和正文组成。主体是一组树模式头部由也出现在主体中的变量列表组成联接是通过在查询中多次使用同一变量来公式化的。因此，有三种类型的连接是可能的：树模式之间扩展的XRQ语言。XRQ查询返回一组元组，尽管它接受XR实例作为输入。理想情况下，应该可以生成XR实例作为查询的结果。我们建议将QQxivQQQQQ$VA>>>>>*XX1 1 2 3 4R R R R（$X，rdf：type，：Politician），（$X，：said，$R），（$X，：authorOf，$Y），（$Y，owl：sameAs，$A），（$B，：关于，$A）， （$X，rdf：type，：国会议员）故事<$V A，$CB>1相关微博消息-blogtitleval：$V C1htmldiv2X关于$R报价$CB正文URI：$A值：$V AH2URI：$C值：$VCdivURI：$B内容：$CB图2XRQ语言通过为该语言添加一个构造函数来创建新的树和三元组来实现这一目标。本节的其余部分将给出此扩展的定义和语义。定义（扩展XRQ请求）。一个扩展的XRQ查询，表示为Q=（H X，H R，Q X，Q R，Sk），由一个类似于简单XRQ查询的主体（Q X，Q R）、一个形式为（H X，H R）的头（其中H X是一组XML树模式，H R是一组三元组）和一个双射实现Sk：H X → S（其中S是一组无限的Skolem函数）组成。设V Q是出现在查询正文中的变量集，V H是仅出现在查询头中的变量集，V =V Q V H。对于每个树t xH X，每个节点n xt x可以用三种方式来注释：（i）赋值标签是变量vVH到类型uri，（ii）值标签是变量vVQ或常量，并且只能应用于叶子，（iii）组标签是常量或变量VQ的有序列表，使得它不包含当前节点的祖先的组标签中存在的任何变量。三元组tR SR可以在任何位置（s、p或o）包含V的变量第3.2.2节详细介绍了简单和扩展形式的语言语义。组成。扩展语言特别允许查询组合，即根据另一个查询（或视图）的结果来评估一个查询。我们提出了一个算法，它构造一个新的查询qJ，使得对于任何实例I，qJ（I）相对于（qv）（I）是正确的。XRP平台由于XR模型与XML和RDF标准兼容，因此可以考虑将XR数据存储在本机平台中，或者在HHQ：xv在这种情况下，必须扩展XML数据管理系统以允许管理有时可以直接修改系统以使其能够解释这些URI。但是，当系统是完全封闭的时，就有必要使用考虑到所有这些情况，我们已经建立了一个可用于评估现有系统上的XR查询的技术层次结构这包括水平传递信息的策略，评估三元组的模式（分别在传递和链接树模式变量（分别为三胞胎），使他们更有选择性。这些技术为某些优化铺平了道路例如，如果某些候选人显然会使下一个请求不令人满意，则可以在为了将这一系列评估算法付诸实践，我们开发了XR平台，这是一个完整的查询存储和评估引擎，可以基于任何现有的XML或RDF数据管理系统。该平台包括一个优化器，用于在评估查询时从不同的评估策略中进行选择该引擎具有一组XR模型、XRQ语言和XRP平台已在 国 家 会 议 [GK K + 11b] 、 国 际 orkshop[GKK + 11a]以及国家[GK K + 12]和国际期刊[GK K + 13b]上发表。网络上的事实分析与验证互联网在许多方面重塑了新闻业，打开了信息大规模传播的闸门。新闻专业人员突然发现自己在与新的参与者竞争，其中大多数是积极分子（活动家、博客作者或普通公民），他们将自己定位为现有媒体的替代新闻来源。这场运动的力量部分来自于它所涉及的各方的数量，使它能够集体然而，数量并不是质量的同义词，这一现象催生了一个新的期刊列表类别。数据记者和事实核查员，有时也被称为disinto-xicators，专门虽然核实消息来源是记者工作的一个组成部分6. http://www.liberation.fr/desintoxxvi这些工具是在线服务（如Twitter7或Google Maps8），但主要是政府提供的公共数据集、非政府组织提供的公共数据集和私营公司提供的公共数据集。这些交易在很大程度上仍然是手工的L’écrasante majorité des informations publiées sur la Toile étant auxformats XML ou RDF, nous postulons qu’XRP représente une plateforme de choix pourassister ce type d’utilisateurs dans leurs我们介绍FactMinder软件，这是一个在网络上分析和验证事实的工具 激活扩展后，浏览器屏幕将分为两个当用户访问一个网页（左）时，它会被传输到一个命名实体提取系统（在我们的例子中是OpenCa-lais [wwwi]）。这些实体标识人员、地点、机构、日期和引文，并集成到页面本身中。浏览器的右侧包含一个仪表板，允许您查看与页面相关的信息。仪表板完全由XRQ或XIP（XR信息面板）视图组成，即命名的XR查询。这些视图在XR平台上进行评估，其中存储了以前访问过的页面的数据，以及在Web上打开或收集的一组数据。当某些用户事件发生时（例如，当用户选择屏幕上的项目时），可以在视图之间施加依赖关系，以便仅在提供附加信息的情况下评估视图该软件已在SIGMOD 2013[GKK+13a]上进行了演示。使用位图索引响应RDF查询的方法回答SPARQL查询需要考虑推理规则，如引言中所述通常用于此目的的方法称为前链和后链。第一种方法是从所考虑的数据和规则的扩展中详尽地推导出所有可能的事实。这导致在这种情况下，响应查询的问题被简化为评估查询的问题。L’inconvénient majeur de la méthode réside dans le fait7. http://twitter.com8. http://maps.google.com9. http://data.gov10. http://data.gouv.fr11. http://data.worldbank.org12. http://google.com/publicdata/home13. http://on.ted.com/MarkhamNolanxvii我我它需要潜在的大量存储空间。此外，当数据是动态的时，必须保持其一致性第二种方法在本文中，我们提出了一种数据存储和查询评估的方法，以最大限度地减少与这两种方法相关的问题。通过观察数据集的RDFS围栏因此，属于给定类ap-的资源也属于它的所有超类。类似地，由一个属性链接的两个资源也由其所有超属性链接 例如，尽可能快地检测给定类是否属于集合论运算通常以位对位运算的形式实现为此，为所考虑的集合的元素设置顺序就足够了它的每个子集可以由一个字来表示，对于属于该子集的元素的每个索引，该字的位被设置为1除了对二进制数据进行集合运算的明显速度（例如，通过逻辑AND获得交集，通过OR获得联合）之外，还存在许多压缩技术，包括在不解压缩数据的情况下对数据进行运算我们提出了一个RDF数据存储模型，其中通过这种方法，实现通过前向链接获得的数据围栏只会导致所此外，仍然可以不使数据饱和，并且它与早期工作[MAYU05，RMC11]中提出的语义索引概念非常相似。然而，在我们的例子中，索引是位图索引，它比现有技术具有各种优点。首先，这些有效压缩的第二，在更新类和属性层次结构时，它们更容易我们详细介绍了我们的方法，特别是解释了传统的数据管理系统如何这种方法是在一个国际研讨会上发表的一篇文章[Leb12]的主题。xviii结论有效管理结构化和语义注释信息的需求正变得越来越迫切。在本研究中，我们建立了一个数据模型和查询语言的基础，用于根据数据库的结构和注释的语义来表示和查询数据库。我们深入研究了利用现有应用程序评估和优化可能的查询的技术我们已经开发了一个完整的平台来存储和我们进行了一系列我们介绍FactMin- der，一个帮助在线事实核查的软件最后，我们介绍了一种用于响应RDF请求的替代技术。我们打算在以下方面扩展这项工作：（i）通过在合成算法中引入优化（修剪和最小化），并在多视角的背景下考虑问题，扩展我们在合成方面的工作(ii) 引入了一个成本模型来自动化内容。1引言11.1从Web 1.0到Web 3.011.2动机：结构与语义学21.3贡献和大纲42背景和最新技术水平72.1XML数据管理72.1.1数据模型和查询语言82.1.2存储XML数据82.2RDF数据管理102.2.1数据模型102.2.2查询&存储RDF122.3在RDF和XML处142.3.1使用本体的XML数据集成152.3.2XML和RDF之间的152.3.3文件注释162.3.4摘要183用于语义丰富文档的XR数据模型和查询语言3.1XR数据模型193.2XRQ查询语言223.2.1核心XRQ语法223.2.2核心XRQ语义243.2.3扩展XRQ语法273.2.4扩展XRQ语义29