Example 1 - Formalization of Encoding

- Encoding of dom and its subsets is done by using the symbols 0 and 1.

- Let d Í dom and let a = {d₀, d₁,..d_i,...} be an enumeration of d.

- The encoding of d relative to a is the function enc_a which maps d_i to the binary representation of i (with no leading zeros) for each d_i Î d.

- enc_a(d_i) represents the encoding of d_i.

Given:

- d Í dom

- Enumeration a for d

- Target schema S

- Source schema R = {R₁, ..., R_m}. The encoding of instances of R uses the alphabet {0, 1, [, ], #} È R È {S}

An instance I over R with adom(I) Í d is encoded relative to a as follows:

1. enc_a(<a₁,...,a_k) is [enc_a(a₁)#...#enc_a(a_k)].

2. enc_a(I(R_i)), for R_i Î R, is R_i enc_a(t₁)...enc_a(t_l), where t₁,...,t_l are tuples in I(R_i) in the lexicographic order induced by the enumeration a.

3. enc_a(I) = enc_a(I(R₁))...enc_a(I(R_m))

Let R = {P, Q}, I be the following instance over R and let a = abc:

P :                        Q :

    a  b                    c  c

    b  a

Then enc_a(I) = P[0#1][1#0]Q[10#10].

Back    Table of content