第十章 Web数据库集成系统

第十章Web数据库集成系统分布式数据库系统原理与应用动机Web,我们广泛应用着,但还存在许多挑战性问题?结构化数据

丰富,然而却很少被利用!Web信息分类Web上的信息可分为：SurfaceWeb和DeepWeb。SurfaceWeb是指可以通过超链接被传统的搜索引擎索引到的页面的集合；而DeepWeb是指Web中不能被传统的搜索引擎索引到的那部分内容，只能通过查询接口动态提交查询来访问Web中的内容。

TheDeepWeb:Web上的数据库目前,有关Web的挑战是“双重的”

Getting

access

tothe

structured

information!AccessStructure

SurfaceWebDeepWeb

以前Web上:

搜索通常是基于爬虫和索引(crawlandindex)

当前Web上:

搜索的最终目标是实现数据集成DeepWeb数据集成案例应用案例:Web信息集成系统

动机：

Web上信息以多种形式存在，但目前主要基于Google、yahoo、百度等搜索引擎进行查询，返回含有关键字的URI导航信息页面(包括无用信息)。用户通过逐一点击获取需要的信息，需要人们繁琐的信息收集和识别过程，给人们带来了许多不便。尽管如此，用户得到的还是零散的、不完备的且非系统的信息。

目标：人们希望通过一个统一的获取信息的门户，能按需为用户提供整合的信息。可大大节省大量的人力，提高查询的效率和知识的利用率。购买一本书？Google上找书店对比最后确定要买的书太繁琐！分别查询各书店网页返回优化的结果自动查找和集成多查询统一界面人们希望：存在许多挑战问题：!!!DeepWeb数据集成关键问题主要科学问题

如何从丰富的Web页面中按需并正确地发现和抽取实体资源；

非结构化信息、包含噪声、存在异构

如何发现不同类型实体资源的关联关系；

各种类型资源独立、异构、自治存在

如何整合不同类型的资源；

多种类型资源、大数据量、资源质量不同如：一本书，一辆车，一个人等如：同类书、同一作者的书、同事、合作者等如：按书的价值高低排序；找该书相关的资料，如出版社、作者、作者的单位等国内外研究现状-1

国内外研究现状-1

深层数据源模式抽取技术Web数据库查询接口模式抽取研究

基本思想:基于查询页面的标签布局确定接口模式，如书名：Web数据库结果模式抽取研究

基本思想:基于结果标签布局和基于实例探测确定结果数据的模式，如“书名：数据库原理”

国内外研究现状-2

国内外研究现状-2深层数据源发现技术

DeepWeb发现研究

基本思想:针对查询接口页面布局信息并结合查询探测确定是否为DeepWeb资源，如具有文本框的页面DeepWeb数据源分类研究

基本思想:基于文档分类的算法对Web数据库查询结果页面分类

基本思想:查询接口所在页面上的特征，如有书名为图书类数据源DeepWeb选择的研究

基本思想:主要考虑接口模式属性和用户查询属性间的匹配关系，没有涉及数据源质量、数据源的查询选择度等

国内外研究现状-3国内外研究现状-3实体关联关系发现基于属性文本特征获取实体间的关联关系

基本思想：若两个实体记录在描述属性上越相似，它们就越有可能相互等价，二者的语义关联也就越强。基于上下文语义信息获取实体间的关联关系

基本思想：若实体的上下文语义信息之间存在着较多的联系，则它们将具有较强的语义关联。

国内外研究现状-4

国内外研究现状-4

DeepWeb数据整合技术：主要是对相似重复记录的识别半结构化的XML模式上展开

基本思想：考虑树结构和节点内容；基于实体表示形式转换

基本思想：归纳出实体规则，并以DBLP和Wikipedia为标准进行匹配；用聚类算法基本思想：基于聚类方法实现国内外研究现状-5

国内外研究现状-5

查询松弛技术基于查询属性松弛

基本思想：依次去除不重要的查询属性基于实例的查询松弛

基本思想：扩大查询谓词的选择范围国内外研究现状-6

国内外研究现状-6

在DeepWeb研究领域中，已展开了相关的工作，典型的有：DeepWeb数据源发现与分类、查询页面接口抽取与查询接口间映射和响应页面实例信息抽取等，并取得了一定的进展。但总的来说，目前人们对DeepWeb的研究还只是处于探索性阶段，还不存在一个比较成熟的DeepWeb数据库集成和检索系统，付诸于应用还有一段距离。可见，为支持DeepWeb信息整合，还存在许多挑战性工作。一个DeepWeb数据库集成系统在该集成系统下的相关研究内容DeepWeb集成系统框架结构数据源分类数据源选择接口模式抽取数据抽取与模式识别松弛查询

重复记录识别结果实体Top-k一个面向图书的DeepWeb数据库集成系统18现有DeepWeb集成框架模型数据供应模式(DataFeed)数据收集模式（DataCollection）元搜索模式（Metasearch）19Web数据库集成框架设计思想面向特定领域应用领域知识解决全局抽象和语义信息支持提供查询探测实例基于元搜索模式能够提供即时更新的数据记录具有较好的伸缩性具有较低的维护代价20一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库21一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库接口模式抽取文本输入框<inputtype=“text”name=“tn”>下拉框<selectnme=“sn”>单选按钮<inputtype=“radio”name=“rn”>复选按钮<inputtype=“checkbox”name=“rn”>值标签属性标签HTML表单介绍接口模式抽取查询接口设计规律-属性标签匹配方向LeftUp接口模式抽取查询接口设计规律-范围词的连接作用接口模式抽取查询接口设计规律-元素与文本的分布规律按行分布接口模式抽取查询接口设计规律-元素分组与标签匹配规律元素C1C2C3C4UpDownLeftRightQE-Extractor模型接口模式抽取28一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库29基于领域主题的数据源分类Web数据库分类的意义高效管理Web数据库资源，辅助用户搜索其所需的资源。基本思想根据领域中记录的某一属性将其分为不同的内容主题，如图书可以分为“计算机”，“小说”等；为每个内容主题选择匹配的样本实例；使用内容主题的样本实例探测Web数据库，根据返回的查询结果数量判断。要注意的特性对于不同的Web数据库所包含的数据规模不同；不同主题包含的数据记录数量存在很大的差异；查询接口对应的查询方式不同30基于查询探测的矩阵分类法基于领域主题的数据源分类31基于样本实例的查询探测样本实例的训练在内容主题内：去除关键字重复的样本实例在内容主题间：去除主题区分度低的样本实例查询结果数量的估计数据源的不同查询处理类型AandB(A&B)AorB(A|B)Q(A&B)=Q(A)+Q(B)-Q(A|B)基于领域主题的数据源分类32例：在领域中包含三个主题分类分别标记为C1、C2和C3，以及四个Web数据库标记为S1至S4

基于领域主题的数据源分类

基于主题的数据源分类例主题相对分区矩阵数据源相对规模矩阵主题规模数据源规模基于领域主题的数据源分类34查询结果矩阵的二值化与合并基于参数

对矩阵单元二值化：

xij<xik

合并规则若x’ij=y’ij

，则Fij=x’ij=y’ij；若x’ij

y’ij

，则Fij=-1对于Fij=-1的项，通过重新的查询探测确认其分类关系&基于领域主题的数据源分类35一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库数据源选择基于主要属性的数据源Top-k基本思想：

AttributebasedFrequentPatterngrowth(AFP-growth)algorithm(获得主要属性集)

产生主要属性矩阵:用Top-k算法基于互信息捕获属性关联关系产生混合矩阵:数据源选择构建基于属性的支配模式树ADP-tree-找主要属性DSID Attribute (ordered)frequentitems100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}200 {a,b,c,f,l,m,o}

{f,c,a,b,m}300

{b,f,h,j,o,w}

{f,b}400

{b,c,k,s,p}

{c,b,p}500

{a,f,c,e,l,p,m,n}

