David Gross-Amblard (équipe Vertigo, laboratoire Cédric CNAM Paris)

Le tatouage, ou marquage (watermarking) permet l’insertion robuste et discrète d’information dans un document, comme par exemple l’identité de son propriétaire. De nombreuses techniques de marquage existent pour les documents multimédia comme l’image, le son ou la vidéo. Actuellement se développent des techniques permettant de marquer des données structurées.

Cet exposé présente un modèle de marquage pour les bases de données (relationnelles ou XML), où l’insertion d’information doit préserver la qualité d’un certain nombre de requêtes déclarées au préalable.

Nous montrerons qu’en général, les bases de données ne peuvent être marquées, et cela même contre des requêtes triviales. Ce resultat est en relation avec une notion combinatoire importante, la dimension de Vapnik et Chervonenkis.

Nous exhiberons ensuite plusieurs restrictions des instances de bases de données garantissant l’insertion d’une quantité d’information raisonnable, en preservant la qualite de n’importe quelle requête définie dans un langage donné :

  • les instances dont le graphe a un degré borné, en préservant n’importe quelle requête dans un langage dit “local”. Des exemples de langages locaux sont la logique du premier ordre ou le très populaire langage SQL.
  • les instances ayant une largeur d’arbre bornée, en préservant n’importe quelle requête monadique du second ordre. Ce langage est important car il sert de fondement théorique aux langages pratiques d’interrogation des documents XML.

Ces restrictions sont, dans un certain sens, optimales.