Lecture Notes in Computer Science:

Page 1

An Implementation of Spatial XQuery Component for

Location-Based Applications

Soon-Young Park, Sang Bong Yoo, and Hae-Young Bae

Dept. of Computer Science and Information Engineering, Inha University

sunny@dblab.inha.ac.kr

Abstract. In this paper1 Geography Markup Language (GML) has been extended

for location-based applications. And in order to handle effectively the extension, a

Spatial XQuery language and its processing component has designed. Because our

work is based on a spatial database system, the Spatial XQuery statements are first

translated into Spatial SQL statements. By working on an existing spatial database

system, we can use of the existing functions of database systems such as query op-

timization, spatial indexes, concurrency control mechanism, and recovery scheme.

Translation of the Spatial XQuery into SQL has been explained using examples.

Because the results from the spatial database system are in the form of tables, we

need to translate again the results into spatial XML statements. A working exam-

ple of the proposed system as an Emergency Support System is also presented.

Prospected application areas of the proposed system are almost location-based sys-

tems, ubiquitous systems in mobile environments.

1. Introduction

As the uses of mobile and location-based applications are popularized and extended

recently, requirements to geographic information systems also have been changed. Ge-

ography Markup Language (GML) [14] is the active standard for exchanging spatial

data on the Internet and mobile devices, but it is limited only for text and graphic data of

static geographic information. Location-based Systems (LBS) can provide more attrac-

tive services when they utilize tracking information of moving objects. It would be very

convenient if a car navigation system provide voice mode as well as the basic screen

mode. In this paper, S-XML (Spatial-eXtensible Markup Language), which extends the

GML by adding three schemas: voice schema, tracking schema, and POI schema has

proposed. The characteristics of each schema can be summarized as follows:

- Voice Schema: A grammar of voice information of geographic direction has

been designed. The syntax of voice information has been designed as simple as

possible because it should be brief and concise. The direction information will

enable the user to move to the destination through the shortest path.

1 This research was supported by University IT Research Project in Korea.

Page 2

- Tracking Schema: This schema models the dynamic status of moving objects.

It includes data type of moving objects, specific coordinate information and the

time when the object pass the point, direction information, and velocity infor-

mation.

- POI Schema: This schema has been designed to provide the user with the posi-

tion and path information to interesting objects such as public offices, schools,

hospitals, restaurants, and gas stations. It can refer the voice schema in order to

provide voice mode interface.

In order to handle the S-XML data effectively, a spatial XQuery language has been

designed. In this research, the geographic data are stored in a spatial database manage-

ment system and the spatial XQuery constructs submitted by users are translated into

spatial SQL and evaluated by the spatial database management system. The spatial data-

base management system supports the query optimization methods and concurrency

control for processing multiple queries simultaneously. The spatial XQuery supports

basic operations (e.g., =, <, and >), spatial operations (e.g., sp_disjoint, sp_intersects,

and sp_contains), and operations for moving objects (e.g., mo_after, mo_before,

mo_first, and mo_last). With these spatial operations and the operations for moving

objects, the spatial XQuery can be effectively used on LBS (Location-Based Service)

platforms. The spatial XQuery also supports the VOICE tag, using which the direction

information can be provided by voice mode interface.

This paper is organized as follows. Section 2 summarizes the various approaches to

handle XML queries. Section 3 presents the information model of S-XML and the syn-

tax and semantics of spatial XQuery. Section 4 describes the overall processing of spa-

tial XQuery. Spatial XQueries are first translated into equivalent spatial SQL statements

and then evaluated by database system with spatial operation. Section 5 provides a

working scenario of using the spatial XQuery. In this scenario, the user first locates the

nearest hospital from an accident and the driver of an ambulance from the hospital gets

the direction to the accident site when the car approaches crossroads. Section 6 summa-

rizes the contributions of the paper.

2. Related Work

Two research groups have contributed to the developments of XML query languages.

First, the document research group has their experience in designing languages and tools

for processing structured documents. For example, XQuery uses XPath in order to sup-

port operations on document path expressions. Second, the database research group has

their experience in designing query language and processors for data-oriented computa-

tions. XQuery also uses the basic structure of SQL language for relational databases.

Consequently, there are two major approaches to XML data management and query

evaluation, i.e., database approaches and native approaches.

In database approaches, XML documents are stored in preexisting database systems

[2, 8, 16] and the XML queries are translated into SQL or other database languages [10,

19]. The problems of updating XML data stored in tables [18] and indexing XML data

[7, 13] have also been presented. Prototypes such as SilkRoute [9] and XPERANTO [4]

