MOBILE QUERY AND PROCESSING IN MOBILE
DATABASE ENVIRONMENT
Agustinus Borgy Waluyo1 Bala Srinivasan1 David Taniar2
1
School of Computer Science and Software Engineering, Monash University, Australia
{Agustinus.Borgy.Waluyo, Bala.Srinivasan}@infotech.monash.edu.au.
2
School of Business Systems, Monash University, Australia
David.Taniar@infotech.monash.edu.au
Abstract
Mobile database is a new context of database application in wireless environment. It introduces
unique type of queries, and query-processing strategies that are different to traditional databases.
We classify mobile database query into two categories, especially context-awareness query and ad-
hoc query. Context-awareness query is further classified into location dependent, context
dependent, and hybrid query. As for the query processing, we define three strategies namely mobile
client, on air, and server strategy. Mobile client and on air strategy relates to caching strategy and
broadcast strategy respectively. Finally, we include some challenges in mobile databases.
1. Introduction
Recent advances in wireless technology have led to mobile computing, a new dimension in data
communication and processing. Many predict a new emerging, gigantic market with millions of
mobile users carrying small, battery-powered terminal equipped with wireless connection [1,2,10].
The mobile computing environment provides database applications with useful aspects of wireless
technology, which is known as mobile databases. This advance technology has created a new age
of nomadic database users. Basically, these users are simply accessing a database through a
network. However, the network is now applied in wireless environment, and has several novel
properties, which include user’s locations are constantly changing, the likelihood of losing
connections is much greater than in a traditional network, and asymmetric communication
environment in which the wireless bandwidth for uplink communication is smaller than downlink
communication [11].
In general, mobile user communicates with a Mobile Base Station (MBS) to carry out any activities
such as transaction and information retrieval. MBS has a wireless interface to establish
communication with mobile client and it serves a large number of mobile users in a specific region
called cell. In mobile environment architecture, each MBS is connected to a fixed network as
illustrated in Figure 1(a).
Mobile units or mobile clients in each cell can connect to the fixed network via wireless radio,
wireless Local Area Network (LAN), wireless cellular, or satellite. Each of the wireless networks
provides a different bandwidth capacity. However, the wireless bandwidth is too small as compared
to the fixed network such as ATM (Asynchronous Transfer Mode) can provide speed up to
155Mbps [7].
55
Wireless Network
Mobile Mobile
Base Base Wireless Network
Station Station
Query
Mobile Query Processing Data
High speed Wired
Client Strategy Repository
Network Crossing
Fixed Fixed Crossing Query Result 2
Host Host
Mobile
Mobile
Base
Base
Station
Station
Query
Taxonomy
= Mobile Client 1
= Wireless Network
(a) Mobile Environment Architecture (b) Query Application in Mobile Environment
Figure 1. Mobile Environment Architecture and Query Processing
Figure 1(b) depicts the query processing in mobile databases. Mobile client initiates a query, and
retrieve the data from data repository. The data repository is available in the fixed network. The
query is transmitted through wireless channel, and the result is obtained using certain query
processing strategies. As can be seen in Figure 1b, a sign of number 1, and 2, which is attached in
query taxonomy, and query processing strategy respectively, correspond to the main content of this
paper.
Driven by differences between wired and wireless environment results in differences of type of
queries, query processing mechanisms as well as communication technology. It is the aim of this
paper to provide comprehensive query taxonomy, and processing strategy in mobile databases.
Figure 2 shows a detailed structure of this paper. Subsequent sections in this paper are organized
as follows. Section 2 describes query taxonomy in mobile databases. Section 3 contains the query
processing strategies, and section 4 discusses some challenges in mobile databases. Finally, section
5 concludes the paper. In this paper, the term mobile client, mobile device, mobile user, user and
client are used interchangeably
Location D ependent Q ueries
C ontext C ontext D ependent Q ueries
Aw areness
Taxonomy Hybrid Q ueries
A d Hoc Q ueries
M obile Q uery
and Processing
M obile C lient
Processing
Strategy O n Air
Server
Figure 2. Structure of Paper
56
2. Query Taxonomy
In this section, we classify type of queries in mobile databases. The queries can be entirely new and
specifically applied in the wireless environment, while the other can be a common type of query in
traditional databases.
2.1 Context Awareness
The word ‘context’ implies a variety of aspects. [14] defines the word context into three categories
namely computing context, user context, and physical context. Computing context relates to
computing resources such as network connectivity, bandwidth, printer, and workstations. User
context associates with user’s needs, preferences, roles, profile, and alike. Physical context involves
environment issue, which include lighting, noise, traffic, temperature, and humidity. [5] adds
another category of context called ‘time context’, which refers to time of a day, week, month, year,
etc. [6] defines context as either the aspect of physical world or condition and activities in the
virtual world. It is further described that context information can either be transient when the
context associates with the environment at a point of time or persistent when the context involves a
history of transient context. In simple words, we can always define that context relates to who,
when, where, and what.
Context awareness creates a new class of applications in mobile computing. With context
awareness, mobile device is expected to adapt constantly in a wide range of dynamically and
continually changing situations. It is important for the device to be able to aware of the situation,
environment, and tasks that the mobile client is performing as well as will be performing in the near
future. The utilisation of context information in an application minimises the amount of user
involvement in a service by providing related information.
Having known the context of the query enables the device to pre-fetch all data that is highly related
and likely to be queried in the near future. With this query, client only initiates a single request and
all related data will be retrieved implicitly. This technique avoids client to have multiple request
that result in energy efficiency.
Example: To find restaurants information in current region. The query will result of retrieving
restaurants based on user’s preferences such as Italian, Chinese or fast food as well as pre-fetching
maps, traffic and weather condition, which is likely to be queried next.
Most applications have been focusing on location awareness rather than context awareness as a
whole. Thus, we classify mobile database queries into location dependent queries, context
dependent queries, and the combination thereof.
2.1.1 Location Dependent Queries
Location dependent query is a class of queries that are motivated by mobile clients. In this type of
query, the location of the mobile client is a parameter of the query. The value of the location
parameter can be provided by the client or a global positioning system (GPS). An example of this
query is a traveler’s information system that provides information on hotels, restaurant, bars and the
like, to motorists. Processing of queries must be based on knowledge of the user’s location. For
queries services that are ahead of the current route, direction of motion and speed are necessary to
be taken into account. Recent technology provides a new feature in automobiles, which offers
57
navigational aids as a built-in feature. In general, each location updates generate two direct costs,
particularly transmission cost, which refers to the cost to inform the server of the new location, and
server processing cost, which corresponds to the cost of updating the system containing the location
of the mobile unit. The location parameter can be in any objects, such as taxis, trucks, and
helicopters. This class of query can be further classified into two categories: (i) Continuous query,
and (ii) On-demand query.
Continuous query
The continuous type of query includes real-time monitoring of mobile objects. This is different
compared with conventional queries, which are based on an instant of the database at some
moment in time. Real-time monitoring queries are continuous for monitoring purposes [3, 13].
Examples: (i) To request information about nearby tourist attractions, hotels, or shopping center
while traveling. With this type of query, users only need to send a query once and notification of
the updated information about nearby tourist attractions, hotels, or shopping center will be sent
automatically as they move to different regions. (ii) This query also helps tourists whenever they
are close to a certain situation such as dangerous zone or traffic jam by providing some alerts to
mobile user.
Figure 3 shows an illustration of real-time query monitoring. In this application, the system must
be able to provide the accurate query results and update them in real time whenever some mobile
clients enters or exits the region defined by the query. This class of query can be referred as
range-monitoring queries. The range-monitoring queries are removed from the system only
when the user explicitly ends the query.
Server
Query i Updated End Query
Response i New
Region response i
Region 1 Region 2
Mobile Mobile
Client 1 Moves to Client 1
Figure 3. Continuous Query
On demand query
The on demand location dependent query is different from continuous query in a way that its
database management does not manage the query but only the location of each mobile units in
specified regions. Figure 4 illustrates on demand query. Every mobile unit is registered under
one location server that manages the user profiles and is called the home location server.
Location information of mobile clients can be stored at predefined sites like the user’s home
location server in a network. Consequently, the search space for a user’s location can be
reduced. However, when a mobile user crosses any boundaries of a cell, the information at the
predefined site has to be updated accordingly. This type of query does not have to specify when
to end the query since the server does not keep the query but the location [12].
Examples: To retrieve nearby hospital, police station or petrol station in the area.
58
Server
Q uery i R esponse i Q uery j R esponse j
Region 1 Region 2
M obile M obile
C lien t 1 M oves to C lien t 1
Figure 4. On Demand Query
When the parameter is an object, and mobile client requests an object that satisfies location
criteria, then the situation becomes different. Figure 5 illustrates on demand query with location
object parameter [8,15].
Examples: (i) Taxi operator wants to see how many free taxis are currently in a certain region.
They can find free taxis and allocate them to another region that require more taxis or send them
directly to the nearby customer. (ii) Tourists who come to the country, where there are no
designated bus’ stops, nor timetable. They can utilize mobile device to retrieve incoming buses
within a pre-defined time.
Server
Object Object Location Location
Query Result Tracking Info
Mobile Object
Client
Figure 5. On Demand Query with Location Object Parameter
2.1.2 Context Dependent Queries
This type of query requires maintenance of an internal representation of user’s needs, preferences,
roles, profile, etc. With these parameters, application will be able to decide the situation and task
that a user is currently performing, and adapt to change of user needs and roles. This enables
mobile device not to just retrieve the required information but also some other information that is
highly relevant [6,8].
Examples: (i) Tourist wants to see list of restaurants in a town. Rather than retrieving the entire list
of restaurants, the query retrieves the restaurants based on user’s preferences and need such as
cuisine preference, price, occasion, etc. (ii) A business person wants to check the closest meeting
schedule. The query retrieves the time as well as previous history of the meeting, people involved,
client accounts, meal preferences, required data, etc.
59
2.1.3 Hybrid Queries
Hybrid queries represent a combination of location dependent and context dependent queries. This
type of query requires the system to maintain all parameters of context-awareness queries including
location parameter.
Examples: (i) A Traveler wants to find restaurants in the region that he/she will enjoy and within
10 minutes of current travel distance, (ii) A teenager wants to check movies in the nearby cinemas
that he/she will like, and the show time can be met while considering current travel distance.
These queries are very useful for nomadic users since it not only considers the users’ preferences
and needs but also the location of the user. More sophisticated application utilizes a variety of
sensors to monitor the environment as well as user’s action in order to provide assistance of the
tasks being performed by the user. This application requires the ability to process data streams in
real-time, analyze and interpret it precisely. The main point in context awareness query is to
accurately analyze the environment and user’s intention, regardless of where the context
information is obtained from. It is a difficult challenge since there is a possibility of conflicting
data, and the need to have efficient processing to provide a useful application to the user.
2.2 Ad Hoc Queries
Ad Hoc queries are commonly utilised queries in traditional DBMS. This type of query explicitly
mentions the required information in the query statement, and does not involve any context
awareness information. Thus, the query result is only based on the actual query itself.
Examples: (i) University student wants to retrieve his/her academic record or personal details. (ii)
Travelling sales person inquires about product availability, price, etc.
3. Query Processing Strategy
We divide query-processing strategy for mobile databases into three parts, namely: (i) mobile/client
strategy, (ii) on-air strategy and, (iii) server strategy. Mobile/clients strategy relates to how client
manipulates and maintains the data in its cache efficiently and effectively. On-air strategy
corresponds to data broadcasting strategies. With this strategy, the number of mobile users does not
affect the query performance. Server strategy relates to designing techniques for the server to
accommodate multiple requests so that the request can be processed as efficiently as possible.
We claim that query processing for mobile databases is very much centered around the issues of
caching, broadcasting, and scheduling. Figure 6 shows the architecture of query processing in
mobile databases.
60
Client Strategies Server Strategies
On Air
Strategies
Figure 6. Query Processing in Mobile databases
3.1 Mobile Client Strategy
Mobile client’s strategy defines a number of strategies to maintain cached data items in clients’
local storage. As stated earlier, wireless communication channel in general suffers to narrow
bandwidth while it is also inherently asymmetric communication, in which the downstream
communication bandwidth from a server to the mobile client is much larger than the upstream
communication bandwidth from clients back to server. Due to the above reason, caching of
frequently accessed data items in a client’s local storage becomes important for enhancing the
performance and data availability of data access queries. Another advantage of caching is the
ability to handle fault tolerance. This is related to the characteristics of mobile computing in which
each mobile client connects or disconnects from the network frequently. In some situation, the
MBS may not be accessible due to problem like signal distortion. However, a query can still be
partially processed from caches and at least some of the query results can be returned to the user
[9].
Three main issues characterize a caching mechanism. These issues include caching granularity,
caching coherence strategy, and caching replacement policy. Caching granularity relates to
determining a physical form of cached data items. Caching coherence strategy or invalidation
strategy involves cache invalidation and update schemes to invalidate and update an out-dated
cached item [4]. Caching replacement policy is needed to retain the frequently accessed database
items in a client’s local storage. The more effective a caching replacement policy in keeping the
frequently accessed items, the better a query will perform and the more queries could be served
during disconnection situation.
3.2 On Air Strategy
In this scheme, the server periodically broadcasts the frequently accessed data items to clients
through one or more broadcast channels, but the clients may not cache the data item of interest.
This situation might occur when the client does not have enough memory or space to cache the
required data. The behavior of this channel is unidirectional which means the server disseminates a
set of data periodically, via this type of channel to a multiple number of users. A complete
broadcast file is referred as a broadcast cycle. In this scheme, the client needs to listen to channel
and filter the required data over the channel, which is also generally known as push-mechanism.
Figure 7 shows on air query processing.
61
The advantage of broadcasting channel is its scalability. The number of users in the cell and the
request rate do not affect the performance of the server. Thus, the utilization of bandwidth is better
and the server workload is lower as compared with point to point/on-demand communication.
Consequently, the power utilization of the client to retrieve information is also improved. However,
it is very important to have good strategies to maintain the overall response time of the client to
obtain information from the channel or else the advantages of data broadcast will be diminished.
B ro ad cast C h an n el
M o bile
= listen in g to th e chan n el
C lie nt
= retriev in g th e d esired data
Figure 7. On Air Query Processing
3.3 Server Strategy
This strategy considers the problem of pull-based broadcast scheduling where mobile clients send
queries to the server through dedicated or point-to-point channel, server process the query, and
send the result back to the client. The strategy concerns with broadcast and disk scheduling.
Broadcast scheduling is to determine how queries to be served efficiently in the server considering
a number of factors such as the length of the query, the wait time and the popularity of the items.
Data scheduling is related to how data is placed on the disk that improves the query response time.
The possibility of combining these two methods for query processing strategy is an interesting issue
to be explored.
B road cast
server
C ach e D isk
S erver S erver
T r a n sm itte r
S erver
Figure 8. Broadcast Server Architecture
A database server is able to enhance the data retrieval performance by incorporating its own main
memory and cache to store those database items frequently accessed by most mobile clients. Figure
62
8 shows architecture of broadcast server. A query can be processed either in the disk server or
cache server. If the relevant data items have been retrieved earlier then the query is processed in the
cache server. After processing a query, the results are transmitted to the transmitter queue, which
subsequently send the data items through the wireless channel.
4. Challenges in Mobile Databases
This section discusses some challenges in mobile database environment. The general concept that
has been outlined in this paper contains an enormous issue to investigate. However, due to the
limitation of page, only a few numbers can be mentioned.
Location management is an important issue in mobile database research. Since the number of
user population carrying mobile devices increases linearly with the service demand, the
communication traffic for locating users also increases accordingly. This situation requires an
efficient strategy for location tracking and management. Location management is a very
essential factor in providing context awareness services.
Context security introduces a new issue to be considered. Since context information may
contain a very confidential and private data. It is necessary to ensure privacy issue protection
for every user in a network.
Caching management strategy, which includes caching granularity, caching coherent issue, and
caching replacement strategy, requires a thorough investigation. A good caching management
strategy is able to analyse, predict, and adapt to changing of user’s context in order to assist
user in performing tasks. As for processing issue, data caching in mobile databases enable
clients to obtain a high computing speed as server, by involving a much smaller data items
volume. The asymmetric communication in mobile environment has made it a better reason to
employ caching strategy.
Broadcast scheduling is another issue to investigate. Generally, the more number of data to be
broadcast, the more requests will be served from the data broadcast and this will reduce the
chance of mobile clients to send the request to the server. However, at a certain point the
advantage of the broadcast data will be diminished if there is too many data in the broadcast
cycle. Consequently, it will severely affect the query response time since mobile users have to
wait for considerably long delay before they receive the desired data. Therefore, it is essential
to decide what data to be broadcast that serves most of the requests since the query access
pattern is changed dynamically.
5. Conclusions
Recent emergence of wireless technology enables people to conduct activities, business, or
transactions anywhere and anytime without any attachment to stationary computer like used to be.
Nomadic people are now able to access email, news, weather, and query to the central database
server using wireless devices. Mobile database focuses on the query issue that is the dominant
operation in mobile computing. Since mobile database is a new dimension of database application,
the type of query, query processing strategy, and communication technology that involves in the
application are different than what applies in traditional databases.
We have defined query taxonomy as well as query processing strategy in mobile databases. Query
in mobile databases are categorized into context-awareness query and ad-hoc query. Context-
63
awareness query is further classified into location dependent, context dependent, and hybrid query.
Query processing in mobile databases includes mobile client, on air, and server strategy. Mobile
client and on air strategy corresponds to caching strategy and broadcast strategy respectively.
Finally, we discuss a few challenges that open enormous opportunities for research in mobile
databases.
6. References
1. ACHARYA S., ALONSO R., FRANKLIN M. AND ZDONIK S., Broadcast Disks: Data Management for
Asymmetric Communication Environments, Proceedings of ACM Sigmod, pp.199-210, May, 1995.
2. BARBARA D., Mobile Computing and Databases-A Survey, IEEE TKDE, 11(1):108-117, January/February,
1999.
3. CAI Y. AND HUA K. A., An Adaptive Query Management Technique for Real-Time Monitoring of Spatial
Regions in Mobile Database Systems, 21st IEEE IPCCC, pp.259-266, 2002.
4. CHAN B. Y., SI A. and Leong H. V., Cache Management for Mobile Databases: Design and Evaluation,
Proceedings of the International Conference on Data Engineering (ICDE), pp.54-63, 1998.
5. CHEN G. AND KOTZ D., A Survey of Context-Aware Mobile Computing Research, Technical Report TR2000-
381, Department of Computer Science, Dartmouth College, November, 2000.
6. EBLING R.M., HUNT H.D.G. AND LEI H., Issues for Context Services for Pervasive Computing, Proceedings of
Middleware’01 Advanced Workshop on Middleware for Mobile Computing, Heidelberg, November, 2001.
7. ELMASRI R. AND NAVATHE S. B., Fundamentals of Database Systems, 3’rd Edition, Addison W., U.S.A.,
2000.
8. FRANKLIN J.M., Challenges in Ubiquitous Data Management, Informatics, pp.24-33, 2001.
9. GODFREY P. AND GRYZ J., Semantic Query Caching for Heterogeneous Databases, Proceedings of the 4th
Knowledge Representation meets Databases Workshop (KRDB), pp.61-66, April, 1997.
10. IMIELINSKI T. AND VISWANATHAN S., Adaptive Wireless Information Systems, Proceedings of SIGDBS
(Special Interest Group in Database Systems) Conference, pp.19-41, October, 1994.
11. IMIELINSKI T., VISWANATHAN S. AND BADRINATH B. R., Data on Air: Organisation and Access, IEEE
TKDE, 19(3): 353-371, May/June, 1997.
12. KOTTKAMP H.-E. AND ZUKUNFT O., Location-Aware Query Processing in Mobile Database Systems, ACM
Symposium on Applied Computing, pp.416-423, February, 1998.
13. KUBACH U. AND ROTHERMEL K., A Map-Based Hoarding Mechanism for Location-Dependent Information,
Proceedings of Second Mobile Data Management (MDM), pp.145-157, January, 2001.
14. SCHILIT B., ADAMS N. AND WANT R., Context-Aware Computing Applications, Proceedings of IEEE
Workshop on Mobile Computing Systems and Applications, pp. 85-90, December, 1994.
15. WOLFSON O., ET AL, Databases for Tracking Mobile Units in Real Time, Proceedings of ICDT’99, pp. 169-
186, 1998.
64
