Databases Reference
In-Depth Information
is claimed fragile enough to be impacted by even minor alterations to the data
with reasonable probabilities. Additionally, the encoding can pinpoint at the
exact location of the alteration with the granularity of a subset.
Compared with traditional authentication techniques (e.g., appending sig-
natures of MACs) such a technique can become of relevance, e.g., when the
overhead of storing and managing the signatures or MACs for a large number
of entities is not negligible. This is why it is important to further explore and
understand fragile watermarking scenarios. This work is discussed in more
detail elsewhere in this topic.
5.4 Query Learnability and Consumer-Driven Watermarking
In [12] Gross-Amblard introduce interesting theoretical results investigating
alterations to relational data (or associated XML) in a consumer-driven frame-
work in which a set of parametric queries are to be preserved up to an accept-
able level of distortion.
The author first shows that the main diculty preserving such queries
“is linked to the informational complexity of sets defined by queries, rather
than their computational complexity” [12]. Roughly speaking, if the family
of sets defined by the queries is not
learnable
[37], no query-preserving data
alteration scheme can be designed.
In a second result, the author shows that under certain assumptions (i.e.,
query sets defined by first-order logic and monadic second order logic on
restricted classes of structures - with a bounded degree for the Gaifman graph
or the tree-width of the structure) a query-preserving data alteration scheme
exists.
This research is important as it has the potential to enable a better under-
standing of consumer-driven watermarking designs. For example, as database
instances are often having a bounded degree Gaifman graph (or a bounded
tree-width), these can now be measured and the information capacity of a
query-preserving alteration channel can be computed. This is of interest in
the case of extremely restrictive constraints, e.g., when it is not clear if wa-
termarking can yield enough resilience.
6 State of The Art and the Future
Watermarking in relational frameworks is a relatively young technology that
has begun its maturity cycle towards full deployment in industry-level ap-
plications. Many of the solutions discussed above have been prototyped and
validated on real data. Patents have been filed for several of them, including
Agrawal et.al. [1, 16] and Sion et.al. [29, 30, 32, 33] [34] [25, 27, 36]. In the next
few years we expect these solutions to become available commercially, tightly
integrated within existing DBMS (e.g., DB2 [10]) or as stand-alone packages
that can be deployed simultaneously on top of multiple data types and sources.
