Extraction :

Synchronous Asynchronous

Snapshot = complete current dataset each time.

Differential Snapshot Problem

A sequence of change operations is defined as

where:

  • = insert
  • = delete
  • = update
  • is a sequence of change operations

Applying the sequence to an initial state produces a new state :

For example,

means that we perform these operations in order:

Applying all these operations to transforms it into .

Find the smallest possible sequence such that


The Algorithms for solving the Differential Snapshot Problem differ mainly in how much main memory MM is available and how much disk I/O they require.

Difference Snapshot Algorithms

The goal of all algorithms is to compute the smallest sequence of change operations that transforms snapshot into snapshot :

with

Let

and let denote the amount of available main memory.


: Nested Loops

For every record , scan the entire looking for a record with the same key.

Take R from F1
      ↓
Scan all of F2
      ↓
Same key found?

If no matching key exists:

because the record existed in but disappeared from .

If the key exists:

Same key + same attributes
        β†’ unchanged β†’ ignore
 
Same key + different attributes
        β†’ UPDATE

Finding INSERTs

Scanning records from naturally finds deletes and updates, but it cannot directly find records that exist only in .

Therefore, matched records in must be marked.

After the comparison:

Unmarked record in F2
        ↓
      INSERT

Example:

F1 = {K1, K2, K4}
F2 = {K1, K2, K3}

Comparison:

K1 β†’ unchanged
K2 β†’ unchanged
K4 β†’ DEL(K4)

Final scan of :

K3 was never matched
β†’ INS(K3)

Cost

where is the cost of writing the resulting change sequence.

Improvement

Instead of processing one record at a time, load records from into memory.

M records from F1
        ↓
One scan through F2

The cost becomes approximately

instead of

.


: Small Snapshot

Use this method when one entire snapshot fits into main memory.

Assume, for example,

Load the complete into RAM.

RAM
β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚ Entire F1   β”‚
β”‚ K1          β”‚
β”‚ K2          β”‚
β”‚ K4          β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

Then scan once.

For each :

S exists in F1?
      β”‚
      β”œβ”€β”€ Yes β†’ compare attributes
      β”‚          β”œβ”€β”€ same      β†’ ignore
      β”‚          └── different β†’ UPD(S)
      β”‚
      └── No  β†’ INS(S)

Whenever a matching record is found, mark the corresponding record in .

After scanning , any unmarked record in must have been deleted:

Example

F1 = {K1, K2, K4}
F2 = {K1, K2, K3}

Load into RAM.

K1 β†’ found β†’ unchanged
K2 β†’ found β†’ unchanged
K3 β†’ not found β†’ INS(K3)

Afterwards:

K4 is still unmarked
β†’ DEL(K4)

Cost

Each snapshot is essentially read once:

An efficient in-memory structure such as a hash table or a sorted structure can be used for fast key lookup.


: Sort-Merge

Neither snapshot fits into memory:

and

The idea is to sort both snapshots by key and then scan them simultaneously.

Example:

F1 sorted       F2 sorted
 
K1              K1
K4              K3
K7              K7
K10             K10

Use two pointers.

Initially:

F1          F2
K1    ↔     K1

Equal keys:

so compare their attributes.

Then:

F1          F2
K4          K3

Since

can only occur in .

Therefore,

Advance the pointer:

F1          F2
K4          K7

Now,

so exists only in :

Thus, after sorting, the two files can be compared with a single sequential merge scan.

External Sorting

Large files that do not fit into RAM are sorted using external merge sort.

Split the file into partitions:

where approximately

For every partition:

Read M records
      ↓
Sort in RAM
      ↓
Write sorted run to disk

Example:

Run 1: K1 K8 K20
Run 2: K2 K5 K30
Run 3: K3 K9 K11

Then merge the runs:

K1 K2 K3 K5 K8 K9 K11 K20 K30

Once today’s has been sorted, keep the sorted version.

For the next difference snapshot:

Therefore, tomorrow’s old snapshot is already sorted.

Only the new must be sorted.


: Interleaving

improves the ordinary sort-merge method.

Normally:

Sort F2
   ↓
Write sorted F2
   ↓
Read sorted F2 again
   ↓
Compare with sorted F1

With interleaving, the final merge of and the comparison with happen simultaneously:

F2 sorted runs
      ↓
Final merge
      +
Compare with sorted F1
      ↓
Generate INS / DEL / UPD

Therefore, the completely merged does not need to be written and then read again merely for comparison.

The approximate cost is

Under the memory condition

this can simplify approximately to

Interleaving combines the last merge phase with difference detection, reducing additional disk I/O.


: Partitioned Hashing

Instead of sorting records, divide them into partitions using a hash function.

For example,

This creates partitions such as

with

so every key belongs to exactly one partition.

Apply the same hash function to both and .

Example:

F1                      F2
 
P0: K3 K9               P0: K3 K12
P1: K1 K7               P1: K1 K7
P2: K2 K5               P2: K2 K8

Now only corresponding partitions need to be compared:

F1.P0 ↔ F2.P0
F1.P1 ↔ F2.P1
F1.P2 ↔ F2.P2

Because the same hash function is used, a key placed in in must also be placed in in .

So instead of searching the whole file, we only compare a much smaller matching partition.

The partitions are chosen so that they can be processed efficiently in memory.

The approximate cost is

which is much closer to linear processing than the naive

approach.


AlgorithmMain ideaMemory conditionApproximate cost
Compare each record with Very little memory
Keep one entire snapshot in RAM or
Sort by key and mergeFiles may exceed RAMExternal-sort cost
Merge and compare simultaneouslyFiles may exceed RAMLess I/O than
Hash into matching partitionsEach working partition fits RAM