Xcerpt: A Rule-Based Query and Transformation Language for the Web

This thesis investigates querying the Web and the Semantic Web. It
proposes a new rulebased query language called Xcerpt. Xcerpt
differs from other query languages in that it uses patterns instead
of paths for the selection of data, and in that it supports both
rule chaining and recursion. Rule chaining serves for structuring
large queries, as well as for designing complex query programs
(e.g. involving queries to the Semantic Web), and for modelling
inference rules. Query patterns may contain special constructs like
partial subqueries, optional subqueries, or negated subqueries that
account for the particularly flexible structure of data on the Web.
Furthermore, this thesis introduces the syntax of the language
Xcerpt, which is illustrated on a large collection of use cases
both from the conventional Web and the Semantic Web. In addition, a
declarative semantics in form of a Tarski-style model theory is
described, and an algorithm is proposed that performs a backward
chaining evaluation of Xcerpt programs. This algorithm has also
been implemented (partly) in a prototypical runtime system. A
salient aspect of this algorithm is the specification of a
non-standard unification algorithm called simulation unification
that supports the new query constructs described above. This
unification is symmetric in the sense that variables in both terms
can be bound. On the other hand it is in contrast to standard
unification assymmetric in the sense that the unification
determines that the one term is a subterm of the other term.