Momm72003

MOBILE QUERY AND PROCESSING IN MOBILE DATABASE ENVIRONMENT Agustinus Borgy Waluyo1 1

Bala Srinivasan1

David Taniar2

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 [email protected]

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 adhoc 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 Base Station

Mobile Base Station

High speed Wired Network Fixed Host

Mobile Base Station

Fixed Host

Wireless Network

Crossing

Crossing

Mobile Base Station

Mobile Client

Query Processing Strategy

Query

Query Result

Data Repository

2

Query Taxonomy

1

= Mobile Client = 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 Aw areness

Hybrid Q ueries

Taxonomy

A d Hoc Q ueries M obile Q uery and Processing M obile C lient Processing Strategy

C ontext D ependent Q ueries

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

Region 1 Mobile Client 1

Response i

New Region

Moves to

Updated response i

End Query

Region 2 Mobile 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

Region 1 M obile C lien t 1

R esponse j

Q uery j

M oves to

Region 2 M obile 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 Query

Object Result

Location Tracking

Mobile Client

Location

Info

Object

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 C lie nt

= listen in g to th e chan n el = 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 S erver

D isk 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 TR2000381, 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. 169186, 1998.

64