Transcript mobile computing and databases

Mobile Computing and Databases
(modified from ICDE98)
Margaret H. Dunham
Southern Methodist University
Dept of Computer Science and
Engineering
Dallas, Texas 75275
[email protected]
http://www.seas.smu.edu/~mhd
Outline
Introduction & Data Management Issues
Query Processing
Data Broadcasting
Transaction Processing
Projects & Products
Conclusion
2/24/98
ICDE/SMU - Dunham
2
Mobile Computing Architecture
2/24/98
ICDE/SMU - Dunham
3
Terminology
Fixed Network (FN)
Base Station (BS) (Mobile Support Station (MSS))
Fixed Hosts (FH)
Cell - Area covered by BS (1-2 miles)
Handoff - Changing BS by intercell move
Mobile Host (MH) (Mobile Unit (MU))
2/24/98
ICDE/SMU - Dunham
4
Wireless Networks
Cellular
High Cost
Scalability Issue
Limited Bandwidth: 10 Kbps
Wireless LAN
Traditional LANs with wireless interface
Low Cost
Limited range: 10-100 meters
Bandwidth: 10Mbps
NCR Wavelan,ICDE/SMU
Motorola
ALTAIR
2/24/98
- Dunham
5
Wireless Networks (cont’d)
Satellite Services
Wide Coverage
Very Expensive
Low Bandwidth: 1-2Mbps
Paging Networks
Wide Coverage
Sky Tel, Motorola
Slow: (Ethernet: 10Mbps; FDDI or switched
Ethernet: 100Mbps; ATM: 155Mbps)
Ad Hoc Networks
2/24/98
ICDE/SMU - Dunham
6
Handoff
Changing BS due to
movement between cells
State information
transferred
Current handoffs in
cellular phones may
take up to a few seconds with
breaks in conversation of 100-300 ms.
Soft - Temporarily connected to two BSs
Hard - Only connected to one BS
2/24/98
ICDE/SMU - Dunham
7
Location Management
Tracking mobile user
User associated with home
A
location server (Home Agent)
A
May augment by searching
in local
S
area first
M
May augment with user profiles
Mobile IP [11,14]
h
f
Triangle Routing
Route Optimization
Location Control (Routing Agent)
2/24/98
ICDE/SMU - Dunham
S
Ah
Af
M
8
Location Management (cont’d)
Active Badge (Cambridge,[2])
Track employees and route telephone calls
Unique code emitted every 15 seconds
Sensors placed in offices and corridors
Location Information Replications
No HLR
Hierarchy of Location Servers
Each server maintains information about its subtree
2/24/98
ICDE/SMU - Dunham
9
Mobile Applications
Information Services (Yellow Pages)
Law Enforcement and Medical Emergencies
Sales and Mobile Offices
Weather, Traffic, Sports, Entertainment
Trucking
Cellular Subscribers in the United States:
90,000 in 1984;4.4 million in 1990;
13 million in 1994
Handheld computer market will grow to $1.77
billion by 2002
2/24/98
ICDE/SMU - Dunham
10
Technology Push
Internet: ftp, telnet, email, http,html
Advancing Wireless Communication
Technologies
Laptop, Notebook, and Palmtop Computers
2/24/98
ICDE/SMU - Dunham
11
Classification of Mobile Database
Systems
2/24/98
ICDE/SMU - Dunham
12
Data Management Issues
Speed of wireless link
Scalability
Mobility
Location dependent data; Location specific
queries
Limited by battery power
Disconnection (Voluntary, Involuntary)
Replication/Caching
Handoff
2/24/98
ICDE/SMU - Dunham
13
Insurance Example
2/24/98
ICDE/SMU - Dunham
14
Medical Example
911 Call
Ambulance arrives/departs
Closest hospital
Access patient records
Send vital signs
Update patient records
Page hospital personnel
Order medical supplies
2/24/98
ICDE/SMU - Dunham
15
MC/DB Research
Transaction Processing
Caching - Replication
Broadcast Disks
Agents
Mobility
Location Dependent Data
Recovery
ACID (?)
2/24/98
ICDE/SMU - Dunham
16
Outline
Introduction & Data Management Issues
Query Processing
Location Dependent Queries and Data
New Query Types
Query Optimization
Data Broadcasting
Transaction Processing
Projects & Products
Conclusion
2/24/98
ICDE/SMU - Dunham
17
Location Dependent Data
Value of data depends on location
Temporal Replication - One consistent value at
one time
Spatial Replication - Multiple different correct
data values at one time
Temporal Consistency - All data objects satisfy a
given set of integrity constraints.
Spatial Consistency - Consistency constraints
satisfied within Data Region.
SMU/University of Missouri at Kansas City, [17]
2/24/98
ICDE/SMU - Dunham
18
Location Dependent Queries
Result depends on location
Different from traditional distributed goal of
location independence
Ex: Yellow Pages, Directions, Map
Predicates based on location: “Find the
cheapest hotel in Dallas.”
Location constraints: “Find the nearest hotel (to
me).”
2/24/98
ICDE/SMU - Dunham
19
Similarity to Spatial Queries
Spatial Data: Data associated with space
occupied by object.
Types of spatial queries: contains, contained in,
intersects, neighboring, east of, etc.
Spatial data structures
Spatial operators
Spatial selects and joins
PSQL - extend SQL, [18,20]
2/24/98
ICDE/SMU - Dunham
20
Differences from Spatial Queries
Client is actually moving
Location of client may be
Spatial data is dynamic
part of the query itself
May depend on direction of movement
Data may not directly contain location
information
Includes temporal features as well
2/24/98
ICDE/SMU - Dunham
21
Querying Moving Objects
Moving Objects Spatio-Temporal (MOST) data
model
Dynamic Attributes - Change over time
Queries over temporal history:
Instantaneous - Ex: “Find all restaurants I’ll reach in the
next half hour. ”
Continuous - Ex: “Find all restaurants within 5 miles.” The
answer continuously changes as the MU moves.
Persistent - Ex: “Find the cars that travel greater than 10
miles in the next half hour.”
Future Temporal Logic (FTL) language
University of Illinois, [20]
2/24/98
ICDE/SMU - Dunham
22
Query Optimization
How best to satisfy the information request
made by the client?
Different Cost Factors: I/O, network
Different Access Options: cache, FN, broadcast
Dynamic and Adaptable - environment changes
Alternative plans include deciding (based on
state of MH and environment) whether to
access in the cache at the MH, to request a
mobile transaction, or to obtain from a broadcast
disk.
2/24/98
ICDE/SMU - Dunham
23
Outline
Introduction & Data Management Issues
Query Processing
Data Broadcasting
Overview
Indexing
Research
Transaction Processing
Projects & Products
Conclusion
2/24/98
ICDE/SMU - Dunham
24
Data Broadcasting
Server continually broadcasts data to MUs.
Scalability: Cost does not depend on number of
users listening.
Mobile Unit may/may not have cache.
Facilitates data access during disconnected periods.
Allows location dependent data access.
No need to predict with 100% accuracy the future
data needs.
Broadcast based on probability of access.
Periodic broadcasting of all data.
2/24/98
ICDE/SMU - Dunham
25
Data Broadcasting (cont’d)
Classification:
Coverage - Everything, Subset
Content - Static, Dynamic
Indices - Index, Self Descriptive
Data Stream - Flat, Skewed, Multiple Disks
Client - Passive, Active
For uniform page access, flat disk has best
expected performance.
With skewed page access, nonflat disks are
better.
Push based.
2/24/98
ICDE/SMU - Dunham
26
Broadcast Disks
Simulate multiple
disks of varying
sizes and speeds.
Data of higher
interest on smaller
faster disks
Figure 4.1 from [15]
(broadcast more frequently).
Each “disk” contains data with similar access
behavior.
Combination of caching and broadcast disks.
2/24/98
ICDE/SMU - Dunham
27
Broadcast Disks (cont’d)
Don’t want to store hottest pages. They may be
broadcast frequently.
Store in cache if probability of access (P) is
greater than the frequency of broadcast (X).
Cost based page replacement.
Replace cache page with smallest P/X - PIX.
Too expensive to implement.
LIX - PIX approximation. Works well particularly
with noise.
Brown, MITL, Maryland, [37,38,39]
2/24/98
ICDE/SMU - Dunham
28
Air-Cache
Dynamic - Adapts to system workload.
Define temperature of data:
Vapor (Steamy) Hot - Accessed frequently
and broadcast.
Liquid Warm - Accessed often, not
broadcast, but kept in server’s main memory.
Frigid (Icy) Cold - Accessed infrequently and
stored on secondary storage.
2/24/98
ICDE/SMU - Dunham
29
Air-Cache (cont’d)
Three level memory hierarchy based on
temperature.
Sparks (access) to data can increase
temperature. No sparks, results in a reduction
of temperature.
Simulation results predict very good
performance.
Maryland, [43]
2/24/98
ICDE/SMU - Dunham
30
Adaptive Protocols
Dynamically modify broadcast contents.
Constant Broadcast Size (CBS) Server Protocol:
Limited size and periodic
Priority
Popularity Factor (PF)
Ignore Factore (IF)
Variable Broadcst Size (VBS) Server Protocol:
Aperiodic
All data above threshold PF included.
Arizona and UMKC, [40]
2/24/98
ICDE/SMU - Dunham
31
Outline
 Introduction & Data Management Issues
 Query Processing
 Data Broadcasting
 Transaction Processing
