基于Chase的方法实现星型模式中分析查询的一致性结果

《Information and Computation》：A Chase-based Approach to Consistent Answers of Analytic Queries in Star Schemas

　　多米尼克·劳伦特|尼古拉斯·斯皮拉托斯ETIS实验室——法国塞吉-庞图瓦兹的ENSEA、CY Cergy Paris大学及CNRS，邮编F-95000，法国

摘要
我们提出了一种方法，用于在基于星型模式的数据库中处理可能包含聚合操作符且可能存在缺失值和不一致数据的查询，从而得到一致的答案。我们的方法基于之前针对多表数据库中标准查询（不含聚合操作符）的一致性查询处理研究。在之前的研究中，我们提出了多项式算法，根据查询是否包含选择条件，来计算查询的精确一致答案或该答案的上下界。

在本研究中，我们考虑基于星型模式运行的数据库。我们将这类数据库称为数据仓库，并将之前的工作扩展到涉及聚合操作符的分析查询上。在此背景下，我们提出了特定的算法，用于计算查询的精确一致答案，无论这些查询是否为分析查询，前提是查询中的选择条件满足独立性属性（即该条件可以表示为多个仅涉及单个属性的条件之和）。我们表明，这些特定算法的整体时间复杂度为O(W·log W)，其中W为数据仓库的大小。此外，我们还讨论了在我们的方法框架下涉及“分组子句”与“拥有子句”的分析查询情况。

引言
高效处理涉及聚合操作符的查询，即分析查询，是数据库领域中的一个重要问题，过去三十年来一直有大量研究致力于此。分析查询的主要目的是从大量数据中提取有用的“统计信息”，这些数据来自不同类型数据库的整合，存储在所谓的数据仓库中[1][2]。出于效率考虑，数据仓库中的数据通常按照非规范化模式组织，即星型模式。星型模式由两种类型的关系模式（也称为表）组成：事实表和多个维度表。在这种背景下，分析查询可视为包含某种聚合操作符的SQL分组查询，这些聚合操作符如min、max、count或sum，用于对事实表中的度量属性进行运算。下面通过一个例子来说明星型模式和分析查询的概念。

示例1
假设有一家公司在全球各地设有分支机构，向客户销售各类产品。为分析公司运营效率，人们可能会关注过去一年中每个分支机构的产品销售数量。为了高效回答此类查询，考虑到数据仓库中可能存储着数十亿条销售记录，这些数据会按照以下星型模式进行组织：
- 事实表：该表用F表示，用于存储公司的所有销售记录。在我们的示例中，F包含KB、KP、KC、KD和Qty这些属性，其主键为KBKPKCKD，这意味着F必须满足函数依赖关系KBKPKCKD→Qty。换句话说，不可能存在同一分支机构、同一产品、同一客户以及同一日期下的两条不同销售记录，且对应的销售数量不止一个。
- 维度表：共有四个维度表，分别对应KB、KP、KC、KD这几个属性：
- 分支机构表：包含KB、B_Town、B_Ctry这些属性，分别代表分支机构标识、所在城市以及所在国家。KB是分支机构表的主键，因此该表必须满足函数依赖关系KB→B_Town和KB→B_Ctry。
- 产品表：包含KP、P_Type、Price这些属性，其中KP是产品标识，P_Type和Price分别代表产品的类型和价格。KP是产品表的主键，因此该表必须满足函数依赖关系KP→P_Type和KB→Price。
- 客户表：包含KC、C_Name、C_Addr这些属性，分别代表客户标识、客户姓名和客户地址。KC是客户表的主键，因此该表必须满足函数依赖关系KC→C_Name和KC→C_Addr。
- 日期表：包含KD、Month、Year这些属性，分别代表日期标识/键、日期的月份和年份。KD是日期表的主键，因此该表必须满足函数依赖关系KD→Month和KD→Year。

此外，通常还会设置引用约束，以确保F表中出现的任何键值也出现在相应的维度表中。在我们的示例中，这些约束通过以下四组包含关系体现：πKB(F)?πKB(Branch)、πKP(F)?πKP(Prod)、πKC(F)?πKC(Cust)和πKD(F)?πKD(Date)。

在这种架构下，典型的分析查询是显示2024年期间每种产品的总销售数量。该查询可以用SQL表示为：
Q：select KP, sum(Qty) from J where Year=2024 group by KP
这里的J表示所有维度表与事实表F的（无损）连接结果（不过实际上只需连接F、Prod和Date三张表即可简化查询）。

