物化视图选择和优化方法及装置

摘要

本发明涉及计算机数据处理领域，提出了一种物化视图的选择和优化方法，旨在解决海量数据环境下物化视图的选择、优化和更新问题。该方法包括：获取数据库的信息，根据信息从数据库中获得的带有聚集函数的分组数据，并生成分组数据集合；分解分组数据的非分布式聚集函数，生成分组数据的分组数据元，得到分组数据元集合；将具有相同的数据维度、聚集操作表达式的分组数据元确定为同一分组数据族；建立每个分组数据族所对应的统计二叉树模型，由此建立面向物化视图优化的最小线性规划模型，得到优化的物化视图集合，基于物化视图集合，重构分组数据，依据与物化视图相关的事实表的变化，更新物化视图。该方法能够在海量数据的统计分析中快速响应。

权利要求

1.一种物化视图选择和优化方法，其特征在于，所述方法包括如下步骤：步骤1：获取与数据库相关的数据库信息，根据所述数据库信息从所述数据库中获得带有聚集函数的分组数据，并生成分组数据集合；其中，所述分组数据集合包括各分组数据的查询频率，所述信息包括分组数据的聚集函数的聚集操作表达式；

步骤2：分析所述数据库中的事实表和维度表，获得各所述分组数据的数据维度和数据粒度；

步骤3：分解所述分组数据集合中分组数据的非分布式聚集函数，生成分布式聚集函数；

步骤4：解析所述分组数据集合中的每组分组数据，生成所述分组数据的分组数据元，得到分组数据元集合；

步骤5：将所述分组数据集合中的具有相同的数据维度、相同的聚集操作表达式的分组数据元规划为同一分组数据族；

步骤6：建立每个分组数据族所对应的统计二叉树模型，并基于所述统计二叉树模型建立面向物化视图优化的最小化综合线性规划模型，得到优化的物化视图集合；

步骤7：基于物化视图选择和优化得到的优化物化视图集合，重新构造所述分组数据集合中的每一组分组数据；

步骤8：依据与物化视图相关的所述数据库中的事实表的变化，对所述物化视图的数据作同步变化。

2.根据权利要求1所述的方法，其特征在于，所述聚集操作表达式包括独立聚集操作表达式和可分性聚集操作表达式；所述独立聚集操作表达式是由所述数据库中原始数据字段所构成的表达式，所述可分性聚集操作表达式是由多个独立聚集操作表达式通过算数运算式构成的表达式。

3.根据权利要求2所述的方法，其特征在于，步骤3中生成分布式聚集函数，其方法为：分解所述非分布式聚集函数的聚集操作表达式，得到元聚集操作表达式；所述元聚集操作表达式为不包含聚集函数的表达式；

依据所述非分布式聚集函数所分解出的元聚集操作表达式，生成分布式聚集函数。

4.根据权利要求3所述的方法，其特征在于，所述“分解所述非分布式聚集函数的聚集操作表达式，得到元聚集操作表达式”，其方法为包括：步骤31，判断所述聚集函数的中聚集操作表达式的类型；如果所述聚集操作表达式为独立聚集操作表达式，执行步骤32；如果所述聚集操作表达式为可分性聚集操作表达式，执行步骤33；

步骤32，判断所述聚集操作表达式中是否包含聚集函数，如果不包含执行步骤321，否则执行步骤322；

步骤321，所述聚集操作表达式为元聚集操作表达式；

步骤322，按聚集函数的嵌套顺序从最外层逐步向内分解，直至所述聚集函数的聚集操作表达式中不包含聚集函数为止所得的表达式为所述聚集操作表达式的元聚集操作表达式；

步骤33，分解所述聚集操作表达式为多个独立聚集操作表达式，并从所述多个独立聚集操作表达式中获得所述聚集操作表达式的全部元聚集操作表达式。

5.根据权利要求4所述的方法，其特征在于，所述步骤4中所述分组数据元集合，其生成方法包括：提取所述分组数据集合中各分组数据的数据维度、数据粒度的序列和聚集操作表达式；

构建分组数据的全部分组数据元，生成面向分布式聚集函数的分组数据元集合；所述分组数据元中只包含一个元聚集操作表达式。

6.根据权利要求4所述的方法，其特征在于，所述步骤5中所述分组数据族，其构建方法为：从各所述分组数据中选取数据维度、元聚集操作表达式相同的分组数据；

将具有相同数据维度、相同元聚集操作表达式的分组数据确定为同一分组数据族。

7.根据权利要求4所述的方法，其特征在于，所述步骤6中建立每个分组数据族所对应的统计二叉树模型，其方法包括：提取所述分组数据族中维度集合{d1,d2,...,dn}；所述维度集合{d1,d2,...,dn}中任一维度di＝[1,...,ni]的节点记为＜x1,x2,...,xn＞；

当维度集合包含的维度的数量为n时：节点＜x1,x2,...,xn＞记为节点＜＜x1,x2,...,xn-1＞,xn＞；

