用于访问关系型数据库系统中的分层数据的高效索引结构

摘要

本发明描述了一种分层索引，该分层索引获取由关系型数据库系统仿效的分层结构的分层关系。利用包括用作分层索引项的行的数据库表实现分层索引。另一个表的行与分层结构中的节点相关。分层索引中的每项都映射到与分层结构中的一个节点对应的行。分层中的节点可以是具有一个或多个子节点的父节点。在这种情况下，分层索引中的对应项包括用于识别索引中其它项的标识符，其中其它项对应于与父节点的子节点相关的行。

说明书

相关申请

本申请是由Eric Sedlar于2002年5月28日提交的名称为“关系型系统中分层索引的维护(Maintenance of Hierarchical Index in aRelational System)”的第10/171,728号美国专利申请(代理机构卷号为50277-1985)的部分继续申请，其内容在此全部引入作为参考；

本申请是由Eric Sedlar于1999年2月18日提交的名称为“用于访问关系型系统中的分层组织信息的分层索引(HierarchicalIndexing for Accessing Hierarchically Organized Information in aRelational System)”的第09/251,757号美国专利申请，美国专利号为6,427,123(代理机构卷号为0288)的部分继续申请，它和上述美国专利申请第10/171,728号同系列，并且其内容在此全部引入作为参考；

本申请要求以下专利申请的优先权：Sedlar和ViswanathanKrishnamurthy于2001年9月28日提交的名称为“提供有数据库系统的基于文件的访问(File Based Access Provided With a DatabaseSystem)”的第60/326,052号美国专利申请；

本申请要求以下专利申请的优先权：Nipun Agarwal、RaviMurthy、Eric Sedlar、Sivasankaran Chandrasekar、Fei Ge、SyamPannala、Neema Jalali和Muralidhar Krishnaprasad于2002年5月7日提交的名称为“对提供文件系统提取的数据进行SQL访问(SQLAccess to Data that Provides a File System Abstraction)”的第60/378,800号美国临时专利申请。

本申请还涉及下列美国专利申请，其内容在此全部引入作为参考：

由Nipun Agarwal、Ravi Murthy、Eric Sedlar、SivasankaranChandrasekar和Fei Ge于同日提交的名称为“用于访问关系型系统中的分层数据的操作符(OPERATORS FOR ACCESSINGHIERARCHICAL DATA IN A RELAIONAL SYSTEM)”的美国申请专利，申请号为＿＿＿＿(代理机构卷号为50277-1975)；

由Nipun Agarwal、Eric Sedlar、Ravi Murthy和Namit Jain于同日提交的名称为“提供对关系型数据的一致分层提取(PROVIDINGA CONSISTENT HIERARCHICAL ABSTRACTION OFRELATIONAL DATA)”的美国专利申请，申请号为＿＿＿＿(代理机构卷号为50277-1976)；

由Ravi Murthy、Muralidhar Krishnaprasad、SivasankaranChandrasekar、Eric Sedlar、Vishu Krishnamurthy和Nipun Agarwal于同日提交的名称为“用于将XML模式映射到对象关系型数据库系统的机制(MECHANISM FOR MAPPING XML SCHEMAS TOOBJECT-RELATIONAL DATABASE SYSTEMS)”的美国专利申请，申请号为＿＿＿＿(代理机构卷号为50277-1977)；

由Nipun Agarwal、Eric Sedlar和Ravi Murthy于同日提交的名称为“用于高效管理数据库系统中的变型数据的索引(INDEXINGTO EFFICIENTLY MANAGE VERSIONED DATA IN A DATABASESYSTEM)”的美国专利申请，申请号为＿＿＿＿(代理机构卷号为50277-1978)；

由Ravi Murthy、Eric Sedlar和Neema Jalali于同日提交的名称为“用于存储分层组织资源的内容和属性的机制(MECHANISMSFOR STORING CONTENT AND PROPERTIES OFHIERARCHICALLY ORGANIZED RESOURCES)”的美国专利申请，申请号为＿＿＿＿(代理机构卷号为50277-1979)；

由Ravi Murthy、Eric Sedlar、Nipun Agarwal、Sam Idicula和Nicolas Montoya于同日提交的名称为“用于数据库系统中统一访问控制的机构(MECHANISM FOR UNIFORM ACCESS CONTROL INADATABASE SYSTEM)”的美国专利 申请，申请号为＿＿＿＿(代理机构卷号为50277-1980)；

