Monadic queries over tree-structured data
Proceedings - Symposium on Logic in Computer Science - Trang 189-202
Tóm tắt
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).
Từ khóa
#Database languages #XML #Logic #Data mining #Wrapping #Artificial intelligence #Natural languages #Spatial databases #Information filtering #Information filtersTài liệu tham khảo
liu, 1998, XWRAP: An XML-enabled wrapper construction system for web information sources, Proceedings of the 16th International Conference on Data Engineering
0, XSL Transformations (XSLT) W3C Recommendation Version 1 0
10.1016/B978-155860869-6/50017-2
2001, XML Pointer Language Version 1 0 W3C Candidate Recommendation
hopcroft, 1979, Introduction to Automata Theory Languages and Computation
0, XML Query
10.1145/504077.504079
0, XPath Recommendation
10.1145/543613.543617
10.1016/B978-0-444-88074-1.50021-4
flum, 2001, Query evaluation via tree-decompositions, Proc Int l Conf Database Theory
2001, XML Schema Part 0 Primer W3C Recommendation
deutsch, 2001, Containment and integrity constraints for XPath, CEUR Workshop Proceedings, 45
10.1016/0743-1066(84)90014-1
miklau, 2002, Containment and equivalence for an XPath fragment, Proc 23rd ACM Symp Principles of Database Systems (PODS '04)
maier, 1983, The Theory of Relational Databases Computer Science Press
10.1145/335168.335171
10.1016/0020-0190(88)90124-X
neven, 2000, Expressive and efficient pattern languages for tree-structured data, Proc 19th Symp on Principles of Database Systems (PODS 2000), 145
10.1016/S0304-3975(01)00301-2
papadimitriou, 1994, Computational Complexity
10.1016/S0169-023X(00)00051-3
10.1016/B978-0-444-88074-1.50009-3
10.1007/978-3-642-59126-6_7
10.1007/3-540-45402-0_2
10.1006/jcss.1999.1627
10.1145/502807.502810
abiteboul, 1995, Foundations of Databases
ullman, 1988, Principles of Database and Knowledge Base Systems, 1
bry, 2001, Symmetry in XPath
bru?ggemann-klein, 1998, Regular Tree Languages over Non-ranked Alphabets
wood, 2000, On the equivalence of XML patterns, LNCS, 1861, 1152
bex, 2000, A formal model for an expressive fragment of XSLT, LNCS, 1861, 1137
ullman, 1989, Principles of Database & Knowledge-Base Systems Vol 2 The New Technologies, 2
baumgartner, 2001, Visual web information extraction with lixto, Proc VLDB'01
10.1145/800105.803397
10.1007/978-3-642-83952-8