Stackless Processing of Streamed Trees
Type de document :
Communication dans un congrès avec actes
DOI :
Titre :
Stackless Processing of Streamed Trees
Auteur(s) :
Barloy, Corentin [Auteur]
Linking Dynamic Data [LINKS]
Murlak, Filip [Auteur]
University of Warsaw [UW]
Paperman, Charles [Auteur]
Linking Dynamic Data [LINKS]
Linking Dynamic Data [LINKS]
Murlak, Filip [Auteur]
University of Warsaw [UW]
Paperman, Charles [Auteur]
Linking Dynamic Data [LINKS]
Titre de la manifestation scientifique :
PODS 2021 - Symposium on Principles of Database Systems
Ville :
Xi'an, Shaanx
Pays :
Chine
Date de début de la manifestation scientifique :
2021-06-20
Titre de la revue :
Proceedings of the Symposium on Principles of Database Systems, PODS 2021
Mot(s)-clé(s) en anglais :
weak validation
automata
JSON
XML
querying
streaming
phrases streaming
automata
JSON
XML
querying
streaming
phrases streaming
Discipline(s) HAL :
Informatique [cs]/Base de données [cs.DB]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Traitement du texte et du document
Informatique [cs]/Logique en informatique [cs.LO]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Traitement du texte et du document
Informatique [cs]/Logique en informatique [cs.LO]
Résumé en anglais : [en]
Processing tree-structured data in the streaming model is a challenge: capturing regular properties of streamed trees by means of a stack is costly in memory, but falling back to finite-state automata drastically limits ...
Lire la suite >Processing tree-structured data in the streaming model is a challenge: capturing regular properties of streamed trees by means of a stack is costly in memory, but falling back to finite-state automata drastically limits the computational power. We propose an intermediate stackless model based on register automata equipped with a single counter, used to maintain the current depth in the tree. We explore the power of this model to validate and query streamed trees. Our main result is an effective characterization of regular path queries (RPQs) that can be evaluated stacklessly-with and without registers. In particular, we confirm the conjectured characterization of tree languages defined by DTDs that are recognizable without registers, by Segoufin and Vianu (2002), in the special case of tree languages defined by means of an RPQ.Lire moins >
Lire la suite >Processing tree-structured data in the streaming model is a challenge: capturing regular properties of streamed trees by means of a stack is costly in memory, but falling back to finite-state automata drastically limits the computational power. We propose an intermediate stackless model based on register automata equipped with a single counter, used to maintain the current depth in the tree. We explore the power of this model to validate and query streamed trees. Our main result is an effective characterization of regular path queries (RPQs) that can be evaluated stacklessly-with and without registers. In particular, we confirm the conjectured characterization of tree languages defined by DTDs that are recognizable without registers, by Segoufin and Vianu (2002), in the special case of tree languages defined by means of an RPQ.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-03021960/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03021960/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03021960/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- main_single.pdf
- Accès libre
- Accéder au document