Overview
Transaction Model
Concurrency
Recovery
Research
 Projects & Products
 Conclusion
2/24/98
ICDE/SMU - Dunham
32
Mobile Transaction (MT)
Database transaction requested from a MU.
May execute in FN or MU
Issues
Disconnect/Handoff
Mobility
Location Dependent Data
Error Prone
MU Resources/ Power
Recovery/Restart
Management
2/24/98
ICDE/SMU - Dunham
33
MT Requirements
Keep autonomy of local DBMS
LLT
Interactive
Advanced transaction models
Nested
Multidatabase
Request from MU
Execute anywhere
Capture movement
ACID (?)
2/24/98
ICDE/SMU - Dunham
34
MT Approaches
No consensus on accepted approach
MU may not have primary copy of data [45]:
Transaction Proxy: MU does no transaction
processing
Read Only Transaction: MU only reads data
Weak Transaction: Read and update cached data;
Must synchronize updates with primary copy on FN.
MU may have primary copy of data
MU may access data on other MUs
First class and second class transactions
2/24/98
ICDE/SMU - Dunham
35
MT Recovery
Transaction, site, media, network failure - More
frequent than in wired network.
Different types of failures (partial)
Handoff
Voluntary disconnection
Battery problems
Lose computer??
Checkpoint data at MU to BS
Checkpoint at handoff
Database log plus transaction log
May
need compensating
transactions
2/24/98
ICDE/SMU - Dunham
36
Atomicity for MT
Weaken or provide different types of atomicity
May decompose transaction into
subtransactions
May require atomicity at lower than transaction
level
Atomic commitment difficult (expensive)
Global commit/Local Commit
2/24/98
ICDE/SMU - Dunham
37
Consistency for MT
Weakening isolation and atomicity may weaken
this as well.
May divide data into clusters with consistency
within clusters.
Reintegration of updates after reconnect may
cause many conflicts.
May use bounded inconsistency.
Impacted by location dependent data
2/24/98
ICDE/SMU - Dunham
38
Isolation for MT
May be too restrictive
Can’t always do at MU (disconnection)
Isolation at lower levels in transaction
Commitment at different levels of transaction
Cooperating transactions
2/24/98
ICDE/SMU - Dunham
39
Durability for MT
Durability for partial results
May want durability for parts of transactions.
Due to conflicts at reconnect, even durability of
subtransactions may not be guaranteed.
Local commit vs.. Global commit
2/24/98
ICDE/SMU - Dunham
40
MT Concurrency Control
Mobility of MUs
may increase
message traffic
for lock
management
MU failure may
leave some data
locked /unlocked
2/24/98
1) T1: Lock(Xa);
Read(Xa)
2) T1 moves to B
Server A
Cell A
Server B
Cell B
Xb
Yb
Xa
Ya
3) T1: Lock(Yb);
Read(Yb)
6) T1: Unlock(Yb);
Commit;
6) T1: Unlock(Xa);
Commit;
Fig 2 from [48]
ICDE/SMU - Dunham
Xc
Yc
Zc
Server C
Cell C
4) T1 moves to C
5) T1: Lock(Zc);
Write(Zc);
Unlock(Zc);
Commit
41
Revised Optimistic Locking
 O2PL-MT
 Read locks may be