由Syam Pannala、Eric Sedlar、Bhushan Khaladkar、Ravi Murthy、Sivasankaran Chandrasekar和Nipun Agarwal于同日提交的名称为“用于XML文档惰性显示的可装载装置(LOADABLE UNIT FORLAZY MANIFESTATION OF XML DOCUMENTS)”的美国专利申请，申请号为＿＿＿＿(代理机构卷号为50277-1981)。

技术领域

本发明涉及关系型数据库系统，更具体而言是涉及在关系型数据系统中对分层数据进行索引的技术。

背景技术

人们往往将信息按类别组织。信息被组织的类别是通常按照某种形式的层次相对彼此被组织的信息自身。例如，个体动物属于种，种属于属，属属于科，科属于目，目属于纲。

随着计算机系统的出现，已经开发出的用于存储电子信息的技术，在很大程度上反映了人们对这种分层组织的需求。例如，传统计算机文件系统通常利用基于分层组织的原理实现。具体是，一个典型的文件系统具有分层排列的目录，以及存储在这些目录中的文档。理想地，目录间的分层关系反映了目录被赋予的含意之间的直观关系。类似地，理想情况是每个文档基于文档内容与文档所存储的目录被赋予的含意之间的某种直观关系被存储在目录中。

图1显示了一个典型的文件系统的实施例。该图解的文件系统包括分层排列的多个目录。目录中存储两个文档118和122。具体是，文件名均为“Example.doc”的文档118和122分别存储在名称为“Word”的目录116和名称为“App4”的目录124中。

在目录分层中，目录116是名称为“Windows”的目录114的子目录，目录114是目录110的子目录。类似的，目录124是名称为“VMS”的目录126的子目录，目126是目录110的子目录。子目录110被称为“根”目录，因为其它所有目录都起源于该目录。在许多系统中，符号“/”用于指根目录。

当电子信息按层次被组织时，每项信息可通过跟踪一条从层次到包含该项信息的实体的“路径”被定位。在分层文件系统中，到某一项的路径起始于根目录，并向下通过分层目录最终达到包括所关注的项的目录。例如，到文档118的路径依次包括目录110、114和116。

分层存储系统通常允许不同的项具有相同名称。例如，图1所示的文件系统中，文档118和文档122的名称均为“Example.doc”。因此，为明确识别指定的文档，所需要的不仅仅是文档名。

识别和定位一个存储在分层存储系统中特定项信息的简便方法是使用“路径名”。路径名是一种根据从分层到某一项的路径来唯一识别该项的简便方法。路径名由一系列的被称为路径单元的名称组成。在文件系统中，该名称序列中的每个名称就是“文件名(filename)”。术语“文件名”既指目录名，也指文档名，因为目录和文档都被认为是“文件”。

在文件系统中，指定路径名中的文件名序列起始于根目录名，包括沿着从根目录到所关注项的路径的所有目录名，并终止于所关注项的名称。通常，要遍历的目录列表通过某种分隔符(如‘/’、‘\’或‘；’)被连接在一起，以便组成路径名。这样，文档118的路径是Windows/Word/Example.doc，而文档122的路径是VMS/App4/Example.doc。

在不同类型的分层组织的系统之间，目录(文件)与目录所包含的内容之间的关系差别很大。在被多种实施方案(例如Windows和DOS文件系统)采用的一种模型中，要求每个文件刚好有一个父目录，以形成树结构。在更为复杂的模型如使用硬连接的UNIX系统中，分层采用定向(directed)图表的形式，其中文件具有多个父目录。

与组织电子信息的分层方法相比，关系型数据库将信息存储在由行和列组成的表中。每行由唯一的RowID识别。每列代表记录的属性或字段，每行代表一个特定的记录。通过向管理数据库的数据库服务器提交查询获取数据。查询必须遵照数据库服务器支持的数据库语言。结构化查询语言(SQL)是现由许多数据库管理系统支持的数据库语言。

每种存储系统都具有优点和不足。分层组织的存储系统简单，直观，容易实现，是多数应用程序使用的标准模型。不足的是，简单的分层组织不支持复杂的数据检索操作。例如，必须检查每个目录中的内容，以找到在特定日生成的具有特定文件名的所有文档。由于必须搜索所有目录，因此在简化检索进程中分层组织不起作用。

