Abstract
This thesis investigates a pragmatic approach to typing, static analysis and static optimization of Web query languages, in special the Web query language Xcerpt[43]. The approach is pragmatic in the sense, that no restriction on the types are made for decidability or efficiency reasons, instead precision is given up if necessary. Pragmatics on the dynamic side means to use types not only to ensure validity of objects operating on, but also influencing query selection based on types. A typing language for typing of graph structured data on the Web is introduced. The Graphs in mind are based on spanning trees with references, the typing languages is based on regular tree grammars [37, 38] with typed reference extensions. Beside ordered data in the spirit of XML, unordered data (i.e. in the spirit of the Xcerpt data model or RDF) can be modelled using regular expressions under unordered interpretation - this approach is new. An operational semantics for ordered and unordered types is given based on specialized regular tree automata[21] and counting constraints[67] (them again based on Presburger arithmetic formulae). Static type checking of Xcerpt query and construct terms is introduced, as well as optimization of Xcerpt query terms based on schema information.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-020

BibTeX:

@article{REWERSE-RP-2008-020,
	author = {Sacha Berger},
	title = {Regular Rooted Graph Grammars - A Web Type and Schema Language},
	journal = {},
	year = {2008},
	note = {PhD Thesis, Institute for Informatics, University of Munich, February 2008},
	url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2008-020}
}