xn＞1时，右子枝节点＜x1,x2,...,xn＞R＝＜x1,x2,...,xn-1＞；当xn＝1时，右子枝节点＜x1,x2,...,xn＞R不存在；

所述节点＜x1,x2,...,xn＞的左子枝节点＜x1,x2,…,xn＞L＝＜＜x1,x2,…,xn-1＞R,xn＞；

由各所述分组数据的统计二叉树图存在的子枝节点构建所述分组数据族的统计二叉树图。

8.根据权利要求4所述的方法，其特征在于，所述步骤6中基于所述统计二叉树模型建立面向物化视图优化的最小化综合线性规划模型，其方法为：建立每个分组数据族Fi所对应的统计二叉树图Gi；

基于该统计二叉树图Gi建立面向该分组数据族的最小化综合查询代价的线性规划模型，该模型可表示为：约束条件为：

d(qi,MVi)∈Z+

MVi∈Nodes(G)

其中，设图Gi中相邻节点的有向边长度为1， 为分组数据族Fi中的任意一个分组数据元qi的查询频率，MVi为分组数据族Fi的物化视图，d(qi,MVi)为qi与物化视图MVi在统计二叉树图Gi中的有向通路的长度，d(qi,MVi)为有限正整数。

9.根据权利要求8所述的方法，其特征在于，所述步骤7中重新构造所述分组数据集合中的每一组分组数据，其方法为：以所述分组数据族的各所述物化视图MVi作为唯一数据来源重构所述分组数据族的任意一个分组数据元；

以目标分组数据集合的元聚集操作表达式为数据源重构所述分组数据族的任意一个分组数据。

10.一种存储装置，其中存储有多条程序，其特征在于，所述程序适于由处理器加载并执行以实现权利要求1-9任一项所述的物化视图选择和优化方法。

11.一种处理装置，包括

处理器，适于执行各条程序；以及

存储设备，适于存储多条程序；

其特征在于，所述程序适于由处理器加载并执行以实现：权利要求1-9任一项所述的物化视图选择和优化方法。

说明书

物化视图选择和优化方法及装置

技术领域

[0001] 本发明涉及数据库和数据仓库技术领域，具体涉及海量数据 环境下的物化视图选择和优化技术，特别涉及一种物化视图选择和优化方 法及装置。

背景技术

[0002] 随着大数据时代的来临，从海量的数据中分析和挖掘出具有 某类特征的数据变得越来越重要。对海量数据的分析和挖掘成为越来越多 的企业决策分析和科学管理的必要手段。但是随着企业数据的逐渐增加， 查询响应时间越来越长，物化视图(Materialized View,MV)是一种有效 的查询手段，它是通过预先计算和保存中间结果来提高数据访问时间的物 理结构，能够大幅缩短查询响应时间。然而，使用物化视图需要额外的存 储空间，并需要在数据更新时承担维护费用。物化视图的选择是在考虑查 询性能的情况下，如何选择一个合适的视图集合进行物化，使得总成本最 小。

[0003] 物化视图选择问题是NP(Non-Deterministic Polynomial，非 确定多项式)问题。目前，物化视图的选择主要有：基于数据立方体的方  法，基于MVPP(Multi-View Processing Plan，多视点处理)的方法和基于 AND-OR图的方法。但由于用户查询的复杂性，这些方法在实际应用的过 程中也存在一些不足，主要包括：计算复杂度较大，假设查询均匀分布， 不能处理嵌套查询等。

发明内容

[0004] 为了解决现有技术中的上述问题，即为了解决在实际应用的 过程中计算复杂度较大，假设查询均匀分布，不能处理嵌套查询等问题， 本发明采用以下技术方案以解决上述问题：

[0005] 第一方面，本申请提供了物化视图选择和优化方法，该方法 包括如下步骤：

[0006] 步骤1：获取与数据库相关的数据库信息，根据上述数据库 信息从上述数据库中获得的带有聚集函数的分组数据以及各个上述分组 数据的查询频率，并生成分组数据集合；其中，上述分组数据集合包括各 分组数据的查询频率上述信息包括上述分组数据的字段列表、聚集函数的 聚集操作表达式。

[0007] 步骤2：分析上述数据库中的事实表和维度表，获得各上述 分组数据的数据维度和数据粒度。

[0008] 步骤3：分解上述分组数据集合中分组数据的非分布式聚集 函数，生成分布式聚集函数。

[0009] 步骤4：解析上述分组数据集合中的每组分组数据，生成上 述分组数据的分组数据元，得到分组数据元集合。

[0010] 步骤5：将上述分组数据集合中的具有相同的数据维度，以 及相同的聚集操作表达式分组数据元确定为分组数据族。

[0011] 步骤6：建立每个分组数据族所对应的统计二叉树模型，并 基于上述统计二叉树模型建立面向物化视图优化的最小化综合线性规划 模型，得到优化的物化视图集合。

