CN107992503B - 数据分析中的查询处理 - Google Patents

Abstract

根据本公开内容的实现，提出了一种查询处理的方案。在该方案中，多个数据子集被预先存储、例如被存储在可快速访问的存储设备中，以供数据分析。每个数据子集可以包括与一个或多个维度对应的数据条目。当接收到的查询的多个查询项对应的多个目标维度需由两个或更多的数据子集覆盖时，取代于转向分析未被存储的源数据集，可以将该查询分解为多个子查询。这样的分解可以使得与每个子查询的查询项相关的目标维度由单个数据子集覆盖。针对每个子查询分析相应的数据子集并且基于多个子查询的分析结果，确定该查询的查询结果。通过这种方式，可以从已有的数据子集中快速地处理查询和提供查询结果。

Description

数据分析中的查询处理

背景技术

数据分析或数据探索(data exploration)在数据挖掘、商业智能等诸多应用领域发挥着越来越重要的作用。用户可以向数据分析平台提交针对数据的各个方面(维度)的查询。查询处理工具可以探索和分析数据并且将查询结果返回给用户。由于用户的查询可能涉及数据的多个维度，因此要求查询处理工具可以跨维度理解数据并且挖掘数据背后的信息。可以采用多种联机分析处理(OLAP)技术来执行数据分析。

很多数据分析任务对于时间很敏感并且因此期望以更快速度获得查询结果。例如，存在很多交互式数据探索的使用场景。用户可能希望依赖于上一次查询的结果做出判断，进而发起下一轮查询，通过多次的查询来做出最后的决策。如果查询处理工具不能够快速给出结果，这将极大降低其可用性。然而在如今的信息时代，随着可获得的数据源不断增长，数据变得无处不在并且在数量和维度上都有所增加。面对海量数据，如何为用户查询提供更快更准确的结果是数据分析面临的挑战。

发明内容

根据本公开内容的实现，提出了一种查询处理的方案。在该方案中，多个数据子集被预先存储、例如被存储在可快速访问的存储设备中，以供数据分析。每个数据子集可以包括与一个或多个维度对应的数据条目。当接收到的查询的多个查询项对应的多个目标维度需由两个或更多的数据子集覆盖时，取代于转向分析未被存储的源数据集，可以将该查询分解为多个子查询。这样的分解可以使得与每个子查询的查询项相关的目标维度由单个数据子集覆盖。针对每个子查询分析相应的数据子集并且基于多个子查询的分析结果，确定该查询的查询结果。通过这种方式，可以从已有的数据子集中快速地处理查询和提供查询结果。

提供发明内容部分是为了简化的形式来介绍对概念的选择，其在下文的具体实施方式中将被进一步描述。发明内容部分无意标识要求保护的主题的关键特征或主要特征，也无意限制要求保护的主题的范围。

附图说明

图1示出了能够实施本公开内容的多个实现的计算环境的框图；

图2A和图2B示出了根据本公开内容的一个实现的示例源数据集和数据子集的示意图；

图3示出了根据本公开内容的一个实现的查询处理过程的流程图；

图4示出了根据本公开内容的一个实现的查询分解过程的流程图；

图5示出了根据本公开内容的一个实现的目标维度的关联性的示意图；

图6A和图6B示出了根据本公开内容的一个实现的针对不同查询的目标维度的关联性的示意图；

图7示出了根据本公开内容的一个实现的对数据子集的分析的示意图；以及

图8示出了根据本公开内容的一个实现的用于生成数据子集的过程的流程图。

这些附图中，相同或相似参考符号用于表示相同或相似元素。

具体实施方式

现在将参照若干示例实现来论述本公开内容。应当理解，论述了这些实现仅是为了使得本领域普通技术人员能够更好地理解且因此实现本公开内容，而不是暗示对本主题的范围的任何限制。

如本文中所使用的，术语“包括”及其变体要被解读为意味着“包括但不限于”的开放式术语。术语“基于”要被解读为“至少部分地基于”。术语“一个实现”和“一种实现”要被解读为“至少一个实现”。术语“另一个实现”要被解读为“至少一个其他实现”。术语“第一”、“第二”等等可以指代不同的或相同的对象。下文还可能包括其他明确的和隐含的定义。

如本文中所使用的，术语“数据记录”或“数据条目”指的是数据集或数据子集中涉及一个或多个维度的数据。术语“维度”涉及数据条目的一个方面。维度用于对数据集或数据子集中的不同类型的数据进行分组。例如，在与产品销售有关的数据集中，一个数据条目可以包含与产品名称、产品参数、生产时间、销售时间、销售地域、销售额有关的各类数据，其中产品名称、产品参数、生产时间、销售时间、销售地域和销售额指的是这个数据条目的六个不同维度。在一些情况下，跨越所有维度中的两个或更多维度的数据项也可以组成数据条目，虽然该数据条目不涉及全部维度。不同的维度有时候可以被称为数据集或数据子集的不同列。具有多个维度的数据或数据条目可以被称为“多维度数据”或“多维度数据条目”。

如本文中所使用的，术语“数据项”指的是与数据条目的某个维度相关的数据。例如，在数据条目的产品名称维度中记录的数据可以被认为是一个数据项。一个维度中的数据项也可以被称为该维度的维度值。一般而言，数据项可以是分类数据、序数数据或度量数据。例如，“产品名称”维度中的数据项是分类数据，用于指示不同的产品；“生产时间”和“销售时间”维度中的数据项属于序数数据；“销售额”中的数据项反映与统计有关的定量属性并且因此是度量数据。术语“查询项”指的是在查询中被指定的数据项，并且因此与数据条目的某个维度相关。

数据集可以被分布式存储在数据库或文件系统，并且因此对于其中的数据项的访问速度也将降低。由于可供分析的数据量(例如 TB或PB级别)和维度(数十个维度)较大，为了促进响应于用户查询的数据分析任务，一些方案提出了将数据集存储在可快速访问的存储设备中、诸如内存中。这样的数据集存储例如是分布式内存中的计算架构SparkSQL。通过改进访问速度，这进一步加快了查询结果的获得速度，并且甚至可以将处理时间从数天降低到数小时或数分钟。然而，这个处理时间难以被进一步降低，因为扫描大数据量和高维度数据集非常耗费时间。由此，这无法满足在诸如交互式数据探索之类的对于时间敏感的任务所要求的性能、例如数十秒或数秒响应时间。

还有一些方案尝试通过将较大的源数据集划分为多个较小数据子集的方式来解决大数据交互式探索的问题。这些较小数据子集覆盖源数据集的一个或多个维度，从而具有更小的尺寸。数据子集有时也可以被创建为所谓的数据立方体(data cube)，并且有时候可以由源数据集的一个或多个维度(列)中的数据的聚合结果组成的表格来表示。响应于查询的请求，查询处理设备确定该查询中的一个或多个查询项对应的目标维度，并且直接在覆盖确定出的目标维度的一个数据子集中执行数据分析并计算查询结果。由于数量和维度的降低，因此仅需要非常少的数据扫描操作、降低了查询结果获取时间。取代于被分布式存储的源数据集，数据子集可以被存储在可快速访问的存储设备中，这进一步提高性能。

然而，数据子集或数据立方体的创建、存储和维护均需要消耗计算和存储资源。例如，对于具有d个维度的源数据集而言，将可以生成全部2^d个数据子集用以分别覆盖d个维度的不同组合，这在许多情况下是难以实现的。为了降低维度，一些查询处理平台允许用户手动将源数据集的维度进行分组，并且仅基于各个分组中的维度创建数据子集。由于创建的数据子集没有包括d个维度的全部组合，当接收到的查询包括的查询项涉及被划分在两个或更多数据子集的维度时，查询处理平台无法给出查询结果。

例如，如果覆盖产品名称、产品参数、生产时间、销售时间、销售地域、销售额六个维度的源数据集被划分为两个数据子集，分别涉及产品名称和产品参数或者生产时间、销售时间、销售地域和销售额。当用户希望查询某个产品的销售趋势时，查询处理平台将无法给出查询结果，因为该查询涉及的产品名称和销售额两个维度未被包括在单个数据子集中。当这样的情况发生时，查询处理平台将会转而访问和分析源数据集，因而相较于基于数据子集的分析而言花费更长的处理时间。

