Titre :

Schema Validation via Streaming Circuits

Auteur(s) :

Murlak, Filip [Auteur]
University of Warsaw [UW]
Paperman, Charles [Auteur]
University of Warsaw [UW]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Pilipczuk, Michał [Auteur]
University of Warsaw [UW]

Titre de la manifestation scientifique :

35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS '16)

Ville :

San Francisco, CA

Pays :

Etats-Unis d'Amérique

Date de début de la manifestation scientifique :

2016

Titre de l’ouvrage :

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - PODS '16

Éditeur :

ACM

Date de publication :

2016

Mot(s)-clé(s) en anglais :

semi-structured data
XML
streaming
schema validation
Boolean circuits
nested-relational DTDs

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [en]

XML schema validation can be performed in constant memory in the streaming model if and only if the schema admits only trees of bounded depth - an acceptable assumption from the practical view-point. In this paper we refine ...
Lire la suite >XML schema validation can be performed in constant memory in the streaming model if and only if the schema admits only trees of bounded depth - an acceptable assumption from the practical view-point. In this paper we refine this analysis by taking into account that data can be streamed block-by-block, rather then letter-by-letter, which provides opportunities to speed up the computation by parallelizing the processing of each block. For this purpose we introduce the model of streaming circuits, which process words of arbitrary length in blocks of fixed size, passing constant amount of information between blocks. This model allows us to transfer fundamental results about the circuit complexity of regular languages to the setting of streaming schema validation, which leads to effective constructions of streaming circuits of depth logarithmic in the block size, or even constant under certain assumptions on the input schema. For nested-relational DTDs, a practically motivated class of bounded-depth XML schemas, we provide an efficient construction yielding constant-depth streaming circuits with particularly good parameters.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