\documentclass[10pt,twocolumn]{article}
\usepackage{latexsym,textcomp}
\usepackage{epsfig}
\usepackage{setspace}
%\usepackage{amsfile}
\begin{document}
\setstretch{1.0}
\title{\bf Mobile Computing - The Journey So Far }
\author{Jekkin Shah\\
jekkin1@csee.umbc.edu}
 \date{Laboratory of Information Systems Technology  \\ University of Maryland at Baltimore County \\ 1000 Hilltop Circle \\ Baltimore, MD-21250}
 \maketitle
 \begin{abstract}
 {\it In this paper we conduct a brief survey on the data management
 principles employed in the mobile computing environment, laying special
 emphasis on the issues of cache management and query evaluation. }
 \end{abstract}
 \\
 \\
 {\bf Keywords :}  {\it  Semantic Cache, Semantic Segment,
 Cache Management, Cache Replacement, Query Processing, Query
 Trimming, Coalescing, Remainder Query, Containment, Satisfiability }


 \section{\bf Introduction}

With the tremendous progress in the Internet, equally paralleled by the 
technological advancements in  mobile communication devices, it 
is but evident that the next wave of boom is going to be in the field of 
mobile computing. Hand-held devices will be the norm of the day,  with
millions of users using  mobile Internet based device. These devices could be 
anything from hand-held personal digital assistants, navigation systems in 
car to intelligent GPS systems in cell phones and wrist watches .

\subparagraph{}
We dwell into the various aspects of data management in such a framework, 
taking note of what has been done so far, and which area looks very 
promising for further research .  Our special emphasis is on 
cache management and query processing. We start with the motivation
behind the idea semantic cahing and then  briefly touch upon 
hardware issues involved in mobile computing along with network  
considerations  in section 3.  Section 4 provides an overview in the  cache 
management aspect of mobile computing 
while query evaluation is studied in section 5. 
We conclude the survey in section 6 envisioning  the future needs,
and touch upon issues not fully explored in the current research.

\section{Motivation}
One unique feature of the mobile computing environment  that
distinguishes itself from all other environments is the dynamic
location of the mobile clients  and sometimes even servers. 
The mobility factor can be leveraged in many ways. the management of
data can take into account the location of the mobile. The selection
of transferred data sets and strategies of data replacement can use
the knowledge of user's actual and future position. in short the
systems can be made ``location aware'' \cite{Dunham}\cite{Ouri}.
Systems can combining caching with user profile and context ( location and time )
Semantic query caching is used in DBMS for optimization of query execution and 
management of views\cite{Basu}\cite{Godfrey} .
The scheme is  used in web-oriented applications eg. web search engines.

\section{\bf Pushing the technology to its physical limits }

Small , mobile devices bring with them a set of constraints and
limitations unique to them. 
One of the constraints is that of limited power supply. Since battery power is never unlimited , we 
have to make optimal use of this resource 
Accommodating large amounts of data within  limited 
storage is an equally challenging issue .
Assuming the model to be client-server  network bandwidth  is always a
a bottleneck with incresing number of users of this type, this will be one of the most prominent issues to be handled in near 
the future. a variety of data encoding and/or compression techniques can be used to make 
the optimal use of the available bandwidth during the data transfer. 
also progressing loading of the vector maps can be used as proposed by \cite{Egenhofer99}.
for images and other spatial data resolution reduction techniques can
also be employed \cite{Egenhofer99} \cite{Duda}.
Alternatively, protocols well suited for wireless communications and mobile devices should be used\cite{Wireless} .

Due to network uncertainties, frequent disconnections occur. Also,
many a times high server load and latency leads to inexplicable delays.
To circumvent this problem , more autonomy should be given to the
client and Disconnected Mode of Operation should be made
possible\cite{Dar}.Asynchronous information access should be made possible.


\section{ Semantic Caching }

\subsection{ Overview}

