1.1.1　基本概念

作为数据库系统的核心技术,数据的查询处理一直备受学术界和工业界的关注,它是系统进程对数据集按照既定条件完成过滤并返回结果的过程。面对庞大的数据量和复杂查询条件时,需要较长时间才能反馈精确的查询结果,难以实现交互式的快速响应速度,而太长的响应时间对于特定用户和应用程序而言是不可接受的。同时,在复杂的查询条件处理过程中,用户无法获得查询的阶段性结果及执行进度,难以根据前期结果来决定进一步的操作,如取消查询或有针对性修改查询条件。实际上,大量观察表明,如果适当降低查询精度,允许查询结果中包含一定的误差,那么查询处理的速度可以得以有效提高,近似查询技术(Approximate Query Process,AQP)应运而生。(https://www.daowen.com)

需要运用近似查询技术解决的具体查询问题通常具有下列特点:一是数据量大,二是计算较复杂。涉及的数据量大的典型代表是数据库中聚集函数,其输入为满足条件的所有数据集合,输出为该数据集合的计算结果,通常为一个数值。聚集函数包括平均值、计数、求和、最大值、最小值等,例如计算出某个国家所有年龄大于35岁的受过高等教育的男性的平均收入,采用随机化算法或分层数据采样等技术可以获得一个在给定置信水平上的查询结果的区间,近似查询相比完全查询所需要的时间显著降低。计算较复杂的查询问题的典型代表为最短路径查询,由于计算步骤多,因此通常需要对原始数据进行预处理以生成特定的数据结构,辅助后期的处理,例如预先计算的节点到达度(reach)与k选点覆盖(k-skip cover)网络等。利用这些先期建立的辅助结构进行查询,可以有效减少处理时间,并逐步给出精化的结果。