License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-16762
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1676/
Go to the corresponding Portal


Anantharaman, Siva

Compression vs Queryability - A Case Study

pdf-format:
Document 1.pdf (154 KB)


Abstract

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.

BibTeX - Entry

@InProceedings{anantharaman:DSP:2008:1676,
  author =	{Siva Anantharaman},
  title =	{Compression vs Queryability - A Case Study},
  booktitle =	{Structure-Based Compression of Complex Massive Data },
  year =	{2008},
  editor =	{Stefan B{\"o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  number =	{08261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1676},
  annote =	{Keywords: Tree automata, Tree Grammars, Dags, XML documents, Queries}
}

Keywords: Tree automata, Tree Grammars, Dags, XML documents, Queries
Seminar: 08261 - Structure-Based Compression of Complex Massive Data
Issue Date: 2008
Date of publication: 20.11.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI