2026-08-14T23:52:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1676 2024-03-06T11:08:10Z ddc:004 open_access

Compression vs Queryability - A Case Study Anantharaman, Siva Tree automata Tree Grammars Dags XML documents Queries Some compromise on compression is known to be necessary, if the relative positions of the information stored by semi-structured documents are to remain accessible under queries. With this in view, we compare, on an example, the ‘query-friendliness’ of XML documents, when compressed into straightline tree grammars which are either regular or context-free. The queries considered are in a limited fragment of XPath, corresponding to a type of patterns; each such query defines naturally a non-deterministic, bottom-up ‘query automaton’ that runs just as well on a tree as on its compressed dag. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siva Anantharaman 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08261.8 urn:nbn:de:0030-drops-16762 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.8 eng https://creativecommons.org/licenses/by/4.0/legalcode