Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Mobile databases and caching

Overview of mobile databases and caching: architectures, disconnected operation, replication and consistency models, caching techniques (semantic caching, invalidation, replacement), and transaction reconciliation for mobile environments.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Mobile devices are often disconnected, have limited bandwidth, and limited battery. Engineers use mobile databases and caching to let mobile apps work correctly and quickly when the network is slow or absent, to reduce server load, and to save energy.

Key ideas

  • Mobile database: a database or a portion of it stored on a mobile host to support local data access and updates when disconnected. It often supports special transaction and replication protocols.
  • Transaction: a sequence of read/write operations on a database that should satisfy ACID properties: Atomicity (all or nothing), Consistency (database moves from one valid state to another), Isolation (concurrent transactions do not interfere), Durability (once committed, changes persist). In mobile settings full ACID is often relaxed.

Mobile constraints and consequences

  • Limited, variable bandwidth and high latency mean many standard distributed-database protocols (e.g., two-phase commit) perform poorly. Designers therefore prefer optimistic approaches and local caching.
  • Frequent disconnection requires support for disconnected operation: the mobile client must continue to read and update local data while offline, and later reconcile with the server.

Replication and reconciliation

  • Replication: copying data to multiple nodes. Define primary-copy replication (one primary, many replicas) and update-anywhere (multi-master, optimistic replication).
  • Pessimistic replication: avoid conflicts by restricting updates (lock on server). Not suitable for long disconnections.
  • Optimistic replication: allow updates at replicas while disconnected; reconcile later and detect/resolve conflicts.
  • Conflict detection: find concurrent updates to the same data item. Techniques: version numbers, timestamps, vector clocks.
  • Conflict resolution: automatic (last-writer-wins by timestamp, merge functions) or application-driven (human review, domain-specific merge).

Consistency models

  • Strong consistency: every read sees the latest write as if there were a single, up-to-date copy (linearizability/single-copy-serializability). Hard to provide with mobile disconnection.
  • Weak consistency: no guarantee of immediate visibility; useful in mobile settings.
  • Eventual consistency: if no new updates occur, all replicas converge eventually.
  • Cache coherency: keeping caches up-to-date. Techniques include push-based invalidation (server sends invalidation reports) and pull-based validation (client checks before use).

Caching strategies

  • Client-side caching: data cached on the mobile host for fast local access.
  • Semantic cache: cache stores results of previous queries with their semantic description (e.g., SELECT * FROM Patients WHERE age>60). A new query can be answered from cached query results if the semantics imply it (query containment). Semantic description: a logical predicate over the schema that exactly characterizes the cached result set (e.g., age>60). Query containment: for queries Q1 and Q2 over the same schema, Q2 is contained in Q1 (Q2 ⊆ Q1) if for all database instances, Answers(Q2) ⊆ Answers(Q1); if so, Q2 can be answered by filtering Q1’s cached result.
  • Cache replacement policies: LRU (least recently used), LFU (least frequently used), FIFO. In mobile systems, cost-aware replacement (considering network cost and update cost) is common.
  • Prefetching: proactively fetching data predicted to be needed soon (based on movement, usage patterns).
  • Invalidation reports (IR): server periodically broadcasts IDs of updated/invalidated objects so clients can invalidate their caches.

Mobile transaction models

  • Disconnected transaction: starts on client, executes locally, and commits locally; then a reconciliation phase attempts to commit at server.
  • Tentative updates: local updates marked tentative; final commit after reconciliation.
  • Deferred update: client buffers updates and applies at server during reconnection.

Diagrams to draw (describe exactly):

  1. Client-server mobile transaction flow: draw two boxes labelled "Mobile Host (Client)" on the left and "Fixed Host (Server)" on the right. Between them draw arrows labelled: "(1) Initial fetch / cache fill", "(2) Local updates while disconnected", "(3) Reconnect and send updates (reconciliation)", "(4) Conflict resolution and final commit". Under the client box list: local database, transaction manager, cache. Under the server box list: DBMS, version store, invalidation service.
  2. Semantic cache containment diagram: draw a rectangle labelled "Cached Query Result: Q1: SELECT * FROM R WHERE A>10" and another rectangle labelled "New Query Q2: SELECT * FROM R WHERE A>20". Show an arrow or logic that Q2 is contained in Q1 (explain: A>20 implies A>10). Label the containment and mention necessity to check predicate overlap.

Assumptions commonly used in derivations/exams

  • When deriving formulae for response time, assume independence of hits/misses and fixed average times for local access, network latency, and server access.
  • When tracing optimistic reconciliation, assume unique timestamps or monotonically increasing version numbers, and synchronized clocks if using physical timestamps for ordering.

Formulas

