head	1.1;
access;
symbols;
locks; strict;
comment	@# @;


1.1
date	93.10.01.22.05.53;	author aoki;	state Exp;
branches;
next	;


desc
@@


1.1
log
@Initial revision
@
text
@.sh 1 "INTRODUCTION"
.pp
Relational database management systems are widely available in the
commercial market.
Currently available systems run on a variety of hardware, ranging from
DEC minicomputers (e.g., Informix, Oracle, Unify) to IBM mainframes
(e.g., Adabas, Datacom/DB, DB2, IDMS/R).
These systems have been successful because of the merits of 
the relational model, as first illustrated by
two research prototypes, INGRES [STON76]
and SYSTEM-R [ASTR76].
INGRES and SYSTEM-R not only illustrated the feasibility of
the relational model, but their respective query languages,
QUEL [HELD75b] and SQL [CHAM76], also
showed that it is possible to ask queries without explicitly
specifying access paths.
The ability to support these non-procedural query languages is a result of
sophisticated query optimization algorithms.
INGRES introduced a technique known as query decomposition [WONG76],
while SYSTEM-R employed an exhaustive search algorithm [SELI79].
Largely due to the success of these algorithms, relational systems were made
efficient.
Therefore, coupled with the simplicity and uniformity of the 
relational model, it
is not surprising that relational databases have established a
formidable presence in the commercial market.
.pp
The relational model, however, has been criticized for its impoverished
semantics [KENT79], [ZANI83] and inability to provide strong support
for non-business applications [HASK82].
In recent years, researchers have been investigating the possibility of
extending query languages in relational systems to support new application
areas as well as better semantics.
Examples include:
.ip "\(bu"
a proposal to support abstract data types (ADTs) and operators
in INGRES to improve the semantics of applications [FOGG82], [ONG82]
.ip "\(bu" 
a new language, QUEL*, to support the transitive
closure operations required in artificial intelligence applications [KUNG84]
.ip "\(bu"
a proposal to support QUEL as a data type
to increase the data modeling power of relational systems [STON84], [STON85b]
.ip "\(bu"
a proposal to support rules and triggers in a relational system to
provide inference and forward chaining needed in 
expert system applications [STON85a].
.lp
.pp
The ideas behind these proposals are being incorporated into POSTGRES
(\*(lqPOSTinGRES\*(rq),
a next-generation relational database system being built at
the University of California, Berkeley [STON86b].
Providing better support for engineering design and artificial intelligence
applications are among the goals of POSTGRES.
To meet these goals, POSTGRES will support extendible and user-defined
access methods [STON86a] as well as abstract data types, transitive
closure queries, procedural data fields, triggers, and rules.
The query language for the system will be called \*(lqPOSTQUEL.\*(rq
.pp
POSTGRES is still in its preliminary implementation phase.
However, a query optimizer for the system has been built.
Although the basic optimization algorithm is modeled after the SYSTEM-R
approach, there are many other issues that the optimizer must
contend with given the novel features of POSTGRES.
Section 2 will introduce these features.
Section 3 will then discuss design decisions that were made in formulating 
optimization algorithms.
Section 4 will discuss implementation decisions made, and finally
section 5 will evaluate the performance of the POSTGRES optimizer by comparing
it with the query optimizer of another relational system.
@