Page 3

have proposed algorithms for efficiently encoding relational data as XML documents.

Commercial products such as SQL Server, Oracle, and DB2 also support encoding rela-

tional data as XML documents. XQuery has been designed based on Quilt[5], which is

based on other XML query languages such as XML-QL, XPath, and XQL.

Native approaches design new management systems for XML data. Some examples

of native approaches to XML document processing include Natix [11], Tamino [17], and

TIMBER [12]. Most work on native approaches has focused on efficient evaluation of

XPath expressions using structural join [1] and holistic join [3], and optimal ordering of

structural joins for pattern matching [21]. TIMBER extensively uses structural joins for

pattern match, as does the Niagara system [14]. A structure called generalized tree pat-

tern (GPT) is proposed for concise representation of a whole XQuery expression [6].

Using the GPT evaluation plans are generated for XQuery expressions that includes join,

quantifiers, grouping, aggregation, and nesting.

In general, database approaches make good use of the existing amenities of database

systems, which include query optimization, indexes, concurrency control, and crash

recovery. On the other hand, native approaches are more customized for XML docu-

ments. Because huge amount of geographic information is already stored in spatial data-

base systems, we take the database approach. By using the spatial XQuery language, the

user can access not only the extended spatial information but also the ordinary text and

graphic information in terms of XML forms.

3. S-XML and Spatial XQuery

In this section, the structure of S-XML is introduced first and then the syntax and se-

mantics of Spatial XQuery are discussed with some examples.

3.1 S-XML

S-XML is based on GML 3.0 and is designed to provide effective location based service

to the user in mobile environments. S-XML consists of three main schemas, i.e., voice

schema, tracking schema, and POI schema.

(a) Voice Schema

In mobile environments, voice information is often more useful than text or graphic

information especially when the user is driving a car. To be effective the grammar of the

voice information is designed as simple as possible (see Fig. 1). The voice information

can be either location information or turn information. For example, “Central Hospital is

located 10 miles away on the East.” The turn information can be used when the user is

driving a car or walking. An example of turn information is “turn left in 30 meters to-

ward City Hall.”

Page 4

Fig. 1. Grammar of voice schema

(b) POI Schema

POI schema has been designed based on POIX(Point of Interest eXchange Language

Specification) [14] of W3C and references Feature.xsd, Geometry.xsd, Topology.xsd,

DynamicFeature.xsd, and Direction.xsd of GML. POI schema includes the location

information of objects in specific area, the optimal path to destination, the type of mov-

ing objects (e.g., car, human, subway, …), information of the source and the destination,

information of representative objects near the destination, and additional information

about the destination (e.g., phone number and email address). Fig. 2 shows a part of POI

schema, which includes a starting point, a target point, and a route.

Page 5

Fig. 2. Part of POI schema that includes the specification of starting and target points

(c) Tracking Schema

Tracking schema specifies the changes of status of a specific object as time changes.

The information model includes the type of moving objects, information of specific

points and the time when the point passed, and information of direction and velocity. Fig.

3 shows a part of tracking schema, which specifies the locus type. A locus consists of a

series of points, time, location, and direction.

<xs:complexType name="accessType">

<xs:sequence>

<xs:element ref="method"/>

<xs:element name="ipoint" type="ipointType"/>

<xs:element name="tpoint" type="tpointType"/>

<xs:element name="route" type="routeType" minOccurs="0"/>

</xs:sequence>

</xs:complexType>

<xs:complexType name="ipointType">

<xs:sequence>

<xs:element ref="iclass"/>

<xs:element ref="gml:location"/>

<xs:element name="name" type="nameType" minOccurs="0"/>

</xs:sequence>

</xs:complexType>

<xs:complexType name="tpointType">

<xs:sequence>

<xs:element ref="tclass"/>

<xs:element ref="gml:location"/>

<xs:element name="name" type="nameType" minOccurs="0"/>

</xs:sequence>

</xs:complexType>

<xs:complexType name="locusType">

<xs:sequence>

<xs:element name="point" type="sxml:pointType"/>

<xs:element name="dateTime" type="xs:dateTime"/>

<xs:element name="location" type="xs:string"/>

<xs:element name="dir" type="xs:unsignedShort"/>

</xs:sequence>

</xs:complexType>

Fig. 3. Part of Tracking Schema that includes the Specification of Locus

Page 6

3.2 Spatial XQuery

Spatial XQuery follows basic FLWR (For Let Where Return) structure of XQuery with

path expressions so that SQL users are easy to use and the elements and attributes of S-