关系型数据库十分适合存储海量信息和以非常灵活的方式访问数据。相对于分层组织的系统，可以很容易和高效地从关系型数据库系统中检索出那些与复杂的搜索条件匹配的数据。然而，向数据库服务器表达和提交查询的进程没有仅仅遍历分层的目录直观，并且会超出许多计算机用户技术支持水平。

过去，已通过不兼容的不同方法实现了分层组织系统和关系型组织系统。然而，一些关系型组织系统包括了允许系统仿效分层组织系统的特征。当需要关系型系统的存储能力和灵活性，但又期望分层系统的直观性和普遍性时，这种仿效尤其合适。

一种这样的特征基于由SQL定义的连接(connect-by)语句。连接语句允许用户提交请求基于分层组织的数据的查询。关系型数据库系统以一种反映分层组织的方式返回数据。连接语句指定用于定义分层组织所基于的分层关系的条件。

然而，使用连接语句表达查询有缺点。首先，处理这种查询可伴有计算多重连接操作，对于处理该查询的数据库服务器来说，这是一个非常耗时的过程。使用连接语句还增加了用户负担。在查询中加入连接语句还使本就已复杂的表达查询的任务更为复杂。

因此，需要提供这样一种机制，其允许关系型数据库系统按照较传统仿效机制更高效的方式去仿效分层组织的系统。还需要提供以减轻表达请求和返回分层组织数据的查询的复杂性的这种仿效。

附图说明

通过附图中的例子来说明本发明，而不是限制本发明，在附图中相同的附图标记指相同元件，其中：

图1是说明分层文件系统的方框图。

图2是说明信息分层的方框图。

图3所示的方框图说明了用于获取根据本发明实施例的关系型系统中图2所示的信息分层的表。

图4所示的方框图说明了用作根据本发明实施例的分层索引的数据库表。

图5是本发明实施例在其上实现的系统的方框图。

具体实施方式

描述了一种用于访问存储在关系型数据库系统中的分层信息的方法和装置。出于解释的目的，在下面的描述中阐述了大量的特定细节以完全理解本发明。然而，很显然，没有这些特定细节本发明仍可实现。在其它实例中，以方框图的形式显示了众所周知的结构和装置，以避免对本发明的理解上的不必要的模糊不清。

概述

此处描述了一种分层索引的新的实现，该分层索引获取通过关系型数据库系统仿效的层次的分层关系。通过使用包含有作为分层索引项的行的数据库表实现分层索引。另一张表具有和分层中的节点相关的行。分层索引中的每个项映射到对应于分层中的节点的行。分层中的节点可以是具有一个或多个子节点的父节点。在这种情况下，分层索引中的对应项包含有用于识别索引中其它项的标识符，其中其它项对应与父节点的子节点相关的行。

另外，索引包含关于用户如何访问与分层相关的行的信息。该信息可用于确定用户在执行涉及索引的操作期间的访问权限，从而允许确定访问权限的操作和任务被更加有效地执行。

最后，数据库服务器可以使用分层索引执行数据库服务器支持的类似本地索引的语句。这种以该方式被支持的语句的类型包括数据定义语言(DDL)语句和数据操纵语言(DML)语句。这两种语句通过如SQL这样的数据库语言编写。

系统概述

图2说明了分层结构200，其用于在此提供的帮助理解本发明实施例的例子中。分层结构200包括8个节点。分层结构中的最高节点被称作“根”节点。分层结构中每个分支末端的节点是“叶”节点。根节点和叶节点间的节点是“中间”节点。在所说明的分层结构中，节点1、2和3是中间节点，节点4、5、6和7是叶节点。

在信息分层中，节点对应信息。通常，与每个节点有关的信息项具有某种形式的名称，以及某种类型的内容。例如，在与分层文件系统对应的分层结构中，节点典型地对应于文件(其中“文件夹”或者“目录”是文件的一种)。每个这样的文件都将具有一个名称和某种形式的内容。