[0012] 步骤7：基于物化视图选择和优化得到的优化物化视图集合， 重新构造上述分组数据集合中的每一组分组数据。

[0013] 步骤8：依据与物化视图相关的事实表的变化，对上述物化 视图的数据作同步变化。

[0014] 在一些示例中，上述聚集操作表达式包括独立聚集操作表达 式和可分性聚集操作表达式，上述独立聚集操作表达式是由所述数据库中 原始数据字段所构成的表达式，上述可分性聚集操作表达式是由多个独立 聚集操作表达式通过算数运算式构成的表达式。

[0015] 在一些示例中，步骤3中生成分布式聚集函数，其方法为： 分解上述非分布式聚集函数的聚集操作表达式，得到元聚集操作表达式； 上述元聚集操作表达式为不包含聚集函数的表达式；依据上述非分布式聚 集函数所分解出的元聚集操作表达式，生成分布式聚集函数。

[0016] 在一些示例中，上述“分解上述非分布式聚集函数的聚集操 作表达式，得到元聚集操作表达式”，其方法包括：

[0017] 步骤31，判断上述聚集函数的中聚集操作表达式的类型；如 果上述聚集操作表达式为独立聚集操作表达式，执行步骤32；如果所述聚 集操作表达式为可分性聚集操作表达式，执行步骤33。

[0018] 步骤32，判断所述聚集操作表达式中是否包含聚集函数，如 果不包含执行步骤321，否则执行步骤322。

[0019] 步骤321，所述聚集操作表达式为元聚集操作表达式；

[0020] 步骤322，按聚集函数的嵌套顺序从最外层逐步向内分解， 直至所述聚集函数的聚集操作表达式中不包含聚集函数为止所得的表达 式为所述聚集操作表达式的元聚集操作表达式。

[0021] 步骤33，分解所述聚集操作表达式为多个独立聚集操作表达 式，并从所述多个独立聚集操作表达式中获得所述聚集操作表达式的全部 元聚集操作表达式。

[0022] 在一些示例中，上述步骤4中所述分组数据元集合，其生成方 法包括：提取上述分组数据集合各分组数据的数据维度、数据粒度序列和聚 集操作表达式；构建分组数据的全部分组数据元，生成面向分布式聚集函数 的分组数据元集合；上述分组数据元中只包含一个元聚集操作表达式。

[0023] 在一些示例中，上述步骤5中所述分组数据族，其构建方法 包括：从各上述分组数据中选取的数据维度、元聚集操作表达式相同的分 组数据；将具有相同数据维度、元聚集操作表达式的分组数据确定为同一 分组数据族。

[0024] 在一些示例中，上述步骤6中建立每个分组数据族所对应的 统计二叉树模型，其方法包括：提取上述分组数据族中维度集合{d1,d2,...,dn}； 上述维度集合{d1,d2,...,dn}中任一维度di＝[1,...,ni]的节点记为＜x1,x2,...,xn＞； 当维度集合包含的维度的数量为n时：节点＜x1,x2,...,xn＞记为节点 ＜＜x1,x2,...,xn-1＞,xn＞；xn＞1时，右子枝节点R R＜x1,x2,...,xn＞＝＜x1,x2,...,xn-1＞； 当xn＝1时，右子枝节点＜x1,x2,...,xn＞不存在；节点＜x1,x2,...,xn＞的左子枝节 点＜x1,x2,...,xn＞L＝＜＜x1,x2,...,xn-1＞R,xn＞；
由各上述分组数据的统计二叉树图 存在的子枝节点构建上述分组数据族的统计二叉树图。

[0025] 在一些示例中，上述步骤6中基于上述统计二叉树模型建立面向物 化视图优化的最小化综合线性规划模型，其方法为：建立每个分组数据 族Fi所对应的统计二叉树图Gi；基于该统计二叉树图Gi建立面向该统计家 族的最小化综合查询代价的线性规划模型，该模型可表示为：  约束条件为：d(qi,MVi)∈Z+，MVi∈Nodes(G)，其中，设 图Gi中相邻节点的有向边长度为1， 为分组数据族Fi中的任意一个分组 数据元qi的查询频率，MVi为分组数据族Fi的物化视图，d(qi,MVi)为qi与物 化视图MVi在统计二叉树图Gi中的有向通路的长度，d(qi,MVi)为有限正整 数。

[0026] 在一些示例中，上述步骤7包括：以上述分组数据族的各上 述物化视图MVi作为唯一数据来源重构上述分组数据族的任意一个分组数 据元；以目标分组数据集合的元聚集操作表达式为数据源重构上述分组数 据族的任意一个分组数据。

[0027] 第二方面，本申请提供了一种存储装置，其中存储有多条程 序，上述程序适于由处理器加载并执行以实现上述第一方面所述的物化视 图选择和优化方法。

