用於訪問關係型資料庫系統中的分層數據的高效索引結構的製作方法
2023-05-14 19:45:41 2
專利名稱：用於訪問關係型資料庫系統中的分層數據的高效索引結構的製作方法
技術領域：
本發明涉及關係型資料庫系統，更具體而言是涉及在關係型數據系統中對分層數據進行索引的技術。
背景技術：
人們往往將信息按類別組織。信息被組織的類別是通常按照某種形式的層次相對彼此被組織的信息自身。例如，個體動物屬於種，種屬於屬，屬屬於科，科屬於目，目屬於綱。
隨著計算機系統的出現，已經開發出的用於存儲電子信息的技術，在很大程度上反映了人們對這種分層組織的需求。例如，傳統計算機文件系統通常利用基於分層組織的原理實現。具體是，一個典型的文件系統具有分層排列的目錄，以及存儲在這些目錄中的文檔。理想地，目錄間的分層關係反映了目錄被賦予的含意之間的直觀關係。類似地，理想情況是每個文檔基於文檔內容與文檔所存儲的目錄被賦予的含意之間的某種直觀關係被存儲在目錄中。
圖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可以以載波形式獲得應用代碼。
在如上所述的說明書中，參照了其特定實施例說明了本發明。然而，顯然可在不脫離本發明條件和範圍前提下進行修改和改變。因此，說明書和附圖僅作為說明而不具有限制意義。
權利要求
1.一種具有索引的計算機可讀介質，其中所述索引對包括一個或多個欄位的表進行索引；所述索引基於與所述的一個或多個欄位至少之一相關聯的關鍵字值進行排列和排序；以及所述索引包括多個索引項，其中所述索引項的每一項映射到所述表中的至少一個對應行，並且包含第一訪問控制數據，這不在所述關鍵字值中反映出來，所述第一訪問控制數據定義了訪問所述至少一個對應行的用戶訪問權限。
2.根據權利要求1所述的計算機可讀介質，其中所述表包含與分層結構中的節點相關聯的行；第二訪問控制數據定義用於訪問所述行的用戶訪問權限；以及所述第一訪問控制數據反映由所述第二訪問控制數據定義的用戶訪問權限。
3.根據權利要求1所述的計算機可讀介質，其中所述多個索引項與分層結構中的節點相關聯；以及其中所述第一訪問控制數據表明一個或多個用戶具有遍歷一個或多個所述節點的用戶訪問權限。
4.一種用於解析具有路徑單元序列的路徑名的方法，包括以下步驟訪問索引中與所述路徑單元序列中特定路徑單元相對應的第一項；以及根據所述第一項中的訪問控制數據判斷用戶是否可以以特定方式訪問與所述特定路徑單元相關聯的第一項目。
5.根據權利要求4所述的方法，其中至少一個路徑單元緊接所述序列中的所述特定路徑單元；以及所述步驟還包括只有當所述用戶可以以所述特定方式訪問所述第一項目，才試圖訪問所述索引中與所述至少一個路徑單元對應的項。
6.根據權利要求4所述的方法，其中所述第一項目是包含了與分層結構中節點對應的行的表中的一行。
7.根據權利要求4所述的方法，其中項目對應於分層結構中的節點，並且所述的第一項目對應於所述分層結構中的特定節點；以及其中判斷用戶是否可以訪問第一項目的步驟包括判斷用戶是否被允許訪問所述特定節點的任何子節點。
8.一種訪問由資料庫伺服器管理的信息的方法，包括以下步驟在資料庫伺服器處接收符合所述資料庫伺服器支持的資料庫語言的語句，其中所述語句指定涉及表的操作；其中所述表包括與分層索引描述的分層結構相關聯的行；其中所述語句不參考所述分層索引；以及使用所述分層索引執行所述語句。
9.根據權利要求8所述的方法，其中所述資料庫語句指定對所述表的撤消操作；以及使用所述分層索引的步驟包括對所述分層索引執行所述的撤消操作。
10.根據權利要求8所述的方法，其中所述資料庫語句指定對所述表的截短操作；以及使用所述分層索引的所述步驟包括對所述分層索引執行所述的截短操作。
11.根據權利要求9所述的方法，其中所述步驟還包括生成執行所述語句的執行計劃，所述執行計劃包括操作符，所述操作符定義使用所述分層索引的操作。
12.一種攜帶一個或多個序列的用於解析具有一序列路徑單元的路徑名的指令的計算機可讀介質，其中一個或多個處理器執行的一個或多個序列的指令使得所述一個或多個處理器執行以下步驟訪問索引中的與所述路徑單元序列中特定路徑單元對應的第一項；以及根據所述第一項中的訪問控制數據判斷用戶是否可以以特定方式訪問與所述的特定路徑單元相關聯的第一項目。
13.根據權利要求12所述的計算機讀取介質，其中至少一個路徑單元緊接所述序列中的所述特定路徑單元；以及所述步驟還包括只有當所述用戶可以以所述特定方式訪問所述第一項目，才試圖訪問所述索引中與所述至少一個路徑單元對應的項。
14.根據權利要求12所述的計算機可讀介質，其中所述的第一項目是包含與分層結構中節點對應的行的表中的一行。
15.根據權利要求12所述的計算機可讀介質，其中項目對應分層結構中的節點，並且所述第一項目對應所述分層結構中的特定節點；以及其中判斷用戶是否可以訪問第一項目的步驟包括判斷所述用戶是否被允許訪問所述特定節點的任何子節點。
16.一種攜帶一個或多個序列的用於訪問由資料庫伺服器管理的信息的指令的計算機可讀介質，其中通過一個或多個處理器執行一個或多個序列的指令，使得所述一個或多個處理器執行以下步驟在資料庫伺服器處接收符合資料庫伺服器支持的資料庫語言的語句，其中所述語句指定涉及表的操作；其中所述表包括與分層索引描述的分層結構相關聯的行；其中所述語句不參考所述分層索引；以及使用所述分層索引執行所述語句。
17.根據權利要求16所述的計算機可讀介質，其中所述資料庫語句指定對所述表的撤消操作；以及使用所述分層索引的步驟包括對所述的分層索引執行所述撤消操作。
18.根據權利要求16所述的計算機可讀介質，其中所述資料庫語句指定對所述表的截短操作；以及使用所述分層索引的步驟包括對所述分層索引執行所述的截短操作。
19.根據權利要求17所述的計算機可讀介質，其中所述步驟還包括生成執行所述語句的執行計劃，所述的執行計劃包括操作符，所述操作符定義使用所述分層索引的操作。
全文摘要
本發明描述了一種分層索引，該分層索引獲取由關係型資料庫系統仿效的分層結構的分層關係。利用包括用作分層索引項的行的資料庫表實現分層索引。另一個表的行與分層結構中的節點相關。分層索引中的每項都映射到與分層結構中的一個節點對應的行。分層中的節點可以是具有一個或多個子節點的父節點。在這種情況下，分層索引中的對應項包括用於識別索引中其它項的標識符，其中其它項對應於與父節點的子節點相關的行。
文檔編號G06F17/30GK1561496SQ02819168
公開日2005年1月5日 申請日期2002年9月26日 優先權日2001年9月28日
發明者尼馬·賈拉利, 埃裡克·塞德拉, 尼普恩·阿加瓦爾, 拉維·默西 申請人:甲骨文國際公司