图3是在关系型数据库系统中用于表示分层结构200的两张表302和350的方框图。表302包括分层结构200中每个节点的一行。RowID伪列RRowID具有用于识别表302中的行的RowIDs。列NODE包含用于唯一识别分层结构200中的节点的逻辑标识符(在此为“节点标识符”)。列NODE可以是包括主关键字(key)值的主关键字。列DATA包含代表与节点相关的数据的值。表302中的对应于给定节点的行包括行的RowID，识别节点的节点标识符(id)，以及与节点相关的数据。例如，通过RowID R1识别的行304对应于节点1、与节点1相关的数据306、及其内容。在这里，通过其各自的RowID查询表302中的行。

表350包括定义分层结构200中的父-子关系的行，其中每一行定义一个父-子关系。列PARENT和CHILD包含节点标识符。列CHILD NAME包含分层结构200中对应特定父-子关系的子节点的“子名称”。对于由表350中的一行定义的一个特定的父-子关系，列PARENT包含了定义父节点的节点标识符(id)，列CHILD包含了定义子节点的节点标识符(id)，CHILD NAME包含了在该特定的父-子关系中的该子节点的子名称。类似地，行354和356分别表明节点1是节点2和节点3的父节点。行354中的CHILDNAME说明了在由行354表示的父-子关系中节点2的名称是“b”。

尽管在分层结构200内没有清楚描述，但是在分层结构中一个节点可以具有多个父节点，并且对于这些父-子关系的每一个具有不同的名称。例如，节点4是节点1的一个子节点，并且对于该父-子关系，其子名称为Z。这样，由该父-子关系表示的路径为“/a/Z”。对于表350中代表该父-子关系的行而言，PARENT包含节点1，CHILD包含节点4以及CHILD NAME包含Z。

子名称是链接属性的一个示例，即，一种特定于父-子关系而不是特定于父或子的属性。在另一个实施例中，表350包括用于其它链接属性的其它列。例如，链接属性可以指定某一父-子关系是否能够被除了具有最高级的系统访问权限的人(例如系统管理员)之外的任何人看见。或者，链接属性可以指定某一父-子关系固定不变，即，它不可由终端用户更改。表350中表示这种固定父-子关系的行可以无限期的在易失存储器中缓存，因为它们不太可能被改变。

分层索引

图4显示了根据本发明实施例的分层索引200，其描述了由表302和350表示的分层结构200的分层关系。索引402是一个具有多行多列的表。每行是一个索引项。对于分层结构200中的每个中间节点而言，它在索引402中的对应项识别该中间节点的子节点的索引项和表302中所述子节点对应的行。索引402不包含对应于叶节点的项。

索引402中的列IRowID是具有用于识别索引402中的项的RowID的RowID伪列。列NODE ID KEY包含索引402的主关键字值，该关键字值是表302中列NODE中的节点标识符(id)。列CHILD IDs包含组合标识符(id)的集合，每个组合id包括子节点的子名称，用于识别索引402中对应于该子节点的索引项的RowID(如果有的话)，以及用于识别表302中对应于该子节点的行的RowID。例如，CHILD IDs可被实现为数据类型“字符大型二进制对象”的列。该数据类型允许对于指定的索引项，许多组合id存储在一个列中。列AccInfo包含了用于访问节点及其在表302中的相应行的访问信息。

对于指定的节点及其在索引402中的相应项，该项包含了组合id，这些组合id用于识别在索引402中的对应于指定节点的子节点的其它项，但是只适于这些子节点是中间节点的情况。例如，在项408中，列NODE ID KEY包含节点id值1。从而，项408对应于节点1。项408中的CHILD IDs包含组合id{“b”，r2，R2}和{“c”，r3，R3}，识别分别对应中间节点2和3的索引项412和414。节点2是节点1的子节点。组合id{“b”，r2，R2}说明表302中的行R2对应于子节点2，其子名称是“b”。在项412中，NODE ID KEY包含值2，CHILD IDs包含{“d”，，R4}，{“e”，，R5}。组合ID{“d”，，R4}和{“e”，，R5}识别在索引402中没有项，表明相应的子节点为叶节点。组合ID{“d”，，R4}识别为对应于表402中的行R4的节点4为子节点。节点4是一个叶节点。

表302和350以及索引402以关系型格式获取分层结构200的信息。虽然下面将利用涉及分层结构200、表302和350以及索引402的例子来描述本发明的实施例，但是这种实施例只是示范性的。关系型数据库系统存储关于分层的信息的实现方法很多，本技术并不限于任何特定的实现方法。

索引的示范性遍历