此外，由于用户往往无法准确地把握哪些维度的数据更可能组合在一起以方便后续分析，依赖于用户手动的分组将会使得创建的数据子集不能用于准确和快速地计算查询结果，使得整体性能降低。而且，出于存储空间的限制，为了避免最后生成的数据子集的数据总量超过可用存储空间，通常会采取保守估计的方法来限制用户的选择和数据子集的生成。这些都将会导致后续无法对各种各样的查询进行快速响应。

还有一些方案旨在于牺牲查询结果的准确性来获得更快的响应速度和更少的存储空间。这些方案可以称为近似查询处理 (Approximate Query Processing，AQP)。基于AQP的查询处理是基于这样的假设：用户通常对近似结果或答案也感到满意。例如，期望做销售趋势调查的用户不需要关心特定时间段内的准确销售额。常规的AQP方案可以包括采样、建立直方图(histogram)、小波变换 (wavelet)和构造轮廓(sketch)。不考虑数据立方体，一种AQP方法在原始数据集的基础上构建分层样本集合，并且在运行时选择最恰当的样本来针对查询分析数据。分层样本集合的确定要考虑历史工作量、数据分布和稀疏性、存储限制等因素。尽管在查询结果方面可能有效，然而这样的方法将面临“冷启 动”问题。由于要严重依赖于历史工作量，这不适用于新获得的数据，因为此时尚不具有历史信息。

通过上述分析可知，已有的多种方案无论是在数据子集的构建还是对查询结果的估计方面均存在各种缺陷。为了至少部分地解决上述以及其他潜在问题，在此提出一种新的查询处理方案。如上文简述，根据本公开内容的实现，当接收到的查询中的多个查询项相关的目标维度需两个或更多数据子集覆盖时，将查询分解为多个子查询。每个子查询具有多个查询项中的至少一个查询项，并且因而每个子查询的查询项相关的目标维度可以由单个数据子集覆盖。通过分析对应的数据子集，可以确定子查询的分析结果。多个子查询的分析结果可以被汇总(例如通过概率分析的方式)用于估计针对查询的最终查询结果。相较于从覆盖多个查询项相关的目标维度的源数据集确定查询结果而言，所估计的这个查询结果可能在准确度上有所降低，然而却能够在已有的数据子集的基础上快速且实时地呈现查询结果。此外，对于查询结果的估计也不要求数据分布、历史工作量之类的先验知识。

以下参考附图来说明本公开内容的基本原理和若干示例实现。图1示出了能够实施本公开内容的多个实现的计算环境100的框图。应当理解，图1所示出的计算环境100仅仅是示例性的，而不应当构成对本公开内容所描述的实现的功能和范围的任何限制。

如图1所示，计算环境100包括通用计算设备形式的计算系统/ 服务器102和数据集180。计算系统/服务器102可以用于实施本公开内容的实现的查询处理设备(以下也称为“查询处理设备102”)。计算系统/服务器102可以接收查询并且提供查询结果106。计算系统/服务器102的组件可以包括但不限于一个或多个处理器或处理单元 110、存储器120、存储设备130、一个或多个通信单元140、一个或多个输入设备150以及一个或多个输出设备160。处理单元110可以是实际或虚拟处理器并且能够根据存储器120中存储的程序来执行各种处理。在多处理器系统中，多个处理单元并行执行计算机可执行指令，以提高计算系统/服务器102的并行处理能力。

计算系统/服务器102通常包括多个计算机存储介质。这样的介质可以是计算系统/服务器102可访问的任何可以获得的介质，包括但不限于易失性和非易失性介质、可拆卸和不可拆卸介质。存储器120 可以是易失性存储器(例如寄存器、高速缓存、随机访问存储器 (RAM))、非易失性存储器(例如，只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、闪存)或其某种组合。存储器 120可以包括一个或多个程序产品122，其具有一个或多个程序模块集合，这些程序模块被配置为执行本文所描述的各种实现的功能。

存储设备130可以是可拆卸或不可拆卸的介质，并且可以包括机器可读介质，诸如内存、闪存驱动、磁盘或者任何其他介质，其能够用于存储信息和/或数据170(例如一个或多个数据子集172)并且可以在计算系统/服务器102内被访问。在一些实现中，取代于存储在存储设备130中，数据子集172可以与程序产品122一起被存储在可快速访问的存储器120中。或者，存储设备130可以被实现为可快速访问的存储器的形式。应当理解，以上描述仅仅是示例性的，数据子集172也可以存储在其他任何适当形式存储器中。在一个示例中，数据子集172可以以分布式存储的方式存储在多个存储设备中。

计算系统/服务器102可以进一步包括另外的可拆卸/不可拆卸、易失性/非易失性存储介质。尽管未在图1中示出，可以提供用于从可拆卸、非易失性磁盘进行读取或写入的磁盘驱动和用于从可拆卸、非易失性光盘进行读取或写入的光盘驱动。在这些情况中，每个驱动可以由一个或多个数据介质接口被连接至总线(未示出)。

通信单元140实现通过通信介质与另外的计算设备进行通信。附加地，计算系统/服务器102的组件的功能可以以单个计算集群或多个计算机器来实现，这些计算机器能够通过通信连接进行通信。因此，计算系统/服务器102可以使用与一个或多个其他服务器、网络个人计算机(PC)或者另一个一般网络节点的逻辑连接来在联网环境中进行操作。

输入设备150可以是一个或多个各种输入设备，例如鼠标、键盘、追踪球、语音输入设备等。输出设备160可以是一个或多个输出设备，例如显示器、扬声器、打印机等。计算系统/服务器102还可以根据需要通过通信单元140与一个或多个外部设备(未示出)进行通信，外部设备诸如存储设备、显示设备等，与一个或多个使得用户与计算系统/服务器102交互的设备进行通信，或者与使得计算系统/服务器102与一个或多个其他计算设备通信的任何设备(例如，网卡、调制解调器等)进行通信。这样的通信可以经由输入/输出(I/O)接口(未示出)来执行。

如图1所示，存储设备130中存储有数据170，其包括数据子集 172(例如涉及产品销售的统计数据)，作为查询处理设备的计算系统/服务器102能够通过输入设备150接收来自例如用户的查询104。举例而言，该查询可以涉及某个具体产品在某地区的销售情况。基于已存储的数据子集172，查询处理设备102可以确定查询结果106。查询结果106可以利用图形、表格、文本、音频、视频或其任意组合形式来进行展示，使得用户或者其他查询结果的接收方能够获知。应当理解，查询结果106可以以任意适当的形式来展示，以上所述形式仅仅是示例性的，无意限制本公开内容的范围。

查询处理设备102还可以通过通信单元14与数据库180通信，并且数据库180中存储有数据集182。数据集182可以包括与多个维度对应的多个数据条目。数据集182可以是数据子集172的源数据集。数据子集172基于数据集182而被生成并且包括与数据集182的一个或多个维度对应的数据条目。如果无法基于数据子集172直接提供查询结果106，根据需要，查询处理设备102可以访问数据集182以在更大范围的数据中执行数据分析。

以下通过具体示例来进一步描述本公开内容的实现。图2A示出了根据本公开内容的实现的源数据集200的示意图。数据集200可以实现为图1的数据库180中的数据集182。虽然图2A中采用了多维表格的形式来示出该数据集200，应当理解，给出数据集200仅仅是为了方便后续示例的描述，数据集200可以具有任意适当的形式和内容。图2A中的示例无意限制本公开内容的范围。