XML can be effectively accessed. Spatial XQuery also supports the spatial data, spatial

relational operators, and spatial functions that recommended by OGC specifications [4].

In Spatial XQuery, spatial operators and spatial functions have ‘sp’ as a prefix in their

names. Functions of moving objects have ‘mo’ as a prefix in their names. A list of op-

erators and functions specified in Spatial XQuery are as follows.

(a) Basic Operator for Spatial Objects

sp_Dimension (g Geometry): int, sp_GeometryType (g Geometry): string

sp_AsText (g Geometry): string, sp_AsBinary (g Geometry): binary

sp_IsEmpty (g Geometry): int, sp_IsSimple (g Geometry): int

sp_Boundary (g Geometry): geometry, sp_Envelop (g Geometry): geometry

(b) Functions of Point Type

sp_x (p Point): double, sp_y (p Point): double

sp_StartPoint(c Curve): point, sp_EndPoint(c Curve): point

sp_IsClosed(c Curve,): int, sp_IsRing(c Curve): int, sp_Length(c Curve): double

(d) Functions of LineString Type

sp_NumPoints(l LineString): int, sp_PointN(l LineString, n Int): point

(e) Functions of Surface Type

sp_Centroid (s Surface): point, sp_PointOnSurface(s Surface): point, sp_Area(s Surface): double

(f) Functions of Polygon Type

sp_ ExteriorRing(p polygon): linestring, sp_InteriorRingN(p polygon, n int): linestring

sp_ NumInteriorRing(p polygon): int

(g) Functions of GeometryCollection Type

sp_NumGeometries(g GeomCollection): int

sp_GeometryN(g GeomCollection, n int): geometry

(h) Functions of MultiCurve Type

sp_IsClosed(mc MultiCurve,): int, sp_Length(mc MultiCurve): double

(i) Topology Operators between two spatial objects

sp_Equals(g1 Geometry, g2 Geometry): int, sp_Disjoint(g1 Geometry, g2 Geometry): int

sp_Intersects(g1 Geometry, g2 Geometry): int, sp_Touches(g1 Geometry, g2 Geometry): int

sp_Overlaps(g1 Geometry, g2 Geometry) int, sp_Crosses(g1 Geometry, g2 Geometry): int

sp_Within(g1 Geometry, g2 Geometry)): int, sp_Contains(g1 Geometry, g2 Geometry): int

(j) Functions of Distance Relationship

sp_Distance(g1 Geometry, g2 Geometry): double

(k) Functions of Spatial Operations

sp_Intersection(g1 Geometry, g2 Geometry):geometry

sp_Difference(g1 Geometry, g2 Geometry) : geometry

sp_Union(g1 Geometry, g2 Geometry) : geometry

sp_Symdifference(g1 Geometry, g2 Geometry): geometry

sp_Buffer(g1 Geometry, d Double precision) : geometry, sp_Convexhull(g Geometry) : geometry

(l) Functions of Moving Objects

mo_First(p Position, n Int): point, mo_Last(p Position, n Int): point

mo_After(p Position, t Time): point, mo_Before(p Position, t Time) : point

mo_Snapshot(p Position, t Time) : point, mo_Snapshot(p Position, g Geometry) : time

mo_Slice(p Position, pe Period(start , end)): Linestring

mo_Slice(p Position, g Geometry): Linestring

