对数据的函数应用的结果进行结构化索引

摘要

索引视图或物化视图被用作对带有多值属性的基表的次级索引。这提供了使用索引在嵌套数据中搜索。此外，对去除嵌套操作的结果提供索引。对去除嵌套操作的结果索引视图提供了索引嵌套集合的内容的能力。一个这样的去除嵌套操作是“交叉应用去除嵌套”。这为查询执行计划提供了附加选项，导致更为优化的查询。提供从索引视图到基表的反向联接，以允许不存在于索引视图中的来自基表的字段被包含在对表查询的结果中，对所述表的查询使用索引视图作为访问路径来处理。这提供了将不存在于索引视图而存在于基表中的查询结果中的列包括在内的方法。支持经由唯一聚类关键字从单表索引视图到基表的反向联接，所述聚类关键字被用作逻辑行定位符。因此，该系统能够经由唯一聚类关键字从索引视图到基表的反向联接。这些特征允许使用索引视图对多集合或多值属性的内容索引一表。

说明书

有关申请的交叉参考

本申请要求于2004年3月8日提交的美国专利申请第10/795,623号的优先权，该专利申请引用在此作为参考。

技术领域

本发明一般涉及信息存储和恢复领域，尤其涉及有效地搜索存储数据。

发明背景

消费者主要使用它们的计算机来通信和组织个人信息，不管它是传统的个人信息管理器(PIM)风格数据还是诸如数字音乐或照片等媒体。数字内容的量和存储原始字节的能力大大地提高了；然而，可供者使用的组织和统一这些数据的方法没有跟上步伐。知识工作者花费大量的时间管理和共享信息，一些调查估计知识工作者花费他们15-25％的时间在与非生产性信息相关的活动上。其它调查估计一个典型的知识工作者每天大约花费2.5小时来搜索信息。

计算机系统中传统的组织信息的方式集中在基于用于存储文件的存储介质的物理组织的抽象，使用基于文件-文件夹-和-目录的系统(“文件系统”)来将文件组织到文件夹的目录层次结构中。这种在20世纪60年代期间发展起来的Multics操作系统可被认为是使用文件、文件夹和目录在操作系统层上管理数据的可存储单元的先驱。特别是，Multics使用文件层次结构中的符号地址(由此引入文件路径的概念)，其中文件的物理地址对用户(应用程序和最终用户)不透明。这个文件系统整体与任何个别文件的文件格式无关，文件之间的关系在操作系统层次上被认为是无关的(即，除了层次中文件的位置)。由于Multics的出现，可存储数据在操作系统层被组织成文件、文件夹和目录。这些文件一般包括文件层次自身(“目录”)，包含于由文件系统维护的特殊文件中。这个目录反过来维护对应于目录中所有其它文件的条目列表和层次中这种文件的节点位置(这里被称为文件夹)。这是本领域大约四十年来的状况。

然而，虽然提供了驻留在计算机物理存储系统中信息的合理表示，但是文件系统是那个物理存储系统的抽象，由此使用文件需要用户操纵(具有范围、特征和与其它单元关系的单元)和操作系统所提供的(文件、文件夹和目录)之间的间接(解释)层次。因此，用户(应用程序和/或最终用户)不得不强制信息单元成为文件系统结构，即使这样做是低效的、不一致的、或者是非期望的。因为多数现有的文件系统随着文件的增加，使用嵌套文件隐喻来组织文件和文件夹，维护灵活且有效的组织方案所需的努力变得非常令人畏缩。

过去已经作出几次解决文件系统这个缺点的不成功尝试。这些先前的尝试中的一些涉及使用内容可寻址存储器以提供数据能够被内容而非物理地址访问的机制。然而，这些努力被证实是不成功的，因为虽然内容可寻址存储器被证明对诸如高速缓存和存储管理单元等设备的小规模使用来说是有用的，但是由于多种原因诸如物理存储介质等设备的大规模使用还不可能，因此这样的解决方案完全不存在。作出了其他使用面向对象数据库(OODB)系统的尝试，但是这些尝试(虽然表现了强的数据库特征和好的非文件表示)不能有效地处理文件表示，且不能在硬件/软件接口系统级别复制基于层次结构文件和文件夹的速度、效率和简单性。

新发展的存储系统，诸如“WinFS”(以下详细描述)将文件的目录存储为数据库中的表格。每个文件由基表中的一行表示，诸如“列举目录中的所有文件”等文件系统操作满足于对数据库引擎使用查询。因此，对存储有效地执行基本操作变成了有效地优化数据库查询的操作。

在这种存储系统中，文件的概念被扩展到“对象”的概念。关于文件的元数据和表示那个对象的可容许描述数据的方案(在存储系统中定义的)一起存储在管理CLR(通用语言执行环境)对象中。例如，图片可以有代表性的CLR对象，所述CLR对象会存储诸如其分辨率、所化的时间和位置信息等数据。这个对象模式支持数据继承。有了数据继承，能够从另一个数据得出类型并增加新的字段。例如，可以建立图像的“子类”，诸如“DriversLicensePicture”。这样的子类可以包含额外的信息，诸如驱动程序的许可证ID字段。

在这些新开发的存储系统中，诸如WinFS，所公开的方案通过翻译层被映射到表格上。用户只看到一系列数据的视图，而非对基表的操作。当这种映射的精确设计不重要时，它用作WinFS API和基础存储格式之间的胶合物。用户并不直接控制或看到这个映射。

WinFS存储也揭示了基于对象的类型查询对象的概念，与早先传统的文件系统中基于它们的文件名称查询形成对比。基于类型的查询可以查找准确的类型或从给定类型导出的任何类型。后者的形式被称为层次匹配，它被期望成为通用WinFS操作。WinFS也支持按文件搜索。

WinFS方案模型对查询处理器提出了一些新的难题。用户定义类型或UDT被广泛使用，基于UDT类型从表格检索所有UDT是通常的。此外，WinFS使用UDT继承，它也要求从表格检索所有给定类型的元素和任何子类型。存在多个表格，每个包含不同数目的UDT、类型、类型拓扑和该拓扑中的UDT分布。此外，搜索操作会超过传统关系数据库系统中所见的操作，包括例如搜索XML文件或执行对一对象中所有字段的搜索。这些特征使得难以作出精确的技术且和成本估计，也使得难以基于类型、子类型层次有效地检索值。