在一些实现中，数据集200可以是存储在数据库中的单个表格、逗号分隔数值(CSV)文件或者任何其他适当形式的文件，也可以从多个表格联合得到。在图2A的示例中，数据集200是一个涉及产品销售的表格，其具有多行和多列。每一个数据条目是该表格中的一行，而“日期”210、“CPU”(中央处理单元)220、“OS”(操作系统)230、“区域”240、“品牌”250、“解析度”260和“销售额”270等列分别是数据集200的不同维度。每个数据条目中与一个维度对应的数据被称为数据项或维度值，其由数据集200的行和列共同限定。

由于数据集200的数据量较大且维度较多，可以预先创建数据集200的多个数据子集。每个数据子集可以包括图2A所示的7个维度中的一个或多个维度的数据，并且因此每个数据子集的数据量被降低且其中的每个数据条目包含较少维度的数据。例如，可以基于数据集200生成如图2B所示的四个数据子集202至208，分别覆盖以下的维度：{210、250、270}；{220、230、260}；{230、240、250、260} 和{220、230、240}。这些数据子集可以与数据集200独立地被存储并且可以实现为图1的存储设备130中的数据子集172。

图3示出了根据本公开内容的一个实现的查询处理过程300的流程图。过程300可以被实现在查询处理设备102处。在310，查询处理设备102接收包含多个查询项的查询104。多个查询项与数据条目的多个目标维度相关并且可以指示期望获得的信息的不同方面。查询可以是由用户输入或者以其他方式生成。例如，查询104可以是“SELECT SUM(销售额)WHERE CPU＝’ARM’AND OS＝’iOS’AND 品牌＝”Brand1”AND区域＝’US’”，其与图2A的数据集200中的维度“销售额”270、“CPU”220、“OS”230、“品牌”250和“区域”240相关。这些相关的维度被称为目标维度。在查询104中被定义的各个目标维度的数据是查询项，用于表示用户期望获知CPU是 ARM、OS是iOS、品牌是Brand1的产品在US的销售情况。

在320，查询处理设备102确定相关的多个目标维度是否需至少两个数据子集覆盖。查询处理设备102将从源数据集生成的多个数据子集存储在存储设备130(其可快速访问)。为了获得准确的查询结果，期望已存储的单个数据子集覆盖与当前查询项相关的多个目标维度，从而可以依赖于该数据子集执行针对查询的数据分析。本文中使用的“覆盖”指的是与目标维度对应的数据被包括在一个数据子集中，而该数据子集可以还包括或不包括其他维度的数据。

如果已有的多个数据子集中的单个数据子集无法覆盖相关的多个目标维度，也即需要两个或更多数据子集才能覆盖所有这些目标维度，根据本公开内容的实现，将分解该查询以确定估计的查询结果。在图2A和2B的示例中，如果查询104涉及目标维度“销售额”270、“CPU”220、“OS”230、“品牌”250和“区域”240，那么查询处理设备102中存储的数据子集202至208均无法单独地覆盖所有这些目标维度，因而将分解查询104。

在330，查询处理设备102将查询104分解为多个子查询，使得分解所获得的每个子查询具有查询104的多个查询项中的至少一个查询项。在一些实现，可以随机地划分查询104的多个查询项以获得每个子查询的查询项。由于每个子查询的查询项数目的减少，在已有的数据子集中查找到每个子查询的结果的概率将会增加。另外的一些实现中，查询的分解可以依赖于当前已有的数据子集。例如，可以随机地划分查询104，并且如果某个子查询涉及的目标维度仍然需要由两个以上的数据子集覆盖，则进一步分解该子查询。在一些实现中，还可以基于数据子集对目标维度的覆盖情况构建目标维度的关联性，从而在该关联性的基础上将查询104分解为使得与每个子查询的查询项相关的目标维度可以由已存储的单个数据子集覆盖。查询分解的过程将在以下详细描述。

在340，查询处理设备102通过分析多个数据子集中与每个子查询的查询项相关的目标维度的数据条目，确定针对查询104的查询结果。当每个子查询涉及的目标维度均可以由单个数据子集覆盖时，可以对这些单个数据子集执行数据分析，给出针对该子查询的分析结果。这时可以采用多种已有的针对查询给出查询结果的分析技术来确定结果。其他分析技术也是适用的。多个子查询的分析结果可以被汇总起来用于确定针对查询104的查询结果。可以采用概率分析方法来估计查询104的查询结果。一种概率分析方法的示例是：在已知查询 104中的单个变量(查询项)和/或多个变量的组合的分析结果的情况下，估计满足查询104的全部变量(查询项)的查询结果。可以采用各种概率分析方法来执行估计。

如果查询处理设备102确定相关的多个目标维度不需多个数据子集覆盖而是可以由已有的单个数据子集覆盖，在350，通过分析单个数据子集中与多个目标维度对应的数据条目，可以确定针对查询 104的查询结果。此时，可以给出对于查询104的准确结果。多种已有的针对查询给出查询结果的分析技术也可以被使用。

以下将详细描述查询104的分解的各种示例实现。可以理解的是，查询分解涉及将高维度(多查询项)的查询104降低至低维度(少查询项)的子查询。基于这样的分解之所以能够确定查询104的查询结果，是因为发明人已经认识到如下情况。

首先，数据集的维度(或者列)之间的相关性不高。在很多使用例如朴素贝叶斯网络(

Bayesian Network)的机器学习的试验中，已经证明当假设所有特征均彼此独立时，仍然能够获得非常好的结果。进一步地，在例如基于树增强的朴素贝叶斯网络(TreeAugmented

Bayesian Network)的学习模型中，假设每个特征仅与最多一个其他特征相关，也可以获得良好的结果。基于这些观察，发明人发现降低查询104的维度是可行的。

其次，在实际使用过程中，大数据集的数据条目在维度上是稀疏的(例如，某些数据条目在一些维度上的值是空的)，因而难以直接获得高维度查询的结果。正因如此，只有基于查询的分解才能得出有意义的结果。而且，生成和存储低维度的多个数据子集会使得查询过程更有效。进一步地，如以上提及的，在数据分析和挖掘的时候，用户通常对近似结果或答案也感到满意。

正是基于以上认识，本公开内容的实现提出了分解查询以便基于已有的数据子集给出估计的查询结果的方案。以下将参照图4来描述查询104的分解过程400。可以理解的是，分解过程400是图3的过程300的一种具体实现并且因而也可以由查询处理设备102来实现。为了使得在无法从单个数据子集找到全部目标维度的情况下查询 104的查询结果更准确，基于概率分析理论可知，期望尽可能多地知道针对查询104的不同查询项组合的分析结果。因此，在分解查询时，将考虑子查询可以包括查询项的不同组合。

总体而言，查询104的分解过程400依赖于两个因素。一个因素是上文以提及的当前已存储的数据子集对目标维度的覆盖情况。另一个因素是查询104中的多个查询项之间的相关度，也即该查询要在各个目标维度中查找的数据项。在考虑相关度时，不是机械地考虑涉及到的目标维度之间的整体相关度，而是考虑目标维度中当前被查询的数据项之间的相关度。

分解过程400的目标是根据已知信息确定多个目标维度的关联性，以便于基于该关联性来分解查询104。在关联性的确定过程中可以考虑以上提及的两个因素。具体地，在410，查询处理设备102确定查询104的多个查询项中的每个查询项对之间的相关度。在420，查询处理设备102基于相关度和每个数据子集对应的目标维度，确定多个目标维度的关联性。以下详细描述相关度和关联性的确定。

在一些实现中，可以基于贝叶斯网络来生成多个目标维度的关联性，并且因而该关联性可以由有向无环图(DAG)表示。多个目标维度可以被认为是DAG的顶点，并且与两个目标维度对应的查询项之间的相关度可以作为两个顶点之间的边的权值。由此可见，与常规的贝叶斯网络不同，在本公开内容的实现中生成的贝叶斯网络是有条件约束的(即在给定查询的查询项和给定数据子集的目标维度的条件下)。因此，本文中提出的贝叶斯网络可以被称为有条件的贝叶斯网络或者动态贝叶斯网络。