可以遍历索引402，以访问分层结构200中的节点，响应基于分层结构200中节点位置的请求。例如，提交由路径“/a/b”识别的节点(即节点2)的子节点的相关的数据请求查询。这种查询可以利用由Nipun Agarwal、Ravi Murthy、Eric Sedlar、Sivasankaran、Chandrasekar和Fei Ge于同日提交的名称为“关系型系统中访问分层数据的运算符”，申请号为第＿＿＿＿号的美国申请专利(代理机构卷号为50277-1975)中描述的运算符表达。为获得子节点，访问与节点“a”对应的项，即项408。通过检测项408的列CHILD IDs中的组合id，确定在索引402中与路径中的下一个节点对应的项。包含了与路径“/a/b”中的下一个节点匹配的子名称的组合id{“b”，r2，R2}识别RowID r2，即项412的RowID。然后，访问项412。项412的CHILD IDs中的组合id是{“d”，，R4}和{“e”，，R5}，它们识别在表302中与作为子节点的节点2相关的行，即行R4和行R5。行R4和R5分别对应分别由路径“a/b/d”和“a/b/f”确定的节点4和节点5。通过这些行的RowID访问这些行，以检索行中被请求的数据。

一个单元中存储多个行ID的益处

索引402的优点在于用于识别某一父节点的子节点的索引项和表302中的行的数据可以位于一个数据块内。数据块是用于存储由数据库管理的数据库数据的最小存储单元，也是可从静态存储器中加载到易失存储器的最低级间隔尺寸(granularity)的数据单元。访问数据块是一种费时的操作，这是因为数据块必须从静态存储器被加载到易失存储器中。通过减少需要执行该过程的数据块的数量，可以获得访问数据块处理的效率的显著提高。因此，存储用于识别某一父节点的子节点的索引项和表302中的行的数据的能力是一个有利的特征，这是因为只需要访问一个数据块以获得该数据。

该特征尤其有利于被称作“路径解析”或者称作“解析路径”的进程。路径解析指用来完成判断路径所确定的一个或多个实体的一组操作。它是任何基于路径访问分层组织的数据的系统所执行的普通而又重要的功能。因此，提高其效率尤为重要。

例如，要解析路径“/a/b”，访问与节点a对应的索引项，即项408。估算项408的CHILD IDs中的组合id，以确定其包括用于识别对应于节点b的索引项r2。从而，该路径识别了一个有效节点，表302中的行R4是路径“/a/b”被解析的数据结构。

如上所述，解析路径“/a/b”需要相对路径中的每一级访问一个索引项和一个数据块，最后一级除外。因此，在使用索引402解析路径过程中访问的数据块的数量与路径中的级的数量成线性比例。

当需要用于识别所有的子节点索引项的RowID可以被存储在一个数据块内时，就存在这种线性关系，对于通常被存储在数据库服务器上的分层组织的数据而言，这很可能是真实的情况。例如，典型的数据库服务器具有大小平均为8k(“千字节”)的数据块，以及RowID平均为16个字节。因此数据块可以存储足够的RowID以识别约500个子节点的项。在绝大多数由数据库服务器表示的分层结构中，对于指定的父节点，不太可能有超过该阈值数的子节点。

索引402的另一个优点在于它被数据库服务器结构化，并被管理为表。这一优点允许利用有力的本地特征并行地访问索引402，该本地特征允许高效地并行访问数据库表。这种特性的示例是行级的并行。在行级并行中，要访问表中的某一行，进程需要仅锁定该行。另一种形式的并行是表级并行，其效率比行级并行低。在表级并行中，要访问表的一行或者其中任何部分，进程必须锁定整张表。一般来说，如果多个并行进程同时访问同一个数据结构，可以提高其执行效率。在行级并行中，如果多个进程访问表中的不同行，它们可以并行访问该表。锁定某一行的进程不会阻碍要求访问另一行的进程。然而，在表级并行中，为了访问表中的某一行，进程必须锁定整个表，从而阻碍了其它要求访问该表中任何行的进程，即使是那些需要访问没有被锁定该表的进程需要或访问的行的进程。

预提交缓存(PRE-COMMIT CACHE)