物化视图(在这里也被称为索引视图)是过去十年所探索的数据库的主题。这个基本的概念是物化或存储某些查询的结果，接着当类似的查询被体送到数据库时，使用这些计算结果。例如，会期望存储每天销售的结果，以后使用这个结果(这个物化的视图)来回答几个相关的查询，诸如给定月份的销售或整年的全部销售。

为了额外的灵活性，应用程序无需知道某些视图的存在或它们被物化。查询处理器应该确定用户查询和现有预计算结果(物化的视图)之间的匹配，并在适用时使用这些结果。这被称为视图使用问题：给出对基表改写的用户查询以及物化的视图的集合，哪个物化视图可以被用作回答这样的查询？以及问题的基于代价的变体：这些物化视图的哪些应被使用？

物化视图类似于索引，其中应该有部分对数据库的物理设计，它们的主要目的是改进性能。对数据库的逻辑设计和对应用程序的正确性应该独立于物化视图的存在和不存在。如同使用索引，物化视图可以对查询性能引入惊人的改进。

一般将查询优化程序构造成有一初始简化阶段，接着是对可选项的探索和对执行计划基于代价的选择，如图1所示。

在简化/标准化阶段2，对原始查询Q作出了一些变化，诸如将选择下推或者可能时将子查询重新写为联接。这些修改旨在获取“更好的”查询。一般地，在这个阶段没有详细的代价估计，产生单个“更好的”查询Q’作为结果。

优化第二阶段5(探索和基于代价的选择)针对生成多个可选项，和使用详细的代价模型来用最低估计执行代价来选择可选项。探索阶段的两种传统构架是自底向上、动态编程联接列举和可选项的变换驱动生成。两种构架都建立了可选项表格，如公知的，它紧缩地对每个查询的子表达式的各种可能性进行编码。

考虑探索过程中的物化视图包含用使用这种物化视图的条目来增广可选项表格。假设原始查询是表A、B、C的联接。以下给出典型的可选项(只用逻辑算子)：

ABC：

AB：

BC：

AC：

经编码的操作符树通过遍历可选项的表来获得，从根条目(上述查询中的ABC)开始，并从每个条目选择一操作符。例如，通过取得每个条目中的第一选择，获取图2中所示的操作符树10。

现在假设有一物化视图这意味着有一存储表，被称为Vt，包含A和B联接的结果。因为这是获取联接子表示式的有效途径，用这个可选项增广所述可选项，成为：

ABC：

AB：

BC：

AC：

图3示出了优化程序可生成和考虑的有效操作符树13。

增广可选项表格的机制取决于优化程序的构架。在基于转换的优化程序的情况下，通过对系统增加新的变换规则来获取扩展；对于自底向上联接列举，应该改变构造过程。在向表格加入可选项之后，应用通用优化程序机制以估计代价、去除昂贵的解答、装配操作符树和构建最佳解答。

为了保证事务处理的正确，物化视图的内容必须与基表的变化保持同步。例如，当输入或改变定单时，必须更新每周销售的物化来反映这种变化。这被称为视图维持问题。换而言之，如果基表中的基础数据改变，那么必须在物化视图中作出这些改变。由于重新计算的时间和费用，所期望的是无需重新计算整个物化视图以反映这种变化。

考虑到在现有数据存储和数据库技术中上述的缺点，需要有效地使用物化视图。本发明满足了这些需要。

发明内容概述

以下发明内容提供了对本发明各方面的概述。它并非旨在提供对本发明所有重要方面的详尽描述，也不是为了定义本发明的范围。然而，这个发明内容概述是意在用作对下述详细描述和附图的介绍。

本发明针对使用物化视图(在这里也被称为索引视图)作为对带有潜在的多值属性的基表的二级索引。这提供了使用索引在对数据的函数应用结果中搜索。此外，本发明提供了对表值函数调用的结果进行索引。对这种函数调用结果的视图索引提供了对复杂结构内容索引的能力。

例示的去除嵌套操作是“交互应用去除嵌套”。在这个例子中，UNNEST是将UDT集合作为复杂结构并为集合中的每个元素输出行的函数。其它函数例子可以将XML数据转换为较为可搜索的形式或将多列分解成特定搜索的单个索引结构。本发明提供了查询执行计划附加的选项，导致更为优化的查询。

依照本发明的还有方面，提供了从索引视图到基表的反向联接。这允许不存在于索引视图中的基表的字段被包含在查询结果中，这作为访问路径使用索引视图来处理。这提供了在查询结果中包含列的方法，所述查询结果不在索引视图中而在基表中。经由唯一的聚类关键字，从单表索引视图到基表支持反向联接，所述聚类关键字作为逻辑行定位符。因此通过唯一的聚为关键字本系统可以从索引视图到基表的反向联接。这些特征允许使用索引视图来对表格的复杂函数调用内容进行索引并从在这个函数调用上匹配准则的行有效地恢复数据。

本发明的其他特征和优势将通过以下对发明的详细描述和附图变得显而易见。

附图说明

结合附图阅读，将更好地理解上述说明内容和以下对优选实施例的详细描述。为了说明本发明，在附图中示出了本发明的示例性构造；然而，本发明不限于所揭示的特定方法和手段。在附图中：

图1是常规查询优化程序的框图；

图2是示例性操作符树的图表；

图3是包含物化视图的图2的操作符树的图表；

图4是表示可以包含本发明各方面的计算机系统的框图；

图5是说明被分成三个组件组的计算机系统的框图：硬件组件、操作系统组件和应用程序组件；

图6是说明用于用文件夹中经分组的文件的基于树的分层结构；

图7是说明与本发明一起使用的示例性存储平台；

图8是依照本发明的示例性索引视图的图表；

图9是依照本发明的示例性聚类关键字的图表；

图10示出了依照本发明的示例性执行计划；

图11示出了依照本发明的示例性访问计划；

