基于容斥原理的Skyband基数估计方法

Skyband查询是决策支持领域一类非常重要的查询.为了使数据库系统有效支持Skyband查询,必须解决Skyband基数估计的问题,即估计Skyband查询结果中包含的Skyband元素数,因为Skyband基数估计对于扩展数据库系统查询优化器的代价模型以便能够对Skyband查询进行优化非常重要.基于容斥原理的推广形式对Skyband基数进行理论分析并给出了时间和空间代价很小的对Skyband基数进行估计的算法.实验结果表明,该方法能够准确地对Skyband基数进行估计.     

基于机器学习的基数估计技术综述

基数估计是数据库关系系统查询优化器的基础和核心.随着人工智能技术的发展,其在数据处理、提取数据之间的关系等方面显现出优越的性能.近年来,基于机器学习的基数估计技术取得了显著的进展,受到了学术界的广泛关注.首先总结了基于机器学习的技术估计技术的发展现状,其次给出了基数估计的相关概念及其特征编码技术.接着建立了基数估计技术的分类体系.在此基础上,进一步将基于机器学习的基数估计技术细分为查询驱动、数据驱动和混合模型这3类基数估计技术.然后重点分析了每一类技术的建模流程、典型技术和模型特点,并对其在SQL和NoSQL中的应用进行了分析和总结.最后讨论了基于机器学习的基数估计技术面临的挑战和未来的研究方向。     

基于查询特征表示学习的联邦复杂查询基数估计

准确的基数估计是实现最佳查询计划的关键因素,现有方法大多基于深度学习来解决基数估计问题。然而,这种基于RDF图模式的方法专注于具有特定拓扑结构的简单查询,适用范围有限,缺乏对现实场景中频繁使用的复杂类查询的支持。为了解决以上问题,提出一种基于查询特征表示学习的联邦复杂查询基数估计模型。该模型主要处理带有FILTER或DISTINCT关键字的复杂查询,使用新提出的FILTER查询特征化方法将SPARQL查询表示为特征向量,通过模型预测查询基数。同时使用模型预测DISITINCT查询中唯一行比率。在LUBM数据集上的实验表明,与最先进的基数估计方法相比,该模型在估计质量上表现优异,平均估计误差中位数可达1.16,并对多连接查询的基数估计表现出潜力和可扩展性。     

面向多表连接查询优化的基数估计方法

基数估计是实现数据库多表连接（JOIN）查询优化的重要手段之一。对数据量较大的数据表进行基数估计时常用数据抽样来获得较小的样本,从而估计各种查询负载下所需的数据基数。在单表上利用数据抽样来完成基数估计的方法已经得到广泛研究,但在多个数据表的抽样样本总体存储预算存在限制时,目前仍缺乏有效的多表间样本数划分方法使得整体基数估计达到较优。为此,提出一种面向多表JOIN查询优化的基数估计方法,针对一组给定的含有复杂多JOIN操作的查询负载,为其合理分配数据库中每个表的抽样率,从而在满足样本大小总和限制的同时使得基数估计准确率达到最高。将上述过程抽象为一个抽样率分配搜索问题,在数据库数据抽样问题中引入贝叶斯优化搜索算法,利用该算法快速搜索出不同表之间抽样样本大小的分配比例,使得有限时间内获得的样本分配方案对应的基数估计准确率最高,从而达到查询优化的目的。在TPC-H数据集上的实验结果表明,在相同时间内确定多JOIN操作查询负载下基数估计准确率最高的抽样比例方案时,相比随机搜索算法,贝叶斯优化算法所得方案对应的基数估计误差率降低54.8%~60.2%。     

基于增量局部加权学习的查询模板自适应基数估计

基数估计是基于代价查询优化的关键步骤,已经被研究了近40年.传统方法如基于直方图的方法在一些假设如属性相互独立、相交的表满足包含原则等成立时能基本满足准确性要求.然而,在真实运行环境中这些假设往往不再成立,可能导致基数估计严重错误进而造成查询延迟.近年来,随着数据的增多和新硬件的发展,使用机器学习方法来提高基数估计的质量成为了可能.由于基于代价的查询优化主要根据查询中子执行计划的估计代价来选择最优的查询执行计划,因此,有一些最近的工作针对一些关键的子执行计划模板建立相应的局部学习模型,取得了不错的进展.但是,这些局部模型主要用于查询(查询空间)分布和数据(数据库数据)分布不变的场景,而在真实运行环境中,它们往往不断地发生变化,限制了这些估计技术的有效性.在本文中,我们针对子执行计划模板在查询分布和数据分布不断变化的环境下提出了一种使用增量的局部加权学习进行自适应基数估计的方法.具体地说,首先抽取子执行计划的语义和统计特征使之能代表当前查询和数据的特性,然后使用增量的局部加权学习模型根据查询分布和数据分布的变化进行自适应的学习,实现基数估计.最后,通过对比实验验证了本文方法的有效性.     

基于树型门控循环单元的基数和代价估计器