在数据库系统上执行的事务处理程序改变父-子关系以及表302和350中代表父-子关系的行。一般来说，当事务处理程序改变某一行时，在提交事务之前锁定该行。例如，如果事务处理程序改变了节点1和节点2间的父-子关系，则行354和项408被锁定。行354的锁定阻碍了试图改变节点1和节点2的父-子关系的其它进程。然而，锁定项408的锁定不仅阻碍了试图改变该父-子关系的进程，还阻碍了试图改变其它(即节点1和节点3间的父-子关系)的进程。为改变父-子关系，在父节点级锁定表402上的行，而在父-子关系级的较低级锁定表350上的行。

为减少反映父-子关系变化的表402中行的变化所引起的并行阻碍效应，以及为提高并行性，由事务处理程序改变的行的锁定被推迟，直到事务将要被提交为止。事务处理程序造成的行的改变被记录在“预提交缓存”中。只有当事务将要被提交时，被改变的行才被锁定，从而减少了事务处理程序锁定行的总时间，以及减小了否则将会发生的并行阻碍效应。

遍历分层索引时使用访问控制数据

列AccInfo包含了用于确定用户访问权限的访问控制数据，即，确定单个用户、一组用户或一类用户访问分层结构200中的节点的方式(如果有的话)。对于索引402中的特定项，AccInfo包含了用于确定用户访问某一节点和对应于该节点的行的权限的数据。该数据可以采用以下的形式：明确地指定用户访问权限，指出访问控制数据的源，或者其组合。

根据本发明的实施例，数据库服务器管理和维护访问控制数据，以访问数据库服务器管理的表350和其它表。在此，这些访问控制数据被称作表访问控制数据。一个表的表访问控制数据至少被部分地存储在例如表的一个或多个列中。

存储在AccInfo中的数据反映了(即与其相一致)表350的表访问控制数据。从而，对于特定的项，存储在AccInfo中的访问控制数据指示了这样的用户访问权限，它与该行的表访问控制数据所指定的用户权限一致。例如，如果项408的AccInfo中的数据指示用户对节点1具有只可读不可写的权限，则用于行R1的表访问控制数据指示相同用户对行R1具有只可读不可写的权限。

根据本发明实施例，管理对分层和关系组织的数据的访问控制数据可被实现为如以下专利申请所描述的那样：由Ravi Murthy、Eric Sedlar、Nipun Agarwal、Sam Idicula和Nicolas Montoya于同日提交的名称为“数据库系统中统一访问控制的机制”，并且申请号为＿＿＿＿的美国专利申请(代理机构卷号为50277-1980)。

由AccInfo中的访问控制数据定义的用户访问权限包括节点内容的读权限，节点内容的写入权限，为节点定义用户权限的权限，删除节点的权限，以及遍历节点的权限，并且不受以上限制。遍历节点的权限是指对节点的子节点进行任何类型访问的能力。例如对于节点1，用户具有遍历节点1的权限，但不能读或写其内容。用户可以访问节点1的子节点2和3，但是不能读节点1的内容，即读行R1。

把访问控制数据存储在AccInfo中，将使得在执行涉及到遍历索引402的操作例如路径解析的期间，能够更有效地确定用户访问权限。因为访问控制数据被存储在索引402的项中，索引项在遍历节点期间都被访问，所以不需要从另一个源例如表302中存储的访问控制数据获得访问控制数据，但路径的最终节点除外。例如，要解析路径“/a/b”，访问索引项408而不是项412，该项412把该路径的最终节点2的访问控制信息包含在AccInfo中。相反，该信息可从表302中获得。

路径解析是个很小的操作，它不仅包括定义由路径指定的节点，而且包括决定用户是否具有执行涉及该节点的特定类型操作所需的特定用户权限。AccInfo中的访问控制数据使得这种路径解析实现更为有效。例如，当为用户遍历分层索引402以解析路径“/a/b/c”时，项408被访问。检测AccInfo中的数据以判断用户可以遍历节点1。然后，项412被访问。检测项412的AccInfo中的数据以判断用户不能遍历节点2。从而，用户无法看到节点2的任何子节点，包括路径识别的子节点3。路径解析完成，并且不需要继续遍历索引402。从而，路径解析被执行了，同时不仅避免了访问表350的表访问控制数据，而且避免了完全遍历路径的每个路径单元对应的项。

把访问控制数据存储在分层索引中是一种可以包含访问控制信息的索引类型的例子。其它类型的索引，如B-树型索引，可以包含关于被索引项目的访问控制信息。存储在其它类型索引中的访问控制信息可用于改进涉及遍历索引和访问控制的进程。因此，本发明不只限于把访问控制信息存储在分层索引中。

