332
S.
Skiadopoulos et al.
Fig. 1. Reference tiles and relations
is in REG*. Notice that region is disconnected and has a hole.
Let us now consider two arbitrary regions and in REG*. Let region be
related to region through a cardinal direction relation (e.g., is north of
Region will be called the reference region (i.e., the region which the relation
refers to) while region will be called the primary region (i.e., the region for
which the relation is introduced). The axes forming the minimum bounding box
of the reference region divide the space into 9 areas which we call tiles (Fig. 1a).
The peripheral tiles correspond to the eight cardinal direction relations south,
southwest, west, northwest, north, northeast, east and southeast. These tiles
will be denoted by and
respectively. The central area corresponds to the region’s minimum bounding
box and is denoted by By definition each one of these tiles includes the
parts of the axes forming it. The union of all 9 tiles is
If a primary region is included (in the set-theoretic sense) in tile of
some reference region (Fig. 1b) then we say that is south of and we write
Similarly, we can define southwest (SW), west (W), northwest (NW),
north (N), northeast (NE), east (E), southeast (SE) and bounding box (B)
relations. If a primary region lies partly in the area and partly in
the area of some reference region (
Fig. 1c) then we say that

is partly
northeast and partly east of and we write N E:E
The general definition of a cardinal direction relation in our framework is as
follows.
Definition 1. A cardinal direction relation is an expression where
(a)

relations of as our basis, we can define the powerset of which contains
relations. Elements of are called disjunctive cardinal direction relations
and can be used to represent not only definite but also indefinite information
about cardinal directions, e.g., { N, W} denotes that region is north or west
of region
Notice that the inverse of a cardinal direction relation R, denoted by inv(R),
is not always a cardinal direction relation but, in general, it is a disjunctive cardi-
nal direction relation. For instance, if S then it is possible that
N E:N:NW
regions and is fully characterized by the pair where and
are cardinal directions such that (a) (b) (c) is a disjunct
of inv and (d) is a disjunct of An algorithm for computing
the inverse relation is discussed in [21]. Moreover, algorithms that calculate the
composition of two cardinal direction relations and the consistency of a set of
cardinal direction constraints are discussed in [20,21,22].
Goyal and Egenhofer [5,6] use direction relation matrices to represent cardi-
nal direction relations. Given a cardinal direction relation the
In general, each multi-tile relation is defined as follows:
B
:
S
:
SW
:
W
:
NW
:
N
:

Computing Cardinal Direction Relations
Typically, in Geographical Information Systems and Spatial Databases, the con-
nected regions in REG are represented using single polygons, while the com-
posite regions in REG* are represented using sets of polygons [18,23]. In this
paper, the edges of polygons are taken in a clockwise order. For instance, in
Fig. 2 region is represented using polygon and re-
gion is represented using polygons and
Notice than using sets of polygons, we can even represent re-
gions with holes. For instance, in Fig. 2 region is represented using
polygons and
Given the polygon representations of a primary region and a reference
region the computation of cardinal direction relations problem lies in the cal-
culation of the cardinal direction relation R, such that R holds. Similarly,
we can define the computation of cardinal direction relations with percentages
problem.
Let us consider a primary region and a reference region According to
Definition 1, in order to calculate the cardinal direction relation between region
and we have to divide the primary region into segments such that each
segment falls exactly into one tile of Furthermore, in order to calculate the
cardinal direction relation with percentages we also have to measure the area of
each segment. Segmenting polygons using bounded boxes is a well-studied topic
of Computational Geometry called polygon clipping [7,10]. A polygon clipping
algorithm can be extended to handle unbounded boxes (such as the tiles of refer-
ence region as well. Since polygon clipping algorithms are very efficient (linear
in the number of polygon edges), someone would be tempted to use them for the
calculation of cardinal direction relations and cardinal direction relations with
percentages. Let us briefly discuss the disadvantages of such an approach.
Let us consider regions and presented in Fig. 3a. Region is formed
by a quadrangle (i.e., a total of 4 edges). To achieve the desired segmentation,
polygon clipping algorithms introduce to new edges [7,10]. After the clipping

from the union of the tiles of
For instance, if and then we have
tile-union and tile-union
Let and be sets of polygons representing
a primary region and a reference region To calculate the cardinal direction
R between the primary region and the reference region we first record the
tiles of region where the points forming the edges of the polygons
fall in. Unfortunately, as the following example presents, this is not enough.
Example 2. Let us consider the region (formed by the single polygon
and the region presented in Fig. 4a. Clearly points and
lie in and respectively, but the relation between
and is B:W:NW:N:NE and not W:NW:NE.
The problem of Example 2 arises because there exist edges of polygon
that expand over three tiles of the reference region For instance,
expands over tiles and In order to handle such situations,
we use the lines forming the minimum bounding box of the reference region to
divide the edges of the polygons representing the primary region and create
new edges such that (a) region does not change and (b) every new edge lies in
exactly one tile. To this end, for every edge AB of region we compute the set of
intersection points of AB with the lines forming box We use the intersection
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Computing and Handling Cardinal Direction Information
337
Fig. 4. Illustration of Examples 2 and 3
points of to divide AB into a number of segments Each
segment lies in exactly one tile of and the union of all tiles is
AB. Thus, we can safely replace edge AB with without affecting
region Finally, to compute the cardinal direction between regions and we
only have to record the tile of where each new segment lies. Choosing a single
point from each segment is sufficient for this purpose; we choose to pick the

OMPUTE
-CDR is where (respectively is the total number of
edges of all polygons in (respectively
Summarizing this section, we can use Algorithm COMPUTE-CDR to compute
the cardinal direction relation between two sets of polygons representing two
regions and in REG*. The following section considers the case of cardinal
direction relations with percentages.
3.2
Cardinal Direction Relations with Percentages
In order to compute cardinal direction relations with percentages, we have to
calculate the area of the primary region that falls in each tile of the reference
region. A naive way for this task is to segment the polygons that form the primary
region so that every polygon lies in exactly one tile of the reference region. Then,
for each tile of the reference region we find the polygons of the primary region
that lie inside it and compute their area. In this section, we will propose an
alternative method that is based on Algorithm C
OMPUTE-CDR. This method
simply computes the area between the edges of the polygons that represent
the primary region and an appropriate reference line without segmenting these
polygons.
We will now present a method to compute the area between a line and an
edge. Then, we will see how we can extend this method to compute the area of
a polygon. We will first need the following definition.
Definition 3. Let AB be an edge and be a line. We say that does not cross
AB if and only if one of the following holds: (a) AB and do not intersect, (b)
AB and intersect only at point A or B, or (c) AB completely lies on
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Computing and Handling Cardinal Direction Information
339
Fig. 6. Lines not crossing AB

also the discussion at the beginning of Section 3). In the rest of this section, we
will present a method that utilizes expressions and and does not require
polygon clipping.
Example 4. Let us consider polygon and line pre-
sented in Fig. 8d. The area of polygon can be calculated using formula
All the intermediate
expressions
are presented as the gray areas
of Fig. 8a-d respectively.
We will use expressions and to compute the percentage of the area of
the primary region that falls in each tile of the reference region. Let us consider
region presented Fig. 9. Region is formed by polygons and
Similarly to Algorithm COMPUTE-CDR, to compute the cardinal
direction relation with percentages of with we first use the to divide
the edges of region Let and be the lines forming
These lines divide the edges of polygons and
as shown in Fig. 9.
Let us now compute the area of that lies in the NW tile of (i.e.,
Notice that area To com-
pute the area of polygon it is convenient to use as a reference line
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Computing and Handling Cardinal Direction Information
341
Fig. 9
.
Computing cardinal direction relations with percentages
Doing so, we do not have to compute edges and because
and hold and thus the area we are looking for
can be calculated with the following formula:
In other words, to compute the area of that lies in

The above described method is summarized in Algorithm COMPUTE-CDR-CDR%
presented in Fig. 10. The following theorem captures the correctness of Algo-
rithm C
OMPUTE-CDR% and measures its complexity.
Theorem 2. Algorithm COMPUTE-CDR% is correct, i.e., it returns the cardi-
nal direction relation with percentages between two regions and in REG* that
are represented using two sets of polygons and respectively. The running
time of Algorithm COMPUTE-CDR% is where (respectively is
the total number of edges of all polygons in (respectively
In the following section, we will present an actual system, CARDIRECT,
that incorporates and implements Algorithms COMPUTE-CDR and COMPUTE-
CDR%.
4
A Tool for the Manipulation of Cardinal Direction
Information
In this section, we will present a tool that implements the aforementioned reason-
ing tasks for the computation of cardinal direction relationships among regions.
The tool, CARDIRECT, has been implemented in C++ over the Microsoft Vi-
sual Studio toolkit. Using CARDIRECT, the user can define regions of interest
over some underlying image (e.g., a map), compute their relationships (with and
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Computing and Handling Cardinal Direction Information
343
Fig. 10. Algorithm COMPUTE-CDR%
without percentages) and pose queries. The tool implements an XML interface,
through which the user can import and export the configuration he constructs
(i.e., the underlying image and the sets of polygons that form the regions); the
XML description of the configuration is also employed for querying purposes.
The XML description of the exported scenarios is quite simple: A configura-
tion (

be a finite set of thematic attributes for the regions of REG* (e.g., the color of
each region) and a function, practically relating each of
the regions with a value over the domain of C (e.g., the fact that the Spartan
Alliance is colored red).
A query condition over variables is a conjunction the following
types of formulae where is a
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
Computing and Handling Cardinal Direction Information
345
Fig. 12.
Using CARDIRECT to extract cardinal direction relations
region of the configuration, is a value of a thematic attribute and
is a (possibly disjunctive) cardinal direction relation. A query over
variables is a formula of the form
where is a query condition.
Intuitively, the query returns a set of regions in the configuration of an image
that satisfy the query condition, which can take the form of: (a) a cardinal
direction constraint between the query variables (e.g., B:SE:S (b) a
restriction in the thematic attributes of a variable (e.g., and
(c) direct reference of a particular region (e.g.,
For instance, for the configuration of Fig. 11 we can pose the following query:
“Find all regions of the Athenean Alliance which are surrounded by a region in
the Spartan Alliance”. This query can be expressed as follows:
5
Conclusions and Future Work
In this paper, we have addressed the problem of efficiently computing the car-
dinal direction relations between regions that are composed of sets of polygons
(a) by presenting two linear algorithms for this task, and (b) by explaining
their incorporation into an actual system. These algorithms take as inputs two
sets of polygons representing two regions respectively. The first of the proposed

underlying model with extra thematic information and the enrichment of the
employed query language on the basis of this combination. Finally, a long term
goal would be the integration of C
ARDIRECT with image segmentation software,
which would provide a complete environment for the management of image con-
figurations.
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
E. Clementini, P. Di Fellice, and G. Califano. Composite Regions in Topological
Queries. Information Systems, 7:759–594, 1995.
M.J. Egenhofer. Reasoning about Binary Topological Relationships. In Proceedings
of SSD’91, pages 143–160, 1991.
A.U. Frank. Qualitative Spatial Reasoning about Distances and Directions in
Geographic Space. Journal of Visual Languages and Computing, 3:343–371, 1992.
A.U. Frank. Qualitative Spatial Reasoning: Cardinal Directions as an Example.
International Journal of GIS, 10(3):269–290, 1996.
R. Goyal and M.J. Egenhofer. The Direction-Relation Matrix: A Representation
for Directions Relations Between Extended Spatial Objects. In the annual assem-
bly and the summer retreat of University Consortium for Geographic Information
Systems Science, June 1997.
R. Goyal and M.J. Egenhofer. Cardinal Directions Between Extended Spatial
Objects. IEEE Transactions on Data and Knowledge Engineering, (in press), 2000.

17.
18.
19.
20.
21.
22.
23.
D.J. Peuquet and Z. Ci-Xiang. An Algorithm to Determine the Directional Rela-
tionship Between Arbitrarily-Shaped Polygons in the Plane. Pattern Recognition,
20(1):65–74, 1987.
F. Preparata and M. Shamos. Computational Geometry: An Introduction. Springer
Verlag, 1985.
J. Renz and B. Nebel. On the Complexity of Qualitative Spatial Reasoning: A
Maximal Tractable Fragment of the Region Connection Calculus. Artificial Intel-
ligence, 1-2:95–149, 1999.
P. Rigaux, M. Scholl, and A. Voisard. Spatial Data Bases. Morgan Kaufman, 2001.
S. Skiadopoulos, C. Giannoukos, P. Vassiliadis, T. Sellis, and M. Koubarakis. Com-
puting and Handling Cardinal Direction Information (Extended Report). Techni-
cal Report TR-2003-5, National Technical University of Athens, 2003. Available
at
http://www.dblab.ece.ntua.gr/publications.
S. Skiadopoulos and M. Koubarakis. Composing Cardinal Directions Relations. In
Proceedings of the 7th International Symposium on Spatial and Temporal Databases
(SSTD’01), volume 2121 of LNCS, pages 299–317. Springer, July 2001.
S. Skiadopoulos and M. Koubarakis. Qualitative Spatial Reasoning with Cardinal
Directions. In Proceedings of the 7th International Conference on Principles and
Practice of Constraint Programming (CP’02), volume 2470 of LNCS, pages 341–
355. Springer, September 2002.
S. Skiadopoulos and M. Koubarakis. Composing Cardinal Direction Relations.
Artificial Intelligence, 152(2):143–171, 2004.

both existing XML Schema documents and the XML Schema recommendation.
1
Introduction
XML is becoming an increasingly popular language for documents and data. XML
can be approached from two quite separate orientations: a document-centered
orientation (e.g., HTML) and a data-centered orientation (e.g., relational and object-
oriented databases). Schemas are important in both orientations. A schema defines the
building blocks of an XML document, such as the types of elements and attributes.
An XML document can be validated against a schema to ensure that the document
conforms to the formatting rules for an XML document (is well-formed) and to the
types, elements, and attributes defined in the schema (is valid). A schema also serves
as a valuable guide for querying and updating an XML document or database. For
instance, to correctly construct a query, e.g., in XQuery, a user will (usually) consult
the schema rather than the data. Finally, a schema can be helpful in query
optimization, e.g., in constructing a path index [24].
Several schema languages have been proposed for XML [22]. From among these
languages, XML Schema is the most widely used. The syntax and semantics of XML
Schema 1.0 are W3C recommendations [35, 36].
Time-varying data naturally arises in both document-centered and data-centered
orientations. Consider the following wide-ranging scenarios. In a university, students
take various courses in different semesters. At a company, job positions and salaries
change. At a warehouse, inventories evolve as deliveries are made and good are
E. Bertino et al. (Eds.): EDBT 2004, LNCS 2992, pp. 348–365, 2004.
© Springer-Verlag Berlin Heidelberg 2004
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
A Tale of Two Schemas: Creating a Temporal XML Schema
349
shipped. In a hospital, drug treatment regimes are adjusted. And finally at a bank,
account balances are in flux. In each scenario, querying the current state is important,
e.g., “how much is in my account right now”, but it also often useful to know how the

representation while preserving the semantics of the data. has a suite of
auxiliary tools to manage time-varying documents and schemas. There are tools to
convert a time-varying document from one physical representation to a different
representation, to extract a time slice from that document (yielding a conventional
static XML document), and to create a time-varying document from a sequence of
static documents, in whatever representation the user specifies.
As mentioned, reuses rather than extends XML Schema. is
consistent and compatible with both XML Schema and the XML data model. In
a temporal validator augments a conventional validator to more
comprehensively check the validity constraints of a document, especially temporal
constraints that cannot be checked by a conventional XML Schema validator. We
describe a means of validating temporal documents that ensures the desirable property
of snapshot validation subsumption. We show elsewhere how a temporal document
can be smaller and faster to validate than the associated XML snapshots [12].
1
We embrace both the document and data centric orientations of XML and will use the terms
“document” and “database” interchangeably.
2
Three-level architectures are a common architecture in both databases [33] and spatio-
temporal conceptual modeling [21].
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
350
F. Currim et al.
While this paper concerns temporal XML Schema, we feel that the general
approach of separate temporal and physical annotations is applicable to other data
models, such as UML [28]. The contribution of this paper is two-fold: (1) introducing
a three-level approach for logical data models and (2) showing in detail how this
approach works for XML Schema in particular, specifically concerning a theoretical
definition of snapshot validation subsumption for XML, validation of time-varying
XML documents, and implications for tools operating on realistic XML schemas and

athletes participating in the 2002 Winter Olympics in Salt Lake City, USA was added
on 2002-01-01. On 2002-03-01 the document was further edited to record the medal
winners. Finally, a small correction was made on 2002-07-01.
To depict some of the changes to the XML in the document, we focus on
information about the Norwegian skier Kjetil Andre Aamodt. On 2002-01-01 it was
known that Kjetil would participate in the games and the information shown in Fig. 1
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.
A Tale of Two Schemas: Creating a Temporal XML Schema
351
was
added
to
winter.xml.
Kjetil
won a
medal;
so on
2002-03-01
the
fragment
was
revised to that shown in Fig. 2. The edit on 2002-03-01 incorrectly recorded that
Kjetil won a silver medal in the Men’s Combined; Kjetil won a gold medal. Fig. 3
shows the correct medal information.
Fig. 2. Kjetil won a medal, as of 2002-03-01
Fig. 3
.
Medal data is corrected on 2002-07-01
A time-varying document records a version history, which consists of the
information in each version, along with timestamps indicating the lifetime of that

rs
”
namespace
to
distinguish
it
from
any
<timestamp>
elements already in the document. This namespace will be discussed in
more detail in Sections 0 and 0.
Fig.
1. A
fragment
of
winter.xml
on
2002-01-01
Please purchase PDF Split-Merge on www.verypdf.com to remove this watermark.