primitive if it is simple (Preparata et al 1985). A
primitive polygon may contain holes which are also
simple polygons. Examples of primitive and non-
primitive lines and polygons are shown in Figure 1.
(a)
(b)
Figure 1. (a) Primitive lines and polygons.
(b) Non-primitive lines and polygons.
Non-primitive objects can be decomposed into a set
of primitive objects.
To efficiently handle spatial objects in spatial
databases, spatial data types are used. A spatial data
type can be viewed as a data structure for storing
spatial data of objects. Each instance of the spatial
data types is a specific object which is uniquely
identified by its identifier. Operators upon the data
types are defined to alter or retrieve some
information from the structure. Spatial data types
can be either system-defined or user-defined.
The semantics of spatial data types can be described
using set and binary relation concepts (Stanat et al
1977). The structure of the data type POINT is a pair
<p.q >, where p and q are real numbers representing
coordinates.
The data type POINTSET is defined as a countable set
of points (pop1,..Pn-1).
The data type LINESEGMENT is a pair <pspe>,
where ps, pe represent the start and end points of a
line segment.
The data type LINE is defined as
< POINTSET, R >
where R is a binary relation on POINTSET
representing a set of line segments connected to
form a primitive line.
The data type LINESET is a set of lines ( I0, I1,...Ik-1 ).
The data type POLYGON is defined by
274
«lo, Lh »
where lo is a simply closed line representing the
outer boundary and Lh is a set of simply closed lines
representing holes of a primitive polygon.
Spatial data types can be used in a way similar to
other data types such as INTEGER, REAL, TEXT. For
example, relations can be defined by spatial data
types in an extended relational database
management system (ERDBMS) (Huang et al 1992).
These relations become spatial because they contain
spatial objects. Since each object in the database is
uniquely identified, columns defined by spatial data
types can be used as a key to the relations.
Generally speaking, spatial objects are stored
independently in tuples in the spatial relations.
Relationships between objects are not explicitly
described. Spatial relationships, however, are
detected by spatial operators defined in the spatial
query language.
Some of the fundamental functions and operators
needed in the spatial query language will be
discussed in the following sections.
3. Functions on spatial data types
Based on the structures of spatial data types, a
number of necessary functions can be defined
(Svensson et al 1991). Some extract subsets of data or
components of objects, such as extracting coordinates
of a point or the outer boundary of a polygon. Some
compute new data from the existing data set of an
object instance, such as the length of a line. This
section introduces some functions which are used in
the following discussions.
XCOORD(p) and YCOORD(p) are functions to extract
values of x,y coordinates of point p.p can be a
specific identifier or the name of a relation column
defined by the data type POINT.
SP(I) and EP(l) return the start and end points of line
l.
LENGTH(]) returns a real number representing the
length of line /.
AREA(pg ) returns a real number representing the
area of polygon pg.
BOUNDARY (yg ) returns a closed line representing
the boundary of polygon pg.
New functions can be built from compositions of the
functions or combinations of the functions by logical
operators.
For example, the function
PERIMETER (pg) =
LENGTH(BOUNDARY(pg))
com
func
retu:
a clo
4. To
Topx
are
betw
(Arn
cont:
total
betw
By d
and
topol
be ne
topol
objec
In s
topol
name
OVE]
two
EQU.
Table
topo!
relati
DISK
MEE:
EQU.
CON
COV|
OVEI
Visua
two p
5. Tof
Spati:
relati
they 1
meet
the c
polyg
primi
primit
a non