分层索引的综合

数据库服务器支持的本地索引的优点在于，数据库服务器使用本地索引去执行不需要指定是否使用和如何使用索引的数据库语句。这种能力减轻了用户在指定需要使用索引的操作时表达查询的繁琐工作。例如，数据库服务器接收一个执行查询的请求，其不指定是否或如何使用索引。然后，数据库服务器生成一个执行计划，该计划定义了操作符以及一个执行这些操作符的顺序，其中操作符是执行任务的一组操作的定义。这些操作符包括一个用于访问特定索引的操作符。当生成一个执行计划时，数据库服务器计算影响效率的各种因素。一旦生成执行计划，数据库就执行该计划的操作符，包括用于访问索引的操作符。

当不需要数据库语句指定是否或如何使用索引的情况下数据库服务器自动使用索引执行数据库语句时，索引或其应用被称作“在数据库语言层之下”或者“在SQL层之下”。

为了以数据库命令层之下的方式支持索引，数据库服务器软件可以被编程为按这种方式支持索引。允许这种支持类型的另一种方式是通过使用被称作可扩充索引的机制。可扩充索引的描述见结合于此处以供参考的由Jagannathan Srinivasan、Ravi Murthy、ChinHong、Samuel DeFazio和Anil Nori于1 999年4月6日提交的名称为“可扩充索引(Extensible Indexing)”的第5,893,104号美国专利。可扩充索引使得不具备对索引类型进行支持的内置支持的数据库服务器通过注册由数据库服务器调用的索引类型和索引例程(如对象方法)以使用和支持作为索引类型实例的索引，来扩充其索引能力，以便支持新索引类型。一般来说，索引例程包括创建、删除和修改索引定义的例程(DDL索引例程)，修改现有索引中数据的例程(DML索引例程)，从现有索引中检索数据的例程(查询处理索引例程)，以及被调用以便生成和计算执行计划的历程(查询优化索引例程)。

可扩充索引使得数据库服务器可以自动在数据库语言层之下执行为使用和支持特定索引类型的索引所需的操作。例如，数据库服务器接收到一条撤消或者截短表350的DDL语句。该DDL语句参考表302而不是索引402。当数据库服务器执行该DDL语句时，通过调用和执行DDL索引例程自动地撤消或者截短索引。当数据库服务器接收到一条查询时，它计算并生成一执行计划，同时调用查询优化索引例程参与评定是否和如何使用索引402。一旦生成执行计划，数据库服务器就执行该执行计划，调用所需的查询进程索引例程去执行该执行计划。

为创建索引，用户提交一条创建索引的DDL语句。根据本发明的实施例，分层索引的创建索引语句指定资源表和链接表为参数(argument)。诸如表302这样的资源表包含了如分层结构200这样的分层结构中的(逻辑的、物理的或者两者组合的)节点的内容。如表350这样的链接表将代表父节点的行链接到代表该父节点的子节点的行。数据库服务器为资源表定义一个表对象类型(资源表类型)，为链接表定义一个表对象类型(链接表类型)。分层索引的创建索引DDL命令指定了一个作为资源表类型实例的表和一个作为链接表类型实例的表。链接表类型定义了具有将父节点映射到子节点的节点id的列属性(如表302中的PARENT和CHILD)。资源表类型定义了具有节点id的列属性(如表302中的NODE)。用于创建分层索引的DDL索引例程采用资源表类型和链接表类型的参数(arguments)。

硬件概述

图5是说明实现本发明实施例的计算机系统500的方框图。计算机系统500包括总线502或者其它用于传递信息的通信机构，以及与总线502连接的用于处理信息的处理器504。计算机系统500还包括和总线502连接的用于存储信息和处理器504要运行的指令的主存储器506，例如随机存取存储器(RAM)或者其它动态存储设备。主存储器506还用于在处理器504运行指令期间存储临时变量或者其它中间信息。计算机系统500还包括和总线502连接的用于存储静态信息和处理器504的指令的只读存储器(ROM)508或者其它静态存储设备。存储装置510如磁盘或者光盘被提供，并且与总线502连接用于存储信息和指令。

