视图确定性问题研究范文

本站小编为你精心准备了视图确定性问题研究参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

《计算机工程与应用杂志》2014年第十四期

1问题描述

1.1视图确定性视图确定性问题形式化描述为：给定模式R上的一个查询Q和一组视图V如果对于R上的任意两个数据库实例D1和D2都有V(D1)=V(D2)蕴含Q(D1)=Q(D2)则称视图V确定查询Q。实际上，如果确定性成立，则可以找到一个算法，对每一个视图查询实例I=V(D)返回Q的查询结果Q(D)。算法描述如下：按照某一顺序遍历模式R上的数据库实例；假设当前遍历的数据库为D′首先判断V(D′)=I是否成立，若成立，则计算Q(D′)并结束，否则继续遍历。一方面，因为V确定Q如果V(D′)=I=V(D)则必有Q(D′)=Q(D)保证了算法的正确性；另一方面，总能够找到一个数据库D′（例如D′=D）使得V(D′)=I=V(D)保证了算法的终止性。因此，如果视图V确定查询Q则必存在一个算法利用视图V计算出Q的查询结果，也即从理论上保证视图V含有足够的信息来回答查询Q。

1.2查询重写与基于视图的查询回答相关的另一个问题是基于视图的查询重写（QueryRewriting），形式化描述如下：给定模式R上的一个查询Q和一组视图V以及查询语言类L如果存在一个查询PÎLP仅对V中的视图进行访问并且对于R上的任意数据库D都有Q(D)=P(V(D))则称Q能够使用V在语言L中查询重写。显然，如果Q能使用V在某一语言类L中进行查询重写，则V必定确定Q；反之不一定成立，因为查询重写和重写语言L的表达能力有关。换言之，查询重写其实是从语法的角度回答“如何形式化地描述一组视图V含有足够的信息来回答一个查询Q”这一问题。如果Q能使用V在某一语言类L中进行查询重写，则V必定含有足够的信息回答Q。但是查询重写限定了重写的语言类L如果Q不能使用V在语言类L内进行重写，并不能说明V中的信息不足以回答Q因为很有可能是由于L的表达能力太弱而不能够表达出利用V计算Q的算法（或称可计算函数）。实际上，文献[9-11]均举例指出，对于一个合取查询Q和一组使用合取查询描述的视图V不存在Q使用V的合取查询重写，但是存在一个一阶逻辑查询可以利用V计算出Q。

1.3语言完全性根据查询重写和视图确定性之间的关系，Segoufin等人[8]提出重写语言完全性（Completeness）的概念：给定查询定义语言类LQ和视图定义语言类Lv称语言类L对于LV到LQ的查询重写（记作LV-to-LQ）是完全的，当且仅当对于LQ中的任意查询Q和Lv中的任意一组视图V如果V确定Q则存在一个Q使用V在语言L中的查询重写P。语言完全性实质上是说如果视图确定性成立，则依靠该语言类的表达能力足够描述利用视图计算查询结果的算法（或称可计算函数）。

2研究维度

视图确定性相关的研究主要围绕以下两个问题展开：（1）给定一个查询Q和一组视图V是否有V确定Q?（2）给定查询定义语言类LQ和视图定义语言类Lv对于LV到LQ的查询重写完全的语言类是什么?其中第一个问题属于判定问题，主要考虑问题的判定性以及判定复杂度。一般来说，问题的判定复杂度和输入参数所属语言类的表达能力之间存在着制约关系。例如，上下文无关语言的包含判定是不可解的[12]，但是正则语言（使用正则表达式表示时）的包含判定问题则可以在PSPACE内解决[13]，进一步缩小到确定性正则语言时判定复杂度可以降低为PTIME[14]。因此，对于视图确定性问题的判定复杂度按照输入参数即查询Q和视图V所属的不同语言类LQ和LV来进行分析。第二个问题本质上属于证明性问题，一般解决思路是先猜测一个语言类L然后严格证明L对LV到LQ的查询重写是完全的。同样，猜测的语言类L与输入参数LQ和LV有关。一般而言，LQ和LV的表达能力越强，其完全语言类L的表达能力也越强。因此，与第一个判定问题类似，寻找查询重写完全语言类也按照不同语言类LQ和LV来进行。关系数据库中常见的查询语言是SQL（StructuredQueryLanguage）。其表达式基本结构包括三个子句：select子句、from子句和where子句，分别对应于关系代数中的投影、笛卡尔积和选择谓词。另外两种具有影响力的商业语言是QBE和Quel，以及一种在系统研究中使用的语言Datalog。QBE基于域关系演算，Quel基于元组关系演算，Datalog基于逻辑编程语言Prolog[15]。判定问题主要考虑查询语言的表达能力，只关注这些商业语言的底层理论基础，因此需要从理论的角度对查询进行刻画。理论上，关系查询可以从逻辑（Logic）、规则（Rule）和代数（Algebra）三个角度进行定义。例如，给定模式R=(R1R2)关系R1和R2的元数均为2，要求查询R1的第二列和R2的第一列相同的那些元组，返回R1的第一列和R2的第二列。该查询从以上三个角度分别定义如下。视图确定性问题的研究主要考虑以下几类查询语言：合取查询（CQ）、并合取查询（UCQ）、一阶逻辑查询（FO）和Datalog查询。这些语言的具体定义参见文献[16]，此处只简单从逻辑和代数的角度给出其描述，如表1所示。其中与Datalog对应的RE算子表示递归，也即Datalog是在UCQ的基础上增加了一个不动点（Fixpoint）操作。合取查询从关系代数的角度而言是指只使用选择（Selection）、投影（Projection）和笛卡尔乘积（CartesianProduct）操作构成的一类查询，因此又称为选择-投影-乘积（简称SPC）查询。视图确定性问题的研究中还考虑合取查询的如下几个特殊子类：SP查询，仅有选择和投影操作构成的查询；PC查询，仅有投影和乘积操作构成的查询；SC查询，仅有选择和乘积操作构成的查询。除了从输入参数所属不同语言类进行划分外，视图确定性问题还从以下两个角度进行研究：单个视图vs多个视图：单个视图是指视图V中只含有一个，换言之，视图定义中只有一条查询语句。即使对于最简单的合取查询CQ，单个视图下的和多个视图下的视图确定性问题是否等价尚未可知[10]。因此研究时往往从比较简单的单个视图情况开始，继而扩展到多个视图情况下。下文中如未特别指出均指的是多个视图情况下。无限制数据库vs有限制数据库：无限制（unrestricted）数据库没有限制数据库实例必须是有限的（即数据库中的元组可以无限），有限制（restricted）数据库则相反。实际使用中的数据库实例都是有限的，但是在理论研究时允许有无限数据库实例的情况，而且往往这种情况下问题证明会变得比较简单，因为在进行构造证明时可以向构造的数据库中添加任意需要的元组而不用考虑最终构造的数据库是否会违反无限性。视图确定性问题的研究大多都是针对有限制的情况，在下文中除非特别说明均指有限制情况下。

3研究进展

视图确定性问题由Segoufin和Vianu于2005年首次提出，之后得到众多数据库理论方面研究学者的持续关注。下面总结已有的主要研究成果以及未解决的开放性问题。

3.1不可判定的情况Segoufin和Vianu[8]利用一阶逻辑的可满足性以及有效性问题进行归约，证明出当视图语言或者查询语言是一阶逻辑查询（FO）时，视图确定性问题是不可判定的。并且，一阶逻辑对于一阶逻辑到一阶逻辑的查询重写（FO-to-FO）是不完全的，也即，对于一个一阶逻辑查询Q和一组一阶逻辑视图V如果V确定Q则不一定仍旧存在一个一阶逻辑查询P使得对于任意数据库实例D有Q(D)=P(V(D))。实际上，任何一种对FO-to-FO查询重写完全的语言必须是图灵完全的。但是在无限制数据库的情况下，一阶逻辑对于一阶逻辑到一阶逻辑的查询重写（FO-to-FO）是完全的。Segoufin和Vianu[8]同时指出当视图语言和查询语言都是并合取查询（UCQ）时，视图确定性问题是不可判定的。即使视图V是固定的，该问题仍旧是不可判定的。证明利用有限幺半群上的字问题进行归约。并合取查询对于并合取查询到并合取查询的查询重写（UCQ-to-UCQ）是不完全的。实际上，任何一种对于UCQ-to-UCQ查询重写完全的语言都是非单调的。查询语言的单调性是指对于该语言中的任意查询Q和任意数据库实例D1、D2如果D1ÍD2则Q(D1)ÍQ(D2)。已知并合取查询和合取查询都是单调的[16]，而一阶逻辑查询是非单调的。Nash和Segoufin等人[8，10]指出对于UCQ-to-UCQ查询重写完全的语言的表达能力位于存在二阶逻辑($SO)和任意二阶逻辑("SO)[17]之内，但是仍不知道是否位于一阶逻辑之内。Fan等人[18]考虑Datalog查询语言类，利用Datalog查询包含问题归约证明出当查询语言类是Datalog、视图语言类是CQ或者相反地，当视图语言类是Datalog、查询语言类是CQ时，视图确定性问题都是不可判定的。但是没有分析有关Datalog查询重写相关的完全语言类。

3.2合取查询的可判定子类合取查询是一类使用比较广泛并且较为简单的查询语言。Nash等人[10]证明出，与并合取查询类似，任何一种对于合取查询到合取查询的查询重写（CQ-to-CQ）完全的语言都是非单调的，因此，合取查询对于CQ-to-CQ查询重写是不完全的。但是如果已知查询重写P本身是单调的，则P可用合取查询来表达，也即在这种情况下，CQ对于CQ-to-CQ查询重写是完全的。但是合取查询的视图确定性问题是否是可判定的至今尚不知道，并被指出具有相当难度和挑战性[9-10]。视图确定性问题的后续研究大多集中于合取查询的可判定子类上。Nash、Segoufin和Vianu[9-10]给出了合取查询的几种特殊情况，对于这些特殊情况，视图确定性问题是可判定的，并且合取查询对于CQ-to-CQ查询重写仍旧是完全的。（1）当查询是合取查询，视图是布尔合取查询（BoolCQ）时。布尔合取查询是指不含自由变量的查询，其查询结果只有“真”和“假”两个值。例如定义在二元关系R上的如下查询是布尔查询：q()¬R(xx)R(ab)。（2）当查询是合取查询，视图是一元合取查询（MonadicCQ）时。一元合取查询是指含有一个自由变量的查询。例如定义在二元关系R1和R2上的如下查询是个一元合取查询：q(x)¬R1(xa)R2(bx)。（3）当查询是合取查询，视图是单个的路径合取查询（PathCQ）时。路径合取查询是指定义在单个二元关系R上的具有如下形式的合取查询：q(xy)¬R(xx1)R(x1x2)R(xk-1xk)R(xky)。Afrati[11，19]指出当查询是合取查询，视图是完全合取查询（FullCQ）时，视图确定性问题是可判定的，并且合取查询对于CQfull-to-CQ的查询重写是完全的。完全合取查询是指不含有受限变量的合取查询。例如，SC查询即是典型的完全合取查询。当查询和视图都是链合取查询（ChainCQ）时，视图确定性问题是可判定的，并且一阶逻辑FO对于CQchain-to-CQchain的查询重写是完全的。链合取查询是路径合取查询的扩展，其形式与路径合取查询的形式相同，但是允许定义在多个二元关系上。Pasailä[20]在Afrati的基础上进一步指出当查询是链合取查询，视图是连通图合取查询（ConnectedGraphCQ）时，视图确定性问题是可判定的，并且在查询最小化的情况下可在多项式时间内判定。一阶逻辑FO对于CQchain-to-CQcgraph的查询重写是完全的。这里的连通图合取查询是指定义在二元关系上，只含有两个自由变量并且满足如下条件的合取查询：当将查询的体部看作一个无向图时，图是联通的。体部无向图定义为：以查询中的变量为结点，结点x和y之间存在边当且仅当查询体部（即定义规则中）中存在R(xy)或者R(yx)其中R是任意一个二元关系符号。连通图合取查询是对链合取查询的一种扩展，后者的体部无向图实际上构成了一条连接两个自由变量的简单无环路径。例如，如下定义的查询Q1是链合取查询，Q2是连通图合取查询但不是链合取查询。q1(xy)¬R1(xz1)R2(z1z2)R1(z2y)q2(xy)¬R1(xz1)R2(z1z2)R1(z2z3)R2(z3z1)R1(z1y)当查询和视图都是连通图合取查询时，Pasailä给出了一个满足视图确定性的必要非充分条件，但是其判定性仍旧没有解决。Zheng等人[21]证明出当查询和视图都是定义在一元模式上的合取查询（unaryCQ）时，视图确定性问题可在PTIME时间内判定，并且合取查询对于CQunary-to-CQunary的查询重写是完全的。他们同时给出一个O(|Q||V|)复杂度的判定算法，其中|Q|和|V|分别指查询Q和视图V的大小，大小根据Q和V中出现的变量和常量的个数决定。这里的一元模式是指关系模式中的每个关系都是一元的，即只含有一个属性。Fan等人[18]考虑合取查询的三个特殊子类SP、PC和SC查询，证明出当查询Q是合取查询，视图V分别是SP、PC和SC查询时，视图确定性问题的判定复杂度分别是NP完全、PTIME和NP完全的。若查询Q是最小化的，则在视图V为SP查询的情况下，判定复杂度会降低为PTIME。对于这三种情况，合取查询对于查询重写而言仍旧是完全的。一个合取查询Q是最小化的当且仅当不存在一个查询Q′满足Q与Q′等价并且Q′的规模（大小）比Q小。Marx[22]考虑一阶逻辑查询的一个子类，称作Packed一阶逻辑（记作PF），证明出对于这类查询，视图确定性问题是可判定的，并且PF对于PF-to-PF查询重写是完全的。当限定在合取查询上时，也即Packed合取查询（记作PCQ），结论仍旧成立。

3.3存在的问题目前，视图确定性问题相关研究的最大开放性问题是关于合取查询的判定性以及判定复杂度。合取查询是一类使用比较广泛并且较为简单的查询语言，但是不管是在无限制数据库情况下还是有限制数据库情况下，其视图确定性问题至今尚为解决，具有相当难度和挑战性。而且，在这两种情况下视图确定性问题是否等价也尚未可知。一种猜测是在无限制数据库情况下，问题是可判定的；在有限制数据库情况下则相反[10]。但是该猜测尚未得以证实。另外一个开放性问题是在有限制数据库情况下对于CQ-to-CQ查询重写完全的语言类是什么?已知对于UCQ-to-UCQ查询重写完全的语言的表达能力位于存在二阶逻辑($SO)和任意二阶逻辑("SO)之内[8]。由于CQ的表达能力弱于UCQ，可以推知对于CQ-to-CQ查询重写完全的语言类其表达能力的上限是存在二阶逻辑($SO)与任意二阶逻辑("SO)的交集，但下限是什么至今还不知道。表2总结了视图确定性问题已有的研究成果和存在的开放性问题。表中主要给出的是有限制数据库的情况。目前为止，视图确定性问题的研究都是理论方面的，主要关注判定复杂度。从实际应用的角度来讲，设计和实现高效的判定算法也应该是一个重要的研究方向。应用研究可以从两个方面着手：（1）对于在理论研究中已经证明出的可判定的情况，设计尽可能高效的算法，并进行实现和实验；（2）对于理论上证明出不可判定的情况，寻找其可判定的子类。语言的表达能力和判定复杂度之间往往存在着制约关系，表达能力越强的语言类，其判定复杂度越高甚至是不可判定的。但是，实际应用中常见的查询定义或者视图定义往往对应于受限的表达能力。例如，关系查询中一阶逻辑的表达能力要强于合取查询，但是常用到的是合取查询（即简单的SQL语句）。因此，寻找可判定或者判定复杂度较低但是在实际应用中常见的语言子类是很有意义的。同样地，对于找到可判定子类，也要设计尽可能高效的算法。视图确定性判定算法可应用于所有基于视图的查询回答中。如果通过判定算法已知确定性不成立，则说明视图所含信息不足以回答查询，因此没有必要进一步寻找查询重写或查询回答的算法。

4结束语

基于视图的查询回答中一个基本的问题是：如何形式化地描述一组视图V含有足够的信息来回答一个查询Q。“视图确定性”是从信息理论的角度回答该问题而提出的一个新概念。本文对视图确定性问题的研究及进展进行了较全面的论述。视图确定性问题是一个相对比较新的研究问题，目前为止的研究都是针对关系型数据，大部分集中在证明问题的判定复杂度和寻找可判定的合取查询子类方面。随着Web应用的发展，出现了大量的半结构化数据，典型代表是XML[23]数据。XML因其结构简单灵活、允许用户自定义标记、具有良好的可扩展性等优点，在推出的短短几年内已被广泛应用于电子商务、B2B通信、企业信息交换/集成、Web服务等应用中，成为网络环境下进行数据、数据交换和数据集成的标准格式。因此，对于XML数据上相关问题的研究也将具有重要的意义。目前尚未发现有关XML数据上视图确定性问题的研究成果发表。文中已指出视图确定性问题与查询重写问题比较相近，但并不等价。因此，尽管目前对XML数据上的查询重写有大量的研究[24-26]，但是其成果并不能扩展到XML数据的视图确定性问题上。解决关系型数据上的遗留问题以及由关系型数据扩展到XML数据将会是视图确定性问题的后序研究重点。

作者：郑黎晓常青玲徐世廷单位：华侨大学计算机科学与技术学院 中国科学院计算机网络信息中心中国科学院大学