XDES is a Java 1.2 class library for optimizing regular path queries using graph simulation (using techniques such as a generalized form of query pruning of [3]). Several kinds of simulating graphs can be used, including schema graphs [2,3], data guides [1], and so-called meta-level databases [4].
Compared to graph schemata, meta-level databases are an alternative kind of description based on the notions of meta-objects and homomorphisms used by the object-oriented programming (OOP) community [6]. This viewpoint of meta-data has recently become very popular in that community, as evidenced by outspoken efforts such as the OMG MDA [5]. Meta-level databases differ from graph schemata in that meta-objects may contain descriptive attribute values, permitting to lift important data to the meta-level, thus reducing redundancy and facilitating the management and configurability of large systems. Since values used in query conditions are in practice most often chosen from such meta-data, databases described in this way are a particularly fertile ground for query optimization.
The XDES framework consists of code for parsing, representing and optimizing XPath queries [7] and full regular path queries with nested conditions similar to those of XPath. We provide methods for the most common operations on finite automata and regular expressions, such as translating regular expressions into finite automata, eliminating epsilon-transitions, making automata deterministic, minimizing them, computing several kinds of automata intersections such as product automata, translating finite automata into regular expressions, and minimizing those. Internally, to be able to deal with nested conditions in queries, the alphabet on which such an automaton is defined may consist of complex objects representing query constraints that affect the optimization.
XDES can read graph schemata and meta-level databases represented as XML files (with ID/IDREF) using a standard DOM parser such as the one of XERCES and is compatible with the Apache XALAN XPath classes. XDES represents meta-data as finite automata and can also be smoothly integrated with semistructured database management systems that use their proper internal format for managing such meta-data.
We currently only provide some highly "experimental" documentation, more will follow. The cited references (particularly [3]) certainly are required reading.
We will make the full XDES framework implementation publicly available soon. In the future, we plan to extend this framework to further query languages such as XQuery, and by a database frontend which will permit the verification of the soundness of data against simulating meta-data and automatic integrity checks for database updates.