We address a problem of updating XML documents having their XML schema described by a Document Type Definition (DTD) without breaking their validity. We present a way how to express constructs available in DTD in a functional data model and propose algorithms for performing insert, update and delete operations. After that we embed the update capability into an existing query language for XML. This paper thus outlines the whole ”life cycle” of the approach from the problem analysis to its implementation.
During our work on a functional framework for querying XML – XML-λ – we identified a need for extending the language with support of data modification operations. Our aim is to develop an approach similar to the SQL language for relational databases, i.e. have an ability both to query and update underlying data.
With respect to our aim we set up basic requirements for our approach. First, we always consider typed data (this is a natural requirement because of the fact that our framework is based on a type system). At this stage we use DTD for constraining document validity. Second, we have already a query language designed. It makes sense to extend this language in a ”logical” way with update operations. By the term ”logical” we mean the utilization of existing constructs as sets, existing type system and the idea of functional approach in general.
The paper is structured as follows: Section 2 lists existing approaches for updating XML data and discusses their contribution. In Section 3 we briefly outline the concept of the functional framework we use, its data model and the query language that is used for implementing the proposal. We discuss the problem in Section 4 where we show our solution. Section 5 deals with enriching the syntax of our query language with update operations. In Section 6 we conclude with ideas for future work.
By the term updating XML we mean the ability of a language to perform modifications (i.e. insert, update and delete operations, etc.) over a set of XML documents.
Since the creation of the XML in 1998 there have been many efforts to develop various data models and query languages. A lot of time has also been spent on indexing and query optimization. On the other hand the problem of updating XML gains more interest in few past years. Yet there seems to be not a complete solution for this problem.
Existing papers dealing with updating XML are mostly related to XQuery [
For the sake of completeness we should not omit XUpdate [
Considering previous works we can deduce that there are common types of operations for performing modifications that are embedded in a language – delete, update, insert before or insert after. This seems to be a sufficient base for ongoing work. None of those proposals but deals with the problem of updating typed data and thus it makes sense to put some effort into studying of this problem. The evolution process around XML leads to use of types so it makes sense to work on this problem in the world of typed XML documents. 3
XML-λ Framework
XML-λ is a proposal published in 2001 by Pokorny´ [
The framework is based on type system theory – it can be informally said that first a “base” type system Tbase is defined then a regular type system Treg that extends Tbase with regular types is induced. Upon this the Treg is enriched with types corresponding to an XML schema and the TE type system is defined. Over such type system we define a query (and update) language based on simply typed lambda calculus. Having the Treg type system we have to extend it to be able to work with XML data. We build the type system TE induced by Treg. Key idea is to define abstract items that are particular XML elements or attributes with some content and also define a set containing all abstract items within an XML instance – E. Definition 3. Let Treg over base B be a type system from definition 2 and E is the set of abstract items. Then type system TE induced by Treg is the least set containing type given by this rule:
Let tag : T ∈ Treg. Then T AG : T is a member of TE . (Replacement of all tags in tag : T by uppercase version)
With types from TE we can consider functional types for extracting data values from elements (via abstractions and projections) with two ways 1. for simple element: if tag : String ∈ Treg, then (E → tag : String) ∈ TE 2. for compound element: if tag : T ∈ Treg, then (E → T ′) ∈ TE
Note also that in TE we can express attributes in the same way as XML elements – as functions. 3.3
Typical query has the query part – an expression to be evaluated over data – and the constructor part that wraps query result and forms the XML output. XML-λ’s query language is based on λ-terms defined over the type system TE as shown in Definition 4.
Main constructs of the language are variables, constants, tuples, use of projections and λ-calculus operations – applications and abstractions. Tagged terms might be used for declaring functions. Syntax of this language is similar to λ-calculus expression i.e. λ . . . (λ . . . (expression) . . .). In addition, there are also typical constructs such as logical connectives, constants or comparison predicates.
Language of terms is inductively defined as the least set containing all terms created by application of following rules: Definition 4. Let T, T1, . . . , Tn, n ≥ 1 be members of Tbase. Then
2. constant: each constant (member of F ) of type T is a term of type T 3. application: if M is a term of type ((T1, . . . , Tn) → T ) and N1, . . . , Nn are (in the same order) types T1, . . . , Tn, then M (N1, . . . , Nn) is a term of type T 4. λ-abstraction: if x1, . . . , xn are distinct variables of types T1, . . . , Tn and M is a term of type T , then λx1, . . . , xn(M ) is a term of type ((T1, . . . , Tn) → T ) 5. n-tuple: if N1, . . . , Nn are terms of types T1, . . . , Tn, then (N1, . . . , Nn) is a term of type (T1, . . . , Tn) 6. projection: if (N1, . . . , Nn) is a term of type (T1, . . . , Tn), then N1, . . . , Nn are terms of types T1, . . . , Tn 7. tagged term: if N is a term of type N AM E and M is a term of type T then
N : T is a term of type (E → T ). 3.4
For our purposes we use the notoriously known bibliography example DTD from
the XML Query Use Cases [
A query returning all books published by ”Addison-Wesley” is in XML-λ expressed as shown in Figure 1. xmldata("bib.xml") lambda b ( /book(b) and b/publisher = "Addison-Wesley" ) Previous sections outline the definition of type system TE that we use for modelling types in an XML schema. This means that for each DTD we can construct a particular type system of respective types. In the Language of terms we propose a mechanism based on lambda calculus operations (applications and abstractions) combined with projections to work with XML documents.
The most important idea in the framework is the fact that even the smallest piece of information in an XML document (e.g. an attribute of element containing just a PCDATA value) is modelled as a partial function that assigns a value for exactly one e ∈ E. For example, having an XML element <phone>+420-800123456</phone> there is a function phone(e) that for exactly one e ∈ E returns value +420-800123456. For more complex types, e.g. <!ELEMENT author (last, first)> the result of the function is a Cartesian product E × E.
In XML-λ we model each XML document by a set of items E where each e ∈ E is of type TIT EM . TIT EM is a type consisting of a couple (t : T Y P E, uid : IN T ); T Y P E ∈ T and uid is an integer value for maintaining order of items in the set. Note that some types in a particular type system can have related information attached (each item of type PCDATA has attached a value of the item – its content).
In following text we consider following semantic functions with informal meaning as summarized in following table:
Semantic Function parent(e) type(e) application(e, t) projection(n-tuple, t) childTypes(t)
Behaviour For an e ∈ E return its parent item For an e ∈ E return its type t (t ∈ T) Executes an application (rule 3 in Definition 4) of t-object to the e item. In general it returns a Cartesian product of E × . . . × E Retrieves all items of type t from given n-tuple.
Retrieves an list of types (sorted by document order) that might be contained in the result of application of a t-object
For further usage we present an algorithm of traversing a fragment of XML data utilizing our functional framework. The algorithm traverse(E, e, op) takes three parameters, E – set of items (this represents an XML document in our model) and e – start-up item for traversing, op – an operation to be performed on each node.
ALGORITHM traverse(E, e, op) 1: Initialize stack S; 2: Mark e as NEW; Push e to stack S; 3: while (any NEW or OPEN node in S) 4: Pop i from S; Mark i as OPEN; 5: Type t = type(i); 6: n-tuple nt = application(i, t); 7: List_of_types lt = childTypes(t); 8: if lt is String 9: op(i); 10: Mark i as CLOSED;
else 11: For each type in lt 12: n-tuple nt = application(i, type); 13: Mark all items as NEW and push to S; 4
Document Type Definition (DTD) [
EMPTY, ANY, MIXED or ELEMENT_CONTENT, 2. Structure constraints – The occurrence of elements in a content model. Options are exactly-one, zero-or-one, zero-or-more, one-or-more 3. Attributes constraints – #REQUIRED, #IMPLIED, #FIXED, ID, IDREF(S)
Each update operation can or cannot affect any construct from the particular DTD. Considering a transactional behaviour we can see two violation scenarios: 1. Fully consistent. After each operation (insert, update or delete) the instance remains valid. This means that we have to define a complete set of operations that are strong enough to perform all possible updates. 2. Partially consistent. In this mode we allow partial inconsistency i.e. we consider the whole query as an atomic operation. Therefore we do not require to have atomic insert,update and delete operations but we have to ensure that at the end of the processing the instance is valid. In general it means revalidation of the document being updated.
In our approach we use the first scenario and declare all operations as fully consistent.
With respect to abilities of the existing XML-λ framework we have to extend this framework with features allowing us to check constraints available in DTD. The cornerstone of the framework is its type system (it is the basis of types we can use). For modelling DTD constraints we propose four sets of types, where all types come from the type system, i.e. T ∈ TE . 1. Tunmodifable is a set of types that cannot be modified. This set contains types for attributes declared as #FIXED and element types with EMPTY content model. 2. Tmandatory is a set of types that must not be removed from a document instance because it would break the DTD constraints. This set contains attribute types with #REQUIRED declaration and element types for those T iff all occurrences of T are exactly-one. 3. Treferencing is a set of types that may reference another type, for DTDs those are attributes declared as IDREF or IDREFS. 4. Treferenced is a set of types that may be referenced by another type, for DTDs those are attributes declared as ID.
These sets we use in our semantics for particular update operations. We will use access functions isUnmodifable(e), isMandatory(e), isReferencing(e) and isReferenced(e) that check the containment of item’s type in respective sets.
In general the semantics of all operations consists of two parts: (1) Check if the operation is permitted regarding the DTD constraints and (2) Execution of given update operation. Following sections discuss the semantics of delete, insert and update operations in detail. 4.1
Deletion is a operation of removing given part of XML data (i.e. element or attribute) with its potential subelement(s). We can see the function with a signature DELETE(e) where e : t ∈ E, t ∈ T.
With respect to validity issues there are two scenarios where this operation is denied: 1. e is an attribute and is declared as #REQUIRED or #FIXED 2. e is an element with exactly-one or one-or-more occurrence
In our framework it means checking whether the type of item being deleted is a member of Tmandatory or Tunmodifiable sets. After that we have to ensure that by deleting of the item we do not delete the last remaining item with exactlyone or one-or-more occurrence. Following algorithm outlines conceptually the operation.
Algorithm delete(E, e) takes two parameters, E– set of items (this represents an XML document in our model) and e – the item to be deleted. It returns true if the item has been deleted or false if the delete has been denied. ALGORITHM delete(E, e): 1: if (isMandatory(e) or isUnmodifieble(e)) 2: return false; else p = parent(e); List_of_types pt = childrenTypes(p); if (type(e) in pt) is exactly-one
return false; if (type(e) in pt) is one-or-more and data contains at least 1 occurrence of item with type(e) return false; else traverse(E, e, delete); return true;
Informally we can imagine the operation as a subset subtraction Eresult = E \ e with ongoing renumbering of remaining items to keep document order. Maintenance of potential references in document (attributes of type ID, IDREF and IDREFS) that should take place in the traverse function. For now we consider it as being out scope of this paper.
By the insert operation we mean adding an XML fragment into the target document. By the fragment we understand an element, an attribute or an XML subtree. Insert is more complicated operation than delete because there are more conditions and restrictions to be checked. We write the statement as
INSERT e1 ( AFTER | BEFORE | AS CHILD) e2; where e1 : T1, e2 : T2 ∈ E; T1, T2 are types. Note that e1 must be a valid expression in T , i.e. it must be of a type from TE. We can see the operations as finsert(F, E1, Ei) = Eresult where F ∈ TE and Eresult = E1 ∪ Ei
Algorithm insert after(E, e1, e2) takes three parameters, E – set of items, e1 – the item to be inserted (e1 6∈ E) and e2 – the context item. It returns true if the item has been inserted or false if the insert has been denied. ALGORITHM insert_after (E, e1, e2): 1: p = parent(e1); 2: List_of_types pt = childrenTypes(p); 3: if (type(e1) not in pt) 4: return false; 5: if (following type of e2) is exactly-one and 6: item with the same type already exists in n-tuple 7: return false; 8: Put item into E and perform uid renumbering; 9: return true; Update operation means replacing one item by another with the same type. We can write the signature of this operation as UPDATE e1 WITH e2; where e1 : T1, e2 : T2 ∈ E; T1 = T2 are types.
Because of the fact that we require both expressions to be of the same type there cannot occur any validation conflict (both of them are valid before the operation). The algorithm for performing update is then straightforward.
First implementation of the XML-λ language was developed in [
With respect to the concept of the language we declare all operations as tagged terms. This means that we consider each function as a term of functional type (E → T ). Consequently we define the semantics for all operations.
Following fragment of EBNF shows a concept of including all operations into
the language
[
::= ConstructorPart QueryBody Eof
[
Insert Expr (after|before|as child of) SubQuery |
Note that the non-terminal SubQuery (rule [18] in [12, p.55]) presents a lambda term that may return set of items. There is also a significant advantage of using non-terminals SubQuery and Expr. In general these can be function calls (even user-defined). This is a difference with XUpdate, where only XPath expressions are used.
An example of delete operation removing all books published by
”AddisonWesley” is then written as follows
xmldata("bib.xml")
delete( lambda b ( /book(b) and b/publisher = "Addison-Wesley"))
The insert operation that adds a new element author after the first author of a
book specified by its name we write as
xmldata("bib.xml")
insert-after( lambda a (
/book(b) and b/title="TCP/IP Illustrated" and a=b/author[
We have shown a proposal for updating XML data constrained by a Document Type Definition. We present a functional framework for querying XML that is extended by structures for expressing DTD semantics. By enriching the query language with modification operations – inserts, deletes and updates – we obtain a language suitable both for querying and updating XML documents.
There is still a lot of future work ahead. To get a complete framework we have to finalize the issue with references within documents (IDs and IDREFS). This is only a technical problem how to formalize the algorithm to be executed to keep the documents consistent and valid. Another questionable area are the dependencies of multiple update operations in one ”query” statement. In this paper we do not solve any potential conflicts.
Probably the biggest challenge for future work is replacement of DTD by XML Schema. This means restructuring the type systems Treg and TE and redeveloping the idea of constraint sets.