mo_Project(p Position): Linestring, mo_Project(pe Period(start, end, g Geometry): point

(m) Functions of Voice Service

Page 7

POIDirection(p Position): string, ShortestPathDirection(p Position, i Int): string

Details of XQuery syntax are not discussed in this paper. The meaning of Spatial

XQuery will be clear with the following example.

Example 1. This query retrieves the names of cities that located within 5 km from

any river in rivers.xml.

for $a in document(“cities.xml”) //city

$b in document(“rivers.xml”) //river

where

sp_overlap($a/obj, sp_buffer($b/obj, 5000)) eq true

return

4. Processing of Spatial XQeury

The query processor of Spatial XQuery consists of Parser, SQL Info Generator, Result

Info Generator, and SQL Translator (see Fig. 4). The queries from the user interface are

first parsed to generate parse trees, which are sent to SQL Info Generator and Result

Info Generator. Spatial XQueries finally translated into spatial SQL based on the infor-

mation generated by SQL Info Generator and Result Info Generator. SQL Info Genera-

tor analyzes the clauses FOR, LET, and WHERE from the Spatial XQuery statements

and generates a mapping table for query translation. The RETURN clause of Spatial

XQuery is analyzed by Result Info Generator and a linked list of tags and elements is

generated.

Fig. 4. Structure of the Query Processor of Spatial XQuery

Details of the procedure of translating Spatial XQuery are presented using an exam-

ple. Consider the query in Example 1. By analyzing the FOR and WHERE clauses, we

can generate the mapping table as in Table 1. In Table 1, tag names and variable names

are translated into corresponding Table names in spatial database. Operators in Spatial

XQuery are also mapped into the corresponding ones in spatial database. Such mapping

information is provided by the Mapping Module of Spatial Operators. In this example,

the spatial operator of Spatial XQuery sp_overlap in mapped into operator overlap in

spatial database.

Page 8

Table 1. Mapping from Spatial XQuery to spatial SQL

Spatial XQuery

SQL

From

Cities.xml//City

Rivers.xml//River

City

River

Select

$a/name

City.name

Where

sp_overlap($a/obj,

Buffer($b/obj, 5000)) eq true

overlap(City.obj, Buffer(River.obj,

5000)) = true

Order by

NULL

Based on the mapping table in Table 1, spatial SQL query can be generated as fol-

lows.

Select City.name

From City , River

Where Overlap(City.obj, Buffer(River.obj, 5000)) = true;

The SQL Info and Result Info can be represented as a graph. The graph in Fig. 5 is

generated for this example, which includes nodes for start tag, table name, column name,

and end tag.

Fig. 5. Graphical Representation of SQL Info and Result Info

Using the Result Info in Fig. 5 and the table returned as a result for the SQL state-

ment, the following XML document will be generated for this example.

<name> Han River </name>

< /Within5000CityName>

5. Working Scenario

A scenario to apply Spatial XQuery in LBS environment is discussed in this section.

This is an example of Emergency Support System that includes POI Service and Short-

est Path Service. Suppose that a car accident takes place and there are some injuries (see

Page 9

Fig. 6). The user of this system is looking for the nearest hospital and wants an ambu-

lance for injured people. Once the nearest hospital is identified by the Emergency Sup-

port System, the hospital is requested to dispatch an ambulance to the accident place.

Then the driver of the ambulance asks the direction to the accident place while he or she

drives. The Spatial XQueries made for the requests, SQL queries that translated, and

XML results generated from the system are explained in this Section.

Fig. 6. Car Accident and Ambulance from the Nearest Hospital

Fig. 7 is a Spatial XQuery that looks for the nearest hospital from the accident place.

The coordinates of the accident place are available from a GPS.

for $a in document("textshape.xml")//TextShape

let $b := min(sp_distance($a/obj, point(4559734.910290 1348143.837131)))

where contains($a/tex(), “%hospital%”) and text_kind eq '50'

return <POI> {

for $c in document(“textshape.xml")//TextShape

where contains($a/tex(), “%hospital%”) and sp_distance($a/obj,

point(4559734.910290 1348143.837131)) <= $b and text_kind eq '50'

return {

sp_distance($c/obj, point(4559734.910290 1348143.837131))

</Distance>

<voice>

<Direction>POIDirection(point(4559734.910290 1348143.837131))</Direction>

</voice> }

}

</POI>

Page 10

Fig. 7. Spatial XQuery looking for the nearest hospital

Fig. 8 is the SQL query that is translated from the Spatial XQuery in Fig. 7. The spa-

tial operator sp_distance is translated into spatial database operator distance and for

optimization the selection condition is included in the WHERE clause.

select text, obj, distance(obj, point(4559734.910290 1348143.837131))

from textshape

where text like '%hospital%' and distance(obj, point(4559734.910290 1348143.837131) ) <=

(select min(distance( obj, point(4559734.910290 1348143.837131) )) from textshape where text

like '%hospital%' ) and text_kind = '50';

Fig. 8. SQL Query that is translated from the Spatial XQuery in Fig. 7

From the result returned for the SQL query in Fig. 8, an XML document is generated

as in Fig. 9. In Fig. 9, a hospital named “Dr. Gye’s Hospital” is selected and the distance

and direction to it are included.

<POI>

<Label>Dr. Gye’s Hospital </Label>

<gml:Point>

<gml:coord>

<gml:X>4559375.060000</gml:X><gml:Y>1348618.010000</gml:Y>

</gml:coord>

</gml:Point>

</Location>

<vml>

Dr. Gye’s Hospital is located 638.692749 meter away on the east

</POIblock>

<vml>

</POI>

Fig. 9. The nearest hospital and its distance and direction from the accident place

6. Conclusion

Geography Markup Language (GML) has been extended for mobile and location-based

applications. In order to handle effectively the extension, we have designed a Spatial

XQuery language and its processing modules. Because our work is based on a spatial

database system, the Spatial XQuery statements are first translated into spatial SQL

statements. By working on existing spatial database system, we can use of the existing

functions of database systems such as query optimization, spatial indexes, concurrency

control, and crash recovery. Translation of the Spatial XQuery into spatial SQL has been

explained using an example.

Page 11

Application areas of the proposed system are almost all mobile and location-based

systems such as LBS, ubiquitous systems, and distributed control and management sys-

tems. In order to be more powerful, it needs to be extended with various development

tools. Novice users may have difficulties to program their queries using Spatial XQuery.

Some user-friendly designed GUI tools could make the system more effective. Even

current execution model allows multiple queries; we need to devise more sophisticated

optimization strategies for multiple queries.

References

[1] S. Al-Khalifa et al., “Structural joins: A primitive for efficient XML query pattern match-

ing,” Proceedings of IEEE International Conference on Data Engineering (ICDE), 2002.

[2] P. Bohannon, J. Freire, P. Roy, and J. Simeon, “From XML schema to relations: A cost-

based approach to XML storage,” Proceedings of IEEE International Conference on Data

Engineering (ICDE), 2002.

[3] N. Bruno et al., “Holistic twig joins: Optimal XML pattern matching,” Proceedings of ACM

SIGMOD International Conference on Management of Data (SIGMOD), 2002.

[4] M. Carey et al., “XPERANTO: Publishing Object-Relational Data as XML,” Proceedings of

Workshops on Web and Databases (WebDB), 2000.

[5] Don Chamberlin, Jonathan Robie, Daniela Florescu, “ Quilt: an XML Query language for

heterogeneous data sources” LNCS, 1997.

[6] Z. Chen, H. Jagadish, L. Lakshmanan, and S. Paparizos, “From Tree Patterns to Generalized

Tree Patterns: On Efficient Evaluation of XQuery,” Proceedings of International Confer-

ence on Very Large Databases (VLDB), 2003.

[7] B. Cooper et al., “A Fast Index for Semistructured Data,” Proceedings of International

Conference on Very Large Databases (VLDB), 2001.

[8] A. Deutsch, M. Fernandez, and D. Suciu, “Storing semistructured data with STORED,”

Proceedings of the ACM SIGMOD International Conference on Management of

Data(SIGMOD), 1999.

[9] M. Fernandez et al., “Publishing Relational Data as XML: The SilkRoute Approach,” IEEE

Data Engineering Bulletin, 24(2), 2001.

[10] M. Fernandex, Y. Kadiyska, A. Morishima, D. Suciu, and W. Tan, “SilkRoute: A frame-

work for publishing relational data in XML,” ACM Transactions on Database Systems, 2002.

[11] T. Fiebig et al., “Anatomy of a native XML base management system,” VLDB Journal,

11(4), 2002.

[12] H. Jagadish et al., “TIMBER: A native XML database,” VLDB Journal, 11(4), 2002.

[13] D. Kha, M. Yoshikawa, and S. Uemura, “An XML Indexing Structure with Relative Region

Coordinate,” Proceedings of IEEE International Conference on Data Engineering (ICDE),

2001.

[14] J.

Naughton

al.,

“The

Niagara

Internet

Query

System,”

http://www.cs.wisc.edu/niagara/papers/NIAGARAVLDB00.v4.pdf.

[15] OGC, Geography Markup Language (GML) Implementation Specification 3.0, 2003.

[16] S. Park, J. Lee, and H. Bae, “Easily Accessible GML-based Geographic Information System

for Multiple Data Server over the Web,” Proceedings of International Conference on Infor-

mation System Technology and its Applications (ISTA), 2003.

[17] H. Schoning, “Tamino – A DBMS designed for XML,” Proceedings of IEEE International

Conference on Data Engineering (ICDE), 2001.

Page 12

[18] I. Tatarinov, Z. Ives, A. Halevy, and D. Weld, “Updating XML,” Proceedings of ACM

SIGMOD International Conference on Management of Data (SIGMOD), 2001.

[19] I. Tatarinov, S. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang, “Storing

and querying ordered XML using a relational database system,” Proceedings of ACM

SIGMOD International Conference on Management of Data (SIGMOD), 2002.

[20] W3C, XQuery 1.0: An XML Query Language, 2002.

[21] Y. Wu et al., “Structural Join Order Selection for XML Query Optimization,” Proceedings of

IEEE International Conference on Data Engineering (ICDE), 2003.