Title :

Schema Validation via Streaming Circuits

Author(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]

Conference title :

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

City :

San Francisco, CA

Country :

Etats-Unis d'Amérique

Start date of the conference :

2016

Book title :

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

Publisher :

ACM

Publication date :

2016

English keyword(s) :

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

HAL domain(s) :

Informatique [cs]

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL