6533b857fe1ef96bd12b4318
RESEARCH PRODUCT
Expressive and efficient pattern languages for tree-structured data (extended abstract)
Frank NevenThomas Schwenticksubject
SQLRoot (linguistics)Theoretical computer scienceProgramming languageComputer scienceUSablecomputer.software_genreQuery languageTree (data structure)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESFragment (logic)Path (graph theory)Regular expressioncomputercomputer.programming_languagedescription
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 monadic second-order logic (MSO), and (3) efficiently evaluable. The paper develops some ideas in this direction. Towards (1) the specification of sets of vertices of a tree by combining conditions on their induced subtree 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, anguably, (1).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2000-01-01 | Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems - PODS '00 |