计算机系统500可以通过总线502连接到用于向计算机用户显示信息的显示器512，如阴极射线管(CRT)显示器。包括字母数字和其它键的输入设备514与总线502连接，用于向处理器504传送信息和指令选择。另外一种类型的用户输入装置是光标控制器516，如鼠标，跟踪球或者光标方向键，用于向处理器504传送方向信息和指令选择以及用于控制光标在显示器512屏幕上的移动。该输入装置通常在两轴上即第一轴(例如x轴)和第二轴(例如y轴)具有两个自由度，使得装置在一个平面上定位。

本发明涉及用于实现这里所描述的技术的计算机系统500的应用。根据本发明的一个实施例，通过计算机系统500执行这些技术，响应处理器504执行主存储器506中的一个多个序列的一个或者多个指令。这种指令可以从另一种计算机可读介质(例如存储器510)被读取到主内存506中。执行主存储器506中包含的指令序列使得处理器504执行这里描述的进程步骤。在另外的实施例中，使用硬连线的(hard-wired)电路取代软件指令或者组合软件指令来实现本发明。因此，本发明的实施例不只限于硬件电路和软件的任何特定组合。

这里使用的术语“计算机可读介质”指任何参与向处理器504提供用于执行的指令的介质。这种介质形式多样，包括但不限于非易失介质、非易失介质和传输介质。非易失介质包括，例如光盘或者磁盘，如存储设备510。易失介质包括动态存储器，例如主存储器506。传输介质包括同轴电缆、铜线和光纤，包括组成总线502的线路。传输介质还可以是如在无线电波和红外数据通信中生成的声波或者光波的形式。

计算机可读介质通常包括，例如，软盘(floppy disk)，弹性磁盘(flexible disk)、硬盘、磁带或者其它任何磁介质、CD-ROM、其它任何光介质、穿孔卡片、纸带、其它任何具有孔图样的物理介质、RAM、PROM、EPROM、FLASH-EPROM、其它任何存储芯片或者卡式磁带，此后描述的载波或者计算机可以读取的其它任何介质。

计算机可读介质的各种形式涉及将一个或多个序列的一条或多条指令传送到处理器504执行。例如，指令最初被到远端计算机的磁盘携带。远端计算机可将指令加载到其动态存储器，并使用调制解调器通过电话线发送指令。计算机系统500的本地调制解调器可以接收电话线上的该数据，并使用红外发射器将数据转换为红外信号。红外探测器可以接收红外信号中携带的数据，并且适当的电路可以将数据传到总线502上。总线502将数据传送到主存储器506，处理器504可以从该主处理器取回并执行指令。主存储器506收到的指令在处理器504执行前或执行后选择性地存储在存储装置510。

计算机系统500还包括和总线502连接的通信接口518。通信接口518提供了与连接到局域网522的网络链路520连接的双向数据通信。例如，通信接口518可以是综合服务数字网(ISDN)卡或者一个提供到对应类型电话线的数据通信连接的调制解调器。作为另一个例子，通信接口518可以是提供到兼容的局域网(LAN)的数据通信连接的LAN网卡。在任何这样的实现中，通信接口518发送和接收传送代表不同类型信息的数字数据流的电、电磁或者光信号。

网络链路520通常通过一个或多个网络向其它数据装置提供数据通信。例如，网络链路520可以通过局域网522提供到主机524或者互连网服务提供商(ISP)526操纵的数据设备的连接。ISP 526又通过现在普遍被称为“互连网”的世界范围分组数据通信网络528提供数据通信服务。局域网522和互连网528均使用传输数字数据流的电、电磁或者光信号。通过不同网络的信号以及在网络链路520上并通过通信接口518的信号将数字数据将传输至和传输出计算机系统500，这是载波传输信息的示范方式。

计算机系统500可以通过网络、网络链路520和通信接口518发送信息和接收数据，包括程序代码。在互连网中，服务器530可能通过互连网528、ISP 526、局域网522和通信接口518传送应用程序所请求的代码。

接收的代码在接收时通过处理器504运行，并/或存储在存储设备510或者其它非易失存储器中，用于以后的执行。这样，计算机系统500可以以载波形式获得应用代码。

在如上所述的说明书中，参照了其特定实施例说明了本发明。然而，显然可在不脱离本发明条件和范围前提下进行修改和改变。因此，说明书和附图仅作为说明而不具有限制意义。