图12示出了依照本发明的查询数据方法的流程图。

具体实施方式

特别描述了主题以符合法定需求。然而，描述自身不是为了限制本权利申请的范围。而是，发明者期望所做权利要求的主题也可以以其它方式结合其它现有或将来的技术体现，以包含类似于这个文件中所描述的步骤的不同步骤或这些步骤的组合。此外，虽然可以在这里使用术语“步骤”来表示所采用方法的不同元素，但是这个术语不应该被解释为意味这里所揭示的各种步骤之间任一特定顺序，除非个别步骤的顺序被明确地描述。

WinFS是引入文件系统中的对象概念的文件系统/数据存储。这个存储中的一个操作是能够有效地定位和查询对象。本发明描述了如何能够非常有效地作出这个操作的各方面。

示例性计算环境

如这里和权利要求中所使用的，以下的术语有以下的意义：

“对象”是硬件/软件接口系统可访问的可存储信息单元，所述硬件/软件接口系统具有一组基本特征：它们通常在所有展现给最终用户的对象上被硬件/软件接口系统的外壳程序所支持。对象也具有通常在包含允许引入新的属性和关系的特征的所有类型上被支持的属性和关系。

“操作系统”(OS)是特定的程序，用作应用程序和计算机硬件之间的中介。在大多数情况下，操作系统包含外壳和核心。

“硬件/软件接口系统”是软件或硬件和软件的组合，用作计算机系统下层硬件组件和在计算机系统上执行的应用程序之间的中介。硬件/软件接口系统一般包括操作系统(在一些实施例中，可以单独地由操作系统组成)。硬件/软件接口系统也可以包含虚拟机管理器、通用语言执行环境(CLR)或其功能等价物、Java虚拟机(JVM)或其功能等价物或其它计算机系统中位于操作系统中或操作系统外的这样的软件组件。硬件/软件接口系统的目的是提供用户可以在其中执行应用程序的环境。任何硬件/软件接口系统的目标是使得计算机系统便于使用以及以有效的方式使用计算机硬件。

本发明的许多实施例可以在计算机上执行。图4和以下描述旨在提供对适用于本发明实现的计算环境的简要概述。虽然不是必须的，本发明可以在计算机可执行指令的一般环境中描述，所述计算机可执行指令诸如由计算机执行的程序模块，所述计算机诸如客户机工作站或服务器。通常，程序模块包括执行一特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等。此外，本发明的技术人员会理解本发明可以用其它的计算机系统配置来实现，包括手持式设备、多处理器系统、基于多处理器或可编程消费电子产品、网络PC、微型计算机、大型计算机等等。本发明还可以在分布式计算环境中实现，其中在分布式计算环境中任务由通过一通信网络链接的远程处理设备执行。在分布式计算环境中，程序模块可以位于包含存储器设备的本地和远程计算机存储介质中。

如图4所示，示例的通用计算系统包含一常规的个人计算机20等等，所述个人计算机包含处理单元21、系统存储器22、和连接包括系统存储器在内的各个系统组件到处理单元21的系统总线23。系统总线23可以是几种类型的总线结构中的任何一种，其中这几种类型的总线结构包含：使用各种总线体系结构中任何一种的存储器总线或存储器控制器、外围总线和本地总线。系统存储器包括只读存储器(ROM)24和随机存取存储器(RAM)25。基本输入/输出系统(BIOS)26一般被保存在ROM 24中，其中该基本输入/输出系统(BIOS)133包含有助于例如在启动过程中在个人计算机20内部的元件之间传输信息的基本例程。

个人计算机20还可以包括从硬盘(未示出)中读取或写入到其中的硬盘驱动器27、从可移动磁盘29中读取或写入到其中的磁盘驱动器28和从可移动光盘31，诸如CD-ROM或者其它光介质中读取或者写入到其中的光盘驱动器30。硬盘驱动器27、磁盘驱动器28和光盘驱动器29分别通过硬盘驱动器接口32、磁盘驱动器33和光盘驱动器34被链接到系统总线23上。这些驱动器和它们相关联的计算机可读介质提供对计算机可读指令、数据结构和用于个人计算机20的其它数据的非易失性存储。

虽然这里所描述的示例性环境采用了硬盘、可移动磁盘29和可移动光盘31，本领域的技术人员可以理解其它类型的用于存储计算机可访问数据的计算机可读介质也可在示例性操作环境中使用，所述的其它计算机可读介质诸如磁带盒、闪存卡、数字视频盘、Bernoulli盒式磁带、随机存取存储器(RAM)、只读存储器(ROM)等等。

许多程序模块可以存储在硬盘、磁盘29、光盘31、ROM 24或RAM 25上，包括操作系统35、一个或多个应用程序36、其它程序模块37和程序数据38。用户可以通过输入设备输入命令和信息到计算机20中，输入设备诸如键盘40和指点设备42。其它输入设备(未示出)可以包括麦克风、操纵杆、游戏垫、卫星接收天线、扫描器等等。这些和其它输入设备一般通过耦合到系统总线的串行口接口46连接到处理单元21，但也可能由其它接口连接，诸如并行端口、游戏端口、通用串行总线(USB)。监视器47或其它类型的显示设备也可以通过诸如视频适配器48这样的接口连接到系统总线23。除监视器47外，个人计算机一般包括诸如扬声器和打印机等其它外围输出设备(未示出)。图4的示例性系统中也包含主机适配器55、小型计算机系统接口(SCSI)总线56和连接到SCSI总线56上的外部存储设备62。

计算机20可能工作在使用到一个或多个诸如远程计算机49这样的远程计算机的逻辑连接的网络环境内。远程计算机49可以是个人计算机、服务器、路由器、网络PC、对等设备或其它公共网络节点，并且一般包括与计算机20相关的许多或所有上述元件，然而图4中仅说明了存储器存储设备50。图4所述的逻辑连接包括局域网(LAN)51以及广域网(WAN)52。这种网络环境常见于办公室、企业范围的计算机网络、内联网以及因特网。

当用于LAN网络环境时，计算机20通过网络接口或适配器53连接到局域网51。当用于WAN网络环境时，个人计算机20一般包括调制解调器54或其它装置，用于在诸如因特网或广域网52上建立通信的装置。调制解调器54可能是内置或外置的，它通过串行口接口46连接到系统总线23。在网络化环境中，所述与个人计算机20相关的程序模块或其中的一部分可能存储在远程存储设备内。可以理解，所示网络连接是示例性的，并且可以使用其它用于在计算机间建立通信连接的技术。

虽然预见到本发明的许多实施例特别适用于计算机化系统，但是本文件中没有东西旨在将本发明限制于这些实施例。相反地，这里所使用的术语“计算机系统”意在包含任何和所有包括按钮或能够确定按钮或按钮等价物的设备，不管这样的设备本质上是电子的、机械的、逻辑的还是虚拟的。

如图5的框图中所示，计算机系统200能够大体上被分成三个组件组：硬件组件202、操作系统组件204和应用程序组件206。

在某些计算机系统200中，再参见图4，硬件202可以格外包括中央处理单元(CPU)21、存储器(ROM 24和RAM 25)、基本输入/输出系统(BIOS)26和各种输入/输出(I/O)设备，诸如键盘40、鼠标42、监视器47和/或打印机(未示出)。硬件组件202包括计算机系统200的基本资源。

应用程序组件206包括各种软件程序，包括但不限于编译器、数据库系统、文字处理器、视频游戏等等。应用程序提供使用计算机资源解决问题、提供解决方案和为各种用户(例如，机器、其它计算机系统和/或终端用户)处理数据的方法。

操作系统组件204包含操作系统本身及其外壳和核心。操作系统(OS)是用作应用程序和计算机硬件之间的特定程序，操作系统的目的是提供用户可以执行应用程序的环境。任何操作系统的目标在于使得计算机系统便于使用以及以有效的方式使用计算机硬件。

操作系统一般在启动时被载入到计算机系统，此后管理计算机系统中所有的应用程序(或简称为“应用”)。应用程序经由应用程序编程接口(API)通过请求服务与操作系统交互。一些应用程序使得终端用户能够经由用户接口与操作系统交互，所述用户接口诸如命令语言或图形用户界面(GUI)。

操作系统传统上为应用程序执行各种服务。在多任务操作系统中，其中多个程序同时运行，操作系统确定哪些应用程序应该以哪种顺序运行，在允许从一个应用程序轮流切换到另一应用程序之前每个应用程序允许运行多少时间。该操作系统也管理多个应用程序之间内部存储器的共享，并处理到所附硬件的输入和输入，所述硬件诸如硬盘、打印机和拨号端口。该操作系统也向每个应用程序(并且在某些情况下给最终用户)发送关于操作状态和任何可能发生的错误的消息。操作系统也可以卸载对批作业(例如，打印)的管理，使得开始的应用程序从该工作释放并且可以继续其它的处理和/或操作。在可以提供平行处理的计算机上，操作系统也可以管理划分程序使得它可以每次在多于一个处理器上运行。

操作系统的外壳是对操作系统(也被称为“命令解释器”)的交互式的终端用户界面。外壳是应用程序直接访问甚至是终端用户直接访问的操作系统的外层。相对于外壳，核心是直接与硬件组件交互的计算机系统的最里层。

如相关领域的技术人员所理解的，“文件”是能够由操作系统作为离散(可存储或可恢复)实体操纵的信息实体(包括但不限于操作系统自身以及应用程序、数据集合等等)。在现代操作系统(Windows、Unix、Linux、Mac OS等等)中，文件是可存储信息(例如，数据、程序等等)的基本单元，由操作系统使用，文件组以“文件夹”的形式组织。在Microsoft Windows、Macintosh和其它操作系统中，文件夹是文件的集合，可以被作为实体来检索、移动或操纵。在某些其它操作系统中，诸如DOS、z/OS和大多数基于Unix的操作系统，使用术语“目录”而非文件夹，早期的Apple计算机系统(例如Apple IIe)使用术语“目录册”；然而，如这里所使用的，所有这些术语都是同意的且是可交换的，并且在这里旨在进一步包含所有其它用于或引用分层信息存储构架的等价术语。

如本领域的技术人员所公知和理解的，目录(即文件夹的目录)是基于树的分层结构，其中文件基于文件夹的位置来分组，所述文件夹包含树结构的节点。例如，如图6中所示，基于DOS的文件系统基文件夹(或“根目录”)302可以包括多个文件夹304，每个文件夹可以进一步包括附加的文件夹308’直至无穷。虽然在操作系统层，这些文件夹的每一个可以具有一个或多个文件，文件夹中的初始文件在树分层结构中除了位置没有共同点。不惊奇地，这个将文件组织或文件夹层次的方法间接地反映了用于存储这些文件的典型存储介质(例如硬盘、软盘、CD-ROM等等)的物理组织。

除了上述以外，每个文件夹是其子文件夹和其文件的容器-即，文件夹拥有这些子文件夹和文件。例如，当操作系统删除文件夹时，它的子文件夹和文件也被删除(对于每个子文件夹，递归地包括它的子文件夹和文件)。同样地，每个文件只能被一个文件夹所拥有，虽然文件可以被拷贝且其拷贝可以位于不同的文件夹中，文件的拷贝自身是与原文件没有直接连接的独特的和分开的实体(例如，在操作系统层上，对原文件的修改不会被镜像到其拷贝文件)。在这方面，文件和文件夹因此在特性上是实质“物理的”，因为文件夹是物理容器的概念等价物，文件是容器中离散的和分开的物理元素的概念等价物。

用于组织、搜索和共享可以用于本发明的数据的存储平台被设计成存储所有类型的数据，包括被称为对象的数据形式。参见图7，依照本发明的存储平台400包括在数据库引擎414上实现的数据存储402。在一个实施例中，数据库引擎包括带有对象关系扩展名的关系型数据库引擎。在一个实施例中，关系型数据库引擎414包括Microsoft SQL服务器关系型数据库引擎。

数据存储402实现支持数据组织、搜索、共享、同步和安全性的数据模型。模式中描述了特定类型的数据，诸如模式440，存储平台400为部署那些模式和扩展那些模式提供了工具446。

在数据存储402中实现的改变跟踪机制406提供了跟踪对数据存储改变的能力。数据存储402也提供安全能力和升级/降级能力410。数据存储402也提供一组应用程序编程接口412以使得数据存储402的能力可以被其它存储平台组件和使用存储平台的应用程序(例如应用程序450a、450b和450c)使用。

本发明的存储平台进一步包括应用程序编程接口(API)422，使得诸如应用程序450a、450b和450c等应用程序能够访问存储平台的所有前述能力并访问模式中所描述的数据。应用程序可以将存储平台API 422与其它API(诸如OLE DB API 424和Microsoft Windows Win32 API 426)结合使用。

本发明的存储平台400可以向应用程序提供多种服务，包括便利用户或系统之间数据共享的同步服务430。例如，同步服务420可以允许和与数据存储420具有相同格式的其它数据存储440协同工作以及访问具有其它格式的数据存储442。存储平台400也为文件系统提供允许数据存储402与现有文件系统协同工作的能力，所述现有文件系统诸如Windows NTFS文件系统418。

在至少一些实施例中，存储平台420也可以提供具有附加能力的应用程序，使得能够操作数据或允许与其它系统的交互。这些能力可以以附加服务428的形式体现，诸如Info Agent服务434和通知服务432以及其它工具软件436的形式。

在至少一些实施例中，存储平台体现在计算机系统的硬件/软件接口中或形成计算机系统的硬件/软件接口的组成部分。例如，非限制性的，本发明的存储平台可以体现在操作系统、虚拟机管理(VMM)、通用语言执行环境(CLR)或其功能等价物、或Java虚拟机(JVM)或其功能等价物中，或形成它们的组成部分。

通过其通用存储基础和原理化数据，本发明的存储平台能够为消费者、知识工作者和企业提供更为有效的应用程序开发。它提供了充足的和可扩展的编程表面区域，不仅使得其数据模型中固有的能力可用，而且也包含和扩展了现有文件系统和数据库访问方法。

在这里描述和各个附图中，本发明的存储平台400可以被称为“WinFS”。然而，使用这个名字来指存储平台仅仅是为了描述方便，而不是以任何方式限制本发明。

本发明的存储平台400的数据存储402实现了支持驻留在存储器中数据的组织、搜索、共享、同步和安全性数据模型。在本发明的数据模型中，“对象”是存储信息的基础单元。数据模型提供了用于宣称对象和对象扩展和用于在对象之间建立关系和用于组织和分类对象的机制。

关系型数据库引擎414，在一个实施例中包含Microsoft SQL服务器引擎，支持内置的标量类型。内置标量类型是“原生的”和“简单的”。原生的是指用户不能定义他们自己的类型，简单的是指它们不能封装一复杂结构。用户定义类型(UDT)通过使得用户能够通过定义复杂的、结构化类型来扩展类型系统提供了上述类型扩展和操作原生标量类型系统的机制。一旦被用户定义，UDT可以被用在内置标量类型可以使用的类型系统中的任何地方。

存储平台图解被映射到数据库引擎存储中的UDT类。数据存储对象被映射到从Base.Item类型获取的UDT类。扩展还被映射到UDT类并使用继承。根扩展类型是Base.Extension，所有扩展类型都是从根扩展类型得出的。

UDT是CLR类-它具有状态(即，数据字段)和行为(即，例程)。使用任何管理语言来定义UDT-C#、VB.NET等等。UDT方法和操作符可以相对那个类型的实例在T-SQL中被调用。UDDT可以是例如行中列的类型、T-SQL中例程参数的类型或T-SQL中可变量的类型。

示例性实施例

本发明提供了称为基表(因为在这个基础上视图被定义)上的索引视图(即物化视图)的创新方法并且在可以用于增强查询的附加操作和结构中使用这种索引视图。索引视图用作-在基表上的索引。此索引可以被用作一个到基表的访问路径以便解答与索引视图和基表的结构相匹配的查询。

典型索引视图包含数据条目并且可能包含关联的子条目或者其他依赖或源于此的数据。索引视图可能包含一个传输数据的函数调用的结果。举例而言，索引视图可能包含嵌套，在这样的情况下一个条目会有多个关联的子条目。例如，假设第一基表包含名字，同时第二基表包含地址。一个在两个基表上的“联接”操作会为一个特定的名字提供一个地址。索引视图可能被以包含名字和相关地址的方式存储，正如图8中所示的索引视图500。在索引视图500中，名字“Alice”有三个相关地址：地址1、地址2和地址3。每个在示例的索引视图500中的其它名字(例如“Bob”和“Charlie”)都有一个相关地址。此索引视图被认为是嵌套的，因为多重地址与名称“Alice”相关联。移去嵌套是希望的，所以如果与Alice相关的地址中的一个改变了，这个地址可以直接被访问，并且索引视图也不需要为了反映这个变化而重新计算。其他功能的结果也可以通过这个方式被索引。

为了移除这个嵌套，唯一的聚类关键字550被构造出来，如图9所示。如图示及下面更详细的描述，关键字550为索引视图中的有嵌套的条目提供了一个单独的子条目。这样，在这个例子中的关键字550提供三个条目“Alice”，每一个条目与三个地址：地址1、地址2和地址3中的一个不同的地址相关联。这个关键字允许一个应用程序在基表和索引视图之间来回。

索引视图可被当作在有多值属性的基表上的次级索引。这样，本发明提供使用索引视图在函数调用的结果中进行搜索(正如在这个例子中被嵌套的数据)。索引在函数调用(例如一个去嵌套操作)的结果上被执行。换言之，被导出的数据(即子条目)被索引了。本发明索引复杂的结构，所以更多的索引视图可以被确定和可供使用。这为查询执行计划提供了更多的选项，导致更优化的查询。

如下文进一步的描述，在函数调用的结果上索引一个视图提供了一个索引复杂数据(例如一个嵌套集合的内容)变换的方法。一个本发明支持的可效仿的去嵌套操作是SQL Server的“交叉应用去嵌套”。具体来说，使用“交叉应用去嵌套”操作，在索引视图里的一个嵌套的级别可以被去嵌套。然而，依据本发明，任何级数的去嵌套都是可预期的。更一般的，可以预期，通过这个方法多重级别的函数调用可以被索引。