Traditional caching mechanisms employed in traditional DBMS, 
like page caching or tuple caching do not work well in mobile environments . 
one reason being that they statically exploit spatial and/or temporal
locality. they fail to capture constantly changing location of the
mobile client. page caching suffers from poor clustering of the
database and can lead to inefficient use of cache while tuple caching may incur high overheads in maintaining
information about individual tuples in the cache . 
In mobile environments , we need a caching mechanism which can take
into account the clients constantly changing location and leverage
this information to maximize cache efficiency . We need a  hybrid
caching mechnaism which have the advantages of both tuple and page
caching, and ideally disadvantages of neither.
It is in  this scenario that semantic caching comes into play. Semantic
caches keep information about the dynamic locations of the clients in
the cache .

The idea of semantic caches is very simple. along with the query
results , the query itself is stored in the cache. When a new query
enters the systems, an attempt is first made to see if the answer to
the query can be obtained from the results already present in the cache. This check is made by 
evaluating the new query against the queries already present in the cache . 
even if the query can be answered partially from the cache , it can
substantially reduce the network bandwidth and also the load on the
server.
In what follows , we detail the semantic cache model, along with
cache management strategies.


\subsection{ Semantic cache model }

We start with the discussion with the cache  model adopted from \cite{Dunham} ,
Dunham . the cache consists of a number a regions called semantic
segments. Each semantic segment is the result of a  query ,
unlike traditional page-level caches which contain pages directly from the
base relations. the semantic segment $S$ can be formally expressed as a tuple 
\[ <S_R,S_A,S_P,S_C> \]
where  $S_R$ and $S_A$ are the base relations and attributes involved
with the semantic segment. $S_P$ is the query predicate while $S_C$ is
the actual result of the query. 
Some other information like timestamp is also stored with each
segment.
The physical organization of this, can vary depending on the
application and the available memory. in a typical scenario,each
segment starts on a new page, and continuous on other pages, if need
be. The pointer to the start pages of all the segments is maintanied
in a table for quick referencing.
 
\subsection{Cache granularity}

Semantic caches are stored as regions and their sizes vary
dynamically. At the extreme end a region could be as small as a tuple ,
or it could even extend several pages. The varying size gives
flexibility in maintaining and manipulating the regions. It gets rid
of the rigidity of the page caching ,at the same time it does not
incur high overheads associated with tuple caching . 
Also the regions grow and shrink dynamically depending on the
operations performed for cache management, respectively coalescing and 
region shrinking. The decision to coalesce or shrink
regions is application dependent and is basically a trade off between
cache efficiency and query execution speed . 

If the regions are never coalesced, answering new queries could be
cumbersome and time consuming. On the other hand , coalescing the
regions every time , would lead to frequent cache replacements thus
decreasing the utilization of cache\cite{Dunham}.


\subsection{Cache Management }

Cache management generally involves cache replacement and cache
coherency. We look into each of these topics in the following sections

\subsubsection{Cache Replacement}
 
A number of cache replacement strategies have been proposed in the
literature. Conventional strategies like Least Recently Used are
rendered ineffectively due to the constantly changing location  of the
client . For a client moving in somewhat circular path, LRU would fail miserably.
\cite{Dar} proposes a replacement strategy which exploits
the location parameter, called the Further Away Replacement (FAR)
The basic strategy of FAR algorithms is to choose the victim in
such a manner that its distance is greatest from the current location
of the client. The distance can be calculated in a variety of Way's,
one of them being the euclidean distance measured from the centroid of
the regions (Manahattan distance). There have been improvisations over this algorithm ,
namely to take into account not only the current location of the
moblie, but also its direction. Also a number of matrices to calculate
the distance function have been suggested in the literature \cite{Dar}\cite{Access}. 


A totally different replacement strategy suggested is to shrink
( reduce ) the region(s) in order to accommodate a new region in the cache. The
reasoanlyness being , if only some part of the region may be useful
in near future, it is better to keep only the useful part in the cache
instead of keeping the entire region . At the same time, by not throwing
the entire region , it tries to decrease the number of page faults due
to cache misses\cite{Dunham}.


\subsubsection{Cache coherency}

