The expressivity of XPath with transitive closure

ABSTRACT

We extend Core XPath, the navigational fragment of XPath 1.0, with transitive closure and path equalities. The resulting language, Regular XPATH^≈, is expressively complete for FO* (first-order logic extended with a transitive closure operator that can be applied to formulas with exactly two free variables). As a corollary, we obtain that Regular XPATH^≈ is closed under path intersection and complementation. We also provide characterizations for the *-positive fragment of Regular XPATH^≈, and for μRegular XPATH (the extension of Regular XPATH^≈ with least fixed points).

REFERENCES

• 1: S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web. Morgan Kaufmann, 2000.
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The LOREL query language for semistructured data. Journal on Digital Libraries, 1(1):68--88, 1997.
• 4: L. Afanasiev, P. Blackburn, I. Dimitriou, B. Gaiffe, E. Goris, M. Marx, and M. de Rijke. PDL on ordered trees. Journal of Applied Non-Classical Logics, 15(2):115--135, 2005.
• 5: Rakesh Agrawal, Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries, IEEE Transactions on Software Engineering, v.14 n.7, p.879-885, July 1988 [doi>10.1109/32.42731]
• 6: Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Direct transitive closure algorithms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.15 n.3, p.427-458, Sept. 1990 [doi>10.1145/88636.88888]
• 7: R. Agrawal and H. V. Jagadish. Method for computing transitive closure. United States Patent 4930072. Filed August 31, 1987; Published May 29, 1990. URL: http://www.freepatentsonline.com/4930072.html.
• 8: Pablo Barcelo, Temporal Logics over Unranked Trees, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), p.31-40, June 26-29, 2005 [doi>10.1109/LICS.2005.51]
• 9: Michael Benedikt , Wenfei Fan , Gabriel Kuper, Structural properties of XPath fragments, Theoretical Computer Science, v.336 n.1, p.3-31, 25 May 2005 [doi>10.1016/j.tcs.2004.10.030]
• 10: R. Bloem and J. Engelfriet. Characterization of properties and relations defined in monadic second order logic on the nodes of trees. Technical Report 97-03, Leiden University, August 1997.
• 11: M. Bojańczyk, M. Samuelides, T. Schwentick, and L. Segoufin. On the expressive power of pebble automata. Manuscript.
• 12: J. Bradfield and C. Stirling. PDL and the modal μ-calculus. In Handbook of Modal Logic. Elsevier North-Holland, 2006. To appear.
• 13: A. Brüggemann-Klein and D. Wood. Caterpillars, context, tree automata and tree pattern matching. In Proceedings of DALT 1999, pages 270--285. World Scientific, 1999.
• 14: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 15: E. Codd. Relational completeness of data base sublanguages. In R. Rustin, editor, Database Systems, pages 33--64. Prentice-Hall, 1972.
• 16: S. Dar , R. Agrawal, Extending SQL with Generalized Transitive Closure, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.799-812, October 1993 [doi>10.1109/69.243510]
• 17: A. Deutsch and V. Tannen. Containment and integrity constraints for XPath fragments. In Proceedings of KRDB 2001, volume 45 of CEUR Workshop Series. CEUR-WS.org, 2001.
• 18: E. Allen Emerson , Charanjit S. Jutla , A. Prasad Sistla, On Model-Checking for Fragments of µ-Calculus, Proceedings of the 5th International Conference on Computer Aided Verification, p.385-396, June 28-July 01, 1993
• 19: J. Engelfriet and H. J. Hoogeboom. Automata with nested pebbles capture first-order logic with transitive closure. Tech. Report LIACS 2005-02, Leiden University, April 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

General Terms:
Languages, Theory

Keywords:
XML, XPath, semi-structured data, transitive closure