Saarland University Database Group
Lehrstuhl für Informationssysteme
Prof. Christoph Koch
Universität des Saarlandes
Fachrichtung 6.2 - Informatik
D-66041 Saarbrücken, Germany
Building 36.1, 2nd floor
Talk Announcement
Composition-free XQuery
Speaker: Christoph Koch
Abstract:
Nonrecursive XQuery is known to be hard for nondeterministic
exponential time. Thus it is commonly believed that any
algorithm for evaluating queries of that language
has to require exponential amounts of
working memory and doubly exponential time in the worst case. In this
paper we present a property -- the lack of a certain form of
composition -- that virtually all real-world XQueries have and that
allows for query evaluation in singly exponential time and polynomial
space.
Still, we are able to show for an important special case --
our nonrecursive XQuery fragment
using only atomic value equality --
that the composition-free language is just as expressive as the language
with composition. Thus, under the usual complexity-theoretic assumptions,
the composition-free language is an exponentially less succinct version
of the language with composition.
Time and location:
At the
seminar "Querying and Storing XML",
Saarland University.
April 26th, 4.15 p.m. (punctual/s.t.) in seminar room 14 (building 45).
For questions, contact scherzinger@cs.uni-sb.de.