[0028] 第三方面，本申请提供了一种处理装置，包括处理器，适于 执行各条程序；以及存储设备，适于存储多条程序；上述程序适于由处理 器加载并执行以实现上述第一方面所述的物化视图选择和优化方法。

[0029] 本申请提供的物化视图选择和优化方法和处理设备，通过数 据库的信息获得分组数据，根据数据库的事实表和维度表确定出各分组数 据的数据维度和数据粒度，解析分组数据得到分组数据元集合，将具有相 同的数据维度，以及相同的聚集操作表达式的分组数据元确定为分组数据 族，建立分组数族的统计二叉树模型，由此，建立物化视图，依据与物化 视图相关的事实表的变化，更新物化视图。实现了物化视图选择和优化中 所确定的每一个物化视图都是能够响应所对应家族的全部分组数据的最 粗粒度的聚集操作，提高了分组数据的快速响应和物化视图的最小化。

附图说明

[0030] 图1是本申请可以应用于其中的示例性系统架构图；

[0031] 图2是根据本申请的物化视图选择和优化方法的一个实施 例的流程图；

[0032] 图3为本申请提供的Northwind数据库结构图；

[0033] 图4为本申请提供的Northwind数据库统计示意图。

具体实施方式

[0034] 下面参照附图来描述本发明的优选实施方式。本领域技术人 员应当理解的是，这些实施方式仅仅用于解释本发明的技术原理，并非旨 在限制本发明的保护范围。

[0035] 需要说明的是，在不冲突的情况下，本申请中的实施例及实 施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本 申请。

[0036] 图1示出了可以应用本申请的基于统计二叉树图和线性规 划模型的物化视图选择和优化方法或物化视图选择和优化处理设备的实 施例的示例性系统架构。

[0037] 如图1所示，系统架构可以包括数据处理器101，网络102和 数据存储单元103。其中，网络102用以在数据处理器101和数据存储单 元103之间，提供通信链路的介质。网络102可以包括各种连接类型，例 如有线、无线通信链路或者光纤电缆等等。

[0038] 数据处理器101可以通过网络102与数据存储单元103之间 进行信息交互，以接收或发送信息等。数据处理器之间可以通过网络102 进行信息交互。

[0039] 数据处理器101可以是具有显示屏并支持网络通信的各种 电子设备，包括但不限于智能手机、平板电脑、膝上型便携计算机和台式 计算机以及由多个计算机构成的计算机处理系统等等。需要说明的是，数 据处理器可以包括存储数据的单元，以及，在数据处理器上装设有用于数 据处理的软件或应用。上述应用可以是，例如，从数据库中所存储的数据 中统计出某类产品的销售数据、供应商数据、客户数据等。

[0040] 数据存储单元103可以提供数据的存储，可以是数据库服务 器，还可以是各类具有数据存储及运算功能的处理器。与其通信连接的数 据处理器可以根据权限对上述数据存储单元103进行查询、修改等操作。

[0041] 需要说明的是，本申请实施例所提供的物化视图选择和优化 方法一般由数据处理器101执行，相应地，物化视图选择和优化处理设备 一般设置于数据处理器101中。

[0042] 应该理解，图1中的数据处理器、网络和数据存储单元的数 目仅仅是示意性的。根据实现需要，可以具有任意数目的数据处理器、网 络和数据存储单元。

[0043] 继续参考图2，图2示出了根据本申请的物化视图选择和优 化方法的一个实施例的流程。该物化视图选择和优化方法，包括以下步骤：

[0044] 步骤1：获取与数据库相关的数据库信息，根据上述数据库 信息从上述数据库中获得的带有聚集函数的分组数据以及各个上述分组 数据的查询频率，并生成分组数据集合，其中上述分组数据集合包括各分 组数据的查询频率。

[0045] 在本实施例中，物化视图选择和优化方法运行于其上的电子 设备(例如图1所示的数据处理器)首先，可以通过有线连接方式或者无 线连接方式从数据存储单元获得与数据库相关的信息，或直接从数据库获 得与数据库相关的数据库信息。根据上述数据库信息从上述信息所指示的 数据库中获得的带有聚集函数的分组数据以及各个上述分组数据的查询 频率。这里，上述分组数据为数据库查询中执行统计操作所对应生成的数 据集合，其中，统计操作是带有聚集函数的聚集操作。上述信息包括分组 数据的字段列表、聚集函数的聚集操作表达式，以及上述数据库的事实表 和维度表。上述事实表用来描述和存储多维数据的度量值和各个维的码值， 上述维度表用来描述维或维度的信息，是围绕事实表建立的较小的表。上 述聚集操作表达式是面向一定的数据表达式采用某个或某些聚集函数进 行聚集操作。

