吴文莉， 刘国华,

(1 东华大学 计算机科学与技术学院, 上海 201620; 2 上海市数据科学重点实验室(复旦大学)， 上海 201203)

0 引 言

查询(即，由数据库到关系的函数)和查询语言(即，用于表示这一函数的语言)[1]一直以来都备受人们关注。Codd于1970年提出关系数据模型后，关系模型的查询及查询语言成为研究热点，出现了一批具有影响力的研究成果，如一阶关系演算以及关系代数[2-3]、合取查询[4]、表查询[5]、函数查询语言[6]等。

近年来，随着大数据地位的提升，如何在大数据环境下准确、高效地得到查询结果是函数查询亟待解决的问题，其中如何解决查询解答问题一直是人们关注的重点问题。大数据为查询解答带来了挑战，大数据查询的计算复杂性不再类似传统查询[7]。文献[7]对查询解答问题难易程度的判定提出了形式化的方法，并对预处理问题进行了研究，提出了数据驱动的预处理和查询驱动的预处理两种方法。文献[8]明确了大数据环境下查询解答问题难易程度的划分标准，对什么查询在大数据上是易处理的、如何求解大数据查询的复杂性等问题给出了一系列预处理方案，对查询解答问题的近似求解算法进行了探讨。

在大数据应用环境下，函数查询成为主要操作，如函数查询语言可以用于定义大数据上的分析查询，用其结果定义各种执行任务[9]。为了便于表示大数据上的函数查询，Nicholas等人[9]提出一种高级函数查询语言(HIFUN)，但没有给出函数查询的形式化定义，也没有对函数查询的结构特征及复杂性问题进行研究。……