executed at multiple
servers.
 Read unlock can be
executed at any site
 Benefit shown using
analytic model
 Purdue, [48]
2/24/98
LOCK
HELD
W_INTEND R_LOCK W_LOCK
LOCK
REQUEST
W_Intend No
Yes
No
R_Lock
No
Yes
No
W_Lock
No
No
No
Figure 3 from [48]
ICDE/SMU - Dunham
42
Kangaroo Transaction (KT)
Built on top of global transactions
Captures data and movement behavior
DAA as BS - Maintains logging and transaction
status
Logging at BS
Flexible atomicity
Restart after disconnect
Management moves
2/24/98
ICDE/SMU - Dunham
43
Kangaroo Transaction (cont’d)
Local Transaction - Sequence of read and write
operations ending in commit or abort
Global Transaction - Sequence of global or local
transactions
Joey Transaction - Sequence of global and local
transactions ending in commit, abort, or split
Kangaroo Transaction - Sequence of one or
more Joeys with last one ending in commit or
abort. All earlier end in split
SMU, [47]
2/24/98
ICDE/SMU - Dunham
44
KT and Movement
2/24/98
ICDE/SMU - Dunham
45
Reporting and Co-Transactions
Mobile transaction is a special type of
multidatabase transactions.
GDMS exists at each base station.
Subtransactions of the mobile transaction will
commit or abort independently.
Atomic and non-compensatable transactions.
Reporting and co-transactions.
Pittsburgh, [46]
2/24/98
ICDE/SMU - Dunham
46
Clustering Model
Views mobile transaction as beginning on
mobile and nonmobile hosts.
Transaction migration
Transaction model is designed to maintain
consistency of the database.
Database is divided into clusters.
Data is divided into core and quasi copies.
Mobile transactions and operations are
decomposed into a set of weak and strict
transactions.
2/24/98
ICDE/SMU - Dunham
47
Clustering Model (cont’d)
Weak operations access only data in the same
cluster. Strict operations allowed database wide
access. Two copies of data can be maintained
(strict and weak).
Clusters defined based on location and user
profile.
Transaction Proxy: dual transaction of one
executed at mobile host which includes only the
updates.
Purdue, [51,52]
2/24/98
ICDE/SMU - Dunham
48
Mobile Transactions and
Ambulatory Care
Medical Personal Digital Assistant (MPDA)
Battlefield - Cache copy of soldiers’ medical
records in MPDA
Distributed Medical Database - EMT obtains
patient’s medical record and updates.
BSA (Base Station Agent) is responsible for
logging and recovery.
Recovery based on sagas with save-points.
Mailboxes used to save information.
Purdue, [49,50]
2/24/98
ICDE/SMU - Dunham
49
Semantics-Based Mobile
Transaction Processing
Views mobile transaction processing as a
concurrency and cache coherency problem.
A stationary database server dishes out the
fragments of an object on a request from a
Mobile Unit.
On completion of the transaction, the Mobile
Units return the fragments to the server.
These fragments are put together again by the
merge operation at the server.
Pittsburgh, [54]
2/24/98
ICDE/SMU - Dunham
50
Multidatabase Transaction
Processing Manager
Mobile transactions built on top of multidatabase
global transactions.
Timestamps used to enforce ordering
Allows voluntary disconnections.
MU part of MDS
Message Queuing Facility (MQF)
MU sends request to designated coordinating
node on FN.
Monash, [56]
2/24/98
ICDE/SMU - Dunham
51
PRO-MOTION
MC/Database Transaction Processing approach
Multiple transaction types
Controlled divergence
ACID
Update cache and later DB at FH
Compact - Compact Agent at MU, Mobility
Manager at BS, Compact Manager at Server
Pittsburgh, [55]
2/24/98
ICDE/SMU - Dunham
52
MT Research Limitations
Architectural Assumptions
No support for location dependent data
Few Implementations
2/24/98
ICDE/SMU - Dunham
53
MT Management Options
MU
BS
Combination
Fixed/Relocatable/Moving
Agent
2/24/98
ICDE/SMU - Dunham
54
Outline
Introduction & Data Management Issues
Query Processing
Data Broadcasting
Transaction Processing
Projects & Products
Conclusion
2/24/98
ICDE/SMU - Dunham
55
Some DB/MC Projects URLs
 MobiDick - Monash Univ. (Australia);
