Nov 19: T. Schwentick, Pattern Languages for Tree-Structured Data

Subject: Nov 19: T. Schwentick, Pattern Languages for Tree-Structured Data
From: Helmut Veith (
Date: Thu Nov 18 1999 - 16:31:38 MET

Lecture Announcement

Thomas Schwentick
Johannes-Gutenberg Universitaet Mainz

Expressive and efficient pattern languages
for tree-structured data
Friday, November 19, 11:30

It would be desirable to have a query language for tree-structured data that
is (1) as easily usable as SQL, (2) as expressive as MSO-logic, and (3)
efficiently evaluable. The talk develops some ideas in this direction.
Towards (1) the specification of sets of
vertices of a tree by combining conditions on their induced subtreee with
conditions on their path to the root is proposed. Existing query languages
allow regular expressions (hence MSO logic) in path conditions but are limited
in expressing subtree conditions. It is shown that such query languages fall
short of capturing all MSO queries. On the other hand, allowing a certain
guarded fragment of MSO-logic in the specification of subtree conditions
results in a language fulfilling (2), (3) and, arguably, (1).

Place: Seminrraum 184/2, 3rd floor,
Favoritenstrasse 9-11, A-1040 Wien

Kurt Goedel Society

This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:21 MET DST