UnQL: a query language and algebra for semistructured data based on structural recursion. This paper presents structural recursion as the basis of the syntax and semantics of query languages for semistructured data and XML. We describe a simple and powerful query language based on pattern matching and show that it can be expressed using structural recursion, which is introduced as a top-down, recursive function, similar to the way XSL is defined on XML trees. On cyclic data, structural recursion can be defined in two equivalent ways: as a recursive function which evaluates the data top-down and remembers all its calls to avoid infinite loops, or as a bulk evaluation which processes the entire data in parallel using only traditional relational algebra operators. The latter makes it possible for optimization techniques in relational queries to be applied to structural recursion. We show that the composition of two structural recursion queries can be expressed as a single such query, and this is used as the basis of an optimization method for mediator systems. Several other formal properties are established: structural recursion can be expressed in first-order logic extended with transitive closure; its data complexity is PTIME; and over relational data it is a conservative extension of the relational calculus. The underlying data model is based on value equality, formally defined with bisimulation. Structural recursion is shown to be invariant with respect to value equality.
Keywords for this software
References in zbMATH (referenced in 9 articles )
Showing results 1 to 9 of 9.
- Hamana, Makoto; Matsuda, Kazutaka; Asada, Kazuyuki: The algebra of recursive graph transformation language UnCAL: complete axiomatisation and iteration categorical semantics (2018)
- Xu, Kevin H.: A class of bounded functions, a database language and an extended lambda calculus (2017)
- Fan, Wenfei; Li, Jianzhong; Ma, Shuai; Tang, Nan; Wu, Yinghui: Adding regular expressions to graph reachability and pattern queries (2012)
- Santini, Simone: Regular languages with variables on graphs (2012)
- Robertson, Edward L.; Saxton, Lawrence V.; Van Gucht, Dirk; Vansummeren, Stijn: Structural recursion as a query language on lists and ordered trees (2009)
- Martens, Wim; Neven, Frank; Gyssens, Marc: Typechecking top-down XML transformations: Fixed input or output schemas (2008)
- Martens, Wim; Neven, Frank: Frontiers of tractability for typechecking simple XML transformations (2007)
- Van den Bussche, Jan; Van Gucht, Dirk; Vansummeren, Stijn: Well-definedness and semantic type-checking for the nested relational calculus (2007)
- Kim, Jongik: Advanced structural joins using element distribution (2006)