此外提供了从索引视图提供到基表的“反向联接”。这允许来自基表的字段(不出现在索引视图中)被包含在对表的查询的结果中，所述表使用被视为访问路径的索引视图来处理。从索引视图到视图在其上被定义的基表上使用反向联接。这提供了包含不在索引视图而在基表中的查询结果中的的列的方法。

所期望的是经由唯一的聚类关键字，从单表索引视图到基表支持反向联接，所述聚类关键字作为逻辑行定位符。系统可以经由唯一的聚类关键字从索引视图反向联接到基表中。这些特征允许使用索引视图对表格的函数调用数据的结果的内容索引，诸如对多个集合或多个值属性的“交叉应用去嵌套”操作。

如上所述，可以对函数调用数据的结果定义索引视图(诸如交叉应用去嵌套操作)。结合反向联接能力，这允许基于包含在这些记录中的值的集合的内容来访问表格中的记录。因此，可以使用经索引的视图来创建对UDT的多重集属性的索引。例如，以下经索引的视图可以帮助加速对city的检索性能：

       Create view iv_city with schemabinding as

       Select a.addr.city city，a.addr.addrID addrID，person.htid，person.pid

       From person cross apply unnest(pcol.addresses)a(addr)

       Create unique clustered index iv_city_idx on iv_city(city，pid，addrID)

注意期望将addrID和pid用于使得索引唯一，假设addrID在单个多重集地址中是唯一的。以下例子示出通用函数调用如何可能有这个索引能力：

       Create view iv_city with schemabinding as

       Select a.addr.city city，a.addr.addrID addrID，person.htid，person.pid

       From person cross apply FUNCTION(pcol)a(addr)

       Create unique clustered index iv_city_idx on iv_city(city，pid，addrID)

在这个例子中“unnest”被表示“对这里所讨论的数据函数调用”的“FUNCTION”代替。一般地，不同的函数可以用在“FUNTION”的位置处。可能的例子包含在集合中去除嵌套数据、分解XML文档或对来自复杂结构(诸如UDT)的多个字段索引。也可能将这个机制使用于其它对数据进行处理的函数上。

查询的经索引的视图可以用于无需读基表(例如基表“person”)就回答查询。这可以是有益的，因为索引可能比基表小很多。例如期望基表“person”包含属性pcol，它是UDT。Pcol字段(地址)之一是多重集(集合值属性)。考虑表1，它是假设的“person”表。

  Person  Pid  Htid                                Pcol  Pid  Name  …               Addresses  1  N/A  1  Bob  AddrID  City  …  1  Bellevue  2  Corvallis  2  N/A  2  Sue  AddrID  City  3  Bellevue  4  Berkeley

                                表1

表1示出了粒度的最精细层次。对本例不是必须的列被省略并且用省略号表示。注意到在本例中pid和name是原子属性，因此只包含一个值，而地址是集合，因此包含多于一个值。City是每个成员的地址的一个字段。

在“person”表中，为每个名字示出了多个子行。例如，Bob有两个地址子行：AddrID1和2，分别对应于Bellevue和Corvallis；Sue有两个地址子行：AddrID3和4，分别对应于Bellevue和Berkeley。

考虑经索引的视图iv_city。对于“person“表中上述值，iv_city的内容如表2示出。

  iv_city  City  AddrID  Htid  Pid  Bellevue  1  1  1  Bellevue  3  1  2  Berkeley  4  1  2  Corvallis  2  1  1

                          表2

iv_city中每行对应于粒度尺寸数据的最精细层次中的信息。因此，经索引的视图示出现在每个子行条目在其自己的行中。注意Pid可以被用作反向到第一表反向联接。例如，iv_city中的Pid1将反向联接到“person”表的Pid1。可能对部分数据索引(即，只对感兴趣的数据，例如只对住在Bellevue的人)。

现在，考虑以下查询以发现至少在Corvallis有一个地址的所有人的名字：

      Select distinct person.pid，person.pcol.name

      From person cross apply unnest(Pcol.addresses)as a(addr)

      Where a.addr.city＝‘Corvallis’

图10示出的执行计划通过使用iv_city(对去除嵌套结果的索引视图)和基表“person”的关键人员pid的反向联接，可以回答上述的查询。

注意交叉应用去除嵌套索引视图iv_city与反向联接操作组合(如图10所示)使得可以基于包含在个人的pcol UDT字段值的地址结合中个人地址值的城市，对“person”表行进行快速关联查找。

对于给出的示例数据，对左方的索引扫描将仅识别iv_city的一行(上述示出iv_city的内容的表2中的最后一个)。Iv_city的这行与人员Bob的行联接。Bob的“person”表行接着将传递上述半联接操作符。在图10中，“nest-loopright semi-join“操作用作反向联接操作。接着会投影pid和pcol.name字段，又得出一行。没有重复，因此排序和重复消除不会改变它们的输入流。最终的结果在表3中示出：

  Pid  Name  1  Bob

     表3

更特别地，关于来自索引视图的反向联接，假设索引视图V是N个基表(T1..TN)的函数。此外，假设V被构建成只使用选择、投影、联接、分组和集合操作。每个表T1...TN具有一个或多个在表的元数据中确定的关键字。关键字是表的一列或多列的集合，使得集合中的值唯一地识别表中的行。

假设匹配针对T1...TN定义的查询Q的行集合可以只用V中的行来识别。(Q可以是较大查询的一部分。不失一般性地，考虑Q是自立的查询。)即使Q的结果的行可以通过参考V来识别，这不意味着从Q得出的行可以整个从V构建。情况可以是期望应该出现在Q的结果中一些列值出现在T1...TN的之一中。