if the data at the server changes, the data at the client cache has to
be validated before use. simple validation scheme can be used based on
timestamps . the validation can take place at different granularity
depending on the application , and the frequency of updates at the
server. for an application which provides a map service, for example, the updates
will be very infrequent as compared to a stock ticker application ,
where updates are  quite frequent and at regular intervals.
also the validation can take place at client machine and at the
server. 




restriction of spatial queries : [12]
evaluation of continuous queries [ MOST 15 ]



\section{Semantic Query processing}

the issue of semantic query processing has been a widely researched topic in
the academic world. although the concept of semantic caches is pretty
straightforward, that is , storing the results of a query along with the
query itself,  the use of semantic caches to answer queries 
is a difficult problem and a rather daunting task.
in general there can be 4 cases to be dealt with 
\begin{itemize}
\item deciding when answers are in cache,
\item extracting answers from cache,
\item semantic overlap and semantic independence, and 
\item semantic remainder.
\end{itemize}

there are cases when the result of a query is present in the cache in
its entirety, but we do not have sufficient information to extract the
results from the cache. hence the distinction between the first and
the second.

 in this section we start with the concept of query folding . then we go on to address the
satisfiability and the containment problem involved with the query
processing . we then briefly explain the query trimming
technique and finally end this section by detailing the remainder query operation.


\subsection{query folding}

{ refer dunham }
query folding refers to the activity of determining if and how a query
can be answered using a given set of resources, which might be
materialized views ,cached results of previous queries, or queries
answerable by other databases. 

basically what we do is to try to rewrite a query by means of other
queries. the problem can be considered as an extension to the query
containment problem, to be discussed in the following section.
{cite } shows that the problem of finding rewritings that mention as
few of the database relations as possible is NP-complete for
conjunctive queries and resources.  there are two independent sources of
complexity in query folding : the first comes from the number of
possible mappings from the resources to the query, and the second is
to determine which parts of the query can be removed when the mapped
resources are added to the query { cite }

checking the satisfiability , equivalence or implication relationship
between the query and the set of derived relations is the first step
for query folding . Comparing a derived relation predicate P and a
query predicate Q, there are three scenarios :
\begin{itemize}
\item P and Q is unsatisfiable, implying the derived relation will not
  contribute to the answer of the query Q; 
\item $Q \longrightarrow P$ i.e. Q implies P, implying a the whole
  answer of Q is contained in the derived relation
\item Neither P contradicts Q nor Q implies P, implying that there may
  exist tuples in the derived relation that contribute to the answer of
  the query Q.
\end{itemize}
the satisfiability and implication problems have been studies
intensively in the literature { cite } . when the $\neq$ comparison
between variables is allowed , the problem becomes more difficult , or
even NP-hard in the integer domain.

\subsection{Query Trimming}
if a query Q can be partially answered by a semantic region S, it must
be divided into two parts : one that is satisfied by S and the other
part that cannot be satisfied. the unanswered part of the query is
sent to the server for processing. this entire operation is known as
query trimming. 
Basically query trimming is the process of dividing Q into two
sub queries:
Probe Query : which retrieves the portion of Q satisfied by S.
Remainder Query : which is sent to the server of r execution, and it
retrieves the portion of Q not found in S



\subsection{Coalesce and Decomposition}

