Monadic queries over tree-structured data
- 1 January 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10436871,p. 189-202
- https://doi.org/10.1109/lics.2002.1029828
Abstract
Monadic query languages over trees currently receive considerable interest in the database community, as the problem of selecting nodes from a tree is the most basic and widespread database query problem in the context of XML. Partly a survey of recent work done by the authors and their group on logical query languages for this problem and their expressiveness, this paper provides a number of new results related to the complexity of such languages over so-called axis relations (such as "child" or "descendant") which are motivated by their presence in the XPath standard or by their utility for data extraction (wrapping).Keywords
This publication has 16 references indexed in Scilit:
- Monadic datalog and the expressive power of languages for web information extractionPublished by Association for Computing Machinery (ACM) ,2002
- Query automata over finite treesTheoretical Computer Science, 2002
- Datalog LITEACM Transactions on Computational Logic, 2002
- Efficient Algorithms for Processing XPath QueriesPublished by Elsevier ,2002
- Building intelligent Web applications using lightweight wrappersData & Knowledge Engineering, 2001
- Typechecking for XML transformersPublished by Association for Computing Machinery (ACM) ,2000
- Temporal and Modal LogicPublished by Elsevier ,1990
- Automata on Infinite ObjectsPublished by Elsevier ,1990
- LTUR: a simplified linear-time unit resolution algorithm for horn formulae and computer implementationInformation Processing Letters, 1988
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984