http://www.ct.monash.edu.au/~mobidick
 Mobisaic - Univ. of Washington;
http://www.cs.washington.edu/homes/voelker/mobisaic
 Purdue; http://www.cs.purdue.edu/research/cse/mobile
 SMU; http://www.seas.smu.edu/~mhd/mobile.html
 MCC - Collaboration Managment Infrastructure;
http://www.mcc.com/projects/transaction
 University of Ioanina; http://zeus.cs.uoi.gr/
 Michigan - CITI;
http://www.citi.umich.edu/projects/mobile.html
 UCLA - Ficus; http://ficus-www.cs.ucla.edu/ficus
2/24/98
ICDE/SMU - Dunham

Columbia; http://www.mcl.cs.columbia.edu
56
Rover
 Figure 6.1 from [15]
2/24/98
ICDE/SMU - Dunham
57
Oracle Mobile Agent
Commercial Product
Application, Static,
Multiple
Message Manager - MU
Message Gateway - BS
Agent - FN (Server)
[67,69]
Message Manager
Gateway
Corporate
Network
Agent
Database Server
2/24/98
ICDE/SMU - Dunham
58
Sybase - SQL Anywhere
Designed for
Windows, (95, 3.x,
NT), OS/2, DOS
Limited memory
requirements
Full TP capabilities
Includes SQL Remote
Compatible with
Sybase SQL Server
[68]
2/24/98
ICDE/SMU - Dunham
Remote Database
SQL Anywhere standalone engine
Message agent
Consolidated Database
SQL Anywhere network server
Message agent
59
Sybase (cont’d) - SQL Remote
Two way replication based on
Consolidat
message passing.
ed
DB
Remote database are synchronized
with consolidated DB
Message Agent required at DB server
Replication of subscribed fragments
Remote Databases
Periodic changes sent from consolidated
DB to remote DBs
Updates from committed transactions at remote
submitted to consolidated database.
Conflicts:
Consolidated
is master; Triggers used. 60
2/24/98
ICDE/SMU - Dunham
Informix
I-Mobile 1.0 discontinued:
No replication
Three tier approach appropriate for long term, but in
the short term users wanted to be able to use
existing client-server applications (not rewrite).
Small DBMS server to run on mobile client
Only dial up needed for now
Informix Dynamic Server/Personal Edition
(IDS/PE) for Windows 95/NT. Mobiles and
desktop clients
[64,66]
2/24/98
ICDE/SMU - Dunham
61
Outline
Introduction & Data Management Issues
Query Processing
Data Broadcasting
Transaction Processing
Products
Conclusion
2/24/98
ICDE/SMU - Dunham
62
Future
Combine different approaches
Semantic caching
Query Optimization
Adaptive Data Broadcasting
Performance Benchmarks
Security
Location Dependent Queries
2/24/98
ICDE/SMU - Dunham
63
Acknowledgements and URL
Bibliographies
 Earlier version of this tutorial presented at the 1996
Brazilian Database Symposium.
 We particularly want to thank Evaggelia Pitoura for
providing several tables and figures from her recent
book [15].
 Some slide information obtained from slides presented
at a database class at the University of Massachusetts,
http://www-ccs.cs.umass.edu/mobile.
Online bibliographies
http://www.seas.smu.edu/~mhd/mobile.html
http://www.ct.monash.edu.au/~mobidick
2/24/98
ICDE/SMU - Dunham
64