Learning Schemas for Unordered XML

Radu Ciucanu 1, 2, * Slawomir Staworko 1, 2
* Auteur correspondant
1 LINKS - Linking Dynamic Data
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We consider unordered XML, where the relative order among siblings is ignored, and we investigate the problem of learning schemas from examples given by the user. We focus on disjunctive multiplicity schemas (DMS) and its restriction, disjunction-free multiplicity schemas (MS). A learning algorithm takes as input a set of XML documents which must satisfy the schema (i.e., positive examples) and a set of XML documents which must not satisfy the schema (i.e., negative examples), and returns a schema consistent with the examples. We investigate a learning framework inspired by Gold, where a learning algorithm should be sound i.e., always return a schema consistent with the examples given by the user, and complete i.e., able to produce every schema with a sufficiently rich set of examples. Additionally, the algorithm should be efficient i.e., polynomial in the size of the input. We prove that the DMS are learnable from positive examples only, but they are not learnable when we also allow negative examples. Moreover, we show that the MS are learnable in the presence of positive examples only, and also in the presence of both positive and negative examples. Furthermore, for the learnable cases, the proposed learning algorithms return minimal schemas consistent with the examples.
Type de document :
Communication dans un congrès
14th International Symposium on Database Programming Languages (DBPL), Aug 2013, Riva del Garda, Trento, Italy. 〈http://dbpl2013.inria.fr/〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00846809
Contributeur : Radu Ciucanu <>
Soumis le : jeudi 7 mai 2015 - 17:16:35
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27
Document(s) archivé(s) le : mercredi 19 avril 2017 - 19:27:53

Fichier

ciucanu-dbpl13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00846809, version 1
  • ARXIV : 1307.6348

Citation

Radu Ciucanu, Slawomir Staworko. Learning Schemas for Unordered XML. 14th International Symposium on Database Programming Languages (DBPL), Aug 2013, Riva del Garda, Trento, Italy. 〈http://dbpl2013.inria.fr/〉. 〈hal-00846809〉

Partager

Métriques

Consultations de la notice

190

Téléchargements de fichiers

70