文件的中文标题：表示和查询相关信息完备性的模式模型和代数数据库

表示和查询相关信息完备性法特玛-祖赫拉·汉努引用此版本：法特玛·祖赫拉·汉努表示和查询相关信息完备性的模式模型和代数数据库[cs.DB]。索邦大学，2019年。英语NNT：2019SORUS110 .电话：02503212HAL Id：tel-02503212https://theses.hal.science/tel-025032122020年3月9日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire索邦大学巴黎6号博士论文集学科：信息相对信息完整性作者Fatma-Zohra HANNOU报告员：Nicole BIDOIT-TOLLUEscherseur，巴黎大学Dimitris KOTZINOSEscherseur，Cergy Pontian考试主持人：Ladjel BELLATRECHEEQUIPSEUR、ENSMA、PoitiersLaure BERTI-EQUILLEEQUIPSEUR、Aix-Marseille大学Christophe MARSALAEQUIPSEUR、Sorbonne大学Director de thèse：Bernd AMANNSchoinseur，Sorbonne UniversityEncadrant de thèse： Mohamed-Amine BAAZIZIMdC，索邦大学”Have诺贝尔物理学和化学奖v摘要信息不完整是一个主要的数据质量问题，而从不可靠来源收集的数据量越来越多，使这一问题更加严重。评估数据的完整性对于确定数据本身的质量至关重要，而且对于验证不完整数据的查询答案的有效性也至关重要。虽然有大量的工作对建模数据的完整性，推导这种完整性信息并没有得到太多的关注。在这项工作中，我们解决的问题，提取和推理的完整和缺失的信息相对信息完备性设置。在此设置下，相对于完整的参考数据集来评估数据集的完整性。 很少有工作一直致力于表示数据的完整性，在这种情况下，我们提出了两个贡献：一个模式模型，提供最小的覆盖范围内总结完整和缺失的数据分区和模式代数，用于导出最小的模式覆盖查询答案，以分析其有效性。完整性模式框架为实现许多应用程序提供了一个有趣的机会，特别是那些旨在提高受缺失数据影响的任务质量的在我们的工作中，我们解决的问题，修复从不完整的数据查询结果 数据插补是一种众所周知的用于修复缺失数据值的技术，但当应用于大型数据集时可能会产生高昂的成本。查询驱动的插补提供了一个更好的选择，因为它允许只修复与查询相关的数据。我们采用了基于规则的查询重写技术，用于估算由于数据不完整而丢失或不正确的分析查询的答案我们提出了一种新的查询重写机制，是由完整性模式模型和代数。 我们的解决方案致力于推断最广泛的缺失答案集，同时提高不正确答案的精度。在最后的贡献中，我们研究了概括任何数据片段的模式模型的泛化。 广义模式模型可用于生成数据片段在任何属性子集上的模式摘要，并且这些摘要可被查询以综合和灵活的方式分析和比较数据片段。关键词：相对信息，完备性评价，模式模型，模式代数，插补，汇总vii简历L’incomplétude 在相对信息的背景下，通过与基本参照物进行比较，可以看出对基本参照物的完整性我们认为，这两个领域的主要贡献是：一个产生最小尺寸的图案的模式，它涉及到对完整的和复杂的分区的扩展，这是一个渗透最小尺寸的图案的集合，用于分析需求响应的有效性Ce modèle de motifs offre une opportunité intéressante pour réaliser de nombreusesapplications ， en particulier celles visant à améliquant à qualité des tâches affectées par lesdonnées manquantes.Nous adoptons une technique de récriture de requêtes à base de règlespour imputer les réponses des requêtesNous étudions également la généralisation de notre modèle de motifs pour effectuer lapastièsedes fragments de données.Les resumés peuvent être interrogés pour analyzer etcomparer les fragments de données de manière qualitatique et flexible.关键词：相对信息、知识的补充、模式、模式算法、归责、综合ix德迪卡塞斯Nour-Filastine，为了所有的爱，我在你的怀抱中，我在你的怀抱中，如果我跟你说为了所有的夜晚，这些都是我们的小时光，为了所有其他人我要求你在你不理解的情况下帮助我，请把你的文件作为你不理解的情况下的证词上帝啊，如果你不对我表示怜悯，你会让我感受到力量，希望，决心也许大家都能理解，但你让我想起了我的童年，也让我想起了你的童年。巴黎冰川的早晨，你身上的太阳，你的夜晚，你的节日，你的凹痕，你的沉默，你的话语......我写一本书只是为了感谢你，因为你看起来像我，但我可以用一些我喜欢的词我亲爱的女儿，因为你是我的亲生母亲，所以我拒绝了你C’est为了你在生活中的一天，永远不要忘记，在生活中，他必须没有任何限制今天，我们两个人都在一起就像我白天和晚上一样。..........................我把这件事告诉你Mamanxi雷默西芒我对我的导演贝恩德·阿曼深表敬意和感激。D'abord，pourlaqualitédesesconseilsetdirectiviques，ainsiquesadisponibilitémalgrétoutessesresponsabilités. 贝恩德从来没有时间让我想出一些好主意，也没有时间改变我的想法。由于他的专业知识，我对他的教学质量和能力有深刻的印象我对我的回忆和信心充满了怜悯，因为我对你的一切都很难理解。我一直都有动力，因为我有局限性，当科学完成时我更有把握，当她喜欢我时我就分享快乐。他看到我的表情我感谢我的导师穆罕默德·阿明·巴齐齐教授对科学的思考，对今天的讲座的重新讲授，以及对研究工作的参与。我感谢尼科尔·比杜伊特-托吕和迪米特里斯·科齐诺斯两位专家接受我的报告员，并感谢他们提出的质量不佳的报告我感谢陪审团的所有成员，让我有机会获得协助者的荣誉，以帮助我评估我的工作，并使我能够从专家的专业知识中获益我感谢Ebita项目，它允许资助这一项目，而那些支持这一项目的成员，则丰富了我对科学问题的看法我有机会在LIP6实验室的Données基础上通过这些年的研究，在一个实验室的支持下。我非常欣赏我的朋友们的才华，因为我很感激他们能给我带来欢乐和快乐。Jegarderai de ma thèse les agréablesmemories de nos riches discussions sur la science et parfois la vie，avec ou sans caféine.谢谢安妮，卡梅里亚，休伯特，李克和斯特凡。xii当我在我的生活模式中完成任务时，我发现我有一个家庭是我所爱的，也是我一直渴望的我感谢我伟大母亲的回忆，她给我灌输了最好的价值观，给了我最好的爸爸我的上帝啊，你告诉我一所学校不告诉我，一本书也不传给我，感谢你的牺牲，你的爱，你的智慧和你的支持，谢谢你让我觉得你不是我的总理，你说你会把我的头发弄得更长，你会把头发弄得更长Maman亲爱的朋友，谢谢你的爱和你的忠诚。我觉得你是个牧师，但我不想让你在我怀疑的时候给我压力。我只想让你的女儿不再是个大姑娘Ilhem，Meriem，Hadjer，Mouloud，Yasmine即使是几百公里的距离，你的生活乐趣，你的能源消耗和你的爱情C’estPeu importe oatrila vie nous mènent，je portrai nos promesses enfantines comme uneétoile au cou，Ma fierté est sans égale.穆罕默德感谢为了大家的聚会我们就在酒吧休息为了你的支持，你的信任，你对我也很想知道我们的梦想是什么.xiii内容1介绍和动机11.1一般背景和动机21.2EBITA和智慧校园31.3实例5的挑战1.3.1挑战#1：完整和缺失的数据表示61.3.2挑战#2：查询结果注释71.3.3挑战#3：聚合数据正确性81.3.4挑战#4：汇总查询插补101.3.5挑战5：数据片段汇总111.4论文贡献121.5大纲13I相对完整性表示152数据完整性表示172.1一.导言. 182.2数据质量182.2.1数据质量问题192.2.2数据质量维度222.3数据完整性概述242.4数据完整性表示模型262.4.1缺失值表示272.4.2缺少元组表示292.5摘要383模式模型和代数413.1导言. 423.2相对信息模型42xiv3.2.1约束表423.2.2评估数据完整性443.3模型443.3.1分区模式453.3.2模式语义463.3.3图案覆盖493.4模式代数513.4.1模式运算符543.4.2重写规则和优化563.4.3安全投影583.5模式593.6独立参考文献613.7摘要624模式代数实现与实验654.1一、导言. 664.2模式代数表达式在SQL66中的转换4.3折叠数据684.4折叠模式724.5实验774.5.1数据集774.5.2模式表生成784.5.3模式查询处理814.5.4折叠模式查询结果824.6摘要84II不完整查询结果插补855数据和查询结果估算技术5.1一、导言. 885.2处理缺失数据问题885.3数据插补905.3.1基于人类的估算905.3.2自动数据填补935.3.3摘要955.4查询驱动的估算95xv5.4.1近似查询处理965.4.2动态插补5.4.3缺少元组对查询结果的975.5摘要986聚合查询结果插补1016.1导言. 1026.2动机1036.3插补模型1056.3.1聚合查询和查询模式1056.3.2估算规则和估算1076.4查询估算过程1086.4.1步骤1：注释查询结果1096.4.2步骤2：生成候选插补1116.4.3第三步：估算策略1116.4.4步骤4：插补查询生成1126.5执行1136.5.1分区模式分类1136.5.2估算查询SQL实现1156.6实验1166.6.1查询结果注释1186.6.2查询结果插补1196.7摘要121III用片段总结推理1237使用模式总结和比较数据片段1257.1导言. 1267.2动机1267.3片段和摘要模型1287.3.1数据碎片1287.3.2摘要1297.4使用片段摘要进行1307.4.1形式推理模型1307.4.2第132章推理7.5实验133xvi7.6相关工作1367.7摘要138IV结论和今后的工作1398结论和展望1418.1一般结论. 1428.2关于完整性模型的1438.2.1用户友好界面1438.2.2增量最小覆盖1458.3查询结果插补1468.3.1质量模型1468.3.2估算策略1468.3.3共享查询结果估算148附录ARésuméen Français1491„介绍和动机1如果我们知道我们在做什么，那就不叫研究了，对吧？内容- 阿尔伯特·爱因斯坦诺贝尔物理学奖1.1一般背景和动机。. . . . . . . . . . . . . . . . . . . . .21.2EBITA和智慧校园. . . . . . . . . . . . . . . . . . . . . . . . .31.3以挑战为例。. . . . . . . . . . . . . . . . . . . . . . . . . .51.3.1挑战#1：完整和缺失的数据表示。. .61.3.2挑战#2：查询结果注释。. . . . . . . . . . . .71.3.3挑战#3：聚合数据的正确性。. . . . . . . . .81.3.4挑战#4：聚合查询插补。. . . . . . . . . .101.3.5挑战5：数据片段汇总。. . . . . . . .111.4论文贡献。. . . . . . . . . . . . . . . . . . . . . . . . . . . .121.5 Thesis Outlinee13.................................................................................................................................10第1章介绍和动机1.1 一般背景和动机“世界上最有价值的资源不再是石油，而是数据。“《经济学人》的这句话充分说明了数据在我们社会中的重要性。社交网络应用程序和连接的对象已经改变了我们的日常生活，第四次工业革命正在将静态生产流程转变为动态和数据驱动的制造工作流程。数以百万计的用户在互联网上订购食物，在亚马逊上购物，要求谷歌在他们的地方附近找到一家意大利餐馆，并在Facebook上交换信息。 物体变得智能，房屋可以自我调节能源消耗，汽车可以自动驾驶，很快机器人将进行医疗诊断。现代飞机，如这场数据革命得到了技术进步、新算法和丰富数据存储能力的支持，这些技术存储能力使得能够创建新的服务、工具以及生产和消费大量数据的行业这方面的一个主要挑战是最大限度地提高数据质量例如，IBM表示，美国每年3.1万亿美元的损失主要归因于不准确、过时或不完整的数据，这些数据不符合特定的任务要求。该报告认为，数据质量是公司发展的最重要障碍之一，排在物质工具或人类专业知识之前。尽管产生了大量的数据，但“缺失数据”是一个常见的质量问题[Her+07]，它源于多种原因：物理异常，数据库设计，人为错误，缺乏来源或隐私规则。不完整数据问题产生了一些有趣的研究挑战，关于缺失信息的表示和处理尽管已经开发了许多数据模型来表示任何类型的复杂数据，但在这些模型中准确表示缺失的信息通常是困难的。第一种解决方案是引入占位符来指示应该填充的缺失信息 这种占位符是E.F. Codd[Cod79]的形式是一个“缺失信息”的空符号。Codd的null-“values”表示缺失或未知的属性值，并且仍然是数据库中缺失信息的最常用表示。这种解决方案的一个显著缺点是很难就空符号的唯一含义及其查询语义达成一致。例如，如果A为空值（未知），则A=3这样的简单筛选条件无法评估为true或false另一个问题与聚合函数有关，它使用空值产生不正确的结果 这些限制导致了“更强”的表示系统的发展，以更精确地描述丢失的数据，更好地理解它们对查询结果的影响。例如，c-tables[Imi+88 a]使用“标记的”空值来描述缺失值，这些值可以由不同的元组属性共享此设置下的完整性评估不包括缺失数据元组，这些元组被视为假（封闭世界假设）。的31.2EBITA与智慧校园开放世界假设（Open World Assumption）是一种范式，它假设并接受数据库中不包含的额外数据元组（缺失元组）的存在，但由于缺乏关于缺失内容的知识，只有少数查询找到完整在[Mot89]中首次引入了一个中间假设，为描述缺失元组提供了更好的理论基础所提出的模型假设存在一个虚拟数据库与一组完整的元组，这可以与可用的，不完整的数据库进行比较在这种情况下，被称为部分封闭世界假设，已经提出了大量的表示系统来建模数据不完整性。 相对完备性的概念已被提出[Fan +10a]。 代替虚拟参考数据库，相对完整性是相对于物化参考数据集定义的，其允许更有效和精确的质量评估过程[F an15]。在这篇论文中，我们采用相对完整性的方法来解决几个挑战有关的表示不完整的信息注释和修复查询答案。 我们将在下一节通过一个具体的应用场景介绍这些挑战。1.2 EBITA与智慧校园本论文得到了EBITA项目（2016-2018）的资助，这是一个法国-德国研究项目，将索邦大学与德国弗劳恩霍夫研究所[Ebi]联系起来。EBITA是一个为期两年的项目，致力于探索各种智能物联网应用领域（如移动性，环境，能源消耗）的数据库和机器学习研究机会。该项目的一个用例是索邦大学Jussieu网站的智能校园场景。 Jussieu校区配备了传感器网络，可以测量多个能源和环境指标：温度，压力，电力消耗（照明，供暖，供电），水消耗。 这些传感器每小时连续产生多个测量值，数据库每天更新最新值。 Jussieu校园共有96栋建筑，传感器分布在这些建筑物中。 作为该项目的一部分，我们可以访问位于校园地图上突出显示的建筑物中的5，000个传感器产生的数据（图1.1）。 如地图所示，建筑物位于编号的塔楼之间，每栋建筑物都由它所连接的两座塔楼的编号来识别。例如，建筑物1323将塔13与塔23连接。多个其他数据来源的房间占用，会议室规划，地点等。也被收集来丰富原始传感器数据。 表1.1显示了园区位置和传感器的一些一般统计数据。