The inability of existing nonprocedural query languages in expressing
recursion queries, i.e., the queries requesting data according to a
specific transitive ordering among the tuples of relations (e.g. the
managerial structrue of a company), has made it necessary to enhance the
expressive power of this type of language. This dissertation describes a
language, called the Extended Relational Calculus (ERC), which is an
extension of the facilities of Codd's relational calculus to accommodate
various needs of database applications. Through the use of tuple-set
variables, the calculus ERC has the expressive power of a second-order
predicate calculus. Moreover, it is augmented with ordered tuple-set
facilities so that recursion queries can be formulated. The use of
mathematical quantifiers "for all" (A and "there exist" (E) in the
relational calculus makes its query expression hard to read (understand)
and formulate by non-mathematicians. The proposed calculus, like the query
languages QUEL, SEQUEL 2, and Query-By-Example, is incorporated with
functions and set-theoretic facilities in order to free the use of
mathematical quantifiers. The use of these functions and facilities makes
ERC compatible in its constructs with existing nonprocedural, relational
query languages. The features described above allow ERC to be used as
powerful basis for the design and evaluation of other query languages.
This dissertation, secondly, addresses the problem of how to evaluate ERC
queries efficiently. An algorithm is developed for selecting one access
plan with minimal expected cost from a set of possible access plans (which
are used for evaluating an n-variable query.) Also, an algorithm for
evaluating recursion queries is developed. These two algorithms derive the
following two algorithms:one for evaluating simple queries, i.e., queries
not involving any subquery in their expressions, and the other for
evaluating non-simple queries. These algorithms can serve as the
facilities for efficiently evaluating ERC queries in any arbitrary degree
of complexity. This disseration finally addresses the development of a
Set-Structured Data Language (SSDL) founded on ERC, as well as the use of
ERC as a common language for supporting a unified view of the three major
data models namely:the relational, the hierarchical, and the network
models.
The main contributions of this work are in the following:
(1) The results of the work eliminate the reliance on the use of either a
host language or the procedural facilities embedded in the query language
itself for responding to recursion queries, because a nonprocedural,
relational query language can be added with ordered tuple-set facilities
to express this type of query.
(2) THis work introduces the high-level, noprocedural relational query
language ERC which can provide a powerful and convenient means for casual
users to retrieve data from a database, especially when a recursion query
is involved.
(3) This work gives an example language SSDL-- which is founded on the
language ERC and has facilities to support the query, manipulation,
definition, and control of data-- to demonstrate that ERC can be used as a
basis for the design and evaluation of other query languages.
(4) The algorithms developed for query evaluation provide a systematic
approach to the selection and execution of access plans associated with
ERC queries having any arbitrary degree of complexity.
(5) This work demonstrates that ERC can be used as a common language that
can support a unified view of the three major data models and therefore
can be used as a basis for the design of any nonprocedural data language.
當前非程序性詢訊語言無法表達重現型之詢訊，因此如何提高該詢訊語言之表達 能力
是為必要之研究。本論文將柯德氏關係符號算學加以擴展修改成為“擴充關係符 號算
學”（簡稱擴充關係算學）。橫列集變數之使用，使本算學具有二次敘述算學 之表達
能力，而有序橫列集之應用，亦使重現型之詢訊得以表達。柯德氏關係符號算學 採用
全稱量詞與存在量詞，致詢訊句通常不易為一般人所使用。因此，本算學去除數 學量
詞改採函數及集合理論，使本算學之語言架構得與一般高階詢訊語言匹配。綜有 上述
各項特點，本算學可作為一般詢訊語言設計及評估之基礎。
為達實際運用之目的，本研究建有一組計算法，處理擴充關係算學之一般及重現 型詢
詣句，尋求最佳路徑獲取所需資料。另根據擴充關係算學發展出一集合結構資料 語言
，並論及如何以擴充關係算學作為共通語言，應用於關係模式、層次模式、及網 狀模
式三種主要資料庫系統。
本研究主要貢獻列陳如次：
1.使一般詢訊語言毋需應用主程式語言或其本身之程序性功能，回應重現型之詢 訊。
2.提出一高階、非程序性之關係語言，方便一般使用者尋取資料庫資料。尤其涉 及重
現型詢訊時，特見其功效。
3.提出資料庫語言設計實例，顯示擴充關係算學適用於詢訊語言之設計與評估。
4.提出一套有系統之方法，處理擴充關係算學詢訊句，俾能有效地尋取所需資料 。
5.以實例說明擴充關係算學可作為共通語言，應用於三種主要資料模式。本成果 顯示
任意非程序性資料語言之設計可以擴充關係算學作為基礎。