2nd Semester 2003/04: Evaluation of CTL model representations for simple XPath queries

Instructors

Dr Stefan Schlobach

ECTS

6

Description

Background:

Representing XML documents as CTL models facilitates fast evaluation of simple Xpath queries. As XML documents grow larger however, the space needed for representation of the models can exceed primary storage space. This will have serious impact on the actual time it takes for perform model checking. Among the suggested approaches to reduce the severity of this problem are compressed CTL-models (in spirit of the compressed XML skeleton approach suggested by Buneman, Grohe and Koch, 2003) and BDD representations (as in Long, 1993).

Project:

The task is to evaluate these two approaches against the background of naive model checking on uncompressed CTL models, with respects to models derived from XML documents grounded in real world applications on computers reasonably similar with today's servers and workstation. These XML documents may be medium sized (like a library catalogs with document size around 250MB) or large (local search engine systems with document size 10GB and upwards) and runs on resulting models should be performed and the space and time use required for both relative and absolute queries should be recorded and evaluated. Suggestions for optimizations on both conceptual and implementation levels may be investigated of referred to as possible paths for further research. The goal is to get an idea of the strength and weaknesses of these two approaches and get an idea of the relations between document size, document type, efficient query operations and platform requirements.