基数估计和代价估计可以引导执行计划的选择,估计准确性对查询优化器至关重要.然而,传统数据库的代价和基数估计技术无法提供准确的估计,因为现有技术没有考虑多个表之间的相关性.将人工智能技术应用于数据库(artificial intelligence for databases, AI4DB)近期得到广泛关注,研究结果表明,基于学习的估计方法优于传统方法.然而,现有基于学习的方法仍然存在不足:首先,大部分的方法只能估计基数,但忽略了代价估计;其次,这些方法只能处理一些简单的查询语句,对于多表查询、嵌套查询等复杂查询则无能为力;同时,对字符串类型的值也很难处理.为了解决上述问题,提出了一种基于树型门控循环单元, Tree-GRU (tree-gated recurrent unit)的基数和代价估计方法,可以同时对基数和代价进行估计.此外,采用了有效的特征提取和编码技术,在特征提取中兼顾查询和执行计划,将特征嵌入到Tree-GRU中.对于字符串类型的值,使用神经网络自动提取子串与整串的关系,并进行字符串嵌入,从而使具有稀疏性的字符串变得容易被估计器处理.在JOB、Synthetic等数据集上进...     

MS SQL Server查询系统及系统优化方法的研究

查询优化是数据库系统设计时要考虑的重要方面，使用ＳＱＬ进行数据库查询时，也有许多影响系统性能的因素。本文讨论了关系数据库处理高级查询的步骤和几种不同的查询优化方法，介绍了Ｍｉｃｒｏｓｏｆｔ ＳＱＬ Ｓｅｒｖｅｒ的基于成本的优化器所采用的优化策略，并讨论了影响Ｍｉｃｒｏｓｏｆｔ ＳＱＬ Ｓｅｒｖｅｒ性能的几个因素和解决方法。     

基数估计算法参数的分析与优化

基数估计算法(Cardinality Estimation Algorithm)是基于概率统计理论的估算给定数据集中不重复元素基数的算法。算法中的Hash函数和相关参数的设置是影响算法性能的两个关键因素。针对这两个问题展开研究,提出了一种基数估计的优化算法,它可以根据数据规模和数据类型动态调整Hash函数和分桶参数,以提高算法的精度和稳定性。实验结果表明,改进的基数估计算法在经过训练之后,相比传统估计算法,其估计精度和稳定性均有所提高。     

融合启发式和Boosting的子图匹配基数估计方法

由于在建模关联信息方面具备天然优势,图数据已在社交网络、知识表示等方面被广泛运用.但是相较于传统的关系型数据库系统,图数据管理中的以子图匹配为代表的一系列基础操作仍有进一步优化的空间.在一个完善的图数据库系统中,为实现多个子图匹配任务的优化调度,往往需要对每个任务的代价,尤其是匹配结果的基数进行准确预估.然而,现有的子...     

一种触发的动态查询再优化方法

对数据库系统内长期运行的查询处理的查询优化提出了一种触发的动态查询再优化方法，对这种动态再优化机制的动态评价方法、原则以及查询计划的重构进行了说明，着重讨论了触发动态再优化的触发机制和查询处理。     

一种基于势结构分组思想的任一时间联盟结构生成

联盟形成是多agent系统中的一个关键问题,找到最优的联盟结构是NP-完全的.Sandholm和Larson等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能完全解决的问题.在任务分配等实际问题中,不同联盟存在同势同值的特征,或同势的2个联盟的值相差不大.研究了最优势结构生成问题,分析了基于势结构的分组思想,并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法.算法在最小搜索之后给出进一步降低限界至2的搜索,也讨论了限界从2降到1的过程中由底向上的补充搜索.从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法,是基于势结构的联盟生成问题的一个重要进展.     

基于Goldwasser-Micali加密系统的隐私交集基数协议研究*

安全两方计算研究的是如何使两个互不信任的参与方在不借助任何第三方的情况下实现保护隐私的协同计算。隐私交集基数是一类重要的安全两方计算问题,其研究如何使各自拥有一个有限集合的两个参与方,在保护自己输入隐私的前提下,其中一方输出他们的集合交集的基数,而另一方没有输出。在半诚实攻击者模型下,对隐私交集基数问题的解决方案进行了研究,以Goldwasser-Micali加密系统作为基本的密码学工具,构建了一个隐私交集基数协议,证明了其正确性,并在半诚实攻击者模型下给出了基于模拟器的安全性证明。与已有方案相比,提出的协议在某些性能上更具优势。     

基于势结构的任一时间联盟结构生成算法

联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的.Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法,对于较小的限界明显地优于Sandholm等人给出的算法.深刻分析了联盟结构间的关系,采用更小的搜索粒度(势结构),提出基于势结构的任一时间算法,在搜索最底两层及顶层后,进一步搜索势结构集合CCS(n,6)对应的未搜索过的联盟结构,渐进地给出越来越低的限界,大大改进了Sandholm等人(快1035倍,当n=100,K=2)和Dang等人(快1018倍,当n=100,K=3)的工作.     

不含非平凡函数依赖或多值依赖的关系的势

本文讨论了一类特殊的Armstrong关系－不含非平凡函数依赖或多值依赖的关系，给出了这类关系的判定条件，得到了这类关系的势的下界值，并使用基于关系的投影运算方法，得到了精确的下界值，同时还涉及到了多值依赖的情形。     

基于数据垂直划分的高效并行Skyline查询

基于数据垂直划分的分布并行Skyline查询算法大多并行性较低,无法适应海量分布式数据的快速响应要求。为此,在BDS算法的基础上提出一种更高效的分布并行Skyline查询算法PDS-VP。其中,节点被分为协调者与参与者,原本由协调者节点完成的随机访问和本地Skyline计算分发给各参与者节点进行处理,以提高算法的执行效率。实验结果证明,该算法提高了原算法的并行性和运行效率。