从索引视图V到在其上定义视图的基表T(T1...TN的之一)的反向联接被定义为在V和T之间对T的任何关键字和来自T的那个关键字的V中的字段的等价联接。反向联接在其上执行的关键字可以是但不限于单列或多列主关键字或单列或多列候选关键字。关键字可以或可以不具有索引。如果关键字不具有索引，那么索引可以或可以不被聚类。虽然这里将反向联接描述成在基表的聚类关键字上执行，本发明包含了对任何类型的关键字做反向联接的能力。

作为反向联接的一个例子，考虑使用下述SQL语句来定义表：

       Create table emp(eno int，name varchar(30)，salary money)

定义基表“emp”将使用对eno排序的经聚类的访问路径来存储，如下：

       Create unique clustered index eno_idx on emp(eno)

Eno是emp的关键字。现在，考虑索引视图定义如下：

       Create view highpaid with schemabinding as

       Select eno，salary

       From dbo.emp e

       Where salary＞200000.00

       Create unique clustered index on highpaid(eno)

现在，考虑以下查询：

       Select eno，name，salary from emp where salary＞300000.00

作为如何使用索引视图“highpaid”与反向联接来解决这个查询的例子，图11中所示的访问计划将提供对查询的示例性回答。如图11中所示，从索引视图“highpaid”选出的行对于关键词eno被“反向联接”到基表“emp”，其中使用“nested-loop-join”操作作为反向联接操作。因此术语“反向联接”被用于描述对一关键字从索引视图反向到基表的联接。

预期的是任何类型的联接算法可以与反向联接一起使用(例如，nested-loop、sort-merge、hash)。

图12是在具有嵌套数据的基表中查询数据的示例性方法的流程图。在步骤600处，接收到查询。在步骤610处，基表中数据的索引视图被接收、检索或否则被生成。在步骤620处，查询优化程序确定查询是否匹配或包含匹配索引视图的查询模式。在步骤630处，如果查询或其部分匹配索引视图，那么查询优化程序生成一计划：使用匹配索引视图作为索引而非执行该函数应用。在步骤640处，如果索引视图不能传递原始查询中所请求的所有列，那么优化程序引入与原始基表的反向联接以经由聚类关键字获取丢失的列。这允许索引视图中没有的基表的字段被包含在查询结果中。

在步骤650处，如果查询或其部分不匹配任一索引视图，那么查询优化程序生成一计划：对数据应用原始函数。

本发明也允许将索引视图作为部分索引的推广，以及将索引视图作为对类型层次的部分索引。通过将索引视图与从索引视图到基表反向联接的能力相结合，本发明提供了被称为部分索引技术的推广。索引视图加反向联接能力提供了比部分索引更为有力的能力集合。

为了创建表的各行的仅一子集的索引，在索引视图定义(例如在Where短语中)中提供了适合的条件。例如，为了创建加速查找个人“Fred”的视图，定义了以下索引视图：

Create View v_fred with schemabinding as

Select pid，htid

From person

Where pcol.name＝‘Fred’

Create unique clustered index i_v_fred on v_fred(htid，pid)

给出对基表的聚类关键字作反向联接的能力，以及现有查询匹配索引视图的能力，这个索引视图可以帮助回答诸如“Select*from person where pcol.name＝‘Fred’”等查询。可以通过读出索引视图中的一行和将其反向联接到个人表中来解决这个查询。

此外，索引视图加上反向联接到基表的能力也可以在对象关系DVMS(数据库管理系统)中支持索引一组用户定义类型(也被称为UDT或对象)。如果类型以推广的层次排列(也被称为类型层次或IS-A层次)，那么可能使用索引视图加上到一表中的索引值的反向联接的能力，所述表的类型具有给定类型或其子类型之一。

为了对子类型的字段索引，其中对类型过滤的部分索引不需要或不是期望的，可以实现对经计算的列的常规索引。所期望的经计算的列的值对于没有索引的字段的类型为NULL。索引可以被聚类或不聚类。例如，为了对个人工资建立聚类索引，其中非雇员的工资字段为NULL：

Alter table person add salary as(treat pcol as employee_t).salary

Create clustered index i_sal on person(salary)

为了为给定UDT列对类型层次的子集索引(例如因为只有那个子集中的值具有期望被索引的特定属性)，于是在视图定义的Where短语中的IS OF判定来创建部分索引。例如，为了对雇员工资创建索引，所述索引不包括对不是雇员的个人的索引中的记录：

Create view v-emp_sal2 with schemabinding as

 Select(treat pcol as employee_t).salary salary，htid，pid

 From person

 Where pcol is of(employee_t)

 Create unique clustered index i_emp_sal2 on v_emp_sal2(salary，htid，pid)

这个示例性索引视图对非雇员工资没有NULL条目。非雇员不被索引，因为它们更适合被视图的Where短语中的IS OF条件过滤掉。

XML字段的索引

本发明的各方面可以被用于对XML值数据字段索引。相对于存储在数据库的表中的关系型数据，XML是半结构化的：数据不是依附于先验宣称的模式，而是用表示模式信息的标签注释。为了索引和处理常规数据库系统中的XML数据，它必须被分成表格式。以下例子示出了XML分段，且图4中示出了一个可能的相应表格式。

<person>

 <name>Jim Smith</name>

 <phones>

    <home>425-601-9229</home>

    <cell>425-799-1532</eell>

 </phones>

 …

</person>

  TAG  VALUE  HIERARCHICALINFORMATION  Person  1  name  Jim Smith  1.1  phones  1.2  home  425-601-9229  1.2.1  cell  425-799-1532  1.2.2

                  表4

可能有各种不同的将XML分成表的格式的方式，本发明不限于使用特定的一个。然而，可以使用任何给出一XML分段输出表值格式的函数，例如这里被称为XMLTransform。

函数XMLTransform是上述的表值函数。本发明允许对在XML分段上对XMLTransform的调用的结果索引。例如，用户可能希望对TAG，VALUE和HIERARCHICAL INFORMATION列或它们的组合建立索引。

用户可以查询XML分段的一个可能的方式如下写出：

Select Value

From‘<xml...>’xmlstring cross apply XMLTransform(xmlstring)

Where Tag＝‘name’and Value＝‘Sam Jones’

其中‘<xml...>’表示对任一给定的XML分段。查询可以搜索XML分段以找到具有值‘Sam Jones’标记‘name’的元素。

此外，XML分段可以以数据库表中XML数据类型字段的形式提供，而非以XML文本串给出。使用XML从XML数据类型列查询的例子可以如下写出：

Select Value

From sales cross apply XMLTransform(sales.salesperson)

Where(Tag＝‘cell’or Tag＝‘home’)and Value like‘425％’

And sales.date＝‘02/28/2004’

这假设在表sales中有列salesperson，所述表sales是类型XML分段，即sales中的每行包含被称为salesperson的XML分段。上述查询将查询sales表与查询XML分段相结合；它返回在02/28/2004结束一交易的销售人员的电话号码。

多列或字段变换

另一个示例性实施例允许对多列和/或复杂结构的多字段的索引。一般地，数据库系统中的索引结构可以从复杂结构中的单列或位置索引数据。例如，关于表2所描述的例子描述了在嵌套集合中索引Address字段的机制。本发明的各方面也可以被用于对从复杂对象或一行中的多个字段导出的数据索引。

  tbl_peopleaddresses  City  State  ID  Name  Bellevue  WA  1  George  West Lake  WA  2  Sara  Berkeley  CA  3  Bob  Corvallis  OR  4  Jeff

                     表5

表5中的示例索引视图描述了人员和他们住处的表。对数据的函数调用可以返回如表6所示的数据。

  iv_peopleaddresses  City  ID  (additionalcolumn(s))  Bellevue  1  …  West Lake  2  …  Berkeley  3  …  Corvallis  4  …  WA  1  …  WA  2  …  Washington  1  …  Washington  2  …  CA  3  …  California  3  …  OR  4  …  Oregon  4  …  George  1  …  Sara  2  …  Bob  3  …  Jeff  4  …  West  2  …  Lake  2  …

                           表6

表6描述了对来自表5的数据不同种类的索引视图的结果。在这个例子中，来自表5的多列在索引视图中被一起索引。虽然这个例子使用多列，也可能使用来自诸如UDT等复杂对象的多个字段或它们两者的组合。此外，这个变换可以包含应用到数据中各列或各字段的特殊逻辑。在这个例子中，每个状态的缩写是目标变换和原始源数据的一部分。然而，每个状态的全名被作为函数调用的部分生成并且也被插入到结果中。许多变换是可能的并且不限于引入对于单值的附加映射。可能的映射可以包含但不限于获取列中数据的子字符串、将来自多列或多字段的数据以相同的方式组合或从单列或字段将多个单词分成多行。表6也包含一例子，其中来自单字段的多个单词以多行的方式返回。表中附加的列可以用于包含定位符列，它使得能够反向联接或引入列以保证函数调用结果的唯一性。

这个示例性变换允许对复杂变换的结果索引。它也使得对某些查询类更为有效地查询数据。一个这样的查询可以写出如下：

Select*from tbl_peopleaddresses where SOMECOLUMNCONTAINS(‘Lake’)

or SOMECOLUMNCONTAINS(‘California’)；

在这个查询中，所期望的结果是发现与单词‘Lake’或单词‘California’有些关联的人。这个关联可以是与表中的任何列的准确列匹配，或者它可以是附加、潜在的对表中的数据用户定义逻辑的结果。在这个例子中，‘Lake’是与包含‘Sara’的记录相关联的一个字段的第二个单词，而‘California’与包含‘Bob’的记录相关。这个逻辑被封装在函数‘SOMECOLUMNCONTAINS’中，但它可以用在任何搜索情况中。例如，可以使用SQL函数‘LIKE’来应用相同的逻辑，虽然其它函数可以以相似的方式使用本发明。

查询处理器可以对这个函数调用结果使用索引视图以有效地解决包含LIKE或SOMECOLUMNCONTAINS的查询。所期望的是这个逻辑只需要使用匹配逻辑来有效地发现包含对数据的这个特定函数调用结果的索引视图。

结论

这里所描述的各种系统、方法和技术可以用硬件、软件或适当时用它们的组合来实现。因此，本发明的方法和装置或某些方面或其部分可以用有形介质体现的程序代码(即指令)，所述有形介质诸如软盘、CD-ROM、硬盘或任何其它的机器可读存储介质，其中当程序代码被载入并且被机器(诸如计算机)执行，机器成为了实现本发明的装置。在可编程计算机上执行程序代码的情况下，计算机一般包括处理器、处理器可读的存储介质(包括易失性和非易失性存储器和/或存储元件)、至少一个输入设备和至少一个输出设备。一个或多个程序更适宜以高级过程或面向对对象的编程语言实现以与计算机系统通信。然而，如果期望，程序可以以汇编或机器语言来实现。在任一情况下，语言可以是编译或解释语言并且与硬件实现相结合。

本发明的方法和装置也可以以在某些传输介质上发送的程序代码的形式体现，诸如在电线或电缆上，通过光纤或经由任何其它形式的传输，其中当接收到程序代码，将其载入到机器并由机器执行程序代码时，诸如EPPOM、门阵列、可编程逻辑器件(PLD)、客户端计算机、视频录像机等等，机器成为实现本发明的装置。当在通用处理器上实现时，程序代码与处理器相结合以提供用于执行本发明的索引功能的唯一装置。

虽然结合各种附图的优选实施例描述了本发明，应该理解可以使用其它类似的实施例，或者可以对所描述的实施例作出修改和增加以执行本发明相同的功能而不背离本发明。例如，虽然本发明的示例性实施例在数字设备仿真个人计算机功能的环境中描述，本发明的技术人员会认识到本发明不限于这种数字设备，如本应用中所描述的可以应用到任何数量的现有或新兴计算设备活环境中，诸如游戏控制台、手持式计算机、便携式计算机等等，无论有线或无线，并且可以应用到经由通信网络连接或通过网络交互的任何数量的这种计算设备。此外，应该强调的是这里期望各种计算机平台，包括手持设备操作系统和其他应用程序特定操作系统，尤其是随着无线网络设备的数目不断增长。因此，本发明不应被限于任何单一的实施例，而应该按照符合所附权利要求的最广宽度和范围来构造。