×

Structural recursion as a query language on lists and ordered trees. (English) Zbl 1192.68219

Summary: XML query languages need to provide some mechanism to inspect and manipulate nodes at all levels of an input tree. We investigate the expressive power provided in this regard by structural recursion. In particular, we show that the combination of vertical recursion down a tree combined with horizontal recursion across a list of trees gives rise to a robust class of transformations: it captures the class of all primitive recursive queries. Since queries are expected to be computable in at most polynomial time for all practical purposes, we next identify a restriction of structural recursion that captures the polynomial time queries. We also give corresponding results for list-based complex objects.

MSC:

68P15 Database theory
68P05 Data structures

Software:

UnQL; XPath; XQuery
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiteboul, S., Beeri, C.: The power of languages for the manipulation of complex values. VLDB J. 4(4), 727–794 (1995) · doi:10.1007/BF01354881
[2] Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995) · Zbl 0848.68031
[3] Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the polytime functions (extended abstract). In: STOC 1992, pp. 283–293. ACM Press, New York (1992) · Zbl 0766.68037
[4] Boag, S., Chamberlin, D., Fernández, M.F., Florescu, D., Robie, J., Siméon, J.: XQuery 1.0: An XML Query Language. W3C Recommendation, January 2007
[5] Bonner, A.J., Mecca, G.: Sequences, datalog, and transducers. J. Comput. Syst. Sci. 57(3), 234–259 (1998) · Zbl 0917.68053 · doi:10.1006/jcss.1998.1562
[6] Boolos, G.S., Jeffrey, R.C.: Computability and Logic, 3rd edn. Cambridge University Press, Cambridge (1989) · Zbl 0708.03001
[7] Buneman, P., Fernandez, M.F., Suciu, D.: UnQL: a query language and algebra for semistructured data based on structural recursion. VLDB J. 9(1), 76–110 (2000) · doi:10.1007/s007780050084
[8] Buneman, P., Naqvi, S.A., Tannen, V., Wong, L.: Principles of programming with complex objects and collection types. Theor. Comput. Sci. 149(1), 3–48 (1995) · Zbl 0874.68092 · doi:10.1016/0304-3975(95)00024-Q
[9] Caseiro, V.-H.: Equations for defining poly-time functions. PhD thesis, University of Oslo (1997)
[10] Chandra, A.K., Harel, D.: Computable queries for relational data bases. J. Comput. Syst. Sci. 21(2), 156–178 (1980) · Zbl 0456.68128 · doi:10.1016/0022-0000(80)90032-X
[11] Cobham, A.: The intrinsic computational difficulty of functions. In: Logic, Methodology, and Philosophy of Science II, pp. 24–30. Springer, Berlin (1965) · Zbl 0192.08702
[12] Colby, L.S., Libkin, L.: Tractable iteration mechanisms for bag languages. In: ICDT 1997. Lecture Notes in Computer Science, vol. 1186, pp. 461–475. Springer, Berlin (1997)
[13] Colby, L.S., Robertson, E.L., Saxton, L.V., Van Gucht, D.: A query language for list-based complex objects. In: PODS 1994, pp. 179–189. ACM Press, New York (1994)
[14] Draper, D., Fankhauser, P., Fernández, M.F., Malhotra, A., Rose, K., Rys, M., Siméon, J., Wadler, P.: XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Recommendation, January 2007
[15] Fernández, M.F., Malhotra, A., Marsh, J., Nagy, M., Walsh, N.: XQuery 1.0 and XPath 2.0 Data Model. W3C Recommendation, January 2007
[16] Girard, J.-Y.: Light linear logic. Inf. Comput. 143(2), 175–204 (1998) · Zbl 0912.03025 · doi:10.1006/inco.1998.2700
[17] Gladstone, M.D.: Simplifications of the recursion scheme. J. Symb. Log. 36(4), 653–665 (1971) · Zbl 0248.02040 · doi:10.2307/2272468
[18] Grumbach, S., Milo, T.: Personal communication
[19] Grumbach, S., Milo, T.: An algebra for pomsets. Inf. Comput. 150(2), 268–306 (1999) · Zbl 1045.68558 · doi:10.1006/inco.1998.2777
[20] Hofmann, M.: A mixed modal/linear lambda calculus with applications to Bellantoni-Cook safe recursion. In: CSL 1997. Lecture Notes in Computer Science, vol. 1414, pp. 275–294. Springer, Berlin (1998) · Zbl 0908.03022
[21] Hofmann, M.: Linear types and non-size-increasing polynomial time computation. In: LICS, pp. 464–473 (1999)
[22] Hofmann, M.: Semantics of linear/modal lambda calculus. J. Funct. Program. 9(3), 247–277 (1999) · Zbl 0965.68011 · doi:10.1017/S0956796899003433
[23] Hofmann, M., Jost, S.: Static prediction of heap space usage for first-order functional programs. In: POPL, pp. 185–197 (2003) · Zbl 1321.68180
[24] Hull, R., Su, J.: Algebraic and calculus query languages for recursively typed complex objects. J. Comput. Syst. Sci. 47(1), 121–156 (1993) · Zbl 0781.68046 · doi:10.1016/0022-0000(93)90022-O
[25] Immerman, N., Patnaik, S., Stemple, D.W.: The expressiveness of a family of finite set languages. Theor. Comput. Sci. 155(1), 111–140 (1996) · Zbl 0874.68093 · doi:10.1016/0304-3975(94)00287-8
[26] Leivant, D.: Stratified functional programs and computational complexity. In: POPL 1993, pp. 325–333. ACM Press, New York (1993)
[27] Libkin, L., Wong, L.: Query languages for bags and aggregate functions. J. Comput. Syst. Sci. 55(2), 241–272 (1997) · Zbl 0887.68022 · doi:10.1006/jcss.1997.1523
[28] Sazonov, V.Yu.: Hereditarily-finite sets, data bases and polynomial-time computability. Theor. Comput. Sci. 119(1), 187–214 (1993) · Zbl 0782.68063 · doi:10.1016/0304-3975(93)90345-T
[29] Suciu, D.: Bounded fixpoints for complex objects. Theor. Comput. Sci. 176(1–2), 283–328 (1997) · Zbl 0903.68058 · doi:10.1016/S0304-3975(96)00293-9
[30] Suciu, D., Wong, L.: On two forms of structural recursion. In: ICDT 1995. Lecture Notes in Computer Science, vol. 893, pp. 111–124. Springer, Berlin (1995)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.