=Paper=
{{Paper
|id=Vol-355/paper-5
|storemode=property
|title=On the Semantics of Updates in a Functional Language
|pdfUrl=https://ceur-ws.org/Vol-355/loupal.pdf
|volume=Vol-355
|dblpUrl=https://dblp.org/rec/conf/syrcodis/Loupal08
}}
==On the Semantics of Updates in a Functional Language==
https://ceur-ws.org/Vol-355/loupal.pdf
∗
On the Semantics of Updates in a Functional Language
c Pavel Loupal
Department of Computer Science,
Faculty of Electrical Engineering, Czech Technical University in Prague,
Prague, Karlovo nám. 13, 121 35
loupalp@fel.cvut.cz
Abstract ticularly in clarification of proposed update algorithms
and in specification of a link to transaction management.
Issues related to updating data in native XML The paper is structured as follows: Section 2 lists ex-
database systems are studied extensively nowa- isting approaches for updating XML data and discusses
days. In this work we consider a problem of their contribution. In Section 3 we briefly outline the
updating typed XML documents having their concept of the functional framework we use, its data
schema described by a Document Type Def- model and show an example of query evaluation with
inition (DTD) without breaking their validity detailed description. Then, we discuss the problem of
and with ensured transaction consistency. We updates in Section 4 in general and show our solution in
present a way how to express constructs avail- Section 5. In Sections 6 and 7 we conclude with feasible
able in DTD by using a functional framework ideas for future work.
and propose algorithms for performing insert,
replace and delete operations. This solution is 2 Languages for Updating XML
an intermediate step we need for our ongoing
research – formal comparison of XQuery and By the term updating XML we mean the ability of a
XML-λ. language to perform modifications (insert, replace and
delete operations) over an XML document or a collec-
tion of XML documents.
1 Motivation and Problem Statement Since the creation of the XML in 1998, there have
been many efforts to develop various data models and
Fundamental work we continue to work on is Pokorný’s
query languages for databases of XML data. Multiple
proposal of a functional framework for modeling and
approaches for indexing and query optimizations have
querying XML – XML-λ [15, 16]. The main idea therein been invented. On the other hand, the problem of up-
is to use simply typed λ-calculus adherent to a DTD-
dating XML gains more interest in few past years. Yet
based type system for querying XML data. Over time we
there seems to be not a complete solution for this prob-
identified a need for extending the language with support lem. Existing papers dealing with updating XML are
of data modification operations. Our aim is to develop
mostly related to XQuery [3]. Lehti [11] proposes an ex-
an approach similar to the SQL language for relational
tension to XQuery that allows all update operations but
databases, i.e. to have an ability both to query and up- does not care about the validity of the documents. Tatari-
date underlying data within one formal apparatus.
nov et al. [18] also extend XQuery syntax with insert, up-
This work directly continues in the topic that we have date and delete operations and show the implementation
opened in [13]; in this text we clarify more the con- of storage in a relational database system. Benedikt et
cept of the framework by showing its relationship to the al. [1] and Sur et al. [17] deal in deep with the semantics
W3C data model, reformulate proposed algorithms and of updates in XQuery. In the W3C XML Query Work-
we also add some improvements in formal description of ing Group is the need for having updates in the language
the solution. also considered as one of the most important topics in its
Nevertheless, our primary motivation is not to de- further development [5]. As a result, the XQuery Update
velop a totally new sort of an XML update language but Facility has been proposed [6].
rather to propose an update extension that allows us to go For the sake of completeness we should not omit
on with our planned research in the future – comparison XUpdate [10] – a relatively old proposal that takes a dif-
of properties of XQuery and XML-λ and evaluation of ferent way. It uses XML-based syntax for describing up-
potential mutual transformations of queries written in re- date operations. This specification is less formal than
spective languages. We see the benefit of this paper par- those previous but it is often used in practice.
∗ I would like to thank to Prof. Pokorný for his patience and pro-
Another research field is represented by XDuce [9]
visioning of many helpful hints for my research. and its successor CDuce [2] that use also a type system
Proceedings of the Spring Young Researcher’s Colloquium
based approach for pattern matching and manipulation of
on Database and Information Systems, Saint-Petersburg, Rus- XML data.
sia, 2008 Considering previous works we can deduce that there
are common types of operations for performing modifi- these functions to an abstract element allows access to
cations that are to be embedded in a language – delete, element’s content. Elements are, informally, values of
replace, insert-before, insert-after or insert-as-child. This element objects, i.e. of functions. For each t ∈ TE there
seems to be a sufficient base for ongoing work. None of exists a corresponding t-object.
those proposals but deals in detail with the problem of For convenience, we add a ”nullary function” (also
updating typed data and hence it makes sense to put ef- known as 0-ary function) into our model. This function
fort and study this problem. returns a set of all abstract elements of a given element
type from an XML document.
3 XML-λ Framework Finally, we can say that in XML-λ the instance of an
XML document is represented by a subset of E and set
XML-λ is a proposal published by Pokorný [15, 16]. In of respective t-objects.
contrast to W3C specifications it uses a functional data For readers familiar with W3C terminology, there is a
model instead of tree- or graph-oriented model. The comparison of related terms in both environments shown
primary motivation was to see XML documents as a in Table 1.
database that conforms to an XML schema (defined, for
example, by DTD) and to gain a possibility to use a func- 3.2 XML-λ Example
tional language, particularly a simply typed λ-calculus,
as a query language for such database. This section shows an example of using the XML-λ
Except of the original proposal, that defines its formal Framework in a real example with detailed description.
base and shows its usage primarily as a query language Let us consider an example DTD shown in Figure 2.
for XML, there is a consecutive work that introduces up-
dates into the language available in [13].
Here, we focus primarily on extending and improving
the update part of the framework. Basic facts about the
framework are repeated in following sections rather for
convenience.
3.1 Basic Terms
In XML-λ there are three important components related
to its type system: element types, element objects and el- Figure 2: Example DTD
ements. We can imagine these components as the data For given schema we obtain element types as follows:
dictionary in relational database systems. Note also Fig-
ure 1 for relationships of basic terms between W3C stan- BIB : BOOK∗,
dards and the XML-λ Framework. BOOK : (T IT LE, AU T HOR+, P RICE),
Element types are derived from a particular DTD and AU T HOR : (LAST, F IRST ),
in our scenario they cannot be changed – we do not al- LAST : String,
low any schema changes but only data modifications. For F IRST : String,
each element defined in the DTD there exists exactly T IT LE : String,
one element type in the set of all available element types P RICE : String.
(called TE ).
Consequently, we denote E as a set of abstract el- Then, we define functional types – designated as
ements. Set members are of element types. Note that t-objects:
(from definition) E is an infinite set.
BIB : E → 2E ,
BOOK : E → (E × 2E × E),
AU T HOR : E → (E × E),
T IT LE : E → String,
LAST : E → String,
F IRST : E → String,
P RICE : E → String.
These types are the cornerstone for manipulation with
typed data from XML documents as shown in the list of
semantic functions (see Table 2).
Having look at DTD in Figure 2 and sample
data in Figure 3 we can obviously see that there
are 7 abstract elements (members of E 0 ⊂ E).
Figure 1: The Relationship Between W3C and XML-λ Now, for instance, the title-object is defined ex-
Data Models actly for one abstract element (the one gained from
TCP/IP Illustrated element and
Element objects1 are basically functions of type either
for this abstract element it returns a string value ”TCP/IP
E → String or E → (E × . . . × E). Application of
Illustrated”.
1 We denote the element object of type t ∈ T as t-object
E
W3C XML-λ
Data Format XML 1.0 XML 1.0
Data Model Constraints Document Type Definition (DTD) Types in TE derived from DTD
XML Data Instance DOM - A tree instance Set of abstract elements – E, definition of t-objects
Query Languages XPath, XQuery, XSLT Simply typed lambda calculus
Table 1: The Relationship Between W3C and XML-λ Terms
TCP/IP Illustrated
TCP/IP Illustrated
Stevens
Stevens W.
W.
65.95
65.95
...
Figure 4: Expected Query Output
stable but the data is changing in time. In our (query
and update) language there is no way how to construct
Figure 3: Fragment of a Valid XML Instance new documents yet – sometimes this approach is called
”incremental update”. In other words we can change
Following example query returns all books with spec- the structure of the input document (w.r.t the DTD) by
ified price a given XML-λ update statement but cannot e.g. create
a set of new XML files.
lambda b (/book(b) and b/price = "65.95" )
Evaluation of this query with respect to semantics de- 4.1 Updates in General
scribed in [19] takes place in following way: We can describe the whole operation of updating an
XML document rather on a physical level as (1) retriev-
1. First, the binding of free variable b is evaluated ing its content from database, (2) performing update, (3)
(/book(b)), i.e. nullary function returns a set of storing document back to database. This paper deals with
all abstract elements of element type BOOK). the second part of the process. Viewed from closer look
2. For each item in b the application of BOOK-object in more detailed pieces it is (a) localization of point in
element (note, it is a function) is performed data model where the change will take place, (b) vali-
dation of requested operation, (c) execution of the up-
BOOK : E → (E × . . . × E) date operation. These steps are shown more from the
and this operation returns an n-tuple. semantical point of view, in implementation it is usually
not necessary to retrieve complete XML document from
3. Projection by name price returns then item(s) of database into memory but we can manipulate only with
type PRICE (there is just one). Application of func- a part of its content needful for update.
tion P RICE : E → P RICE : String returns a There are two options when to perform data valida-
string value of the price element that is compared tion – before or after an update. The XQuery Update Fa-
with literal ”65.95”. Non-matching item is skipped, cility proposal uses optional post-update revalidation; in
otherwise the content of b is serialized to output. our approach we focus more on doing pre-update checks.
4. Steps 2.-3. are repeated for all items found in Step 1. Our goal is to detect the maximum number of possible
conflicts during compilation of the update statement and
For readers familiar with XQuery, here is the same potentially raise a static error. Unfortunately, not in all
query expressed in XQuery syntax: cases is the information from data model enough for val-
idation and, therefore, it is necessary to perform vali-
{ dation with respect to particular data stored in the data
for $b in doc("bib.xml")/bib/book store. We discuss this issue later in Section 5. Regard-
where $b/price = "65.95" less the scenario, the processed XML document is a valid
return {$b} instance in the type system both before and after update.
}
4.2 Validation Constraints in DTD
Expected output is shown in Figure 4.
Document Type Definition (DTD) [4] is a syntactic way
4 Updating XML Documents how to describe a valid XML instance. We can break all
DTD features into disjoint categories:
This section covers the process of updating data in an
existing XML data store. Thus, we do not update XML 1. Elements constraints - Specify the type of element
schema of these documents but their content only. It is a content. The possible value is one of EMPTY, ANY,
typical database life cycle – the database schema remains MIXED or ELEMENT_CONTENT,
2. Structure constraints - The occurrence of elements and then semantics of all supported update operations –
in a content model. Options are exactly-one, zero- insert, delete and replace.
or-one, zero-or-more, one-or-more,
5.1 Validation Approach
3. Attributes constraints - Each attribute can have one
of #REQUIRED, #IMPLIED, #FIXED, ID, IDREF(S) In this paper we base our work on constraints available
options assigned. in DTDs. The goal here is to describe these limitations
in general as much as possible for eventual future ex-
Each update operation can or cannot be affected by tensions. Validating update operations is a problem very
any construct from the particular DTD. Note that element closely related to the problem of validating a complete
content type ANY cannot be used in XML-λ, because of XML instance. This process, however, can be for exten-
the framework’s type system nature. sive documents very time consuming.
In our approach we propose two sets of types and al-
4.3 Concept of Updates in XML-λ gorithms for validation for each update operation. Men-
tioned sets are constructed and initiated during analysis
This section covers the basic concept of updates in the of given DTD and contain element types from TE . Due
XML-λ Framework. It initially had not have any update to the fact that we do not allow schema changes, they are
facility. We had to extend it with features allowing us to stable in time.
check constraints available in DTD. The idea of updates
has been opened in [13] but here we focus just on the 1. Timmutable . Abstract elements of types from this
main idea. set and respective t-objects are not changeable in
As already outlined in Section 3.1, there are three our data model. In terms of DTD these types are as-
crucial components related to the type system - element sociated with DTD types which content cannot be
types, element objects and abstract elements. Element modified, i.e. attributes declared as #FIXED and el-
types are derived from a particular DTD and in our sce- ement types with EMPTY content model.
nario they cannot be changed.
Elements are, informally, values of element objects, 2. Tmandatory . Abstract elements of types from this
i.e. of functions. Thus, by updating an XML document set and respective t-objects are not modifiable (must
in XML-λ we modify the actual domains of these func- not be removed) in our data model. In terms of
tions (subsets of E) and element objects affected by re- DTD this set contains types associated with at-
quired update operation (insert, delete, replace). tribute types with #REQUIRED declaration and ele-
Before of that, we have to validate requested opera- ment types for those types Ti iff all occurrences of
tion. For now let us consider constraints described by Ti in given DTD are exactly-one.
a DTD but in the outlook there are more options which
standards we plan to use as well (e.g. XML Schema). These sets we use in our semantics for particular
Therefore we design our solution keeping this possibility update operations. For future work we can also con-
in mind. sider sets Tref erencing and Tref erenced of types associ-
Sections 5.3 - 5.5 discuss the semantics of delete, in- ated with attributes declared in given DTD as IDREF or
sert and replace operations in detail. IDREFS and for attributes declared as ID respectively. In
following text we use number of functions with informal
meaning as summarized in Table 2.
4.4 Concurrency Support
One disadvantage of the solution proposed in [13] is the 5.2 General Notes to Proposed Algorithms
lack of transaction support [7]. In this work we assume
Following sections contain particular algorithms for data
the existence of a transaction manager that can control
modification shown in detail. The most important of
(i.e. lock, unlock, suspend or abort) user activities. Cur-
them – Delete and Insert – follow the same structure.
rently we carry out a parallel research on using the ta-
First, they check (optionally) the validity of the operation
DOM locking protocol [8] together with XML-λ (there
and if there is no conflict with the type system definition
is a recent paper that introduces our first proposal of the
they break down the modification into a list of primitive
transactional behavior for XML-λ in [14]).
operations (stored in a structure also known as the ”Pend-
For now, we can consider that a transaction manager
ing Update List”). This list represents hence the result of
locks the complete part of XML data that can be modified
these algorithms. Note that the Replace algorithm com-
during the update operation (in the worst case even the
bines aforesaid Delete and Insert with within. The items
whole XML document). It is a significant performance
inside the list are pairs (e, op), where e ∈ E is an ab-
issue but for purpose of this paper it is not fundamental.
stract element and op ∈ {DELET E, IN SERT } is the
Thus, at the beginning of suggested algorithms we
operation to be carried out.
only ask for locking of a specific part of processed XML
The output pending update list, that represents the re-
document and keep all concurency-related worries and
sult of each update algorithm, is then passed to the Pro-
issues on the ”virtual” transaction manager.
cessPendingList algorithm. This algorithm then executes
all primitive changes requested.
5 Analysis and Design of Updates in
XML-λ 5.3 Delete
In this section we describe two parts of the update pro- Formally, we decompose the process into two parts – a
cess – general concept of validation we use in XML-λ function checkDelete that is used for checking whether
Semantic Function Behavior
parent(e) For an e ∈ E returns its parent abstract element. An abstract element can have at most one
associated ”parent” element. When considering E as infinite set of abstract elements, most of
them have no parent associated.
typeOf(e) For an e ∈ E returns its element type (see Section 3.1).
cardMin(e),cardMax(e) Return minimal (or maximal, respectively) cardinality of an abstract element’s type in a particular
data model instance.
alterTObjectDel(e, t), Alters the t-object for given e ∈ E. Regarding the fact that t-objects are functions these semantic
alterTObjectIns(e, t) functions change the domain of given t-object and thus associations among abstract elements.
Basically, alterTObjectDel removes the abstract element e from domain of the t-object and
alterTObjectIns adds the abstract element e into the domain.
isSubtype(t1, t2 ) Describes a relation between element types t1 and t2 . Returns true iff the result of
application(e, t2 ) for an e ∈ E can return an n-tuple containing an abstract element of type t1 (at
any position).
canSubstitute(t1, t2 ) Returns true iff an abstract element e1 of type t1 can replace an element e2 of type t2 without
breaking document’s validity. It is utilized in the Replace algorithm.
isElementary(t) Returns true iff t is an elementary element type.
application(e, t) Executes an application of t-object to the e element. In general it returns an n-tuple from Carte-
sian product of (E × . . . × E).
Note that the application function serves for diving in the ”content” of an element.
projection(n-tuple, t) Retrieves all elements of type t from given n-tuple.
count(n-tuple) Returns number of elements in an n-tuple.
Table 2: List of Semantic Functions and their Informal Meaning
an abstract element can be deleted and a complete algo- let S = new Stack(); S.push(e);
rithm Delete that accomplishes the operation completely:
while (tmp = S.pop()) do
Function: checkDelete; let t = typeOf (tmp);
Input: E - set of abstract elements let nt = application(tmp, t);
e - an abstract element to be deleted For i = 1 to count(nt)
Output: returns true - deletion is allowed, let etmp = nt[i];
false - deletion is denied let ttmp = typeOf (etmp );
begin
let t = typeOf (e); /* Elementary element types are added into
if ((t ∈ Tmandatory ) or (t ∈ Timmutable )) then the pending delete list */
return false; if (isElementary(ttmp )) then
if ((cardM in(e) = 0) and (cardM ax(e) = ∞)) then pList.add(etmp , DELET E))
return true; else
if ((cardM in(e) ≥ 1) and /* Complex element types are stored for
(count(application(parent(e), t)) > 1)) then next iterations */
return false; S.push(etmp );
return true; next;
end end
Algorithm: Delete;
/* Add the initial abstract element to pending list */
Input: E - set of abstract elements
pList.add(tmp, DELET E);
e - an abstract element to be deleted
checkV alidity - a boolean flag. Enables or
/* Deletion is finished */
disables validity check. Default is true.
return true;
trans - a new transaction
end
pList - a list of currently pending update
operations
Output: returns true - delete is allowed, 5.4 Insert
false - delete failed As for the Delete algorithm, we propose two parts of the
pList - updated list of pending operations insert process – function checkInsert that validates inser-
begin tion of given abstract element and Insert algorithm that
/* Lock the data being deleted */ implements the operation in whole.
trans.lockRequest(DELET E N ODE, e);
Function: checkInsert;
/* Check type constraints - if requested */ Input: E - set of abstract elements
if (checkV alidity) then e1 - an abstract element to be inserted,
if (not checkDelete(E, e)) then return false; e2 - an abstract element to be associated with e1
as its parent abstract element,
Output: returns true - insertion is allowed, /* Add the initial abstract element to pending list */
false - insertion is denied pList.add(e1 , IN SERT )
begin
let t = typeOf (e2 ); /* Insert is finished */
if (t ∈ Timmutable ) then return false; return true;
end
/*Traversing through all ”sibling” abstract elements*/
let nt = application(tmp, t); 5.5 Replace
for i = 1 to count(nt) The replace operation can be logically separated into
let etmp = nt[i];
two parts – first, the removal of old data and then in-
let ttmp = typeOf (etmp ); sertion of new data. To ensure that the XML instance
if (isSubtype(typeOf (e1), ttmp )) then remains valid we have to check the relation between
if (cardM ax(etmp ) > 1) then return true;
types of deleted and inserted data. For this reason we
if ((cardM in(e) = 0) and introduce the canSubstitute(told, tnew ) semantic func-
(cardM ax(etmp = ∞)) and tion. This function returns true if and only if we can
(count(application(etmp , ttmp )) = 0)) then
replace an abstract element e1 of type told with e2 of
return true; type tnew (for example, for t1 = (a|b), t2 = a ⇒
next; canSubstitute(t1, t2 ) = true).
return false;
Note that we turn off the type validation for partic-
end ular Delete and Insert calls. Type validity is already
Structure of the Insert algorithm is similar to the checked at the beginning of the algorithm.
Delete algorithm. It is generally a traversal of given data
Algorithm: Replace;
model instance with modification of currently processed
Input: E - set of abstract elements
abstract element of elementary type.
e1 - an abstract element to be replaced,
Algorithm: Insert; e2 - an abstract element used as the substitution of e1
Input: E - set of abstract elements trans - a new transaction,
e1 - an abstract element to be inserted, pList - a list of currently pending update operations
e2 - an abstract element to be associated with e1 Output: returns true - replace is allowed,
as its parent abstract element, false - replace failed
checkV alidity - a boolean flag. Enables or pList - list of pending update operations
disables validity check. Default is true. begin
trans - a new transaction /* It must be allowed to replace e1 with e2 */
pList - a list of currently pending update operations if not (canSubstitute(typeOf (e1), typeOf (e2 )) then
Output: returns true - insert is allowed, return false;
false - insert failed
pList - updated list of pending operations let etmp = parent(e1 );
begin if not Delete(E, e1, trans, f alse, pList) then
/* Lock the data being inserted */ return false;
trans.lockRequest(IN SERT N ODE, e1 ); if not Insert(E, e2 , etmp , trans, f alse, pList) then
return false;
if (checkV alidity) then
if not checkInsert(E, e1 , e2 ) then return false; /* Replace is finished */
return true;
let S = new Stack(); S.push(e); end
while (tmp = S.pop()) do
let t = typeOf (tmp); 5.6 Pending Update List Processing
let nt = application(tmp, t); The Delete, Insert and Replace algorithms introduced in
For i = 1 to count(nt) previous sections transform high-level manipulation op-
let etmp = nt[i]; erations into a sequential list of primitives that is stored
let ttmp = typeOf (etmp ); in the structure called Pending Update List – here it is
denoted as variable pList. This list is to be processed by
/* Elementary element types are inserted the database engine at the end of each high-level opera-
into pending list */ tion in cooperation with the transaction manager.
if (isElementary(ttmp )) then Following algorithm describes the operation more for-
pList.add(etmp , IN SERT ) mally.
else
/* Complex element types are stored for Algorithm: ProcessPendingList;
next iterations */ Input: E - set of abstract elements
S.push(etmp ); t-objects associated with affected abstract elements
next; pList - a list of currently pending update operations
end Output: pList - an empty pending list,
E - (potentially modified) set of abstract elements, The third option for ongoing research is using the
t-objects - (potentially modified) t-objects framework for description of XQuery’s semantics. This
begin is probably the most interesting research branch from the
while (pList.hasN ext()) do theoretical point of view. It generally means that we will
let tmp = pList.next(); pList.remove(); be able to express any XQuery statement with a corre-
let e = tmp.getItem(); sponding XML-λ alternative. This idea represents a the-
let t = typeOf (parent(e)); oretical research related to formal methods and compil-
let op = tmp.getOperation(); ers. In this case the framework is going to be used as a
tool for transformation of queries between various query
if (op == IN SERT ) then and update languages. In addition, we can use this tool
let E = E ∪ e; for evaluation of XQuery queries within our prototype
alterT ObjectIns(e, t); of a native XML database system ExDB [12] based on
else / ∗ DELET E ∗ / XML-λ.
let E = E \ e; Another feasible challenge for future work is redefini-
alterT ObjectDel(e, t); tion of the type system by replacement of DTD types by
next; types available in XML Schema or in RELAX NG. This
end means restructuralization of the type systems Treg and
TE and redevelopment of the idea of constraint sets. This
/* Pending List is now empty */ research would demonstrate that the concept of func-
end tional framework is not strictly bound to DTD but is more
general as we declare.
5.7 Query Language Impact
Considering the XML-λ Query Language as specified 7 Conclusion
in [13], we have changed and extended the semantics We have shown a proposal for updating typed XML data
of all update operations. The syntax of the language re- constrained by a Document Type Definition. We build
mains the same. on a functional framework for querying XML that can
utilize concept of DTD constraints in its type system TE .
6 XML-λ’s Future Exploitation Main part of the paper discusses the idea of extending the
By the extensions proposed in this paper we obtain a framework with update operations with accent to keep
framework suitable for both querying and updating XML the documents always valid. By enriching the XML-λ
data. With respect to its original idea there is a number query language with modification operations - inserts,
of potential applications of the framework. Let us sketch deletes and replacements - we obtain a language suitable
three possible ways how to continue with its develop- both for querying and updating XML documents.
ment: Further work and research directions outlined in Sec-
tion 6 lead to onward framework extensions – either im-
1. further expand its query and update capabilities, proving its query capabilities, using it for integration of
heterogeneous data or utilizing the framework for de-
2. use it for integration of heterogeneous data sources,
scription of semantics of various query languages.
3. use the XML-λ’s formal apparatus for description In any case the work presented in this paper creates
of XQuery semantics. sufficient base for extensive future work.
For each option there is still a lot of work ahead. To
References
get a complete query framework we have to finalize an is-
sue with references within documents (IDs and IDREFS). [1] M. Benedikt, A. Bonifati, S. Flesca, and A. Vyas.
This is only a technical problem of introducing new types Adding updates to XQuery: Semantics, optimiza-
and formalizing the algorithm to be executed to keep the tion, and static analysis. In XIME-P 2005, 2005.
documents consistent and valid. Let us also note another
questionable area that is not covered in this paper and [2] V. Benzaken, G. Castagna, and A. Frisch. CDuce:
thus the dependencies of multiple update operations in An XML-centric general purpose language. In Pro-
one ”query” statement. This issue deals with transac- ceedings of ICFP 2003, Uppsala, Sweden, August
tional processing and optimizing multiple update primi- 2003.
tives’ execution.
[3] S. Boag, D. Chamberlin, M. F. Fernández, D. Flo-
This option is also questionable because of wide ac-
rescu, J. Robie, and J. Siméon. XQuery
ceptance of XQuery as the de-facto theoretical and indus-
1.0: An XML Query Language, January 2007.
trial standard in the area of query languages for XML. At
http://www.w3.org/TR/xquery/.
least, the research here will require extensive enthusiasm
and sufficient resources. [4] T. Bray, J. Paoli, C. M. Sperberg-McQueen,
Integration of heterogeneous data sources (as outlined E. Maler, and F. Yergeau. Extensible markup lan-
in [15]) is a practical application of the solution we have guage (XML) 1.0 (fourth edition), August 2006.
presented. With respect to the universal type system con- http://www.w3.org/TR/2006/REC-xml-20060816.
struction it is possible to use various data models (not
only DTD or XML Schema for XML) but for instance [5] D. Chamberlin. XQuery: Where do we go from
the relational or object data model as well. here? In XIME-P 2006, 2006.
[6] D. Chamberlin, D. Florescu, J. Melton, J. Ro-
bie, and J. Siméon. XQuery Update Facility
1.0, March 2008. http://www.w3.org/TR/2008/CR-
xquery-update-10-20080314/.
[7] C. J. Date. An Introduction to Database Systems,
6th Edition. Addison-Wesley, 1995.
[8] M. P. Haustein and T. Härder. A synchronization
concept for the DOM API. In H. Höpfner, G. Saake,
and E. Schallehn, editors, Grundlagen von Daten-
banken, pages 80–84. Fakultät für Informatik, Uni-
versität Magdeburg, 2003.
[9] H. Hosoya and B. Pierce. Xduce: A statically typed
XML processing language, 2002.
[10] A. Laux and L. Martin. XUpdate – XML Update
Language, 2000. available online at http://xmldb-
org.sourceforge.net/xupdate/index.html.
[11] P. Lehti. Design and implementation of a data
manipulation processor for an XML query lan-
guage. Master’s thesis, Technische Universitaet
Darmstadt, 2001.
[12] P. Loupal. Experimental DataBase (ExDB) Project
Homepage. http://swing.felk.cvut.cz/~loupalp.
[13] P. Loupal. Updating typed XML documents using a
functional data model. In J. Pokorný, V. Snášel, and
K. Richta, editors, DATESO, volume 235 of CEUR
Workshop Proceedings. CEUR-WS.org, 2007.
[14] P. Loupal. Using taDOM Locking Protocol in a
Functional XML Update Language. In DATESO,
2008.
[15] J. Pokorný. XML functionally. In B. C. Desai,
Y. Kioki, and M. Toyama, editors, Proceedings
of IDEAS2000, pages 266–274. IEEE Comp. So-
ciety, 2000.
[16] J. Pokorný. XML-λ: an extendible framework for
manipulating XML data. In Proceedings of BIS
2002, pages 160–168, Poznan, 2002.
[17] G. M. Sur, J. Hammer, and J. Siméon. An XQuery-
Based Language for Processing Updates in XML.
In PLAN-X 2004, 2004.
[18] I. Tatarinov, Z. G. Ives, A. Y. Halevy, and D. S.
Weld. Updating XML. In ACM SIGMOD 2001,
2001.
[19] P. Šárek. Implementation of the XML lambda lan-
guage. Master’s thesis, Dept. of Software Engineer-
ing, Charles University, Prague, 2002.