License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08261.8
URN: urn:nbn:de:0030-drops-16762
Go to the corresponding Portal

Anantharaman, Siva

Compression vs Queryability - A Case Study

08261.AnantharamanSiva.Paper.1676.pdf (0.2 MB)


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

  author =	{Anantharaman, Siva},
  title =	{{Compression vs Queryability - A Case Study}},
  booktitle =	{Structure-Based Compression of Complex Massive Data},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8261},
  editor =	{Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-16762},
  doi =		{10.4230/DagSemProc.08261.8},
  annote =	{Keywords: Tree automata, Tree Grammars, Dags, XML documents, Queries}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI