具有外连接的立即实体化视图的增量维护

摘要

本发明涉及在具有外连接的实体化视图的增量维护的关系数据库管理系统中的使用算法的方法和系统。针对实体化外连接视图的类别以及更新操作的性能，该算法实现了下面的目标：将对视图选择列表中的主关键字属性的存在的要求放松至仅关系中的一些（也就是，关系引用为外连接中的保存侧）；放松对于视图定义中使用的一些谓语的空-不兼容性能需求（也就是，谓语引用关系可以由多于一个的外连接的空-导入）；以及对于视图中引用的每个关系，通过对每个视图使用一个更新语句(例如，MERGE,UPDATE,INSERT或DELETE)从而实施外连接视图的维护。该算法允许具有外连接的实体化视图的增量维护的设计和实施被结合入RDBMS。

说明书

发明背景

技术领域

本发明一般涉及数据库管理系统，以及，更具体地，涉及提供实 体化视图的数据库管理系统，实体化视图的增量维护以及特别地涉及 含有外连接的实体化视图的维护的系统和方法。

背景技术

SYBASE^TM SQL ANYWHERE^TM是一种ANSI SQL顺应式的关系 数据库管理系统（RDBMS），其设计成在各种平台上运行，所述平台 为从服务器类安装到使用Windows移动操作系统的移动装臵。SQL ANYWHERE^TM是一种自我管理RDBMS，其具有高可靠性、高性能、 同步功能、小封装、以及横跨各种32位和64位平台的整个范围的 SQL特性。

目前可用的产品，比如SQL ANYWHERE^TM，支持手动实体化视 图。只能通过全部重新计算被刷新的手动实体化视图，可由任何复杂 的查询定义。然而，一些查询优化器，如SQL ANYWHERE^TM优化器， 在查询优化期间能够仅使用在视图匹配过程中的某类别的实体化视 图。虽然SQL ANYWHERE^TM支持用于群-选择-项目-连接 （GROUP-SELECT-PROJECT-JOIN）视图的某实体化视图的增量维 护，需要的是更普通类别的可被增量地维护的实体化视图。因此，需 要的是用于立即实体化视图(iMV_s)的增量维护的方法和系统。进一步 需要的是一个RDBMS，其支持扩展类别的立即实体化视图，即具有 集合或没有集合的外连接视图。在本发明的一个实施例中，所描述的 算法可以在数据库或数据仓库系统中实施，例如但不限于SQL ANYWHERE^TM。

外连接查询越来越频繁地用于新系统和外部工具，其中，数据库 管理员(DBAs)或经验丰富的数据库开发人员不能直接调整生成的 SQL语句。图1示出了这样生成的查询的例子。例如，对于使用外连 接视图从语义转换至视图匹配的处理外连接查询，SQL ANYWHERE^TM优化器具有复杂的技术。然后，有必要扩展对具有外 连接的实体化视图的增量维护的支持，这可以加快很多使用SQL ANYWHERE^TM RDBMS的应用。对具有外连接的立即实体化视图的 有效支持的目标是多方面的。

用于具有外连接的实体化视图的增量维护的一些传统的技术是 基于连接析取范式表达。一个连接析取范式编码一个外连接查询作为 不同连接的最小联合的一序列。图3中的例子显示了与表1中定义的 查询V₁的连接析取范式对应的亲子关系图。这样的增量维护算法包 括一系列的步骤：第一步为计算和应用主要增量（非空-导入元组）， 然后应用二次增量（空-导入元组）从而删除或插入空-导入增量的一 组后续步骤。主要增量被保存并在二次增量的计算中重新使用。为了 正确地计算空-导入元组，这种计算可能需要再次访问基数关系。这 些传统技术需要一个单独的SQL语句来实现每一个所需要的步骤， 它们引发低效率并需要用于解析和执行多个SQL语句的资源。例如， 如图3所示的用于视图V₁（在表1中定义）的关系X₂，视图更新算 法包括五个步骤：计算和应用主要增量，并计算和应用对应于连接析 取范式关系R₁R₂T₁T₂、R₁R₂、X₁Y₁Y₂以及X₁的四个二次增量。

因此，需要方法和系统，其通过使用用于每一个实体化外连接视 图的单一维护更新语句，用于具有外连接的实体化视图的增量维护。

发明内容

本发明包括用于优化包括外连接和实体化视图的查询的系统、方 法以及计算机程序产品。

根据本发明的实施例，对于具有外连接的实体化视图的增量维 护，提出保存侧/导入空侧(PSNS)算法。这些算法使得对于每个实体 化外连接视图仅产生单个维护更新语句，当更新引用基表时，其将被 用于增量地更新实体化视图。因为这是通过RDBMS执行的通用SQL 语句，为了达到较好的性能，这允许应用强大的优化同时依次处理更 新语句。

第二，由于对视图定义施加较少的限制，因为产生的SQL语句 同时计算非-空-导入元组和空-导入元组，所以这允许立即实体化视图 的扩展类别被支持。

第三，既然仅使用一个更新语句，那么在视图更新操作过程中， 不需要保存中间临时表。与传统方案相比，这还在性能方面产生了实 质性的改进。

结合参考附图，下面将详细地描述本发明进一步的特征和优点， 以及本发明的各个实施例的结构和操作。应当注意：本发明不限于在 此描述的具体实施例。这里介绍的实施例仅为说明发明的目的。基于 这里所包括的教导，对于本领域技术人员而言其他实施例也是明显 的。

附图说明

并入于此并形成说明书一部分的附图描述本发明，以及结合说明 书，进一步用于解释本发明的原理并使得相关领域的技术人员能够制 备且使用本发明。

图1提供了由对象-关系映射系统产生的生成外连接查询的一个 例子。

图2描述了按照本发明的实施例，用于视图V₁（在表1中定义） 的注释PSNS-的标准化连接运算符树。

图3说明了与视图V₁（表1中定义）的连接-析取范式对应的亲 子关系图。

图4-6是阐释了根据本发明的实施例的步骤的流程图，通过该步 骤，立即实体化视图（iMVs）被增量地更新。

图7提供了一个系统的模块视图，在该系统中可以实施本发明。

图8和9是阐释了根据本发明的实施例步骤的流程图，通过该步 骤，从用于具有外连接的立即实体化视图（iMVs）的注释PSNS-的 标准化连接运算符树而创建生成的更新语句。

图10描述了在其中实施本发明的计算机系统的一个示例。

将参考附图描述本发明。在图中，一般来说，相同的参考标记指 示相同的或功能类似的元件。此外，一般来说，参考标记的最左边的 数指示参考标记第一次出现的图。

具体实施方式

介绍

本发明涉及用于增量地更新具有外连接的立即实体化视图(iMVs) 的系统、方法、计算机程序产品实施例以及其组合及子组合。

本发明的下面详细描述参考了阐释与本发明一致的示例实施例 的附图。在本发明的精神和范围内，其它实施例是可能的，也可以对 实施例进行改进。因此，详细的描述并不旨在限制本发明。相反，本 发明的范围通过随附的权利要求限定。

对本领域的技术人员而言，如下所述，本发明能够以软件、硬件、 固件和/或图中阐明的实体的多种不同实施例而实施。具有实现本发 明的硬件专用控制的任何实际的软件代码不限制本发明。因此，理解 到，给定本说明表达的详细级别，能够进行实施例的改进和变型，进 而描述本发明的操作行为。

本发明涉及用于增量地更新具有外连接的立即实体化视图(iMVs) 的实施算法的系统、方法以及计算机程序产品。

根据本发明的一个实施例，该算法可与支持实体化视图的查询优 化器整合，例如，但不限于，SQL ANYWHERE^TM优化器。iMVs的 更新可以使用内部生成的触发器获得，一个触发器用于在iMV中引 用的每一个关系。内部生成的触发器包含更新语句，考虑到ΔT更新 关系代表基表T的已更新的行，更新语句执行对在它们的定义中引用 T的iMV的更新。在一个实施例中，更新语句是内部生成的SQL语 句，SQL语句通过查询优化器处理和优化，查询优化器正如充分利用 存在于任何查询优化器中的查询优化技术的任何其他查询。因此，根 据一个实施例，具有外连接的iMV的增量维护能够以类似的方式进 行，这可以通过MERGE/INSERT/UPDATE语句实现。相关领域的技 术人员会理解可使用其他编程语言，数据库平台和技术来实现这里探 讨的逻辑和算法。

其次，考虑到使用RDBMS服务器的应用的当前现状，施加至可 以被立即维护的外连接类别的限制必须被保持在最低限度。传统的解 决方案对选择列表的内容和施加至谓语的空-不相容的性能是非常限 制的。通过放松空-不相容的性能限制（即，通过空-相容），在此描述 的本发明的实施例改进了传统的方法。

第三，外连接更新语句的新一代算法所需要的额外信息有效地被 加入至查询优化器使用的外连接查询块的内部表示，所述查询优化 器，例如但不限于，SQL ANYWHERE^TM优化器。

这里所描述的算法PSNS()精确地实现了。

词汇和术语

为了帮助理解下面的讨论，下面定义的目的是说明，而不是限制。

连接：连接子句结合来自两个或多个表的记录，例如，但不限于， 数据库表。如本文所用，在一个实施例中，数据库可能是关系数据库， 内存数据库，文件系统，一批Web服务器文档、文件、或资源，或 任何一批电子数据中的一个或多个。

外连接：外连接是一种不要求在两个连接表中的每个记录具有匹 配记录的连接。连接表保留每个记录，甚至在没有其他匹配记录存在 的情况中。外连接可能是左外连接，右外连接，或全外连接，这取决 于那个表保存来自（左，右，或两者）的行。

关系：关系定义为具有相同属性（列）的一组元组（行）。

关系数据库：关系数据库是存储在关系（有时称为表）中的数据 集合。关系数据库由IBM的E.F.Codd在1970年发明。

结构化查询语言（SQL）：SQL代表结构化查询语言。称为 SEQUEL（结构化英语查询语言）的最初版本，由IBM在1970年设 计。SQL-2008是用于SQL的最新标准，国际标准组织在2008年公 布的一份文件中陈述了该标准；参看2008年七月出版的《SQL基础》。

模式（T）：模式（T）表示关系T的所有属性（列），模式（T） ={A₁,…,A_n}。

元组：针对模式(T)的元组t是对模式(T)的属性名称的值分配，t= (a₁,..,a_n)。t[A_i]=a_i，表示用于属性A_i的元组t的值。关系T的实例是 一组对模式(T)中属性定义的元组，T={t₁,..,t_k}。对于就关系T₁,...,T_n的模式定义的元组t，符号t[T_i]表示用于关系T_i的属性的元组t的值。 符号n(t[T])表示模式(T)中的所有属性在元组t中具有空，同时，nn(t[T]) 表示模式(T)中的至少一个属性是非空。另外，t=(...,n(T),...,nn(R)…) 表示元组t在T也是就针对n(t[T])是空，并且在R，也就是针对nn(t[R]) 是非空。

模式（p）：如在此使用，在一个实施例中，谓语p对由模式(p) 识别的一组属性定义。符号p(T₁,T₂,...,T_n,)表示引用关系T₁,T₂,…,T_n的一些属性的谓语，也就是，模式模式(T_i)以及关系(p)={T₁, T₂,…,T_n}。施加至元组t₁∈T₁,t₂∈T₂,…,t_n∈T_n的谓语p具有三个 值，即假、真或未知。当被应用时，符号p(t₁,...,t_n)将表示：当谓语 评估为假或未知时，谓语p评估真或(t₁,..,t_n)<>真。

外部联合：如在此使用，在一个实施例中，两个关系的T_l和T₂的术语外部联合由表示，以及它通过以下计算，首先对于 (Schema(T₁)∪Schema(T₂))\Schema(T_i)中的属性，用Null填补每个关系 T_i,i=1,2的元组，然后计算结果集合的联合。

连接，反连接，左，右，和全部外连接：对于两个关系T₁和T₂， 连接、反连接、左，右，和全连接分别定义如下：

空-导入元组：对于关系T的所有属性都是空-填充或空-扩展的元 组，通过T-空-导入元组表示。

空-导入元组：对于关系T的至少一个属性不为空的元组，通过 T-空-导入元组表示。

控制元组：如果它们基于相同模式定义，且t[Α]=r[A]，其中，r[A]不是空，那么元组t控制元组r。

复制元组：t和r是基于相同模式定义的元组。如果t[A]没有区别于r[A]，即，它们都是空或它们相等，则t 是r的副本。

最佳匹配运算符：最佳匹配运算符β定义为β(R)={r|r∈R，通 过R中的任何元组，r不受控制或是副本，以及它至少有一个非空值}。 应用到一个关系R的最佳匹配运算符消除了由其它元组控制或是其 它元组的副本的所有元组，因此β(R)没有两个彼此控制或是副本的元 组。

复制消除运算符：δ(R)用于复制消除运算符：δ(R)={r|r∈R，r 不是R中任何一个元组的副本}。

强谓语：如果属性(p)中的任何属性具有空值，如果谓语p不评估 为真，那么谓语p是强的。

NS-不相容谓语：对于T-空-导入的元组，如果谓语不评估为真， 那么谓语p(T₁,..,T_n)基于关系T∈{T₁,...,Tn}是NS-不相容的。NS-不 相容谓语和强谓语之间的区别是：要求强谓语p基于模式(p)中的任何 属性是空-不相容的。例如，T.XIS NOT DISTINCT FROM R.X¹AND  rowid(T)IS NOT NULL不是一个强谓语，但是根据NS-不相容定义： T.X可是空（NULL），但是谓语仍评估为真（True），其对于关系T 是NS-不相容的。在我们的经验中，当其是来自图1的查询的情况时 （例如，来自16-17，34-35行的ON谓语），大类别的客户查询不使 用强谓语，甚至在ON子句中。对于某关系T_i，当谓语的性能为NS- 不相容是很重要的，其通过下面的关系T_i，例如p(T₁,...,T_i,…,T_n)， 表示。

逻辑运算符树：逻辑运算符树是查询的表示，其中内部节点是二 进制连接，同时叶是关系。逻辑运算符树中的每个节点可具有引用来 自左子树和右子树的关系的谓语。

外连接查询：如在此使用，在一个实施例中，术语外连接查询是 包含左和全部外连接（右外连接可以转化为左外连接）以及内部连接 的查询。外连接查询可以通过连接运算符树表征，连接运算符树的内 部节点是二进制连接，并且叶为关系。

空-导入外连接：对于类型左外连接的连接运算符树的内部连接 节点，外连接空-导入来自右边的关系。对于一个全外连接节点，外 连接在其两侧均空-导入。请注意，在外连接查询中，相同的基础关 系可以由多于一个的外连接空-导入。

直接外连接：对于通过运算符树表征的外连接查询中的关系T， T的直接外连接是空-导入T的类型左外连接或全外连接的第一个祖 先节点。任何关系T能够具有至多一个直接外连接。

间接外连接：对于由运算符树代表的外连接查询中的任何关系 T，间接外连接是空-导入T但不是T的直接外连接的外连接节点。

------------------------

¹IS NOT DISTINCT FROM谓语在ANSI SQL:1999中引入，并且其等同于谓语T.X= R.X OR(T.X IS NULL AND R.X IS NULL)。

具有外连接的实体化视图：其定义是一个外连接查询的实体化视 图是具有外连接的实体化视图，其具有和不具有集合函数。

在一个实施例中，关于在视图定义中使用的谓语，具有外连接的 增量地维护的实体化视图被假定为具有下面的性能。外连接J的谓语 是仅关于关系的NS-不相容谓语，其具有直接外连接，并且该直接外 连接不同于J。施加至一些外连接谓语上的NS-不相容性能确保空-导 入涟漪效应：如果关系T是由其直接外连接空-导入的，那么所有其 间接外连接还必须空-导入它们的整体空-导入方面。因此，通过具有 空-导入的T的外连接查询生成的任何元组将具有也是空-导入的所有 相关关系。例如，对于外连接查询上述的条 件要求：只有全外连接的谓语p(T,S)对于关系T是NS-不相容， 关系T是通过其直接左外连接T空-导入。谓语不必要 是NS-不相容的，因为涟漪效应不适用其他外连接将 为关系R和T空-导入或均不为两者空-导入，因此其对左外连接 的结果没有影响

在一个实施例中，假定：实体化视图具有唯一索引，该唯一索引 具有空值，该空值在可能是空值的属性上无法区分。例如，如果唯一 索引关于属性(A,B)定义，两个元组(α,Null)和(α,Null)被认为是等同 的且不能同时存在于视图中，这是因为它们违反索引的唯一性。当 PSNS算法被描述时，将在稍后讨论对于具有外连接的立即实体化视 图的额外需求。

PSNS保存侧/空导入侧算法

对于定义了立即实体化视图V的给定外连接查询，所提出的算法 找到基础关系T的空-导入性能的表示，在对关系T进行更新操作后， 对于视图V的更新语句，该基础关系T会给出正确公式。主要目标是 对视图定义施加尽可能少的限制，并且视图更新语句将十分有效且执 行实体化视图V的增量维护。

假设：待被更新的关系T是由视图定义²中的至少一个外连接空 -导入。如果视图V引用一组关系T₁,T₂,...,T_n和关系T，对于关系 T₁,...,T_n和T的实例，V(nn(T))={t\t∈V(T,T₁,T₂,...,T_n),nn(t[T])}表示 实例V(T,T₁,T₂,...,T_n)中的所有元组的集合，实例V(T,T₁,T₂,...,T_n) 不是空-导入关系T（T-null-supplied）。V(nn(T))可以通过使用最初的 视图定义来计算，其中空-导入T的所有外连接被转化为内部或左外 连接，使得T不再是空-导入。

举例，如果V(n(T))是指实例V(T,T₁,…T_n)中的所有T-null-supplied元组 的集合。

V中的T-null-supplied元组的最大集合，由Null(T,V(T,T₁,T₂,..., T_n))表示为就固定关系T₁,T₂,...,T_n和关系T的任何实例计算的视图V 的任何实例中的所有可能T-null-supplied元组的集合，关系T的任何 实例即Null(T,T₁,T₂,...,T_n))=δ(∪_{any instance of T}V(n(T))))。如在此使 用，在本发明的实施例中，假设：对于实体化视图V，只有一个关系 被更新，并且被视图引用的所有其他关系保持不变。因此，只要有可 能，在固定关系没有提到之处使用简化的符号，例如，Null(T,V)= Null(T,V(T1,T₁,T₂,..,T_n))，和V(T,T₁,T₂,..,T_n)=V(T)。通过使用最初 的视图定义得到Null(T,V)，其中关系T由空集(也就是,取代。在前面的示例中，Null(T,V)包含了所有可能的T-null-supplied元组，无关T的内容， T-null-supplied组可以存在于V中。也就是，对于关系T的任何实例， V中的任何T-null-supplied元组存在于Null(T,V)中，只要所有其他基 础关系的内容不改变，即在前面的例子中，如

-------------------

²对于不能由外连接空-导入的关系，视图更新语句类似于用于内部连接立即实体化视 图的公式。 果R={r₀,r₁},S={s₀}，那么任何可存在于V₃中的T-null-supplied元 组是下面元组中的一个：

Null(T,V)={(r₀,Null,Null)，(r₁,Null,Null，(Null,Null,s₀)}。

对于具有外连接的实体化视图的增量维护，对于使用集合ΔT 对关系T的每个插入或删除操作，待被插入或待被从V(nn(T))中删 除的元组是已知的。这用V(nn(ΔT))表示的该集合，可以通过使用在 V(nn(ΔT))定义中的ΔT而不是T得到。然而，每个这样的操作可具 有与T-null-supplied元组相关的副作用。对于对T的删除操作，从V 中删除元组，即，V(nn(ΔT))，可根据新T-null-supplied元组的需要留 下视图V。进一步地，在V中插入新元组，即，V(nn(ΔT))，可能会 在V中留下一些假的旧元组，这些元组现在有V(nn(ΔT))中的新元组 控制。在使用V(nn(ΔT))更新V后，术语“NS-补偿”用于描述在V中 插入或删除T-null-supplied元组的操作。

目标是设计一个具有以下性能的算法：（1）对于每个元组t∈ V(nn(ΔT))，在计算V(nn(ΔT))的同时计算可能的T-null-supplied元组集 合，Null(t,T,V)，无需访问视图V。Null(t,T,V)实际上是通过Null(T,V) 中的t控制的所有元组的集合。在插入、删除或更新操作后，Null(t,T, V)将被用于NS-补偿；（2）对于每个元组t'∈Null(t,T,V)，决定，使 用视图V决定，如果t'将被删除（对于插入以及更新操作）或插入（对 于删除或更新操作）V中从而用于V(nn(ΔT))中插入或删除的元组的 NS-补偿。（3）没有必要将部分增量保存到临时表，因此单个语句都 应该用于使用V(nn(ΔT))的更新操作和使用Null(ΔT,T,V)的NS补偿。

对于每个基础关系T，算法PSNS（表4中的算法2）计算集合 PSNS(T)(保存侧/空导入侧)，其是成对的子集的集合，其中，每个这种子集对精确地描述可从元组t ∈V(nn(ΔT))中得到一个T-null-supplied元组，Null(i,t,T,V)。此外， 一对(ps_i,ns_i)∈PSNS(T)提供了用于检查使用用于V的NS-补偿的元 组Null(i,t,T,V)的需求的条件。集合ns_i包含关系(V)中的所有关系， 关系(V)必须与元组Null(i,t,T,V)中的T一起被空-导入。集合ps_i代表 了保存在元组Null(i,t,T,V)中的所有关系。当然，当且仅当最初元组 t不空-导入ps_i中的关系时，元组Null(i,t,T,V)可以存在。用于在 don’tcare(i,T,V)=Relations(V)\(ns_i∪ps_i)中剩余关系的值在Null(i,t,T, V)中不改变。任何元组Null(i,t,T,V)由元组t控制，因此，它们不能 同时存在于视图V中。

用于集合Null(i,t,T,V),Null(t,T),和Null(ΔT,T,V)的形式定义 通过以下给出：

方程（1）：

don'tcare(i,T,V)=Relations(V)\(ns_i∪ps_i)。

Null(i,t,T,V)==(t[don’tcare(i,T,V)],t[ps_i],n(T),n(ns_i))

Null(t,T,V)=∪_{(psi,nsi)∈PSNS(T)nn(t[psi])}Null(i,t,T,V)

Null(ΔT,T,V)=∪_{t∈V(nn(ΔT))}Null(t,T,V)

注意:集合Null(t,T,V)不包含副本或假的元组，因为每对(ps,ns) ∈PSNS(T)产生不同的元组，即，Null(t,T,V)=δ(Null(t,T,V))。然而， 集合Null(ΔT,T,V)可能包含副本，这是因为ΔT中的两个不同元组可 能产生相同的T-null-supplied元组。可以证明，如果V具有PSNS算 法所需要的所有性能，上述定义的Null(T,V)通过方程2中的公式得 到。换句话说，所有的T-null-supplied元组可以从视图V的任何实例 中计算：

方程（2）：

对于举例，考虑表1和图3中定义的视图V₁，使用ΔX₂更新的 关系X₂。对于元组t∈V(nn(ΔX₂))，已知的是：t[X₂]必须不为空（集 合(V(nn(ΔX₂))只包含X₂-null-supplied）：t=(r_l,r₂,t_l,t₂,x₁,x₂,y_l,y₂)。集 合PSNS(X₂)被计算为{({X₁},{R₁,R₂,T₁,T₂,X₂}),({R₁},{X₁,X₂,Y_1,Y₂})}。直观地说，第一(ps₁,ns₁)=({X₁},{R_l,R₂,T_1,T₂,X₂})表示 X₂-null-supplied元组，其中保存关系X₁。当X₂在Null(1,t,X₂,V₁)中 是空-导入时，X₁将被保存。以及用于全部外连接的谓语p(r₁,x₁, Null,y₂)<>True，然后，除了X₂以外，全部外连接的另一侧也是空- 导入。这可以解释为什么ns₁＝{R₁,R₂,T₁,T₂,X₂}正是全部外连接的另 一侧。如果t[X₁]=x₁不为空，则具有y₁和y₂的Null(1,t,X₂,V₁)= (Null,Null,Null,Null,x₁,Null,y₁,y₂)保留与元组t相同。y₁和y₂可以 是空或非空值，并且Null(1,t,X₂,V₁)的计算独立于其值。类似地，如 果t[R₁]=r₁不是空，那么Null(2,t,X₂,V₁)=(r₁,r₂,t₁,t₂,Null,Null, Null,Null)。Null(2,t,X₂,V₁)中保存的关系是R₁，并且值r₂,t_l,t₂保持 不从t改变。然而，当谓语p(r₁,x₁,Null,y₂)<>True时，全部外连接空-导入整个右侧。如果对关系X₂的更新操作是插入，如果元组Null(i, t,X₂,V₁)存在于V中，它将被删除，因为它是被新元组t控制的假的 元组。如果更新操作是删除，元组Null(i,t,X₂,V₁)可用于NS-补偿， 如果从V中删除V(nn(ΔT))后，在V中没有元组具有值t[ps_i]，即，

表4中描述的算法2计算用于外连接立即实体化视图V中的每 个基础关系的PSNS()集合。算法是使用用作输入的标准化连接运算 符树，其是查询运算符树的紧凑的表示，其中非嵌套的外连接在相同 的子计划中是“扁平的”。在图2中提供了这种标准化的运算符树的例 子。设计注释PSNS-的标准化连接运算符树从而支持查询优化器中具 有外连接的语句的优化，包括但不限于，SQL ANYWHERE^TM优化器。 标准化连接的主要性能是：其关系通过直接或间接外部外连接都一起 被空-导入。例如，在图3中，表示表表达式 的标准化连接，可以通过外 连接被全部空-导入。直观上，作为关系集合的辅助方 案代表外连接的原子空-导入方面。在一个实施例中，对于每个辅助 方案S，基于用于外连接的谓语，算法PSNS()使用标准化连接运算 符树的后序遍历并计算(ps,ns)∈PSNS(S)集合。ns是其他关系的集 合，如果S是空-导入，则其为空-导入。PS是保存关系的集合，如果 S是空-导入，则其被保存。在应用PSNS算法之后，注释PSNS-的标 准化连接运算符树包含所有元数据，对于任何关系T∈Relations(V)， 这些元数据用于产生用于实体化视图V的增量维护的更新语句。图3 示出了用于其中x∈{lo,fo,j}的每个辅助方案的最终PSNS集合。在 下面的部分中，参照表1-4描述实施例，其中PSNS()集合用于产生 用于立即实体化视图的更新语句。

表1：用于V₁的注释PSNS-的标准化连接树

表2：注释PSNS-标准化连接树的例子

表3：算法1-建立标准化连接树

表4：算法2-建立注释PSNS-标准化连接树

示例性实施例

根据一个实施例，在查询优化过程中被增值地维护或使用的实体 化视图，被内部表示成注释PSNS-的标准化连接运算符树，该注 释PSNS-的标准化连接运算符树能够是由基于成本的查询优化 器使用的相同表示，例如但不限于SQL ANYWHERETM优化器。在语 义转换和查询分析应用到最初的查询运算符树后，被建立。视图 匹配算法和用于实体化视图增量维护的更新语句的生成均使用代表 视图定义的

在一个实施例中，对于立即实体化视图，由于服务器被启动，注 释PSNS-的在对视图的第一次引用建立。如果关系T被更新，内 部生成的触发器被创建，其包括用于引用关系T的任何立即实体化视 图的更新语句。该部分描述了一些更新语句，所述更新语句为用于具 有外连接的iMV_s的这些内部触发器而产生。每个更新语句是个SQL 语句，其可能是插入、更新或合并语句。更新语句从实体化视图的注 释PSNS-的表示生成。当ΔT传递至触发器，在对关系T进行任 何更新操作后，完成内部生成的触发器执行。每个生成的更新语句像 任何其他SQL查询一样处理，因此，在例如外键限制开发的查询优 化器中支持的所有优化、外部和内部连接消除被应用从而寻找有效执 行计划。设计生成的算法从而产生正确的更新语句，其可以通过查询 优化器有效地优化，例如但不限于，SQL ANYWHERE^TM优化器。在 本发明的示例实施例中，在此所描述的技术在SQL ANYWHERE^TM12.0中实施。

下面的操作部分描述SQL语句，所述SQL语句为具有外连接的 iMV_s产生。在所有的语句中，派生表V(nn(ΔT))等同于V(nn(ΔT))，但 是保留计算V(nn(ΔT))的选择列表以及Null(ΔT,T,V)中的元组需要所 有列。应当注意：Null(ΔT,T,V)中选择列表的复杂表达式不能直接从 V(nn(ΔT))中直接计算，因为所需要的列在最终选择列表中的投射出。 对于删除和更新操作，通过使用实体化视图必须具有的唯一索引应用 V(nn(ΔT))。条件V.ui IS NOT DISTINCT FROM V(nn(ΔT)).ui（请见描 述插入操作的表6中第22行，以及描述更新操作的表9中的第24行） 包含应用至唯一索引列的所有IS NOT DISTINCT FROM谓语。对于 删除和更新操作，在V(nn(ΔT))应用至视图后，完成Null(ΔT,T,V)的 计算。通过分别使用嵌入式的（请见描述删除操作的表8 的第18-23行）以及（描述UPDATE操作的表9中的行21-32）

插入操作（表5，表6）

根据实施例，对于插入操作，在应用V(nn(ΔT))之前，集合 Null(ΔT,T,V)的计算可以见到视图数据，因为在插入操作前，假的 T-null-supplied元组存在于视图中。因此，与Null(ΔT,T,V)（表6，9-20 行）同时，合并语句计算V(nn(ΔV))（表6,7-8行）。为了效率，只有 在V∩Null(ΔT,T,V)中发现的元组rowids被传递至通过WHEN MATCHED子句处理。在一个实施例中，MERGE语句首先处理通过 WHEN MATCHED子句（表6，24行）（这是NS-补偿操作）删除的 假元组。其次，通过WHEN NOT MATCHED子句（表6，25-26行）， 插入来自V(nn(ΔT))的行。下面的表5描述了典型的逻辑以计算用于 插入操作的应用Null(i,t,T,V)。根据本发明的一个实施例，下面的表 6提供了用于插入操作的典型MERGE SQL语句。

表5：对于插入操作，计算并应用Null(i,t,T,V)

表6：用于插入操作的合并语句

删除操作（表7，表8）

根据实施例，对于删除操作，在应用V(nn(ΔT))后，集合Null(ΔT, T,V)的计算必须只见到视图数据，使得只有当其对于NS-补偿操作所 需求时，元组Null(i,t,T,V)产生。

因此，在一个实施例中，INSERT语句首先计算（表8，21行） 和运用（表8，18行）V(nn(ΔT))。嵌入式的语句（表8,18-23 行）用于计算和应用V(nn(ΔT))。（嵌入式的更新语句（也被称为 select-from-DML）首先被执行，因此，在应用V(nn(ΔT))后，查询的 其余部分只见到修改的数据，在我们的情况中，是修改的视图）。当 检查用于NS-补偿的条件时（表8，第9行和16行），语句 的剩余部分会见到视图V的修改数据。

在语句（表8中第5至17行）和Null(ΔT,T,V)中的元 组被插入视图后（这是NS-补偿操作），计算集合Null(ΔT,T,V)。

表7：对于DELETE操作，计算并应用Null(i,t,T,V)

表8：对于删除（DELETE）操作的插入（INSERT）语句

更新操作（表9）

依照本发明的一个实施例，为了更新操作，使用语句。 在一个实施例中，与删除操作一样，应用V(nn(ΔT))后，集合Null(ΔT, T.V)的计算必须仅见到视图数据，使得元组Null(i,t,T,V)仅当NS- 补偿操作需要时才产生。因此，嵌入式的合并语句（表9，第21至 32行）首先计算（表9，第22行）并应用（表9，第28-30行）V(nn(ΔT))。 当用于NS-补偿的条件被检查时（表9，第10行和16行）时，语句将见到视图V的修改数据。通过WHEN[NOT]MATCHED子句 （表9，第35-37行）处理集合Null(ΔT,T,V)。

表9:用于更新操作的合并语句

立即实体化视图维护方法

按照本发明的实施例，图4-6是说明创建立即实体化视图(iMVs) 的步骤的流程图。

根据本发明的一个实施例，图4是流程图400，其说明更新立即 实体化视图（iMV）的步骤。

更特别地，根据本发明的一个实施例，流程图400说明了执行基 于对基表的更新的iMV更新的步骤。

方法从步骤402开始并进行到步骤404，在步骤404，基于基表 T，执行更新语句。在本发明的一个实施例中，T是关系数据库中的 数据库表。在执行更新语句后，方法进行至步骤406。

在步骤406中，ΔT或指示改变基表T的Δ被计算。在一个实施 例中，该步骤通过比较在步骤404中被更新的基表T中的被更新的行 的之前和之后的图片而被执行。在ΔT被计算后，该方法进行至步骤 408。

在步骤408中，ΔiMV被计算。根据一个实施例，基于在步骤406 中计算的ΔT，ΔiMV被计算。在ΔiMV被计算后，方法进行至步骤 410。

在步骤410中，iMV视图被更新以及控制传递到方法结束处的步 骤412。

依照本发明的一个实施例，使用ΔiMV执行该步骤从而反映在步 骤406中计算的ΔT变化。

依照本发明的一个实施例，图5是阐释了步骤的流程图500，通 过该步骤说明为了立即实化视图(iMV)执行触发器的步骤。

更特别地，流程图500阐释了步骤，通过该步骤，创建用于更新 引用基表的每个iMV的iMV触发器，并执行。

方法在步骤502开始并进行到步骤504，在步骤504，基表T被 更新。根据本发明的一个示例性实施例，T是关系数据库中的数据库 表。在基表T被更新后，方法进行到步骤506。

在步骤506中，针对在步骤504中更新的基表T是否存在iMV 触发器，进行评估。如果确定iMV触发器存在，那么控制传递至步 骤510。如果确定iMV触发器不存在，那么控制传递至步骤508，在 步骤508处，创建iMV触发器。

在步骤508中，在创建iMV触发器后，其对应于步骤504中更 新的基表T，方法进行至步骤510。

在步骤510中，执行iMV触发器从而更新引用基表T的每个 iMV，以及控制传递到步骤512，在步骤512处方法结束。

根据本发明一个实施例,图6是阐释步骤的流程图600，通过该步 骤为立即实体化视图(iMV)保存触发器。

更特别地，流程图600阐释了根据本发明的一个实施例的步骤， 通过该步骤生成iMV触发器并为基表更新而保存。

方法在步骤602开始并进行到步骤604，在步骤604处，所有引 用基表T的iMV被识别。根据本发明的一个示例性实施例，T是关 系数据库中的数据库表。在所有iMV被识别后，方法进行到步骤606。

在步骤606中，对于在步骤604中识别的每个iMV，生成更新语 句。在一个实施例中，通过产生MERGE SQL语句从而将ΔiMV合并 入在步骤606中识别的iMV。在产生更新语句后，方法进行至步骤 608。

在步骤608中，为基表T更新保存触发器，iMV(T)，并且控制 传递至步骤610。在步骤610处方法结束。

图8是阐释根据本发明一个实施例的步骤的流程图800，通过该 步骤，在基表T更新后，为iMV产生SQL更新语句。

更特别地，根据本发明的一个实施例，流程图800阐释了步骤， 通过该步骤，通过来自注释PSNS标准化连接运算符树的ΔT，在更 新基表T后，产生用于iMV的SQL更新语句。

方法从步骤802开始并进行到步骤804，在步骤804处，确定iMV 是否引用基表T。根据本发明的示例性实施例，T是关系数据库中的 数据库表。在iMV被识别后，方法进行到步骤806。

在步骤804中，鉴于iMV是否引用基表T进行评估。如果确定 iMV引用了基表T，控制传递至步骤808。如果确定iMV没有引用基 表T，那么控制传递至步骤806，在步骤806处，方法结束。

在步骤808中，基于引用基表T的iMV定义，建立标准化连接 运算符树在建立标准化连接运算符树后，方法进行至 步骤810。

在步骤810中，鉴于在步骤808中创建的标准化连接运算符树 是否满足谓语条件而进行评估。如果确定标准化连接运算符 树满足谓语条件，控制传递至步骤814。如果确定标准化连接运算符 树不满足谓语条件，那么控制传递至步骤812，在步骤812处，程序 结束。

在步骤814中，执行标准化连接运算符树的PSNS注释创建 在标准化运算符连接树被注释后，控制传递至步骤 816。

在步骤816中，针对在步骤814中注释的标准化连接运算符树 是否满足选择列表条件而进行评估。如果确定被注解 的标准化连接运算符树满足选择列表条件，那么控制传递至步骤820。 如果确定被注解的标准化连接运算符树不满足选择列表条件，那么控 制传递至步骤818，在步骤818处，程序结束。

在步骤820中，产生用于iMV的SQL更新语句，通过来自 的ΔT，在基表T更新后，使用SQL更新语句，并且 控制传递至步骤822，在步骤822处，方法结束。

图9是阐释根据本发明一个实施例的步骤的流程图900，通过该 步骤标准化逻辑连接运算符树。

更特别地，流程图900阐释了根据本发明的一个实施例的步骤， 通过该步骤，基于关系类型以及用于树的节点连接，逻辑运算符树被 标准化。

方法在步骤902开始，在步骤902处，运算符树T，连接节点n 以及标准化连接nJ被读为输入。在树被读取并解析后，方法进行至 步骤904，在步骤904处，进行确定树T中的节点n代表何种类型的 操作。在一个实施例中，树T是逻辑运算符树，其为内部节点n是连 接和叶，是关系的查询表示。在每个实施例中，逻辑运算符树T中的 每个节点具有引用自左子树和右子树中的关系的谓语。

在步骤904中，针对节点n是何种类型进行评估。如果n是代表 关系的树T的叶，那么控制传递至步骤906，在步骤906处，关系信 息传递至步骤908。如果n是代表内部连接的节点，那么控制传递至 步骤910，在步骤910处，连接信息传递至步骤912。

如果n是代表左外连接的节点，那么控制传递至步骤916，在步 骤916处，左外连接信息传递至步骤914。如果n是代表全部外连接 的节点，那么控制传递至步骤920，在步骤920处，全部外连接信息 传递至步骤918。

在步骤908中，基于步骤906中传递的信息，标准化连接nJ随 着新节点n而增大。在一个实施例中，用于在该步骤中执行的函数的 逻辑表达为：

nJ.p=nJ.p AND p//增加节点n的谓语至标准化连接nJ

nJ.ProperRerlations U={T}//关系T是标准化连接nJ的部分

T.Parent=nJ//关系T具有标准化连接nJ的直接父类部分

在执行步骤908的函数后，方法进行至步骤922。

在步骤912中，基于步骤910中传递的连接信息，标准化连接 nJ随着新节点n而增大。在一个实施例中，用于在该步骤中执行的函 数的逻辑表达为：

nJ.p=nJ.p AND p//增加节点n的谓语至标准化连接nJ

CALL nT(T,LEFT CHILD n,nJ)//为了建立标准化连接运算符 树，横过左子类

CALL nT(T,RIGHT CHILD n,nJ)//为了建立标准化连接运算符 树，横过右子类

在执行步骤912的函数后，方法进行至步骤922。

在步骤914中，基于步骤916中传递的外连接信息，标准化连接 nJ随着新外连接n而增大。在一个实施例中，用于在该步骤中执行的 函数的逻辑表达为：

CALL nT(T,RIGHT CHILD n,nJ)//为了建立标准化连接运算符 树，穿过右子类

nJL=NEW JOIN//创建新标准化连接，其代表外连接n的空-导 入侧

nJ_L.type=LEFT OUTERJOIN

nJ_L.p=p//ON谓语是新标准化连接nJ_L的谓语

nJ_L.Parent=nJ//新标准化连接nJ_L具有作为直接父类的输入标 准化连接nJ

nJ.nJoins U={nJ_L}//nJ是新标准化连接nJ_L的直接父类

CALL nT(T,LEFT CHILD n,nJL)//通过横过外连接n的空-导入 侧建立新标准化连接nJ_L

在执行步骤914的函数后，方法进行至步骤922。

在步骤918中，基于步骤920中传递的全部外连接信息，标准化 连接nJ随着新外连接n而增大。在一个实施例中，用于在该步骤中 执行的函数的逻辑表达为：

nJ_F=NEW JOIN//创建类型全部外连接的新标准化连接nJ_F

nJ_F.type=FULL OUTERJOIN

nJ_F.Parent=nJ//新标准化连接具有直接父类nJ

nJ_F.p=p//新标准化连接具有作为谓语的连接n的ON谓语

nJ.nJoins U={nJ_F}//新标准化连接具有直接父类nJ

nJ_L=NEW JOIN//创建新标准化连接nJ_L，其代表连接n的左子 树

nJ_L.type=INNER OUTERJOIN

nJ_L.Parent=nJ_F//新标准化连接nJ_L具有父类nJ_F

nJ_R=NEW JOIN//创建新标准化连接nJ_R，其代表连接n的右子树

nJ_R.type=INNER OUTERJOIN

nJ_R.Parent=nJF//新标准化连接nJ_R具有父类nJ_F

nJ_F.nJoins U={nJ_L,nJ_R}//标准化连接nJ_F具有两个直接子类nJ_L和nJ_R

CALL nT(T,LEFT CHILD n,nJ_L)//通过横过全部外连接n的空- 导入侧中的一个而建立新标准化连接nJ_L

CALL nT(T,RIGHT CHILD n,nJ_R)//通过横过全部外连接n的空- 导入侧中的一个而建立新标准化连接nJ_R

在执行步骤914的函数后，方法进行至步骤922。

在步骤922中，对关系(p)中的所有关系T执行函数，此处p是节点 n的谓语。在一个实施例中，用于在步骤922中执行的函数的逻辑表达 为：

FOR ALL T IN Relations(p)

IF T.Parent!=nJ,nJ_F,nJ_L,nJ_R

THEN p is NS-intolerant

在执行922的函数后，方法结束。

立即实体化视图系统

图7是系统700的例子，在系统700中可以实施上述算法和方法。 示例性系统700包括具有数据库706的服务器704。在一个实施例中， 服务器704包括关系数据库管理系统（RDBMS）并且数据库706是 关系数据库。在系统的实施例中，多个基表T以及立即实体化视图 (iMV_s)被存储并在数据库706中维护。虽然在系统700中描述了单个 客户702、服务器704以及数据库706，可以理解的是多个客户702 和服务器704可以访问多个数据库706。

在图7中描述的示例性系统700中，客户702通过服务器704访 问驻留在数据库706中的基表以及iMV_s。如相关领域的技术人员所 理解的，其他客户702，例如但不限于，移动客户、笔记本电脑和移 动电话，可被用于访问服务器704和数据库706。在一个实施例中， 数据库706是内存数据库，该内存数据库实施无须存储数据文件或数 据，所述数据文件或数据来自服务器706的磁盘上的多个数据源（未 显示）。

计算机系统实施的示例

本发明的各个方面可以通过软件、硬件、固件或其组合实施。图 10说明了计算机系统1000的一个示例，其中本发明或其部分可以作 为计算机-可读代码实施。例如，通过图4-6、8和9中的流程图400、 500、600、800和900说明该方法，该方法可以在系统1000中实施。 而且，例如，图7中描述的系统700的组件可以在系统1000中实施。 发明的各个实施例按照该示例计算机系统1000而描述。在阅读该说 明书后，对相关领域技术人员而言，如何使用其它计算机系统和/或 计算机架构来实施本发明是显而易见的。

计算机系统1000包括一个或多个处理器，例如处理器1004。处 理器1004可以是特殊用途处理器或通用处理器。处理器1004被连接 到通信基础设施1006（例如，总线，或网络）。

计算机系统1000还包括主存储器1008，优选随机存取存储器 （RAM），并且还可以包括辅助存储器1010。辅助存储器1010可以 包括，例如，硬盘驱动器1012，可移动的存储驱动器1014，闪速存 储器，记忆棒，和/或任何类似的非易失性的存储机制。可移动存储 驱动器1014可以包括软盘驱动器，磁带驱动器，光盘驱动器，闪速 存储器等。通过公知的方式，可移动存储驱动器1014从可移动存储 单元1018中读取和/或写入到可移动存储单元1018。可移动存储单元 1018可以包括软盘，磁带，光盘等，其由可移动存储驱动器1014读 写。相关领域的技术人员同样可以理解的，可移动存储单元1018包 括计算机可用存储介质，所述计算机可用存储介质具有存储在其中的 计算机软件和/或数据。

在可选的实施方式中，辅助存储器1010可以包括其他类似的装 臵，用于允许计算机程序或者其它指令被装载到计算机系统1000。 这种装臵可以包括，例如，可移动存储单元1022和接口1020。这种 装臵的例子可包括程序盒式存储器和盒式接口（例如，视频游戏设备 中发现的），可移动存储芯片（如EPROM，或者PROM）以及相关 的插槽，以及允许软件和数据从可移动存储单元1022传送到计算机 系统1000的其它可移动存储单元1022和接口1020。

计算机系统1000也可以包括通信接口1024。通信接口1024允 许软件和数据在计算机系统1000和外部设备之间进行传输。通信接 口1024可包括调制解调器，网络接口（如以太网卡），通信端口， PCMCIA槽和卡等。通过通信接口1024传输的软件和数据是信号的 形式，其可以是电子的、电磁的、光学的、或其他能够由通信接口 1024接收的信号。通过通信路径1026，这些信号被提供到通信接口 1024。通信路径1026携带信号，并且可以使用电线或电缆，光纤， 电话线，移动电话链路，RF链路或其他通信信道来实现。

计算机系统1000另外包括计算机显示屏1030。根据一个实施例， 计算机显示器1030，连同显示器接口1002，可以用于显示用户接口 （UI）或在客户端702或服务器704处的数据库管理员（DBA）控制 台。

在本文档中，术语“计算机程序介质”和“计算机可用介质”一 般指代，例如可移动存储单元1018，可移动存储单元1022，和安装 在硬盘驱动器1012中的硬盘。通过通信路径1026携带的信号也可以 体现本文所描述的逻辑。计算机程序介质和计算机可用介质，也可以 涉及存储器，诸如主存储器1008和辅助存储器1010，它可以是存储 器半导体（如DRAMs等）。这些计算机程序产品是用于将软件提供 给计算机系统1000的装臵。

计算机程序（也称为计算机控制逻辑）存储在主存储器1008和/ 或辅助存储器1010中。计算机程序也可以通过通信接口1024接收。 这样的计算机程序，当被执行时，使计算机系统1000执行如本文中 所论述的本发明。特别地，该计算机程序，当被执行时，使处理器 1004来实现本发明的方法，如由图4-6、8和9中的流程图400，500， 600，800，和900中所示的方法中的步骤。因此，这样的计算机程序 代表计算机系统1000的控制器。使用软件实施本发明，该软件可以 存储在计算机程序产品中并使用可移动存储驱动器1014，接口1020， 硬盘驱动器1012，或者通信接口1024加载到计算机系统1000。

本发明还涉及计算机程序产品，其包括存储在任何计算机可用介 质上的软件。这样的软件，当在一个或多个数据处理装臵中执行时， 使数据处理装臵以如本文所述的方式操作。本发明的实施例采用现在 已知的或在将来已知的任何计算机可用或可读介质。计算机可用介质 的实施例包括，但不限于，主存储设备（例如，任何类型的随机存取 存储器），辅助存储设备（例如，硬盘驱动器，软盘，CD ROMS，ZIP 磁盘，磁带，磁存储设备，光学存储设备，MEMS，纳米技术存储设 备等），和通信介质（例如，有线和无线通信网络，局域网，广域网， 内联网等）。

结论

虽然上面已经描述了本发明的各种实施例，但应当理解，仅作为 示例而非限制性地表示这些实施例。相关领域的技术人员可以理解， 在不脱离随附权利要求书中所定义的本发明的精神和范围的情况下， 可以进行形式和细节上的各种改变。但应当理解，本发明并不限于这 些实施例。本发明适用于如在此描述的操作的任何元件。因此，本发 明的广度和范围不应该限于任何上述示例性实施例，而是仅应该按照 下面的权利要求及其等同物限定。