Learning Schemas for Unordered XML

Ciucanu, Radu; Staworko, Slawomir

Type de document :

Communication dans un congrès avec actes

Titre :

Learning Schemas for Unordered XML

Auteur(s) :

Ciucanu, Radu [Auteur correspondant]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Linking Dynamic Data [LINKS]
Staworko, Slawomir [Auteur]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Linking Dynamic Data [LINKS]

Titre de la manifestation scientifique :

14th International Symposium on Database Programming Languages (DBPL)

Ville :

Riva del Garda, Trento

Pays :

Italie

Date de début de la manifestation scientifique :

2013-08-30

Discipline(s) HAL :

Informatique [cs]/Base de données [cs.DB]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-00846809/document
Accès libre
Accéder au document

http://arxiv.org/pdf/1307.6348
Accès libre
Accéder au document

https://hal.inria.fr/hal-00846809/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

ciucanu-dbpl13.pdf
Accès libre
Accéder au document

1307.6348
Accès libre
Accéder au document

document
Accès libre
Accéder au document

ciucanu-dbpl13.pdf
Accès libre
Accéder au document

Learning Schemas for Unordered XML BibTeX CSV Excel RIS

Fichiers

Learning Schemas for Unordered XML

BibTeX

CSV

Excel

RIS