once the remainder query is sent to the server and the answer is
obtained, we have three disjoint parts at our disposal. 
\begin{itemize}
\item the intersection of Q and S
\item the difference of S with respect to Q
\item the result Q` obtained from the execution of the remainder query
  at the server 
\end{itemize}

we have a number of options to choose from. 
\begin{itemize}
\item Complete coalesce : it reduces the number of semantic segments
  in cache, thus cache maintenance is decreased . in addition it aids
  in   queries processing  . but the price to be paid it that it may
  lead to the bigger and bigger segments leading to poor cache
  utilization 
\item no coalesce : keeps all the three segments separate. but it
  results in large number of semantic segments.
\item partial coalesce : to merge the new segment with either of the
  segments. this seems to me the most viable solution of the three.
\end{itemize}





Data security and replication .

Computing model

Push / pull




* semantic caching and containment ( special case ) :  contribution of this 
paper
data validation and transfer  : contribution of this paper



\section{ Future Directions }


\subsection{Handling Spatial Datasets} 

the above discussion assumes either relational or object oriented
database model with non-spatial data only.
also, the queries are assumed to be select, project and join queries
issued over non-spatial data stored in relational tables  


the entire query processing mechanism will be affected if spatial data is  taken into account, 
we can then consider the 9-intersection model for representing topological relationships
between two spatial objects in a 2D plane.
it would then be challenging to find out the exact relationship
between the cache entries and the new query, considering each of them
to be a spatial object .

\subsection{ Linear Constraint Model}
also to finitely represent infinite data points new models for representing spatial
data will have to be incorporated into the cache model. 

 employing the linear constraint model will guarantee that any
 first-order query can be evaluated in closed form; that is, the query
 result is a DNF quantifier-free formula. it can also be shown that
 the cost of this procedure is polynomial in terms of the size of the
 database. 


however , the representation with constrains present some limitations
. One of them is the necessity of representing spatial data as first
order formulas, which entails a non compact representation with
respect to the common vector data structures.  for instance , when
the DNF normal form is adopted , polygons need to be decomposed into
convex components in the database ( performing such a decomposition at
run tome would be prohibitively costly).

other more important shortcoming  arises from the limitation in the
expressive power of first-order queries . for example distance
operation cannot be expressed in the language because it involves the
use of  multiplication . {  refer SD book }

\subsection{Indexing Queries }
one other future direction is that of indexing cache entries, namely
the queries . the current research either completely ignores this
issue  or makes an over simplified assumption that the cache being  small,  the new query linearly
scans all the entries in the cache before  evaluation . 

the assumption may be true for current technology, but eventual
progress in hardware ( memory capacity , size and computing power )
will render this assumption false, and hence the need to find suitable
indexing structures to index queries. 


\subsection{Query Trimming}
most of the current research in query trimming assumes that semantic
segment in the cache is key-contained segment. 
it would be and interesting problem to relax this assumption and then
try to send the remainder query to the server, obtain the partial results and
join it to the results already present in the cache. 

\subsection{Data Security}


%\section{\bf References} 

\bibliographystyle{plain}
%\bibliography{mysurvey}

\begin{thebibliography}{9}


\bibitem{Egenhofer99}Michela Bertolotto, Max J. Egenhofer: Progressive Transmission of Vector Map Data over the World Wide Web. GeoInformatica 5(4): 345-373 (2001)


\bibitem{Duda}Xavier Delord and Stéphane Perret and Andrzej Duda, Efficient Mobile Access to the WWW over GSM,1998

\bibitem{Wireless}Wireless Application Protocol Architecture
  Specification, April 1998. http://www/wapforum.org.


\bibitem{Dar}Shaul Dar, Michael J. Franklin, Bjorn or Jonsson, Divesh Srivastava,
and Michael Tan. Semantic data caching and replacement,1996

\bibitem{Dunham}Ren, Q. and M. H. Dunham. Semantic Caching and Query Processing. Southern Methodist University, TR-98-CSE-04 , 1998. 

\bibitem{Ouri}A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Querying the Uncertain Position of Moving Objects, chapter Temporal Databases: Research and Practice, pages 310--337. Lecture Notes in Computer Science (Springer Verlag), 1998.

\bibitem{Godfrey}Parke Godfrey and Jarek Gryz, Answering Queries by
    Semantic Caches, Database and Expert Systems Applications,
    pages 485-498, 1999.

\bibitem{Basu}Arthur M. Keller and Julie Basu, " A Predicate-based Caching Scheme for Client-Server Database Architectures," in Third International Conference on Parallel and Distributed Information Systems, Austin, TX, September 1994 


\bibitem{Access}Arunas Stockus, Alain Bouju, Frederic Bertrand,
  Patrice Boursier, Accessing to Spatial Data in Mobile Environment,in
  the Second International Conference on Web Information Systems
  Engineering (WISE'01) Volume 2, December 2001.  
 

\end{thebibliography}

\end{document}