如何高效地处理海量数据中的分析查询已有很多研究，但这超出了本文的范围；关于标准SQL查询优化的内容可参考[3]，而针对分析查询的特定优化技术则可参考[15]。

目前，大多数优化分析查询性能的方法都假定数据仓库满足函数依赖关系和引用约束。然而在实践中情况往往并非如此，因为数据仓库可能存在数据不一致和缺失值的问题。例如，在上述示例中，某个客户在数据仓库中可能有两个不同的地址（一个在巴黎，另一个在雅典），这就违反了函数依赖关系KC→C_Addr；或者产品表中可能缺少某些产品的价格信息。需要指出的是，对于上述查询而言，这些“不一致性”不应影响查询结果的计算，因为查询并未涉及客户地址或产品价格。另外还需注意，如果事实表F中存在某个产品标识，但产品表Prod中不存在该标识——这违反了引用约束πKP(F)?πKP(Prod)——那么在计算上述查询的答案时，仍可处理所有涉及该产品的销售记录。这是因为在计算该查询的答案时，客户表Cust中所有属性中，仅需用到当前正在处理的F表中记录的KC值即可。

更为棘手的情况是，当查询的选择条件为Year=2024且C_Addr=Paris时。因为在对地址可能在巴黎的客户的所有交易进行处理时，其中一些客户的地址可能违反客户表中的函数依赖关系KC→C_Addr。处理这类不一致性问题，也就是为分析查询计算一致答案的问题，并非易事，正如[16][17]中所论述的，用于处理标准非分析查询的技术无法直接应用于分析查询。

为应对数据仓库中的数据不一致和缺失值问题，我们的方法基于我们之前[4]中关于多表数据库中标准非分析查询的一致性查询处理研究。在之前的研究中，我们提出了多项式算法，根据查询是否包含选择条件，来计算标准非分析查询的精确一致答案或该答案的上下界。在本文中，我们展示了如何在星型模式下有效计算精确一致答案，前提是查询的选择条件满足独立性属性。下面我们将结合示例1说明该方法的主要特点。继续示例1：观察图1中展示的表格，结合示例1中先前提到的约束条件，我们可以发现以下几点：
- 由于事实表F的前两行数据，函数依赖关系KBKPKCKD→Qty并未得到满足；同样，由于产品表Prod的前两行数据，函数依赖关系KP→Price也未得到满足。而之前提出的其他函数依赖关系均得到满足。
- 由于F表中存在KP值为p3的记录，而产品表Prod中不存在该值，因此包含关系πKP(F)?πKP(Prod)不成立；不过之前提出的其他包含关系均得到满足。
- 分支机构表和客户表中存在缺失值：分支机构表的第二行缺少B_Ctry属性的值，而客户表的第二行和第三行分别缺少C_Addr和C_Name属性的值。

显然，计算上述分析查询Q的答案存在困难。为解决这一难题，我们的方法如下：不对实际存在数据不一致的问题数据仓库直接处理查询Q，而是应用我们之前[4]中提出的修正程序生成下表；然后以该表作为查询回答的依据。我们将这个表称为修正表，其特点如下：
1. 与标准的修正程序不同，我们的修正表会考虑函数依赖关系方面的不一致性：键为(b1 p1 c1 d1)的记录对应的Qty值为10和50同时出现，而键为p1的记录对应的Price值为75和80同时出现。这表明根据 Qty值是10还是50，以及Price值是75还是80，共有四种可能的修正方式。
2. 与常规修正过程一样，一些缺失值也被“推断”出来：在客户表的修正表中，与KC值为c2相关的C_Name和C_Addr属性的缺失值分别被替换为Jane和NY。

至于上述分析查询Q的一致答案，我们采用传统方法[5][17]，即将事实表中出现的每一个KB值，与在所有修正方案下通过查询计算得到的聚合值的“最小”区间关联起来。在这个示例中，根据不同的修正方式，计算结果要么为{?p1, 30?, ?p2, 40?, ?p3, 15?}（即第一行的Qty值设为10时的结果），要么为{?p1, 70?, ?p2, 40?, ?p3, 15?}（即第一行的Qty值设为50时的结果）。因此，查询Q的一致答案表示为{?p1, [30, 70]?, ?p2, [40, 40]?, ?p3, [15, 15]?}。