为了更直观地理解DAG表示的目标维度的关联性，图5示出了一个示例DAG 500。在该示例中，假设查询104涉及A 510、B 520、 C 530、D 540和E 550这五个目标维度。将这五个目标维度分别作为 DAG 500的顶点。在DAG 500中，两个顶点之间的边的权值可以由与目标维度对应的查询项对之间的相关度来表示。将在下文讨论如何将这些边添加到DAG 500中。

与常规的基于静态信息论的贝叶斯算法不同，本文中提出的贝叶斯网络不计算逐列(维度)的相关度，而是使用与被指定给这些维度的查询项之间的相关度。这是基于以上提及的维度之间的相关度不高的认识。在一些实现中，两个查询项之间的相关度可以是这两个查询项之间的互信息，也可被称为逐点互信息(Point-wise Mutual Information，PMI)。

在一个示例中，两个查询项之间的互信息可以基于其在对应的目标维度中存在的概率值来计算。每个查询项在对应目标维度中存在的概率指该查询项匹配(相同)的数据项在该目标维度中出现的次数与该维度中全部数据项的个数的比率，并且因此表示可以从这个目标维度中查找到该查询项的可能性。例如，如果目标维度A中具有100 个数据项，并且与查询项a相同的数据项a的个数是20，那么查询项 a在维度A中存在的概率值可以被确定为0.2。

基于针对每个查询项的概率值，可以采用多种计算互信息的方法。在一个示例中，假设查询104涉及{A、B、C、D、E}五个目标维度510至550并且与每个目标维度相关的查询项是{a、b、c、d、 e}，那么查询项a和b之间的互信息(被表示为“PMI(a,b)”)可以按如下计算：

其中p(a)和p(b)表示查询项a和b在各自的目标维度A和B中存在的概率值，并且p(a,b)指示查询项a和b两者在目标维度A和B中同时存在的概率值。这些概率值可以被预先计算并且作为元数据与数据子集一起存储，或者可以通过对包含这些目标维度的数据子集中的数据条目进行统计来确定。

出于与逐点互信息进行比较的目的，以下给出两个目标维度(A和 B)之间的互信息(被表示为“I(A,B)”)确定：

可以看出两个目标维度之间的互信息实际上是这些目标维度中的所有数据项之间的PMI的加权平均。在查询的情况中，PMI可以更好地描述在特定查询的情况下两个目标维度之间的关系。相比较而言，两个目标维度之间的互信息因被两个维度值的加权值或者其他不相关的维度值之间的互信息所影响，从而不能如PMI一样准确地反映出在给定查询下两个目标维度之间的相关度。例如，在图2A和2B的示例中，对于目标维度CPU 220和OS230而言，如果查询104的两个查询项是CPU＝“ARM”和OS＝“Linux”，可以计算出这两个查询项的相关度(PMI)是0.305，这比维度CPU 220和OS 230之间的0.037 的互信息更大并且因而指示在维度值ARM和Linux给定后维度CPU 和OS实际上非常相关。

在一些实现中，在确定多个目标维度的贝叶斯网络的关联性时，可以将PMI的绝对值用作目标维度的顶点之间的边的权值。由此，即使确定两个查询项之间是强负相关，也可以认为其存在有影响的相关度。应当知道的是，对于查询104中的多个查询项的每个查询项对，均可以类似地确定其相关度。

在获得查询项之间的相关度之后，可以生成以目标维度为顶点的DAG作为其关联性的表示，并且将查询项之间的相关度作为其对应的目标维度之间的无向边的权值。在DAG中，两个目标维度的关联性可以由这两个目标维度之间的连接边来表示。生成DAG的目标可以是找到一个贝叶斯网络，使其具有所有边的权值之和最大，并且根据DAG分解得到的所有子查询均可以由已有的数据子集直接地给出查询结果。因此，除了查询项的相关度之外，当前已存储的多个数据子集对于目标维度的覆盖情况也会影响DAG中的两个目标维度是否具有关联性。总体而言，期望具有关联性的任何两个或更多目标维度的组合都可以由数据子集覆盖。备选地或附加地，还可以期望为对应查询项的相关度较高的目标维度优先建立关联性。

下文将描述一个建立DAG的过程的示例。可以将多个目标维度作为DAG的顶点并且从多个目标维度随机选择一个目标维度作为根节点。选择根节点的目的是为了方便标识目标维度之间的边的方向，使得其总是从父节点指向子节点。具体地，可以确定已计算的相关度中大于相关度阈值的相关度(例如最大的相关度)。将这个相关度涉及的查询项对应的两个目标维度中的任一个目标维度确定为根节点并且确定这两个目标维度具有关联性。举例而言，在图5的示例中，与目标维度510和520对应的查询项a和b之间的相关度最大，并且因而可以选择目标维度510为根节点，然后以从根节点510指向节点 520的边表示这两个目标维度的关联性。

进一步地，还可以根据相关度的降序顺序，选择并确定其他对应的目标维度之间的边是否可以被添加到DAG中。在确定两个目标维度之间的边是否可以被添加时，可以基于如下准则。

