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