[0046] 上述聚集操作表达式包括：独立聚集操作表达式和可分性聚 集操作表达式，上述独立聚集操作表达式是由数据库中原始数据字段所构 成的数据表达式，上述可分性聚集操作表达式是由多个独立聚集操作表达 式通过算数运算式构成的表达式。其中，上述独立聚集操作表达式可以表 示为：AO＝AF(fields)，其中，AF∈Functions，它表示对由数据库中原始数  据字段fields所构成的数据表达式按AF函数聚集，如SUM(T1.field1+T2.field2)， SUM(T1.field1+MIN(T2.field2))。上述可分性聚集操作表达式可以表示为： 其中， 代表+、—、*、/等算术运算，  如，SUM(field1)/COUNT(*)。

[0047] 步骤2：分析上述数据库中的事实表和维度表，获得各上述 分组数据的数据维度和数据粒度；

[0048] 本实施例中，上述数据维度的数据层次结构是维层级，可以 表示成粒度从粗到细的有序集合，d＝{1,2...,n}，数据中全部的数据维度 的有序集合记为SD＝{di|di＝{1,...,ni},i＝1,...,m}。在数据维度的有序集合中，数 据维度按以下规则排列顺序：层级越多即ni越大，di越排在前面；若层级相 同，则按照维度的名称字母顺序递增排列。

[0049] 分析数据库中的事实表和维度表从而获得数据的维度和粒度。 作为示例，如图3和图4所示，使用Northwind数据库分析图4所示列表的数据 维度，其中，Northwind数据库为示例数据库，可以作为演示使用。

[0050] 通过Northwind数据库的分析，该数据库包含六个维度，按 照维度的排序规则将维度排序如下：

[0051] 时间维度：{Year,Season,Month,Day}；

[0052] d1＝dtime＝[1,2,3,4]

[0053] 雇员维度(Employees)：{Region,Territory,Employee}

[0054] d2＝demployee＝[1,2,3]

[0055] 客户维度(Customers)：{CustomerType,Customer}

[0056] d3＝dcustomer＝[1,2]

[0057] 产品维度：{Category,Product}

[0058] d4＝dproduct＝[1,2]

[0059] 运货商维度：{Shipper}

[0060] d5＝dshipper＝[1]

[0061] 供应商维度：{Supplier}

[0062] d6＝dsupplier＝[1]

[0063] 步骤3：分解上述分组数据集合中分组数据的非分布式聚集 函数，生成分布式聚集函数。

[0064] 本实施例中，根据分组数据的描述，将分组数据的聚集函数 表达式进行分解，生成分布式聚集函数。上述聚集操作表达式包括独立聚 集操作表达式和可分性聚集操作表达式，其中，独立聚集操作表达式由数 据库中原始数据字段所构成的数据表达式，可分性聚集操作表达式通过算 数运算表述的多个独立聚集操作表达式上述分组数据的描述，可以是使用 伪SQL语言进行描述，例如：

[0065] SELECT ShowFields,AO

[0066] FROM T1,T2,...,Tk

[0067] WHERE d1[x1]＝v1,d2[x2]＝v2,...,dn[xn]＝vn

[0068] GROUP BY d1[x1],d2[x2],...,dn[xn]

[0069] 其中，ShowFields表示分组数据q要输出的字段列表，AO表示 分组数据q的聚集操作表达式，T1,T2,...,Tk表示执行分组数据q所需要的事实 表，d1[x1]＝v1,d2[x2]＝v2,...,dn[xn]＝vn表示分组数据q在相对应的维层级上的具 体取值，d1[x1],d2[x2],...,dn[xn]表示对应维度和维层级分组。分组数据q可形式 化描述为：

[0070]

[0071] 即：{d1,d2,...,dn|di＝[1,...,ni]}表示q的筛选条件中维度的集合， ＜x1,x2,...,xn|xi∈di＞表示维度上对应的层级或粒度(出现在GROUP BY子句)， ＜v1,v2,...,vn＞表示在维度和粒度上的具体取值(出现在WHERE子句中)，AO 表示q中的聚集操作表达式(出现在SELECT子句中)。