HitRatio H = hits / (hits + misses) — H is unitless (fraction between 0 and 1). Applies to any cache. MissRatio M = 1 - H — unitless. AverageResponseTime R = H * T_local + M * (T_network + T_server) — R, T_local, T_network, T_server in seconds. Assumes independent hit/miss and constant times. MaxAgeAtUse (TTL caching) <= TTL — TTL (time-to-live) in seconds; this holds when the client serves a cached item only while (now − fetch_time) <= TTL and refreshes on expiry. Staleness (time since last server update at read) <= TTL under synchronized clocks and negligible propagation delay; otherwise add propagation delay/clock skew to the bound. EffectiveBandwidthUsage = RequestRate * M * RequestSize — bytes per second, where RequestRate is requests/sec, M is miss ratio, and RequestSize is bytes per miss. For N requests in time T: EffectiveBandwidthUsage = (N * M * RequestSize) / T.

Syntax to remember (for SQL and cache queries):

  • SQL predicate form: SELECT <cols> FROM <table> WHERE <predicate>.
  • Semantic cache entry: store tuple (QueryText, ResultSet, Timestamp, ValidUntil).

Worked examples

Example 1 — Cache hit ratio and average response time Data: mobile app made 1000 data attempts in 1 hour, with 720 hits and 280 misses. Times: local access T_local = 5 ms (0.005 s), network latency + server access T_network + T_server = 300 ms (0.3 s). Compute: 1) Hit ratio H = hits / (hits + misses) = 720 / 1000 = 0.72. 2) Miss ratio M = 0.28. 3) Average response time R = HT_local + M(T_network+T_server) = 0.720.005 + 0.280.3 = 0.0036 + 0.084 = 0.0876 s = 87.6 ms. Answer: Hit ratio = 0.72; Average response time = 87.6 ms. (Units checked: multiply fractions by seconds → seconds; converted to ms for readability.)

Example 2 — Optimistic replication conflict detection and resolution (trace) Scenario: Record X has initial value v0 on server with timestamp ts0 = 100. Two mobile clients A and B disconnect and update X:

  • Client A updates X to vA at local time ta = 200, assigns tsA = 200.
  • Client B updates X to vB at local time tb = 250, assigns tsB = 250. Reconnection order: A syncs first, then B. Trace steps:
  1. A sends update (X = vA, tsA = 200). Server compares stored ts0=100 < 200 => accept update. Server sets X = vA, server timestamp = 200.
  2. B sends update (X = vB, tsB = 250). Server sees server timestamp 200 < 250 => accept update. Final server X = vB, timestamp = 250. Conflict detection: both updated concurrently (since both created updates while disconnected from each other). Resolution used: last-writer-wins by timestamp. Final value is vB. If instead a merge function is required (application-specific), the server would invoke merge(vA, vB) and apply that result.

Example 3 — Semantic cache use (short) Cache contains result for Q1: SELECT * FROM Orders WHERE amount > 1000 (contains rows where amount >1000). New query Q2: SELECT * FROM Orders WHERE amount > 2000. Containment reasoning: predicate amount>2000 implies amount>1000, so every tuple satisfying Q2 is in Q1. Therefore Q2 can be answered entirely from cached Q1 (filter cached rows for amount>2000) if cache is up-to-date. If cached data may be stale, verify with invalidation or timestamp. Answer: Q2 can be answered from cache if data is valid.

Common mistakes

  • Forgetting to check validity/invalidation when answering from cache (leading to stale reads).
  • Thinking last-writer-wins always correct — it is simple but may lose important updates; mention application-driven merges.
  • Not carrying units in response-time calculations (ms vs s).

For your exam

Question types produced by this topic: definition questions (define semantic cache, optimistic replication), short notes (compare optimistic vs pessimistic replication), diagram questions (draw client-server reconciliation flow), derivations (derive average response time using hit/miss), numeric problems (compute hit ratio, response time), algorithm trace (simulate reconciliation), and small programs/pseudocode (cache replacement policy). What a full-marks answer includes:

  • Clear definitions of terms used (e.g., mobile host, replication, reconciliation).
  • A labelled diagram when asked; follow the diagram descriptions above. Diagrams should show components and message flow.
  • Statement of assumptions (e.g., constant access times) before deriving formulas.
  • Units on numeric answers and step-by-step calculation.
  • Discussion of trade-offs (latency vs consistency, energy vs freshness) and an indication of when each technique is appropriate.

Quick check

  1. What is semantic caching? 2) Give the formula for cache hit ratio. 3) Name two conflict resolution strategies used in optimistic replication. Answers: Semantic caching stores previous query results plus their query predicates and uses query containment to answer new queries; H = hits / (hits + misses); strategies include last-writer-wins (timestamp) and application-specific merge/human reconciliation.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?