Databases Reference
In-Depth Information
7 Data Structure
7.1 Virtual Primary Key
The structural information of the underlying data is taken into account in the
design of the various watermarking schemes. The schemes discussed above are
primarily designed for watermarking relational databases with primary keys.
The primary keys are used to seed a pseudo-random sequence generator or
hash function so as to generate non-correlated pseudo-random numbers for
different tuples in a database relation. In watermark insertion and detection,
the non-correlated pseudo-random numbers are used to select tuples and to
locate and determine watermark values. These techniques cannot be directly
applied to database relations without primary keys. Also, these techniques are
vulnerable to simple attacks that alter or delete the primary key attributes.
The previous watermarking techniques can be extended in two different
ways to address the primary key issues [14]. The first extension is to examine
each watermarkable attribute in each tuple independently in watermark in-
sertion and detection. For each attribute
r.A
i
in each tuple
r
, the bits of
r.A
i
are partitioned into two parts: (i)
mb
(
r.A
i
): the
ξ
least significant bits of
r.A
i
;
and (ii)
vpk
(
r.A
i
): the remaining most significant bits. The most significant
bit part
vpk
(
r.A
i
) is used as a virtual primary key to determine whether,
where, and how to embed a watermark bit to
r.A
i
in a similar way as in the
previous watermarking schemes.
However,
vpk
(
r.A
i
) is not a true primary key and may not be unique for
each value
r.A
i
. With duplicate virtual primary keys, some watermark bits
may be embedded fewer times than others, and some watermark bits may
not be embedded at all. Watermark detection may easily fail in the presence
of attacks if some of the watermark bits are embedded too few times due to
duplicate virtual primary keys.
The duplicate problem can be mitigated by selecting one attribute with
the fewest duplicates to provide the virtual primary keys for all tuples. More
generally, the virtual primary key can be constructed by combining most
significant bits from several attributes so as to minimize duplicates. To thwart
attribute deletion attacks, different attributes may be selected for different
tuples for constructing virtual primary keys. For example, one may choose to
construct a virtual primary key for tuple
r
by concatenating
k
(
k
≤
ν
)hash
values in
that are closest to zero
(hash values are interpreted as natural numbers when compared to zero).
{
HMAC
(
K
,vpk
(
r.A
i
)) :
i
=0
,...,ν
−
1
}
7.2 Data Cube
Data cube is a common data model that supports exploration of a large
amount of data in multiple dimensions. Conceptually, a cube consists of a
base cuboid, surrounded by a collection of aggregation cuboids that repre-
sent the aggregation of the base cuboid along one or more dimensions. In
