×

zbMATH — the first resource for mathematics

Axiomatizing the logical core of XPath 2.0. (English) Zbl 1192.68224
Summary: The first aim of this paper is to present the logical core of XPath 2.0: a logically clean, decidable fragment, which includes most navigational features of XPath 2.0 (complex counting conditions and data joins are not supported, as they lead to undecidability). The second aim is to provide a list of equations completely axiomatizing query equivalence in this language (i.e., all other query equivalences can be derived from these).

MSC:
68P15 Database theory
Software:
Rath; RelView; XPath
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995) · Zbl 0848.68031
[2] Backofen, R., Rogers, J., Vijay-Shanker, K.: A first-order axiomatization of the theory of finite trees. J. Logic Lang. Inf. 4(1), 5–39 (1995) · Zbl 0833.03010 · doi:10.1007/BF01048403
[3] Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. Assoc. Comput. Mach. 55(2), (2008) · Zbl 1326.68154
[4] Benedikt, M., Fan, W., Kuper, G.: Structural properties of XPath fragments. Theor. Comput. Sci. 336(1), 3–31 (2005) · Zbl 1080.68018 · doi:10.1016/j.tcs.2004.10.030
[5] Berghammer, R., Schmidt, G., Winter, M.: RelView and Rath–two systems for dealing with relations. In: Theory and Applications of Relational Structures as Knowledge Instruments. LNCS, vol. 2929, pp. 1–16. Springer, Berlin (2003) · Zbl 1203.68319
[6] Bojanczyk, M., Muscholl, A., Schwentick, Th., Segoufin, L., David, C.: Two-variable logic on words with data. In: Proceedings LICS’06, pp. 7–16 (2006)
[7] Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. Springer, Berlin (1997) · Zbl 0865.03004
[8] Dawar, A.: How many first-order variables are needed on finite ordered structures? In: Artemov, S., et al. (eds.) We will Show Them: Essays in Honour of Dov Gabbay, pp. 489–520. College Publications, Woodend Vic. (2005)
[9] Doets, H.C.: Completeness and definability: applications of the ehrenfeucht game in intensional and second-order logic. Ph.D. Thesis, Department of Mathematics and Computer Science, University of Amsterdam (1987)
[10] Geerts, F., Fan, W.: Satisfiability of XPath queries with sibling axes. In: Proceedings DBPL’05, pp. 122–137 (2005) · Zbl 1159.68418
[11] Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. In: VLDB’02, pp. 95–106 (2002)
[12] Gyssens, M., Paredaens, J., Van Gucht, D., Fletcher, G.: Structural characterizations of the semantics of XPath as navigation tool on a document. In: Proceedings PODS’06, pp. 318–327 (2006)
[13] Henkin, L., Monk, J.D., Tarski, A.: Cylindric Algebras, Part II. North-Holland, Amsterdam (1985) · Zbl 0576.03043
[14] Hidders, J.: Satisfiability of XPath expressions. In: Proceedings DBPL. LNCS, vol. 2921, pp. 21–36. Springer, Berlin (2003)
[15] Hirsch, R., Hodkinson, I.: Relation algebras by games. In: Studies in Logic and the Foundations of Mathematics, vol. 147. North-Holland, Amsterdam (2002) · Zbl 1018.03002
[16] Kay, M.: XPath 2.0 Programmer’s Reference. Wrox (2004)
[17] Lyndon, R.C.: The representation of relation algebras. Ann. Math. 51, 707–729 (1950) · Zbl 0037.29302 · doi:10.2307/1969375
[18] Lyndon, R.C.: The representation of relation algebras, Part II. Ann. Math. 63, 294–307 (1956) · Zbl 0070.24601 · doi:10.2307/1969611
[19] Marx, M.: Conditional XPath. ACM Trans. Database Syst. (TODS) 30(4), 929–959 (2005) · Zbl 05457054 · doi:10.1145/1114244.1114247
[20] Tarski, A.: On the calculus of relations. J. Symb. Log. 6, 73–89 (1941) · Zbl 0026.24401 · doi:10.2307/2268577
[21] Tarski, A., Givant, S.: A Formalization of Set Theory without Variables. AMS Colloquium Publications, vol. 41. Rhode Island, Providence (1987) · Zbl 0654.03036
[22] ten Cate, B., Litak, T., Marx, M.: Complete axiomatizations for XPath fragments. In: Proceedings LID (Logic in Databases) Rome, Italy, 19–20 May 2008 · Zbl 1192.68223
[23] ten Cate, B., Lutz, C.: The complexity of query containment in expressive fragments of XPath 2.0. In: Proceedings PODS’07 (2007) · Zbl 1325.68079
[24] Venema, Y.: Many-dimensional modal logic. Ph.D. Thesis, Institute for Logic, Language and Computation, University of Amsterdam (1992) · Zbl 0785.03007
[25] Venema, Y.: Completeness by completeness: since and until. In: de Rijke, M. (ed.) Diamonds and Defaults, pp. 349–358. Kluwer Academic, Dordrecht (1993) · Zbl 0821.03011
[26] Venema, Y.: Derivation rules as anti-axioms in modal logic. J. Symb. Log. 58(3), 1003–1034 (1993) · Zbl 0793.03017 · doi:10.2307/2275109
[27] Venema, Y.: Completeness through flatness. In: Gabbay, D., Ohlbach, H.J. (eds.) Temporal Logic, First International Conference ICTL’94, pp. 149–164 (1994) · Zbl 0949.03510
[28] Venema, Y.: Cylindrical modal logic. J. Symb. Log. 60(2), 591–623 (1995) · Zbl 0830.03008 · doi:10.2307/2275853
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.