首先，添加的边的方向可以被确定为一致地从上指向下(以根节点为基础)或者一致地从下指向上。如果两个目标维度处于相同级别，则该方向可以被规定为一致地从左到右(或者一致地从右到左。对于DAG的边的方向的规则是为了避免DAG中的循环结构。方向还可以指示两个目标维度之间的关联性的关系。例如，如果维度A指向维度B，可以指示维度B与维度A的关联较强(从而A与B的可以较弱)。

其次，考虑已有的数据子集对目标维度的覆盖。具有关联性的两个目标维度应当可以由单个数据子集覆盖。附加地，如果这两个目标维度中的任一个维度还与其他一个或多个目标维度具有关联性，则所有这些目标维度也应当由单个数据子集覆盖。在一个示例中，指向同一个目标维度的这些目标维度应该与所指向的目标维度一起被单个数据子集覆盖。在图5的示例中，假设目标维度510和530已经被确定为具有关联性。当确定要在目标维度520和530之间是否可以添加边时，确保目标维度510、520和530均可以由单个数据子集覆盖。

当所有可添加的边被确定之后，DAG可以被建立作为一个贝叶斯网络并且用于表示多个目标维度之间的关联性。应当认识到，上述关联性的确定过程是动态的，即每当接收到查询104之后，在该查询 104的基础上生成与该查询对应的目标维度的关联性。由于以上建立的贝叶斯网络是有条件约束的，因此可以理解即使查询104涉及相同的目标维度但是与每个目标维度相关的查询项不同，建立的DAG也可能不相同。

举例而言，如果查询104是“SELECT SUM(销售额)WHERE CPU＝’ARM’AND OS＝’iOS’AND品牌＝”Brand1”AND区域＝’US’”，那么在确定所涉及的目标维度CPU 220、OS 230、区域240、品牌250 和销售额270之间的关联性时，将受到条件{CPU＝”ARM”AND OS＝’iOS’AND品牌＝”Brand1”AND区域＝’US’}的约束。当已存储的数据子集是如图2B所示的数据子集202至208时，所生成的DAG 610将如图6A所示。在另外的示例中，如果查询104是“SELECTSUM(销售额)WHERE CPU＝’ARM’AND OS＝’Linux’AND品牌＝”Brand1”AND区域＝’US’”时，由于查询项的不同，针对相同的目标维度生成的DAG 620如图6B所示。

应当理解的是，虽然以上以树结构的方式解释说明DAG，然而在确定关联性时可以不一定需要建立和存储这样的树结构，而是可以采用任何可以标识目标维度之间的关联性的方式。还应当理解的是，还可以采用除DAG之外的其他方式来表示目标维度之间的关联性。

继续参照图4，基于确定的关联性，查询处理设备102在430将查询分解为多个子查询。每个子查询可以具有多个查询项。对于具有多个查询项的子查询，期望对应的目标维度均具有关联性。可以从为目标维度建立的关联性DAG中选择具有关联性的两个或两个以上的目标维度，并且将这些目标维度对应的查询项分解为一个子查询。多个子查询之间的查询项可以部分重叠。基于以上生成的关联性可知，这样可以使得每个子查询涉及的目标维度由单个数据子集覆盖。附加地，多个子查询中的一个或一些子查询还可以仅具有一个查询项。

通过以上的分解过程，每个子查询(包括具有一个查询项的子查询)均可以由单个数据子集给出查询结果。因此，在数据分析阶段，查询处理设备102可以分析每个子查询涉及的目标维度的数据条目，来挖掘针对该子查询的分析结果。可以采用多种当前已知的或者将来待开发的数据分析技术对单个数据子集执行数据挖掘，本公开内容的范围在此方面不受限制。

在一些示例中，取决于每个子查询中的查询项，查询处理设备 102可以对单个数据子集进行下钻(drill-down)和上卷(roll-up)等多种联机分析处理(OLAP)技术以执行相应的分析任务。图7示出了对于单个数据子集710的上卷和下钻操作的示意图。所示的数据子集710覆盖三个维度A、B和C，并且这三个维度具有各自的数据项 {a1、a2、a3}、{b1、b2、b3}和{c1、c2}。在上卷操作中，给定维度 C的数据项(维度值)c1和c2，可以获得数据块722和724。对数据块722和724进一步进行上卷之后，可以分析维度A和B组成的数据表格730。下钻操作则是上卷操作的逆操作。数据分析任务还可以包括模式挖掘，诸如趋势、异常值或异常点、相关性等等，以便给出针对子查询的分析结果。

当获得查询104的多个子查询的分析结果之后，查询处理设备 102可以以概率分析的方法确定查询104的最终查询结果。在一些情况中，为了获得查询104的更准确的查询结果，可以将多个查询项的尽可能多的组合作为分解的子查询并且分析相应的查询结果。作为一个示例，如果查询104涉及如图5所示的5个目标维度A至E 510至 550，并且基于图5示出的互联性将查询104分解为分别涉及如下目标维度的子查询：{B 520}、{A510}、{A510、E 550}、{B 520、E 550}、 {B 520、C 530}和{A 510、B 520和C 530}。在源数据集的全部数据中找到满足查询104对目标维度510至550的要求(查询项)的数据条目存在的概率(被表示为“P(A,B,C,D,E)”)可以被估计为如下：

其中P(A,B,C,D,E)表示从在源数据集中查找到维度A至E的维度值均匹配查询104中查询项的数据条目的可能性，p(X1..,Xn)表示相应的目标维度X1至Xn对应的查询项在单个数据子集中确定的存在概率，并且n表示大于等于1的整数。如果用户需要查找的是满足查询104的查询项要求的数据条目，可以将估计的概率P(A,B,C,D,E)与源数据集的数据条目的数目(其可以作为元数据被预先存储)相乘。当然，查询104查询其他信息的话，也可以相应地根据概率分析方法给出查询结果。

上文已经描述了如何基于已有的数据子集、通过查询分解的方式估计查询结果。如以上提及的，查询的分解与已有的数据子集覆盖的目标维度有关。为了使得存储的数据子集可以覆盖更多的维度组合以便于为更多不同的查询均给出准确或估计的查询结果，本公开内容的实现还提出了一种从源数据集生成数据子集的方案。该方案可以由查询处理设备102在接收查询104或生成其查询结果之前被执行。在下文中，源数据集的维度被称为源维度，以便于与查询项相关的目标维度进行区分。

不同于已有的方案中由用户引导数据子集的生成，本公开内容的数据子集生成方案可以自动地在一定约束条件下生成数据子集。一个约束条件是对源数据集的维度组合的覆盖率的要求。在存储空间有限的情况下还可以另外地考虑对生成的数据子集的总数据量的要求。提出这些约束是因为考虑在在生成数据子集时通常面临的如下问题。一方面，为了能够获得较高的覆盖率，一些已有方案总是选择存储涉及源数据集的全部源维度的数据子集(相当于源数据集)，以便于能够为所有类型的查询准确地确定查询结果。然而，全维度的数据子集将会消耗过多存储空间。另一方面，数据子集、例如数据立方体的一个特征是高维度的数据子集可以对低维度的查询给出查询结果、但是反过来却不成立。这也是为何希望提高数据子集的维度覆盖率的原因。通过在上述约束条件下执行数据子集的生成，可以在数据存储和维度覆盖率之间进行权衡。

图8示出了根据本公开内容的一个实现的用于生成数据子集的过程800的流程图。过程800也可以实现在查询处理设备102处。在 810，由查询处理设备102从源数据集创建多个候选数据子集。候选数据子集的创建可以基于对源数据集的源维度的组合的预定覆盖率，以使得每个候选数据子集覆盖源维度中的至少两个源维度。

对源维度的组合的预定覆盖率可以由多个候选数据子集覆盖的维度的不同组合数与源维度的全部组合的比率来表示。例如，对于覆盖3个源维度A、B和C的候选数据子集而言，其涉及的源维度的组合包括：

{A}、{B}、{C}、{A、B}、{A、C}、{B、C}、{A、B、 C}。在本公开内容的一个实现中，为了促进查询的分解，预定覆盖率可以包括对源维度中的两个源维度的组合的覆盖率。例如，预定覆盖率可以指示多个候选数据子集应当覆盖所有不同的两个源维度的组合。这是因为在计算查询项的相关度时都要涉及两个目标维度的数据条目。在这样的预定覆盖率的约束下，可以首先将多个候选数据子集创建为覆盖两个不同的源维度。

可以理解的是，也可以将一个或多个候选数据子集创建为覆盖比两个更多或更少的源维度。例如，在对两个维度的组合的预定覆盖率低于100％时，可以创建覆盖其他源维度数目的候选数据子集。另外要注意的是，在810处可以不直接生成候选数据子集，而仅仅创建候选数据子集的架构(例如确定所覆盖的源维度)，以便于节约计算资源。在另外一些实现中，也可以直接从源数据集生成候选数据子集以供后续处理。

在一些实现中，在创建候选数据子集之前，还可以丢弃源数据集中的一部分源维度、例如具有高基数的源维度。已经观察到，在大数据集中，诸如时间戳或标识符之类的源维度总是会产生高基数(即具有大量的不同取值)。由于在数据分析和查询中，用户可能更注意概括性数据而不是具体的数值。因此，可以丢弃源数据集中的涉及时间戳或标识符之类的具有高基数的源维度(如果存在的话)，以便于降低总数据量。

由于创建的候选数据子集中对于源维度的组合的覆盖不高(例如可能没有覆盖三个源维度以上)，因而可以将其中一些候选数据子集进行合并。查询处理设备102在820从多个候选数据子集中选择至少两个候选数据子集，并且在830将选择的候选数据子集合并为一个候选数据子集。合并后的候选数据子集覆盖至少两个候选数据子集对应的源维度。例如，可以选择将具有源维度{A、B}和{B、C}的两个候选数据子集进行合并，从而可以得到合并后的候选数据子集{A、B、 C}。在一些实现中，查询处理设备102可以随机地选择一些候选数据子集。在另外一些实现中，可以选择数据量(尺寸)较小的多个候选数据子集进行选择。选择尺寸较小的候选数据子集进行合并是为了避免合并后的候选数据子集的尺寸增长过快。对于候选数据子集的数据量的估计将在下文详述。

合并后的候选数据子集将会提供更高的维度覆盖。为了防止冗余，在840，查询处理设备102标识其源维度由合并后的候选数据子集覆盖的候选数据子集。被标识的候选数据子集可以被丢弃或者可以从后续操作中被排除。例如，如果在820和830处选择并且将具有源维度{A、B}和{B、C}的候选数据子集进行合并得到候选数据子集{A、 B、C}，那么在840可以将候选数据子集{A、B}和{B、C}丢弃，因为其维度都已经由合并后的候选数据子集{A、B、C}覆盖。当然，可以被丢弃的可能不只是用于合并的那些候选数据子集，因为合并后的候选数据子集还可能涵盖其他的维度组合。例如，如果在820和830 处选择涉及{A、B、D}和{B、C}的两个候选数据子集进行合并，那么在840可以除了可以丢弃这两个候选数据子集之外，还可以丢弃涉及诸如{A、B}、{A、D}、{A、C}、{B、D}、{A、B、C}、{A、C、 D}和{B、C、D}之类的维度组合的候选数据子集(如何存在的话)。

基于除所标识的候选数据子集之外的其余候选数据子集(包括合并后的候选数据子集)，可以确定要被存储到查询处理设备102可访问的存储设备130中的数据子集。在一些实现中，为了满足存储约束，在850，查询处理设备102确定其余候选数据子集的总数据量是否超过可用存储空间。这里的可用存储空间指的是查询处理设备102 将要用于存储数据子集的存储设备的可用存储空间。对于其余候选数据子集的总数据量的计算可以基于每个候选数据子集的数据量，这将在以下详细描述。

如果确定其余候选数据子集的总数据量不超过可用存储空间、也即总数据量小于或等于可用存储空间，查询处理设备102在860将其余候选数据子集确定为查询处理设备102的数据子集。此时，可以基于这些其余候选数据子集覆盖的源维度，从源数据集生成数据子集。

如果确定其余候选数据子集的总数据量超过可用存储空间，则返回820继续选择候选数据子集进行合并。此时可以从之前未被丢弃的其余候选数据子集(包括合并后的候选数据子集)之中进行选择。过程800可以迭代地执行，直到被保留的候选数据子集可以被存储到预定的存储空间中。

接下来讨论对候选数据子集的大小的估计。候选数据子集的数据量可以以该子集中的不同数据条目的数目(也称为不同计数“distinct count”)来衡量。因为不同数据条目的数目可以影响存储该子集时所要占用的存储空间。在本文中，不同的数据条目意味着该数据条目在一个或多个源维度上的数据项(维度值)与其他数据条目不同。确定不同计数的值的一种简单方法是直接分析每个候选数据子集覆盖的源维度中的数据条目并且统计其中不同数据条目的数目。然而，这将会非常耗时。

在一些实现中，出于效率的原因，可以通过对候选数据子集将包括的数据条目进行采样来估计这个数目。具体地，对于给定候选数据子集，可以从其包括的数据条目中采样多个数据条目。对于候选数据子集未被生成的情况，可以基于该子集覆盖的源维度，从源数据集中进行采样。从采样到的数据条目中确定不同数据条目的第一数目和出现次数小于计数阈值的数据条目的第二数目。在此考虑采样到的数据条目中出现频率较低的数目是因为这个数目可以在很大概率上体现出这个候选数据子集中数据条目的变化程度。在一些示例中，计数阈值可以是一。因此，第二数目被确定为采样到的数据条目中仅出现过一次的数据条目的数目。当然，在其他示例中，计数阈值也可以被确定为二或三之类的较小值。

候选数据子集包括的不同数据条目的数目可以与第一数目和第二数目正相关。如果采样到的数据条目中不同数据条目和出现频率较小的数据条目的数目均较大，那么候选数据子集中包括的不同数据条目的数目也较大。以下给出确定候选数据子集中的不同数据条目的数目的一个示例。在该示例中，假设该给定候选数据子集中的数据条目的数目为N，并且从中采样出S个数据条目。经过统计，确定S个数据条目中存在u1个不同的数据条目和u2个出现次数小于计数阈值的数据条目。该候选数据子集中不同数据条目的数目U可以如下计算：

应当理解的是，以上给出的仅是根据数目u1和u2来确定数目U的一个具体示例。还可以以许多其他方式来根据数目u1和u2计算数目U，只要能够体现其正相关关系即可。例如，可以分别对u1和u2进行加权并且与S相乘来计算U。

在一些示例中，可以将每个候选数据子集的不同数据条目的数目作为其数据量的一个度量，并且然后与具有同样度量的数据量阈值进行比较来选择要被合并的候选数据子集。当需要计算多个候选数据子集的总数据量时(例如在850处)，由于总数据量要与可用存储空间进行比较，则可以基于每个候选数据子集的不同数据条目的数目估计要占用的存储空间的大小并且然后计算多个候选数据子集占用的总存储空间。在一些示例中，占用的存储空间的大小可以与不同数据条目的数目正相关。附加地，也可以考虑候选数据子集覆盖的源维度的类型和数目来计算该候选数据子集要占用的存储空间。

根据本公开内容的实现，提供了在数据分析的查询处理中基于已有的数据子集为查询确定尽可能正确的查询结果。这不要求任何对于源数据分布或者历史工作量之类的先验知识，并且避免了离线对源数据集进行分析的时间消耗，实现了更快速的查询处理。此外，本公开内容还提供了从源数据子集生成数据子集的方案。在生成数据子集时，在给定存储空间的约束下，使得生成的数据子集不仅具有较小的数据量、而且能够覆盖更多的维度组合。此外，还能够自动地将数据子集覆盖的维度组合适配为更快速且准确地为更多的查询提供查询结果、并且还能够满足在查询估计时对于相关度的计算的需要。

本文中以上描述的功能可以至少部分地由一个或多个硬件逻辑部件来执行。例如，非限制性地，可以使用的示范类型的硬件逻辑部件包括：场可编程门阵列(FPGA)、专用集成电路(ASIC)、专用标准产品(ASSP)、芯片上系统的系统(SOC)、负载可编程逻辑设备(CPLD)等等。

用于实施本公开内容的方法的程序代码可以采用一个或多个编程语言的任何组合来编写。这些程序代码可以提供给通用计算机、专用计算机或其他可编程数据处理装置的处理器或控制器，使得程序代码当由处理器或控制器执行时使流程图和/或框图中所规定的功能/操作被实施。程序代码可以完全在机器上执行、部分地在机器上执行，作为独立软件包部分地在机器上执行且部分地在远程机器上执行或完全在远程机器或服务器上执行。

在本公开内容的上下文中，机器可读介质可以是有形的介质，其可以包含或存储以供指令执行系统、装置或设备使用或与指令执行系统、装置或设备结合地使用的程序。机器可读介质可以是机器可读信号介质或机器可读储存介质。机器可读介质可以包括但不限于电子的、磁性的、光学的、电磁的、红外的、或半导体系统、装置或设备，或者上述内容的任何合适组合。机器可读存储介质的更具体示例会包括基于一个或多个线的电气连接、便携式计算机盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦除可编程只读存储器(EPROM或快闪存储器)、光纤、便捷式紧凑盘只读存储器 (CD-ROM)、光学储存设备、磁储存设备、或上述内容的任何合适组合。

此外，虽然采用特定次序描绘了各操作，但是这应当理解为要求这样操作以所示出的特定次序或以顺序次序执行，或者要求所有图示的操作应被执行以取得期望的结果。在一定环境下，多任务和并行处理可能是有利的。同样地，虽然在上面论述中包含了若干具体实现细节，但是这些不应当被解释为对本公开内容的范围的限制。在单独的实现的上下文中描述的某些特征还可以组合地实现在单个实现中。相反地，在单个实现的上下文中描述的各种特征也可以单独地或以任何合适的子组合的方式实现在多个实现中。

以下列出了本公开内容的一些示例实现方式。

在一方面，本公开内容提供了一种计算机实施的方法。该方法包括：接收包含多个查询项的查询，所述多个查询项与数据条目的多个目标维度相关；确定所述多个目标维度是否需多个数据子集中的至少两个数据子集覆盖，所述多个数据子集中的至少一个数据子集包括与所述多个目标维度中的至少一个目标维度对应的数据条目；响应于所述多个目标维度需所述多个数据子集中的至少两个数据子集覆盖，将所述查询分解为多个子查询，每个子查询具有所述多个查询项中的至少一个查询项；以及通过分析所述多个数据子集中与每个子查询的所述至少一个查询项相关的目标维度的数据条目，来确定针对所述查询的查询结果。

在一些实现中，将所述查询分解为多个子查询包括：确定所述多个查询项中的每个查询项对之间的相关度；基于所述相关度和每个数据子集对应的目标维度，确定所述多个目标维度的关联性；以及基于确定的关联性将所述查询分解为所述多个子查询，使得具有多个查询项的子查询对应的目标维度被确定具有关联性。

在一些实现中，确定每个查询项对之间的相关度包括：基于所述多个查询项在对应的目标维度中存在的概率值，确定每个查询项对之间的互信息。

在一些实现中，确定所述多个目标维度的关联性包括通过以下至少一项确定所述多个目标维度中的两个目标维度具有关联性：与所述两个目标维度有关的查询项对之间的相关度大于相关度阈值；所述两个目标维度由所述多个数据子集中的第一数据子集覆盖；以及所述两个目标维度以及与所述两个目标维度中的一个目标维度具有关联性的另一目标维度由所述多个数据子集中的第二数据子集覆盖。

在一些实现中，该方法进一步包括：基于对源数据集的源维度的组合的预定覆盖率，从所述源数据集创建多个候选数据子集，每个候选数据子集覆盖所述源维度中的至少两个源维度；将所述多个候选数据子集中的至少两个候选数据子集合并为一个候选数据子集，使得合并后的候选数据子集覆盖所述至少两个候选数据子集的源维度；标识所述多个候选数据子集中其源维度由合并后的候选数据子集覆盖的候选数据子集；以及基于除所标识的候选数据子集之外的其余候选数据子集确定所述多个数据子集。

在一些实现中，该方法进一步包括通过以下选择所述至少两个候选数据子集：确定所述多个候选数据子集中的每个候选数据子集的数据量；以及从所述多个候选数据子集中选择数据量小于数据量阈值的所述至少两个候选数据子集。

在一些实现中，确定每个候选数据子集的数据量包括：从给定候选数据子集包括的数据条目中采样多个数据条目；确定采样到的所述多个数据条目中不同数据条目的第一数目和出现次数小于计数阈值的数据条目的第二数目；基于所述第一数目和所述第二数目，确定所述给定候选数据子集包括的不同数据条目的数目；以及基于所述不同数据条目的数目确定所述给定候选数据子集的数据量。

在一些实现中，基于其余候选数据子集确定所述多个数据子集包括：确定其余候选数据子集的总数据量是否超过可用于存储所述多个数据子集的存储空间；以及响应于所述总数据量小于或等于所述存储空间，将所述其余候选数据子集确定为所述多个数据子集。

在一些实现中，所述多个数据子集被存储在可快速访问的存储设备中。

在另一方面，本公开内容提供了一种设备。该设备包括：处理单元；存储器，耦合至所述处理单元并且存储有指令，所述指令在由所述处理单元执行时执行以下动作：接收包含多个查询项的查询，所述多个查询项与数据条目的多个目标维度相关；确定所述多个目标维度是否需多个数据子集中的至少两个数据子集覆盖，所述多个数据子集中的至少一个数据子集包括与所述多个目标维度中的至少一个目标维度对应的数据条目；响应于所述多个目标维度需所述多个数据子集中的至少两个数据子集覆盖，将所述查询分解为多个子查询，每个子查询具有所述多个查询项中的至少一个查询项；以及通过分析所述多个数据子集中与每个子查询的所述至少一个查询项相关的目标维度的数据条目，来确定针对所述查询的查询结果。

在一些实现中，将所述查询分解为多个子查询包括：确定所述多个查询项中的每个查询项对之间的相关度；基于所述相关度和每个数据子集对应的目标维度，确定所述多个目标维度的关联性；以及基于确定的关联性将所述查询分解为所述多个子查询，使得具有多个查询项的子查询对应的目标维度被确定具有关联性。

在一些实现中，确定每个查询项对之间的相关度包括：基于所述多个查询项在对应的目标维度中存在的概率值，确定每个查询项对之间的互信息。

在一些实现中，确定所述多个目标维度的关联性包括通过以下至少一项确定所述多个目标维度中的两个目标维度具有关联性：与所述两个目标维度有关的查询项对之间的相关度大于相关度阈值；所述两个目标维度由所述多个数据子集中的第一数据子集覆盖；以及所述两个目标维度以及与所述两个目标维度中的一个目标维度具有关联性的另一目标维度由所述多个数据子集中的第二数据子集覆盖。

在一些实现中，所述动作进一步包括：基于对源数据集的源维度的组合的预定覆盖率，从所述源数据集创建多个候选数据子集，个候选数据子集覆盖所述源维度中的至少两个源维度；将所述多个候选数据子集中的至少两个候选数据子集合并为一个候选数据子集，使得合并后的候选数据子集覆盖所述至少两个候选数据子集的源维度；标识所述多个候选数据子集中其源维度由合并后的候选数据子集覆盖的候选数据子集；以及基于除所标识的候选数据子集之外的其余候选数据子集确定所述多个数据子集。

在一些实现中，所述动作进一步包括通过以下选择所述至少两个候选数据子集：确定所述多个候选数据子集中的每个候选数据子集的数据量；以及从所述多个候选数据子集中选择数据量小于数据量阈值的所述至少两个候选数据子集。

在一些实现中，确定每个候选数据子集的数据量包括：从给定候选数据子集包括的数据条目中采样多个数据条目；确定采样到的所述多个数据条目中不同数据条目的第一数目和出现次数小于计数阈值的数据条目的第二数目；基于所述第一数目和所述第二数目，确定所述给定候选数据子集包括的不同数据条目的数目；以及基于所述不同数据条目的数目确定所述给定候选数据子集的数据量。

在一些实现中，基于其余候选数据子集确定所述多个数据子集包括：确定其余候选数据子集的总数据量是否超过可用于存储所述多个数据子集的存储空间；以及响应于所述总数据量小于或等于所述存储空间，将所述其余候选数据子集确定为所述多个数据子集。

在一些实现中，所述多个数据子集被存储在可快速访问的存储设备中。

在又一方面，本公开内容提供了一种计算机程序产品。所述计算机程序产品被存储在非瞬态计算机存储介质中并且包括机器可执行指令，所述机器可执行指令在设备中运行时使得所述设备：接收包含多个查询项的查询，所述多个查询项与数据条目的多个目标维度相关；确定所述多个目标维度是否需多个数据子集中的至少两个数据子集覆盖，所述多个数据子集中的至少一个数据子集包括与所述多个目标维度中的至少一个目标维度对应的数据条目；响应于所述多个目标维度需所述多个数据子集中的至少两个数据子集覆盖，将所述查询分解为多个子查询，每个子查询具有所述多个查询项中的至少一个查询项；以及通过分析所述多个数据子集中与每个子查询的所述至少一个查询项相关的目标维度的数据条目，来确定针对所述查询的查询结果。

在一些实现中，所述机器可执行指令在所述设备中运行时还使得所述设备：确定所述多个查询项中的每个查询项对之间的相关度；基于所述相关度和每个数据子集对应的目标维度，确定所述多个目标维度的关联性；以及基于确定的关联性将所述查询分解为所述多个子查询，使得具有多个查询项的子查询对应的目标维度被确定具有关联性。

尽管已经采用特定于结构特征和/或方法逻辑动作的语言描述了本主题，但是应当理解所附权利要求书中所限定的主题未必局限于上面描述的特定特征或动作。相反，上面所描述的特定特征和动作仅仅是实现权利要求书的示例形式。

Claims (18)

1.一种计算机实施的方法，包括：

接收包含多个查询项的查询，所述多个查询项与数据条目的多个目标维度相关；

确定所述多个目标维度是否需多个数据子集中的至少两个数据子集覆盖，所述多个数据子集中的至少一个数据子集包括与所述多个目标维度中的至少一个目标维度对应的数据条目；

响应于所述多个目标维度需所述多个数据子集中的至少两个数据子集覆盖，将所述查询分解为多个子查询，每个子查询具有所述多个查询项中的至少一个查询项；以及

通过分析所述多个数据子集中与每个子查询的所述至少一个查询项相关的目标维度的数据条目，来确定针对所述查询的查询结果，

其中所述方法进一步包括：

基于对源数据集的源维度的组合的预定覆盖率，从所述源数据集创建多个候选数据子集，每个候选数据子集覆盖所述源维度中的至少两个源维度；

将所述多个候选数据子集中的至少两个候选数据子集合并为一个候选数据子集，使得合并后的候选数据子集覆盖所述至少两个候选数据子集的源维度；

标识所述多个候选数据子集中其源维度由合并后的候选数据子集覆盖的候选数据子集；以及

基于除所标识的候选数据子集之外的其余候选数据子集确定所述多个数据子集。

2.根据权利要求1所述的方法，其中将所述查询分解为多个子查询包括：

确定所述多个查询项中的每个查询项对之间的相关度；

基于所述相关度和每个数据子集对应的目标维度，确定所述多个目标维度的关联性；以及

基于确定的关联性将所述查询分解为所述多个子查询，使得具有多个查询项的子查询对应的目标维度被确定具有关联性。

3.根据权利要求2所述的方法，其中确定每个查询项对之间的相关度包括：

基于所述多个查询项在对应的目标维度中存在的概率值，确定每个查询项对之间的互信息。

4.根据权利要求2所述的方法，其中确定所述多个目标维度的关联性包括通过以下至少一项确定所述多个目标维度中的两个目标维度具有关联性：

与所述两个目标维度有关的查询项对之间的相关度大于相关度阈值；

所述两个目标维度由所述多个数据子集中的第一数据子集覆盖；以及

所述两个目标维度以及与所述两个目标维度中的一个目标维度具有关联性的另一目标维度由所述多个数据子集中的第二数据子集覆盖。

5.根据权利要求1所述的方法，进一步包括通过以下选择所述至少两个候选数据子集：

确定所述多个候选数据子集中的每个候选数据子集的数据量；以及

从所述多个候选数据子集中选择数据量小于数据量阈值的所述至少两个候选数据子集。

6.根据权利要求5所述的方法，其中确定每个候选数据子集的数据量包括：

从给定候选数据子集包括的数据条目中采样多个数据条目；

确定采样到的所述多个数据条目中不同数据条目的第一数目和出现次数小于计数阈值的数据条目的第二数目；

基于所述第一数目和所述第二数目，确定所述给定候选数据子集包括的不同数据条目的数目；以及

基于所述不同数据条目的数目确定所述给定候选数据子集的数据量。

7.根据权利要求1所述的方法，其中基于其余候选数据子集确定所述多个数据子集包括：

确定其余候选数据子集的总数据量是否超过可用于存储所述多个数据子集的存储空间；以及

响应于所述总数据量小于或等于所述存储空间，将所述其余候选数据子集确定为所述多个数据子集。

8.根据权利要求1所述的方法，其中所述多个数据子集被存储在可快速访问的存储设备中。

9.一种电子设备，包括：

处理单元；

存储器，耦合至所述处理单元并且存储有指令，所述指令在由所述处理单元执行时执行以下动作：

接收包含多个查询项的查询，所述多个查询项与数据条目的多个目标维度相关；

确定所述多个目标维度是否需多个数据子集中的至少两个数据子集覆盖，所述多个数据子集中的至少一个数据子集包括与所述多个目标维度中的至少一个目标维度对应的数据条目；

响应于所述多个目标维度需所述多个数据子集中的至少两个数据子集覆盖，将所述查询分解为多个子查询，每个子查询具有所述多个查询项中的至少一个查询项；以及

通过分析所述多个数据子集中与每个子查询的所述至少一个查询项相关的目标维度的数据条目，来确定针对所述查询的查询结果，

其中所述动作进一步包括：

基于对源数据集的源维度的组合的预定覆盖率，从所述源数据集创建多个候选数据子集，每个候选数据子集覆盖所述源维度中的至少两个源维度；

将所述多个候选数据子集中的至少两个候选数据子集合并为一个候选数据子集，使得合并后的候选数据子集覆盖所述至少两个候选数据子集的源维度；

标识所述多个候选数据子集中其源维度由合并后的候选数据子集覆盖的候选数据子集；以及

基于除所标识的候选数据子集之外的其余候选数据子集确定所述多个数据子集。

10.根据权利要求9所述的设备，其中将所述查询分解为多个子查询包括：

确定所述多个查询项中的每个查询项对之间的相关度；

基于所述相关度和每个数据子集对应的目标维度，确定所述多个目标维度的关联性；以及

基于确定的关联性将所述查询分解为所述多个子查询，使得具有多个查询项的子查询对应的目标维度被确定具有关联性。

11.根据权利要求10所述的设备，其中确定每个查询项对之间的相关度包括：

基于所述多个查询项在对应的目标维度中存在的概率值，确定每个查询项对之间的互信息。

12.根据权利要求10所述的设备，其中确定所述多个目标维度的关联性包括通过以下至少一项确定所述多个目标维度中的两个目标维度具有关联性：

与所述两个目标维度有关的查询项对之间的相关度大于相关度阈值；

所述两个目标维度由所述多个数据子集中的第一数据子集覆盖；以及

所述两个目标维度以及与所述两个目标维度中的一个目标维度具有关联性的另一目标维度由所述多个数据子集中的第二数据子集覆盖。

13.根据权利要求9所述的设备，其中所述动作进一步包括通过以下选择所述至少两个候选数据子集：

确定所述多个候选数据子集中的每个候选数据子集的数据量；以及

从所述多个候选数据子集中选择数据量小于数据量阈值的所述至少两个候选数据子集。

14.根据权利要求13所述的设备，其中确定每个候选数据子集的数据量包括：

从给定候选数据子集包括的数据条目中采样多个数据条目；

确定采样到的所述多个数据条目中不同数据条目的第一数目和出现次数小于计数阈值的数据条目的第二数目；

基于所述第一数目和所述第二数目，确定所述给定候选数据子集包括的不同数据条目的数目；以及

基于所述不同数据条目的数目确定所述给定候选数据子集的数据量。

15.根据权利要求9所述的设备，其中基于其余候选数据子集确定所述多个数据子集包括：

确定其余候选数据子集的总数据量是否超过可用于存储所述多个数据子集的存储空间；以及

响应于所述总数据量小于或等于所述存储空间，将所述其余候选数据子集确定为所述多个数据子集。

16.根据权利要求9所述的设备，其中所述多个数据子集被存储在可快速访问的存储设备中。

17.一种计算机可读存储介质，其上存储有机器可执行指令，所述机器可执行指令在设备中运行时使得所述设备：

接收包含多个查询项的查询，所述多个查询项与数据条目的多个目标维度相关；

确定所述多个目标维度是否需多个数据子集中的至少两个数据子集覆盖，所述多个数据子集中的至少一个数据子集包括与所述多个目标维度中的至少一个目标维度对应的数据条目；

响应于所述多个目标维度需所述多个数据子集中的至少两个数据子集覆盖，将所述查询分解为多个子查询，每个子查询具有所述多个查询项中的至少一个查询项；以及

通过分析所述多个数据子集中与每个子查询的所述至少一个查询项相关的目标维度的数据条目，来确定针对所述查询的查询结果，

其中所述机器可执行指令在所述设备中运行时还使得所述设备：

基于对源数据集的源维度的组合的预定覆盖率，从所述源数据集创建多个候选数据子集，每个候选数据子集覆盖所述源维度中的至少两个源维度；

将所述多个候选数据子集中的至少两个候选数据子集合并为一个候选数据子集，使得合并后的候选数据子集覆盖所述至少两个候选数据子集的源维度；

标识所述多个候选数据子集中其源维度由合并后的候选数据子集覆盖的候选数据子集；以及

基于除所标识的候选数据子集之外的其余候选数据子集确定所述多个数据子集。

18.根据权利要求17所述的计算机可读存储介质，其中所述机器可执行指令在所述设备中运行时还使得所述设备：

确定所述多个查询项中的每个查询项对之间的相关度；

基于所述相关度和每个数据子集对应的目标维度，确定所述多个目标维度的关联性；以及

基于确定的关联性将所述查询分解为所述多个子查询，使得具有多个查询项的子查询对应的目标维度被确定具有关联性。

Images