需要强调的是，尽管修正表中的第2、3、4行存在缺失值，但在计算一致答案时仍将它们纳入考虑范围，因为这些行中包含计算所需的所有属性值。而第5行因查询Q限定了年份为2024而被排除在外；最后一行则因缺少关键属性值也被排除。

通过这个示例，我们可以总结本文的主要贡献如下：(a) 我们提出了特定的算法，用于在星型模式下计算查询的精确一致答案，无论查询是否为分析查询，前提是查询的选择条件满足独立性属性；(b) 我们证明了这些特定算法的整体时间复杂度为O(W·log W)，其中W为数据仓库的大小；(c) 我们还在我们的方法框架下，探讨了涉及“分组子句”与“拥有子句”的分析查询的情况。

本文的结构如下：第2节回顾了我们之前[4]中的主要研究成果，当前方法正是基于这些成果发展而来。第3节首先阐述星型模式的定义，并论证[4]中的方法适用于这种场景。第4节探讨了星型模式下的修正概念。第5节探讨了在标准投影选择查询以及分析查询情况下，如何得到一致的查询结果。第6节中，我们提出了高效计算分析查询一致结果的算法，或者在某些情况下给出一致结果的近似值。第7节将我们的方法与文献中的其他方法进行比较，第8节则总结了本文的内容，并为未来的研究方向提出了建议。

基本定义与符号
与[4]、[6]中所做的类似，我们采用了文献[3]中介绍的关系数据库的基本概念。在此背景下，我们考虑一个有限的属性集U={A1,…,An}，称为域，假设每个属性Ai都对应一个值域，记为dom(Ai)。U的非空子集R={Ai1,…,Aip}被称为（关系）模式，简记为Ai1…Aip（即由其属性连接而成）。给定这样的模式R=Ai1…Aip，R上的元组t是一个……

我们方法的背景
首先，我们从文献[1]、[3]中了解到，我们方法中所考虑的星型模式由以下表格和约束条件构成：
•n个维度表D1,…,Dn。对于i=1,…,n，Di的定义基于属性Ki, Ai1,…, Aidi。对于i=1,…,n，Di的模式记为sch(Di)，而集合sch(Di)?{Ki}则记为sch*(Di)。
•一个基于K1,…,Kn,M1,…,Mp定义的事实表F。属性M1,…,Mp被称为度量值，我们将所有度量值构成的集合记为M，即M={M1,…,Mp}。
•FD=?i=1i=n{Ki}

修复及其基本属性
在本节中，我们将[4]中给出的修复定义应用到星型表的情况，然后进一步研究星型表的修复方法。

一致查询响应
此后，给定一个星型表T，我们考虑基于SQL语法对T进行的各种查询：
1.标准查询（或简称查询），将在下一节中定义。这类查询是简单的投影选择查询，形式为select X from T where Γ，其中X是属性列表，Γ是可选的选择条件。
2.没有分组子句的分析查询，见第5.3节。这类查询的形式为select X, aggr(Mi) from T where Γ，其中X和Γ的含义如上所述。

计算分析查询的一致结果
在本节中，我们给出了计算分析查询一致结果的算法，首先是无分组子句时的情况，然后是有分组子句时的情况。本节还考虑了包含分组且有子句的分析查询情况，而单独使用distinct子句的内容则是最后一小节的主题。我们需要再次强调，查询中的选择条件被假定是相互独立的。

相关研究
自从在[9]中提出不一致数据库中的一致查询响应问题以来，这一领域已经引发了大量的研究工作。这些研究最初集中在不涉及聚合运算符的合取查询和自连接查询上。后来在[16]中引入了包含聚合运算符以及可能包含分组子句的查询情况，并在[17]中进行了进一步研究。这些方法针对的是约束条件为唯一键约束的关系，它们依赖于早期的研究成果。

结论性意见
数据分析需要收集和整合来自不同来源、存储在特定类型模式下的数据库中的数据，这种模式被称为“星型模式”。此类数据库在文献中被称为数据仓库[1]。因此，这类整合后的数据往往存在不一致性和缺失值。在本文中，我们提出了一种有效计算数据仓库中分析查询一致结果的方法。

CRediT作者贡献声明
Dominique Laurent：写作——审稿与编辑，写作——初稿撰写，验证，研究，形式分析，概念设计。Nicolas Spyratos：写作——审稿与编辑，写作——初稿撰写，指导，研究，形式分析，概念设计。

利益冲突声明
作者声明他们没有已知的可能会影响本文所述工作的财务利益或个人关系。