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
β
INSERTExample:
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 F2The 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 K10Use two pointers.
Initially:
F1 F2
K1 β K1Equal keys:
so compare their attributes.
Then:
F1 F2
K4 K3Since
can only occur in .
Therefore,
Advance the pointer:
F1 F2
K4 K7Now,
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 diskExample:
Run 1: K1 K8 K20
Run 2: K2 K5 K30
Run 3: K3 K9 K11Then merge the runs:
K1 K2 K3 K5 K8 K9 K11 K20 K30Once 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 F1With interleaving, the final merge of and the comparison with happen simultaneously:
F2 sorted runs
β
Final merge
+
Compare with sorted F1
β
Generate INS / DEL / UPDTherefore, 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 K8Now only corresponding partitions need to be compared:
F1.P0 β F2.P0
F1.P1 β F2.P1
F1.P2 β F2.P2Because 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.
| Algorithm | Main idea | Memory condition | Approximate cost |
|---|---|---|---|
| Compare each record with | Very little memory | ||
| Keep one entire snapshot in RAM | or | ||
| Sort by key and merge | Files may exceed RAM | External-sort cost | |
| Merge and compare simultaneously | Files may exceed RAM | Less I/O than | |
| Hash into matching partitions | Each working partition fits RAM |