{f,c,a,m,p}{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HTableItemfrequencyheadf 4c 4a 3b 3m 3p 3min_support=3HashTabled1d1

TOP-kInvertedIndexs(dsij1,wj1)=0.7…s(dsijk,wjk)=0.2…Repositoryds1,…,dsnQueryQA=(transportation,tunnel,disaster)……transportds780.9ds10.7ds880.2ds10.2ds780.1ds990.2ds340.1ds230.8ds100.8ds1tunnelds640.8ds230.6ds100.6disasterds100.7ds780.5ds640.4k=1Sortandrankds10Aggregatescores数据源选择数据源选择模式级接口模式搜索模式（全文or题目or摘要）实例级类别覆盖度（主题）搜索准确度（依据以前的查询）质量级用户评价值平均响应时间40一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库结果数据抽取基于查询结果模式的记录抽取方法将查询结果页面转换为DOM树结构；利用查询结果模式中的记录节点路径DA，在DOM中匹配符合路径DA的节点集合；针对查询结果模式中每个属性RA的属性值的访问路径P，抽取其中内容作为查询结果记录在属性RA上的属性值。基于节点聚类的抽取方法基本方法查询结果页面DOM树建模识别数据区域与查询结果记录

结果数据抽取复杂结构页面记录识别属性集合

{RA1,RA2,…,RAn}

属性节点集合{RAx.1,RAx.2,…,RAx.m}

查询结果记录Ni={RA1.i,RA2.i,…,RAn.i}

结果数据抽取

基于关键字的数据抽取结果数据抽取结果数据抽取包装器目的使用相同的规则抽取多个查询结果页面中的数据记录；连续地访问结果页面并抽取记录。方法：基于节点路径规则对记录抽取

查询结果页面

查询结果记录

自底向上的抽取方法结果数据抽取多页面训练单页面训练Web页面集待抽取页面集页面中的同一位置可能是“折扣”或者“舱位”同种结构包含不同属性的数据构成数据使用不同的结构作为载体“出版时间”缺失结构化数据类型不唯一页面中两种结构的结构化数据自底向上的抽取方法-结构化数据异构结果数据抽取嵌套结构表结构动态增长重复结构重复结构自底向上的抽取方法-衍生结构结果数据抽取使用纯文本表示结构化数据使用特殊的文本符号分隔不同属性的结构化数据自底向上的抽取方法-结构化数据文本化结果数据抽取实体抽取重复模式抽取数据抽取自底向上的抽取方法-数据抽取模型结果数据抽取对比项自底向上的抽取方法自顶向下的抽取方法核心思想基于页面的语义特征基于页面的结构特征核心技术实体分析技术结构解析技术训练方式重复模式抽取结构相似性、相异性抽取方式抽取模式树页面定位（模板，包装器）属性标注时机开始结束适合页面包含结构化数据的主题页面结构简单的记录型页面自底向上的抽取方法-自底向上与自顶向下对比结果数据抽取52一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库查询松弛当用户的原始查询没有结果或者只有很少的结果返回时，应该如何处理？

直接告诉用户没有查询结果或者把很少量的查询结果返回给用户？

No.

在用户原始查询上进行修改，进行查询松弛，将查询松弛所得到的结果返回给用户？Yes.

现有的查询松弛方法大多数系统采用属性松弛方法，然而，多关键字属性采用值松弛的方法更好，若像其他属性一样采用属性松弛方法，则会出现一些问题优点缺点属性松弛效率高某些情况下松弛粒度过粗值松弛松弛粒度较细，可以得到更多合适的结果查询探测花费较大；且对于多关键字属性，没有较好的值松弛方法现有的查询松弛方法问题1不支持多关键字搜索功能的数据源举例

查询q:书名=数据库系统问题2需要删减查询词的举例查询q：书名=数据库系统实现，作者=王珊现有的查询松弛方法查询松弛思想松弛查询思想：Foramultiplekeywordsquery(1)ExtendingQueryWords

forsinglekeywordsquery

(2)PruningtrivialwordsfromQueryWords

(3)ResultPageEvaluation

decidewhethertofetchthenextpageornot

BookName：DatabasesystemBookName：DatabasemanagementsystemBookName：Database查询松弛执行策略详述数据源关系图(DRG)的生成ABCDABCABDACDBCDABACADBCBDCDADBC属性集{A,B,C,D}的全局数据源关系图

只包含属性{A,B,C}的查询Q的数据源关系图查询松弛执行策略详述转移数据源ABCDABCABDACDBCDABACADBCBDCDADBC带有确定属性B的查询Q的最终DRG查询松弛执行策略详述确保查全率的查询松弛过程ABBCBABC查询Qscore∈（low,high）?查询Q’查询Q{A,B,C}查询Q’{A,B}值松弛中的扩展查询词方法方法

利用支持多关键字查询的数据源的返回结果，统计出现的除原始查询词之外的词，记录出现在词组之间的位置和词频，选出top-k个词，插入原始词组中例：查询Q{书名=数据库概论}书名作者出版社数据库系统概论王珊，萨师煊高等教育出版社数据库系统概论：学习指导与习题解析王珊高等教育出版社数据库系统概论杨开英武汉理工大学出版社数据库系统概论知识要点与习题解析徐乐竹，张泽宝哈尔滨工程大学出版社数据库系统概论史嘉权清华大学出版社数据库系统概论与应用苏中滨水利水电出版社数据库系统概论—习题、实验与考试辅导史嘉权，史红星清华大学出版社大型数据库系统概论朱辉生高等教育出版社值松弛中的删减查询词方法通用的无领域限制的方法

基于词库中查询词的语义重要度，选出最重要的词进行保留查询过程中的结果评价方法获取下一页的结果页面评价

结果页面评价，是在查询所返回的结果为多页时，对数据源的当前结果页进行评价估计，以评价值来决定是否获取下一页结果页。页面评价步骤：计算原始查询和当前结果页中各结果记录的相似度根据相似度为每个结果打分根据结果记录得分计算当前结果页面得分，统计高分的结果数量当结果页面得分足够高；或高分结果数量达到一定值时，查询结束64一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库重复记录识别目的：对重复记录进行识别，减少用户对结果页面的筛选和分类的负担。

重复记录识别离线与在线相结合离线获取知识在线相似度估算二者相辅相成

重复记录识别-实体关联知识构建三阶段逐步求精策略文本匹配模型：语义分析模型：分组统计模型:多相似度估算器优势采用多相似度估算器使相似度计算更具有针对性采用多相似度估算器将有利于系统的扩展

构成估算器匹配算法相关函数文本类型相似度估算器编辑距离N-GramSmith-Waterman距离Jaro距离多相似度估算器估算器匹配算法相关函数数字类型相似度估算器精确距离、范围距离日期类型相似度估算器日期匹配算法TimeSpan()价格类型相似度估算器价格匹配算法重复实体记录的识别策略实体记录相似度的衡量不确定重复记录的处理重复记录集生成算法71一种DeepWeb数据库集成框架Web数据库分类Web数据库模式抽取Web数据库发现Web数据库元信息领域知识用户接口统一接口结果页面数据源选择查询转换结果记录抽取与标注数据集成Web数据库资源搜索查询处理离线系统在线系统Web数据库数据清洗-问题的提出Web数据库集成数据的数据质量数据中重复记录记录不完全、不精确、不正确等脏数据问题

数据源查询结果模式的异构性记录抽取错误基本思想利用数据质量高的记录修复数据质量低的记录解决方案分析全局模式中属性间函数依赖关系。查询结果记录中基于模式属性的实体识别。数据质量的评估。数据清洗集成数据清洗流程全局模式分析阶段数据源分析阶段数据清洗阶段全局模式分析阶段基于函数依赖判断集成模式可被修复的属性对于一个给定的属性Ai，如果记录中在属性Ai上的内容可以被修复，则全局模式GS中必须满足：存在属性集合X，有X

A，X

Ai；数据源分析查询结果模式质量属性完整性函数依赖完整性查询结果记录集质量数据规模每个属性列中，具有完整属性值的记录数量查询结果模式属性值质量属性值精确度与分布数值类型文本类型集成数据记录修复算法

增量式集成数据清洗算法高数据质量低数据质量排序高低修复修复前各