[0072] 通过将分组数据集合(即QF0＝{(q0i,f0i)|i＝1,2,...,n0}中的非分 布式的聚集函数(即AVG、STDDEV和VARIANCE函数)改造成分布式的聚 集函数(SUM、MAX、MIN和COUNT函数)，得到新的分组数据集合 QF1＝{(q1i,f1i)|i＝1,2,...,n1}。

[0073] 上述分解非分布式聚集函数的聚集操作表达式，得到元聚集 操作表达式，包括：分解上述非分布式聚集函数的聚集操作表达式，得到 元聚集操作表达式，上述元聚集操作表达式为不包含聚集函数的表达式； 依据上述非分布式聚集函数所分解出的元聚集操作表达式，生成分布式聚 集函数。

[0074] 在一些可选的实施方式中，上述“分解所述非分布式聚集函 数的聚集操作表达式，得到元聚集操作表达式”，其方法为包括：

[0075] 步骤31，判断所述聚集函数的中聚集操作表达式的类型； 如果所述聚集操作表达式为独立聚集操作表达式，执行步骤32；如果所述 聚集操作表达式为可分性聚集操作表达式，执行步骤33。

[0076] 步骤32，判断上述聚集操作表达式中是否包含聚集函数， 如果不包含执行步骤321，否则执行步骤322；

[0077] 步骤321上述聚集操作表达式为元聚集操作表达式；

[0078] 步骤322，按聚集函数的嵌套顺序从最外层逐步向内分解， 直至上述聚集函数的聚集操作表达式中不包含聚集函数为止，所得的表达 式为上述聚集操作表达式的元聚集操作表达式。

[0079] 步骤33，分解上述聚集操作表达式为多个独立聚集操作表 达式，并从上述多个独立聚集操作表达式中获得上述聚集操作表达式的全 部元聚集操作表达式。

[0080] 作为示例，聚集操作表达式AO可以通过如下的规则递归分 解成一个或多个元聚集操作表达式：当AO为独立聚集操作表达式且其内部 的数据表达式中不包含聚集函数时，该聚集操作表达式为元聚集操作表达 式。如，SUM(T1.field1+T2.field2)；当AO为独立聚集操作表达式但其内部的数 据表达式中包含聚集函数时，按聚集函数的嵌套顺序从最外层逐步向内分 解，直至内层的独立聚集操作表达式AFin(fieldsin)的内部数据表达式中不包 含聚集函数为止，所得到的AFin(fieldsin)为该聚集操作表达式的元聚集操作 表达式。如，SUM(MAX(T1.field1)+MIN(T2.field2))的元聚集操作表达式为 MAX(T1.field1)和MIN(T2.field2)；当AO为可分性聚集操作表达式时，即： AO可分解为n个独立聚集操作表达式， 即AO1＝AF1
(Fields1)，…，AOn＝AFn(Fieldsn)；再将上述所得到的n个独立聚集 操作表达式按照独立聚集操作表达式的元聚集操作表达式处理规则进一 步分析，得到可分性聚集操作表达式的全部元聚集操作表达式。如， AO＝SUM(field1)/COUNT(*)分解为AO1＝SUM(field1)和AO2COUNT(*)。

[0081] 上述将分组数据集合中包含的非分布式聚集函数(即AVG、 STDDEV和VARIANCE函数)的分组数据分解为由分布式聚集函数(即 SUM,MAX,MIN,COUNT函数)构成的分组数据，如，AVG＝SUMCOUNT，即 若某分组数据的聚集操作表达式中包含AVG函数，则可将该分组数据分解 成SUM和COUNT聚集操作。改造后的分组数据与分组数据计具有相同的统 计频率。即：原始的分组数据集合QF0＝{(q0i,f0i)|i＝1,2,...,n0}演变为 QF1＝{(q1i,f1i)|i＝1,
2,...,n1}。

[0082] 步骤4：解析上述分组数据集合中的每组分组数据，生成上 述分组数据的分组数据元，得到分组数据元集合。

[0083] 在识别出数据维度和粒度的基础上通过对分组数据集合 QF1＝{(q1i,f1i)|i＝1,2,...,n1}中的每个分组数据进行特征分析，获得每个分组数 据对应的分组数据元，得到分组数据元集合MQ＝{(qi,fi)|i＝1,2,...,n}。

[0084] 上述对于识别出数据维度和粒度的方法包括：

[0085] 对于QF1＝{(q1i,f1i)|i＝1,2,...,n1}中的每个分组数据，列出该分组 数据的维集合、维粒度序列和聚集操作表达式；

[0086] 对于任意分组数据 分析其 聚集操作表达式，得到其全部元聚集操作表达式{MAO1,...,MAOm}；

[0087] 利用元聚集操作表达式，构造目标分组数据q的全部分组数 据元，分组数据元中只包含一个元聚集操作表达式，且忽略筛选条件的具 体取值，可由如下形式表示：

[0088]

[0089] 需要说明的是，任何一个分组数据元mqi*与分组数据q具有 相同的查询频率。

[0090] 依据上述过程分组数据集合中的每一分组数据构建分组数 据的分组数据元，得到面向分组数据集合QF1＝{(q1i,f1i)|i＝1,2,...,n1}的全部分 组数据元集合MetaQF＝{(mqi,fi)|i＝1,2,...,n}。

[0091] 步骤5：将上述分组数据集合中的具有相同的数据维度，以 及相同的聚集操作表达式分组数据元确定为分组数据族。

[0092] 本实施例中根据分组数据集合中的数据维度和聚集函数的 聚集操作，确定出分组数据族，可以包括如下步骤：从各上述分组数据中 选取数据维度、元聚集操作表达式相同的分组数据；将具有相同数据维度、 元聚集操作表达式的分组数据确定为同一分组数据族。

[0093] 上述分组数据族的划分，是根据上述分组数据集合的维集合和元聚 集操作表达式是否相同，将分组数据元集合划分为不同的分组数据族 Fs＝{F1,F2,...,Fk}，Fi＝{CQi1,...,CQij,...,CQim}(CQij∈MetaQF)，同一分组数据族 中的所有分组数据均具有相同的维集合{d1,d2,...,dn}和聚集操作表达式AO。 一个分组数据族可以描述为：

[0094]

[0095] 其中，{d1,d2,...,dn}表示该分组数据族的维集合，AOi表示该 分组数据族的元聚集操作表达式，[xj1,xj2,...,xjn]表示该分组数据族的第i个 分组数据元在其各个维度上的层级或粒度。

[0096] 步骤6：建立每个分组数据族所对应的统计二叉树模型，并 基于上述统计二叉树模型建立面向物化视图优化的最小化综合线性规划 模型，得到优化的物化视图集合。

[0097] 本实施例中，上述统计二叉树模型表示随着维层级的变化由 细粒度向粗粒度聚集的演变的非循环有向图。上述统计二叉树图由维度集 合{d1,d2,...,dn}(di＝[1,...,ni])决定，其任意一个节点记为＜x1,x2,...,xn＞，表 示该节点在维度di上的维层级为xi，因此，统计二叉树图{d1,d2,...,dn}对应的 最细粒度的维层级为＜n1,n2,...,nn＞，最粗粒度的维层级为＜1,1,...,1＞。上述建 立每个分组数据族所对应的统计二叉树模型，包括：判断上述分组数据族 的维度数据的维度的数量；根据各分组数据的维度数据确定上述分组数据 的统计二叉树图存在的子枝节点；由各上述分组数据的统计二叉树图存在 的子枝节点构建上述分组数据族的统计二叉树图。

[0098] 上述统计二叉树图是对该图中的每个节点采用二叉树的方 法构建有向边形成的，具体为：

[0099] 当维集合包含的维的数量为1时：节点＜xi＞可能只存在右子 枝节点＜xi＞R，当xi＞1时，＜xi＞R＝＜xi-1＞；当xi＝1时，节点＜xi＞R不存在。

[0100] 当维集合包含的维的数量为2时：＜xi,xj＞可能同时存在右子 枝节点＜xi,xj＞R和左子枝节点＜xi,xj＞L：

[0101] 当xj＞1时，右子枝节点＜xi,xj＞R＝＜xi,xj-1＞；当xj＝1时，右 子枝节点＜xi,xj＞R不存在；当xi＞1时，左子枝节点＜xi,xj＞L＝＜xi-1,xj＞；当 xi＝1时，左子枝节点＜xi,xj＞L不存在。

[0102] 当维集合包含的维的数量为n时：节点＜x1,x2,...,xn＞可能同时 存在右子枝节点＜x1,x2,...,xn＞R和左子枝节点＜x1,x2,...,xn＞L：

[0103] 当xn＞1时，右子枝节点＜x1,x2,...,xn＞R＝＜x1,x2,...,xn-1＞；当 xn＝1时，右子枝节点＜x1,x2,...,xn＞R不存在；左子枝节点按 ＜x1,x2,...,xn＞L＝＜＜x1,x2,...,xn-1＞R,xn＞计算。

[0104] 在一些示例中，通过建立每个统计家族Fi所对应的统计二叉 树图Gi，并基于该统计二叉树图Gi建立面向该统计家族的最小化综合查询 代价的线性规划模型，该模型可表示为：

[0105]

[0106] 约束条件为：

[0107] d(qi,MVi)∈Z+

[0108] MVi∈Nodes(G)

[0109] 上式中，设图Gi中相邻节点的有向边长度为1， 为分组数 据族Fi中的任意一个分组数据元qi的查询频率，MVi为分组数据族Fi的物化 视图，d(qi,MVi)为qi与物化视图MVi在统计二叉树图Gi中的有向通路的长度， d(qi,MVi)为有限正整数。

[0110] 表示分组数据族Fi的物化视图MVi与分组 数据族Fi中的所有分组数据元之间都存在有向通路，且综合查询代价  是最小的。

[0111] 对于给定的分组数据族Fi，该线性规划模型存在最优解MVi， 即统计该分组数据族Fi的物化视图为MVi。该分组数据族Fi的任意一个分组 数据元qi可以在MVi上重新构造，即：qi不再依赖于数据表进行统计，而是 将MVi作为唯一数据来源进行统计。

[0112] 当 时，有：

[0113]

[0114] 对所有的分组数据族F＝{F1,F2,...,Fn}进行分析，找出每个分 组数据族Fi对应的物化视图MVi，得到物化视图集合MV＝{MV1,MV2,...,MVn}。

[0115] 在本发明的一个示例中，对Northwind数据库进行物化视图 选择过程如下(Northwind数据库包含的分组数据，如图4所示)：

[0116] 分组数据族P1：其聚集操作方式为COUNT(OrderID)；维度集 合为{d1}，分组数据族P1共有三个伴随分组数据元，分别是：mq1*：月订 单销售量统计，其维粒度序列为＜3＞；mq3*：季订单销售量统计，其维粒 度序列为＜2＞；mq5*：年订单销售量统计，其维粒度序列为＜1＞。

[0117] 因此，分组数据族P1对应的物化视图为：

[0118]

[0119] 分组数据族P2：其聚集操作方式为，  SUM([UnitPrice]*[Quantity]*[1-Discount]；维度集合为{d1}，分组数据族P2共有 三个伴随分组数据元，分别是：mq2*：月订单销售额统计，其维粒度序列 为＜3＞；mq4*：季订单销售额统计，其维粒度序列为＜2＞；mq6*：年订单 销售额统计，其维粒度序列为＜1＞。

[0120] 因此，家族P2对应的物化视图为：

[0121]

[0122] 在mv(p1)和mv(p2)基础上，以分组数据“q3年订单销售量和 销售额”为例，可以基于mv(p1)和mv(p2)构造目标统计，其SQL语句如下： “SELECT年,SUM(销售量),SUM(销售额)FROM mv(p1),mv(p2)WHERE mv(p1).年＝mv(p2).年GROUP BY年”。

[0123] 分组数据族P3：其聚集操作方式为SUM(Quantity)；维度集合 为{d1,d4}，分组数据族P3共有四个分组数据元统计，分别是：mq7*：每种 具体产品的季销售量统计,其维粒度序列为＜2,2＞；mq8*：每项大类产品的 季销售量统计，其维粒度序列为＜2,1＞；mq9*：每种具体产品的年销售量 统计，其维粒度序列为＜1,2＞；mq10：每项大类产品的年销售量统计，其 维粒度序列为＜1,1＞。

[0124] 因此，家族P3对应的物化视图为：

[0125]

[0126] 分组数据族P4：其聚集操作方式为 SUM([UnitPrice]*[Quantity]*[1-Discount]；维度集合为{d1,d3}，分组数据族P4共 有两个伴随分组数据元，分别是：mq11*：每类客户年消费额统计,其维粒 度序列为＜1,1＞；mq12*：每位客户年消费额统计，其维粒度序列为＜1,2＞。

[0127] 因此，分组数据族P4对应的物化视图为：

[0128]

[0129] 分组数据族P5：其聚集操作方式为 SUM([UnitPrice]*[Quantity]*[1-Discount]；维度集合为{d1,d2}，家族P5共有两个 伴随元统计，mq13*：每位员工季销售额统计,其维粒度序列为＜2,3＞；mq14*： 每位员工年销售额统计,其维粒度序列为＜1,3＞。

[0130] 因此，分组数据族P5对应的物化视图为：

[0131]

[0132] 分组数据族P6：其聚集操作方式为SUM(Quantity)；维度集合 为{d1,d6}，分组数据族P6只有一个伴随分组数据元，mq15*：供应商年供货 量统计,其维粒度序列为＜1,1＞。

[0133] 因此，家族P6对应的物化视图为：

[0134]

[0135] 步骤7：基于物化视图选择和优化得到的优化物化视图集合， 重新构造上述分组数据集合中的每一组分组数据。

[0136] 新构造分组数据集合中的每一个分组数据，可以通过两个步骤 实现：

[0137] (1)对于分组数据族Fi的任意一个分组数据元qi将MVi作为唯 一数据来源重构SQL语句；

[0138] (2)对于目标分组数据集合QF1＝{(q1i,f1i)|i＝1,2,...,n1}中的任意 一个q1i根据其聚集操作表达式以及其元聚集操作表达式的分解情况，以分组 数据元qi为数据源重构SQL语句。

[0139] 步骤8：依据与物化视图相关的事实表的变化，对上述物化 视图的数据作同步变化。

[0140] 物化视图集合更新采用及时数据更新策略，即：与任何一个 物化视图相关的事实表发生变化时(数据的新增、删除和修改)，对应的 物化视图采用触发器、存储过程或应用程序同步更新物化视图数据。

[0141] 作为另一方面，本申请还提供了一种存储装置，其中存储有 多条程序，上述程序适于由处理器加载并执行以实现上述物化视图的选择 和优化方法。

[0142] 另一方面，本申请还提供了一种处理装置，包括处理器和存 储设备。其中，处理器，适于执行各条程序；存储设备，适于存储多条程 序。上述程序适于由处理器加载并执行以实现上述物化视图的选择和优化 方法。。

[0143] 至此，已经结合附图所示的优选实施方式描述了本发明的技 术方案，但是，本领域技术人员容易理解的是，本发明的保护范围显然不 局限于这些具体实施方式。在不偏离本发明的原理的前提下，本领域技术 人员可以对相关技术特征作出等同的更改或替换，这些更改或替换之后的 技术方案都将落入本发明的保护范围之内。