Characterizing XML Twig Queries with Examples

Slawomir Staworko 1, 2 Piotr Wieczorek 3
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Typically, a (Boolean) query is a finite formula that defines a possibly infinite set of database instances that satisfy it (positive examples), and implicitly, the set of instances that do not satisfy the query (negative examples). We investigate the following natural question: for a given class of queries, is it possible to characterize every query with a finite set of positive and negative examples that no other query is consistent with. We study this question for twig queries and XML databases. We show that while twig queries are characterizable, they generally require exponential sets of examples. Consequently, we focus on a practical subclass of anchored twig queries and show that not only are they characterizable but also with polynomially-sized sets of examples. This result is obtained with the use of generalization operations on twig queries, whose application to an anchored twig query yields a properly contained and minimally different query. Our results illustrate further interesting and strong connections between the structure and the semantics of anchored twig queries that the class of arbitrary twig queries does not enjoy. Finally, we show that the class of unions of twig queries is not characterizable.
Type de document :
Communication dans un congrès
International Conference on Database Theory, Mar 2015, Brussels, Belgium. International Conference on Database Theory, 2015, International Conference on Database Theory
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01205417
Contributeur : Slawomir Staworko <>
Soumis le : vendredi 25 septembre 2015 - 14:35:45
Dernière modification le : vendredi 13 avril 2018 - 01:26:58
Document(s) archivé(s) le : mardi 29 décembre 2015 - 10:02:59

Fichier

staworko-icdt15b.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Domaine public

Identifiants

  • HAL Id : hal-01205417, version 1

Collections

Citation

Slawomir Staworko, Piotr Wieczorek. Characterizing XML Twig Queries with Examples. International Conference on Database Theory, Mar 2015, Brussels, Belgium. International Conference on Database Theory, 2015, International Conference on Database Theory. 〈hal-01205417〉

Partager

Métriques

Consultations de la notice

136

Téléchargements de fichiers

73