The aim of this paper is to outline an uniform functional approach useful both for constructing query languages for XML and also for formal description of their semantics. This framework offers an alternative way to today's mainstream query languages -XPath and XQuery. With respect to the goal of the VLDB PhD Workshop it is focused more on the concept than on the complete solution.
No doubt XML [4] is nowadays moving the world and thus not surprisingly it might be found almost everywhere. Querying XML data is the essential operation for many algorithms and therefore many researchers focus on this field. Mainstream query languages -XPath [5,7], used for locating nodes in an XML instance, and XQuery 1.0 [3] (more or less a SQL-like language) -are the results developed by the wide community of contributors.
The XML specification itself does not define any data model for XML instances therefore successive query languages had to define a theoretical base for their syntax and semantics. XPath 1.0 is based on the XML Infoset [8], XQuery 1.0 grounds on a newly developed "XQuery 1.0 and XPath 2.0 Data Model" [12]. Based upon this data model its semantics is formally described in [10].
There are various different query languages for XML -especially those used as predecessors of XQuery -e.g. Lorel [1], Quilt [6] or XML-QL [9].
From our perspective one of the most interesting languages is the SXML framework. It seems to be the only framework for manipulating XML in a functional Proceedings of the VLDB2006 Ph.D. Workshop, Seoul, Korea, 2006 way. The goal of its authors is to implement some of W3C standards -XML, XPath, XSLT -in the Scheme language [11]. SXML takes in account only first versions of these specifications but not the latest drafts. The main components of the project are SSAX, SXML, SXPath, and SXSLT [13,14].
The key idea is the usage of S-expressions. Sexpressions are known from the LISP language where there can be either single objects such as numbers, LISP atoms including the special atoms or pairs. The framework claims its fully conformant to XML specification. Regarding to [13] there is a formal algorithm how to rewrite XPath queries to SXPath expressions with identical semantics. SXSLT is apparently an implementation of XSLT 1.0 semantics. Unfortunatelly from published papers it is not exactly obvious that the full XSLT standard was implemented, authors only mention their experiments with real XML documents.
Evolution of a query language usually brings some changes in its syntax or/and the semantics. For example, the progress from XPath 1.0 to XPath 2.0 (i.e. sub-specification of XQuery 1.0) brought a new data model for XML. It was a logical and necessary step forced by requirements given for the new language. Our idea is to use such formalism (formal system) as a base for the language that is universal enough to avoid big changes when enriching the language with new constructs. Therefore the idea of a functional approach combined together with basic lambda calculi operations (lambda abstractions and lambda applications) seems to be very simple and not restrictive, rather it allows to be easily extended in the future.
Our work tries to link to the idea of the XML-λ Framework (see Section 3), explore it further and study its various aspects from different points of view. Its author already identified some issues and drawbacks of the framework. We see one of the biggest issues the missing comparison of the proposed query language with the XQuery language. The question of expressive power of these two languages is very chal-lenging because these approaches represent different formal systems and seems to be not solved yet.
To lay out more specific goals for our consecutive work we formulate the following aims: (a) Utilize the XML-λ Framework for formal description of XQuery semantics, (b) Construct a XQuery-to-XML-λ query compiler (and vice-versa) and compare expressive power of XQuery and XML-λ query languages, (c) Evaluate functional approach for various aspects related to querying XML.
3 The XML-λ Framework XML-λ framework is an idea of using functional approach together with lambda calculi [2] and utilize it for querying XML data. The proposal was originally developed by Pokorný [16,17].
The following sections outline the theoretical base of the XML-λ Framework and the query language built upon it. In Section 3.3 we show an example of a query evaluation.
The type system is built on base B -a set containing a finite number of base types S 1 , . . . , S k (k ≥ 1). Type hierarchy is then created by following inductive definition:
Type System T . Let B is a set of primitive types S 1 . . . S n , n ≥ 1. Type System T over base B is the least set containing types given by 1.-4. Subsequently we define a regular type system T reg that extends type system T with regular constructs: Type System T reg . Let B= {String, Bool}, let N AM E be a set of names. Type System T reg is the least set containing types given by 1.-6.
1. Every member of the base B is an (primitive) type over B.
Let tag ∈ N AM E. Then tag : String is an (elementary) type over B, tag : is an (empty elementary) type over B.
3. Let T be a group type or named character data. Then
• zero or more: T * is a type over B.
• one or more: T + is a type over B.
• zero or one: T ? is a type over B.
Let T 1 and T 2 be types. Then (T 1 |T 2 ) is a type over B.
5. sequence: Let T 1 , . . . , T n be types. Then (T 1 , . . . , T n ) is a type over B.
6. named type: Let T be a type given by a step from 3.-5. Let tag ∈ N AM E. Then tag : T is a type of B.
Note here that this type system T reg is still suitable to describe types not only in a concrete data structure (in our case tree structure) but for all data that might be tagged with name -for example data accordant to the relational model.
Having the T reg type system we have to extend it to be able to work with XML data. We build the type system T E induced by T reg . Key idea is to define abstract elements that are particular XML elements with some content and also define a set containing all abstract elements within an XML instance -E .
Type System T E . Let T reg over base B be a type system from definition 3.1 and E is the set of abstract elements. Then type system T E induced by T reg is the least set containing type given by this rule:
(Replacement of all tags in tag : T by upper case version)
Note one remark: we can see the type system T E as function container that adds functions for extracting data values from elements (via abstractions and projections) with two ways
A typical query has a main (body) part -an expression to be evaluated over data -and a constructor part that wraps query result and forms the XML output. XML-λ's Query Language (XLQL) is based on λ-terms defined over the type system T E . Main constructs of the language are variables, constants, tuples, use of projections and λ-calculus operations -abstractions and applications. Tagged terms might be used for declaring functions. Syntax of this language is similar to λ-calculus expression thus queries are structured as λ-expresions, i.e. λ . . . (λ . . . (expression) . . .). In addition, there are also typical constructs such as logical connectives, constants or comparison predicates.
XML-λ Query Language is inductively defined as the least set containing all terms created by application of following rules:
Let T, T 1 , . . . , T n , n ≥ 1 be members of T . Then Simple implementation of this language is available in [18].
Following example should give more detailed view to an evaluation of a XML-λ query. Let us consider the DTD and a conforming XML instance as shown in Figure 1 and Figure 2 and a query that will return first names of all authors mentioned in the document. Solution First we specify a set E of all abstract elements contained in XML instance as follows (note that subscripts are here only to distinguish abstract elements of the same type): Evaluation of this query takes place in following way: this query is composed of one high-level λ-term and contains two variables called a and f . Navigation over the structure of elements is implemented as continuous λ-applications combined with projections (performed by element name). When evaluating the value of the query first the value of a is evaluated (note that /book/author(a) is syntactically equivalent to author(book(a))). This term is evaluated using sequent application of book and author functions. Then the variable a contains an abstract element of type author. We apply to this element function author that returns a n-tuple of elements from E. Last step is projection from this n-tuple into the first component. The result of this operation is a particular abstract element.
Hereby we receive the output (without enveloping elements): Jaroslav, Karel.
In the previous sections we describe a query language based on the XML-λ Framework. It uses functions as a data model for XML documents and lambda calculi abstractions and applications for development of a query language suitable for querying XML.
Beside that we can also use this data model for different purposes. Due to universality of the λ-calculus, we can construct a language for modifying XML data. Generally it means performing changes (additions/removals) in the set E of abstract elements for a particular XML instance and eventual changes in the type system T E . With this approach we can also be able to express integrity constraints for XML data. This research direction however lays out of scope of this paper.
XQuery [3] is a mainstream language for querying XML. The language uses expressions as its fundamental constructs. Basic expressions are literals and variables, for navigating in XML documents it uses XPath expressions. Related specification [15] contains an extensive list of predefined numeric, arithmetic, string or date-time functions. One important type of expression are the FLWOR expressions. FLWOR is a shortcut for For, Let, Where, Order-By, Return statements that are used in the same way as in imperative languages. This type of expression is sometimes compared to SQL SELECT statement known from relational databases.
The goal of our research is to explore the relationship between XQuery and XML-λ. Thus, in XQuery we can write a query returning all first names in our bibliography database in following way: We want to show that all queries in XQuery can be rewritten into XML-λ and vice-versa. This claim should be backed by formal description of denotational and operational semantics of both languages and by finding a transformation between semantic subtrees of all language constructs.
Future work should lead into a successful completion of the dissertation thesis. Therefore we need to define concrete tasks and formulate consecutive experiments.
The proposed dissertation thesis investigates an utilization of the λ-calculus based framework for description of query language semantics. We plan to formulate both denotational and structured operational semantics of the XQuery language. Having this formalism available we will compare the expressive power of these languages and further study their properties. Our primary aim is to define the existing semantics of XQuery in a functional way as a base for ongoing experiments and then compare their expressive power by finding transformations between queries in XQuery and XML-λ.
There are two concrete ongoing tasks -specification of XQuery semantics by using the XML-λ Framework and consecutive construction of transformation engine for converting XQuery and XML-λ queries.
The functional approach applied in XML-λ might be used not only for constructing a query language but also for a different purpose -description of semantics of various query languages. Within our research we want to describe the semantics of the mainstream XML query language XQuery with help of the functional approach based on λ-calculus -XML-λ. Taking into account the type system used we expect the semantics to be easier to express in comparison with existing W3C semantics. With respect to the scope of the XQuery semantics specification this topic represents a complex theoretical research.
Expression of the XQuery semantics with help of λ-calculus gives us an opportunity to compare expressive power of XQuery and XML-λ. Because of the fact that the semantics of XML-λ query language is closely related to its syntax we can propose a method for conversion of queries based on language's semantics. The result of this aim is to have a transformation engine and its implementation for converting XQuery queries in XML-λ and vice-versa available. The conversion process is generally a transformation of an input semantic tree in one language to an output semantic tree in the other language.
This paper outlines a framework for querying XML data based on a functional approach combined with lambda calculi operations. The functional approach is not common nowadays but offers a universal way that might be used as a base for constructing various query languages for XML. Beside that it can be also used for specifying semantics of these languages. Having the semantics formalized with the same tool we can compare their expressive power and evaluate their relationship.
For consecutive work to lead into a dissertation thesis we plan to describe semantics of XQuery using the functional framework. With this formalism we can construct a XQuery-to-XML-λ compiler (and viceversa) by transformation of respective semantic trees. These transformations describe relationships between various language constructs. With knowledge of these relationships we can then compare XQuery's expressive power with a query language based on lambda calculi.
The main contribution of the thesis should be seen in using functional approach for description of XQuery semantics and for evaluation of properties of lambda calculi based framework and its suitability for querying XML.
This research has been partially supported by M ŠMT under research program MSM 6840770014.