Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 25 Mars 2003

Tatouage de bases de donnees et de documents XML, tout en preservant des requetes

par 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é :

Ces restrictions sont, dans un certain sens, optimales.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr