日本ソ フ ト ウ ェ ア 科学会第 30 回大会 (2013 年度) 講演論文集

BiFluX: A Bidirectional Functional Update
Language for XML
Tao Zan, Hugo Pacheco and Zhenjiang Hu
XML formats are widely used for information exchange and data processing. A common use is to store
information in the same way as relational databases, and many XML query languages such as XQuery havebeen developed for this purpose. De facto XML processing languages are traditionally unidirectional, in thesense that programmers write transformations from source formats to view formats, but backward updating,i.e., translating view modifications into the original XML database, is not considered. To cover this gap,
existing XML bidirectional languages propose particular linguistic mechanisms that aid programmers inwriting a forward XML transformation, such that a consistent backward transformation can be derived forfree. Unfortunately, as the classical view-update problem for relational databases, backward transformations
are generally not unique and existing bidirectional systems simply provide one out of many possible, which
may not match the programmer’s expectations of a view update.
This paper introduces BiFluX, a novel bidirectional XML update language inspired on Flux, a functional XML update language. BiFluX follows a pragmatically different approach from existing bidirectional
languages: instead of writing (simpler) XML queries, programmers write backward transformations by specifying how a view format can be used to update a source database, for which there is a unique query. The
novel approach allows programmers to transparently control how view updates can be reflected back to an
XML database, while offering bidirectionality.

Originated from the well-known view updating

1 Introduction

problem in the database community [1], one of the

Bidirectional transformations [7] [11], transforma-most popular bidirectional transformation idioms

tions that execute both forwards and backwards,

are lenses [9]. A lens focuses on a special asym-

aim at enforcing some notion of consistency be-

metric case: a forward transformation get defines

tween two data domains. Since data evolves natu-

a view of a source database that usually contains

rally over time and is often replicated among differ-more information, and a backward transformation

ent applications, this pattern reoccurs with various

put defines a view update strategy that synchro-shapes in many computer science disciplines, suchnizes an original source database with a modified

as databases, model transformations, data synchro-

view. Naturally, these transformations shall not be

nization or user interfaces.

arbitrary and are expected to satisfy two instrumental well-behavedness properties:

BiFluX: A Bidirectional Functional Update Language
for XML
Tao Zan, Department of Informatics, The Graduate
University for Advanced Studies.
Hugo Pacheco, Information Systems Architecture Research Division, National Institute of Informatics.
Zhenjiang Hu, Information Systems Architecture Research Division, National Institute of Informatics.

put s (get s) = s

PutGetget (put s v) = v

GetPut

The PutGet property means that a lens is acceptable and all views can be reflected to thesource: applying the forward transformation after
putting back any view shall return the same view.

The GetPut property means that a lens is stable:ming of put. Nevertheless, this is not a trivial task

putting back a view immediately after getting it

since not all said put transformations satisfy theshall yield the original source.

bidirectional laws. Moreover, put : S → V → S

During the last decade, several bidirectionalis evidently harder to write than get : S → V ,programming languages [9] [10] [3] [4] [14] [15] [12] haveas programmers cannot think solely in source-to-been developed to aid programmers in writing bidi-

view terms but must consider more complex up-

rectional programs that resemble writing a forward

date strategies that synchronize view updates with

get transformation, and provide automatic mech-existing sources. Therefore, the programmer shallanisms to derive a suitable backward put trans-

be guided and restrained accordingly by a practicalformation for free. Such languages permit writing

put programming approach.

bidirectional programs that are easier to maintain,

In previous work [16] we have explored the design

but fail to adequately address the inherent ambi-

of a put-based language whose building blocks are

guity problem of bidirectional transformations [5].

injective put s transformations (of type V → S),

As most interesting cases of get transformations

for any source s. This motivates a specification

are not injective, there may exist many possiblestyle dual to that of get-based languages, by com-

put transformations that combined with get form

posing put-based combinators from view to source,a well-behaved lens. Despite of this fact, existing

but that allows users to control in a predictable way

bidirectional languages are only designed to sat-the behavior of the backward transformations thatisfy fundamental well-behavedness principles andthey write.

only consider one particular synchronization strat-

Notwithstanding, writing a program in a (get-egy that may not match the programmer’s expecta-

based or put-based) bidirectional language typi-

tions for particular updates. This non-uniquenesscally implies describing the concrete steps that con-often leads to unpredictable bidirectional behavior

vert source databases into smaller views.

as these languages give little insight to users about

makes it impractical to express queries over even-which particular backward synchronization strat-

tually large databases, since one must explicitly de-egy is chosen among the myriad possible.

scribe how it ignores unrelated parts of the source.

An insightful observation is that while one get

This

In this paper, we investigate another approach:transformation may be combined with several put

to flip the definition of put and develop a languagetransformations, only one get transformation isof put v functions (of type S → S), for some view v.

possible per put under the corresponding consis-

This parameterization on views motivates a bidirec-

tency properties. This primacy of put has beentional update language (in contrast to bidirectional

shown in [8] and encourages an excitingly powerfultransformation languages) in which programmers

approach to specifying bidirectional lens programs

write bidirectional updates that modify an originalby their backward transformations, with the dis-

database to embed some view information. Type-tinctive advantage of being capable of completely

preserving updates are simpler to write than type-

expressing all aspects of a bidirectional transforma-changing transformations in that one only needs totion, while retaining the maintainability of writing

specify how the view information changes a smalla single program.

part of the source, leaving the remaining data fixed.

A logical conclusion is then to focus the design

We demonstrate the feasibility of the novel ap-

of a bidirectional language entirely on the program-proach by proposing the BiFluX language for thebidirectional updating of XML databases. BiFluX
is a bidirectional variant of Flux [6], a functional
XML update language. We lift unidirectional Flux
updates to bidirectional BiFluX updates that carryan additional notion of view. Reading BiFluX programs as put transformations will motivate several
language extensions and demand a careful choice ofsemantics and extra static conditions on updates toensure that view information is indeed put back tothe source, thus building well-behaved lenses.
The rest of the paper is organized as follows.
Section 2 gives a taste of our BiFluX bidirectional
update language with a simple lens transformation
written in two different styles. We give an overview<person><name>Tao Zan</name><email>zantao@nii.ac.jp</email><email>zantao007@gmail.com</email><tel>+81-3-5841-7430</tel></person><person><name>Hugo Pacheco</name><email>hpacheco@nii.ac.jp</email><email>hpacheco@di.uminho.pt</email><tel>+81-3-5841-7411</tel></person><person><name>Zhenjiang Hu</name><email>hu@mist.i.u-tokyo.ac.jp</email><email>hu@ipl.t.u-tokyo.ac.jp</email><tel>+81-3-5841-7411</tel></person></addrbook>of the features of the BiFluX language in Section 3

Now imagine that we want to summarize ourand demonstrate them with various practical exam-source address book into a simpler view address

ples in Section 4. Section 5 concludes and discusses

book where people only have one email, and no tele-

directions for future work.

phone numbers, according to the following DTD.

2 Motivation Example

The purpose for this may be for instance to exhibit

This section begins by illustrating a typical ex-a minimal address book in an email application that

ample of a bidirectional transformation written in a

has no concern for telephone addresses.

standard bidirectional programming language. We<!DOCTYPE addrbook [<!ELEMENT addrbook (person*)><!ELEMENT person (name,email)><!ELEMENT name (#PCDATA)><!ELEMENT email (#PCDATA)>]>

then exemplify how the same transformation canbe expressed in BiFluX, giving a flavor of the novel
bidirectional updating style.

For this purpose, we would like to write a bidirec2. 1 Bidirectional programming

tional transformation between the two source andLet us start by defining an address book regularview schemas, providing us a forward transforma-

expression type according to the following DTD.
<!DOCTYPE addrbook [<!ELEMENT addrbook (person*)><!ELEMENT person (name,email+,tel)><!ELEMENT name (#PCDATA)><!ELEMENT email (#PCDATA)><!ELEMENT tel (#PCDATA)>]>

An address book contains a list of persons, each onetion that gets a simplified address book from a more
complete address book and a backward transformation that synchronizes a simplified address bookwith an original address book that contains more
information about each person. One possible way
is to write this bidirectional transformation in the
Boomerang string lens language [3]:possessing a name, a non-empty list of emails and atelephone number. The following XML document
encodes a database of three persons conforming tothis type definition:<addrbook>

let ALPHA = [A-Za-z]+
let DOMAIN = [A-Za-z|.|-]+
let EMAIL = ALPHA . "@" . DOMAIN
let TEL = "+81" . "-" . [0-9] ."-"
. [0-9]{4} ."-" . [0-9]{4}let emails = (del ", " . del EMAIL)*
let comp = key ALPHA . copy ",". copy EMAIL . emails . copy ", ". ins TEL "+81-0-0000-0000"
let comps = copy "" | <comp> . ("\n" . <comp>)*mixed together into a single lens design, namely
key, angle brackets <comp> and ins. These additional combinators are used to provide extra information on how to derive a corresponding backward

Since string lenses were not specifically designed

transformation strategy. Consider for example thefor XML processing, to avoid distracting the read-

modified view address book where we reorder Zhen-

ers from the essential we assume that the XML for-jiang (while updating his email) and Tao and insert

mats are flattened into a simpler format of strings

a new person John Doe:

where fields are separated by commas and people<addrbook><person><name>Zhenjiang Hu</name><email>hu@nii.ac.jp</email></person><person><name>Tao Zan</name><email>zantao@nii.ac.jp</email></person><person><name>John Doe</name><email>foo@bar.com</email></person></addrbook>by newlines; an XML-compliant string lens would
simply involve more parsing and pretty-printing
boilerplate code. For example, an arbitrary source
database would look like:
name1, email11, email12, tel1
name2, email2, tel2

The first four lines of our string lens define theregular expressions for alphabetical data, emails
and telephone numbers. The lens comp processes
each person (per each line): it copies the name tothe view, then copies the first email while deleting remaining emails (emails) and at last deletes
the telephone number; the separating commas aredealt with accordingly. A sequence of lines is handled by comps.
The get transformation of this lens for our source
database then produces the following view address
book.
<addrbook><person><name>Tao Zan</name><email>zantao@nii.ac.jp</email></person><person><name>Hugo Pacheco</name><email>hpacheco@nii.ac.jp</email></person><person><name>Zhenjiang Hu</name><email>hu@mist.i.u-tokyo.ac.jp</email></person></addrbook>

The put transformation of our string lens, wheninvoked with this updated view and the original
source, will produce the following updated address
book:<addrbook><person><name>Zhenjiang Hu</name><email>hu@nii.ac.jp</email><email>hu@ipl.t.u-tokyo.ac.jp</email><tel>+81-3-5841-7411</tel></person><person><name>Tao Zan</name><email>zantao@nii.ac.jp</email><email>zantao007@gmail.com</email><tel>+81-3-5841-7430</tel></person><person><name>John Doe</name><email>foo@bar.com</email><tel>+81-0-0000-0000</tel></person></addrbook>

This put transformation has matched each person

When writing lenses, programmers are invited toin the source with each person in the view by theirthink in terms of the forward transformation, but in

names, and retrieved their additional source infor-

our running lens there are some more subtle details

mation for Zhenjiang and Tao that had contacts inthe original source, but creating a default telephone

derived from the source path expressions that con-number for John Doe. In the lens program, the an-nect selected source data with the view. Through-gled brackets <comp> identify lines (persons) as en-out this paper we will present more examples thattries that can be reordered in the source and view,attempt to practically corroborate this assumption.

and key declares the unique key on which they mustMoreover, since programmers write such put trans-

match to identity the same person; ins specifies theformations in an higher-level update language, theydefault telephone for newly created contacts.

only specify which parts of the source are to be
updated with the updated view information. For

2. 2 Bidirectional updating

instance, in the string lens version we had to ex-

The same bidirectional transformation can beplicitly delete trailing emails and the telephone of

written as a bidirectional update procedure in Bi-

each person, whereas the bidirectional update ver-FluX. Instead of writing a get-based lens program,sion just concentrates on the updated information

the programmer specifies a put update strategy di-

and leaves the remaining parts unchanged by defi-

rectly as an update on the original address booknition.

format. Figure 1 shows the BiFluX code for our

3 A Bidirectional Update Language

address book example.

In this section, we introduce our BiFluX language

To give an intuition, our update starts by defin-

by describing its high-level, natural language syn-ing the root procedure addrbook that accepts

tax similar to other update languages like SQL,

as arguments the original source and updated

XQuery and (naturally) Flux. The complete syn-view.

tax for BiFluX updates is shown in Figure 2.

Then it focuses on a list of persons inthe source address book according to the path$saddrbook/addrbook/person and a list of persons

3. 1 Flux-like syntax

in the view address book according to the path

At the outset, bidirectional BiFluX source up-$addrbook/addrbook/person. Persons in the twodates look just like regular Flux source updates.

lists are matched using an explicit matching condi-

Variables Var are written $x, $y, etc. The syntac-

tion, in this example the name of persons in both

tic classes Expr and Path denote ordinary XQuerylists. Finally, if a person in the view matches a per-expressions and XPath paths, respectively. State-son in the source, its updated view email ($email)ments Stmt include let-binding, conditionals, se-must replace the first email (email[1]) in the source

quential composition, update operations Upd anddatabase; if a new unmatched person appears in theprocedures. A procedure has a name and a tuple of

updated view, then a new contact with a default

argument paths, but it usually takes only two ar-

telephone is inserted in the source.

guments corresponding to the path to the current

The main difference in comparison to the pre-source focus and a path to the current view focus.

vious string lens is that the emphasis is now on(An update program is assumed to start with awriting a put transformation instead of a get trans-

predefined root procedure that is invoked with theformation.

This will allow a much more flexi-

original source and updated view XML documents,

ble and intuitive control over backward synchro-declared in two special reserved variables $source

nization strategies, by making several put design

and $view that are always in the environment.)

choices explicit in the design of a bidirectional up-

An update operation Upd receives a path from

date; the unique forward query can be essentiallythe current source focus and, like in Flux, may

PROCEDURE addrbook($saddrbook, $addrbook) =UPDATE $sperson IN $saddrbook/addrbook/person BY{
MATCH -> REPLACE email[1] WITH $email| UNMATCHV -> CREATE VALUE <person> <name/> <email/> <email>foo@default.com</email> <tel/> </person>}
FOR VIEW person[$name AS name, $email AS email] IN $addrbook/addrbook/person
MATCHING SOURCE BY $sperson/name VIEW BY $name
図1

BiFluX update for the address book example.

::=

Pat → Stmt|

Cases ′ |′ Cases

VStmt

::=

VUpd ′ |′ VUpd|

{ VUpd }

VUpd

::=

MATCH → Stmt|

UNMATCHS → Stmt

Cases

Stmt

Upd

::=

Upd [WHERE Expr ]|IF Expr THEN Stmt ELSE Stmt|

Stmt ; Stmt|

LET Pat := Expr IN Stmt|

CASE Expr OF { Cases }|{ Stmt }|PROCEDURE Name ′ (′ Path, . . . , Path ′ )′::=INSERT (BEFORE | AFTER) PathPat VALUE Expr

Match

UNMATCHV → Stmt::=

MATCHING BY Path|

MATCHING SOURCE BY Path||

INSERT AS (FIRST | LAST) INTO PathPat VALUE Expr|

DELETE [FROM] PathPat|

KEEP Path AS (FIRST | LAST)|CREATE VALUE Expr|

REPLACE [IN] PathPat WITH Expr|

UPDATE PathPat BY Stmt|

UPDATE PathPat BY VStmt FOR VIEW PathPat [Match]

図2|

PathPat

::=

Pat

::=

|

Type

VIEW BY Path
[Pat IN] Path
Var [AS Type]′ ′( Pat, . . . , Pat ′ )′|Var [AS Type] | Type|Name[Pat, . . . , Pat]::=

Name | @Name | Name[Type]|

String | () | Type∗ | Type?

|

Type+ | (Type)|Type ′ |′ Type|

Type, TypeConcrete syntax of BiFluX.

be either singular or plural. Singular updates are
executed once for each node in the result set oft:Tt' : T't'' : T''

the path; plural updates operate on the childrenof each selected value. Briefly, singular insertions

図3

Update composition in Flux.

(INSERT BEFORE/AFTER) insert a value before
or after each selected node, while plural insertions

corresponding child-lists. The singular UPDATE(INSERT AS FIRST/LAST INTO) insert a value

Stmt BY operation applies a statement to eachat the beginning or end of the child-list of the se-node in the result of Path.

lected nodes. Singular deletions (DELETE) delete
selected nodes, whereas plural deletes (DELETE

3. 2 Bidirectional updates

FROM) delete only the child-lists of selected nodes.

In spite of the fact that BiFluX updates strongly

Singular replacements (REPLACE WITH) replaceresemble Flux updates, their bidirectionality en-

all selected nodes with the same expression, whiletails a subtly different semantics. A simple (uni-plural replacements (REPLACE IN) replace thedirectional) Flux statement Stmt is read as type-conditionals IF Expr THEN Stmt ELSE Stmt′ cans:Ss' : S

be defined using composition IF Expr THEN Stmt;

s'' : S

IF not(Expr) THEN Stmt′ – if the condition is verv1 : V1

v2 : V2

ified, then the first statement updates the source
via Stmt and the second statement does nothing,

図4

Update composition in BiFluX.

and vice-versa.
However, the same reasoning can not be appliedchanging transformation: given an input tree t

in BiFluX because, to ensure that view informa-of type T , execute Stmt to update t, producing

tion is embedded into the source, an update that′′a target tree t of some other type T .

In Bi-

does not satisfy the condition must fail (except for

FluX, a (bidirectional) statement Stmt denotes aempty views). This is the reason why we introduce

put : V → S → S transformation, i.e., given ana primitive if-then-else conditional.

updated view of type V , it updates the contents

BiFluX considers two classes of where conditionsof a source of type S with the updated view in-for source-based filtering or view-based filtering. A

formation, preserving the source type S. For thissource-based condition does not refer to view vari-reason, we assume that BiFluX programs are de-ables and performs like a where conditions in Flux,

fined for fixed source and view schemas, while Flux

by filtering only the nodes that satisfy a specify cri-programs are defined for a fixed source schema andteria from the source path. On the other hand, aproduce a corresponding target schema.

view-based condition does not refer to source vari-This justifies a different notion of composition.

ables and imposes a constraint on the nodes from

Imagine that we compose two Flux statementsa view path: since we cannot filter out any view′

Stmt; Stmt (Figure 3). This can be read as: given

information (it must be embedded in the source),

an initial tree t of type S, apply statement Stmt tothe update will fail if the condition is not satisfied.

update s into an intermediate tree u of type U , followed by applying Stmt’ to compute the resulting

3. 4 Pattern matching

updated tree t with final type T . Since a BiFluX

In contrast to Flux, that does not support defin-

update can not change the source type, two com-ing updates by matching tree patterns agains the′posed statements Stmt; Stmt update source trees

source data, pattern matching is a key design deci-of same type, but embedding different view infor-

sion of BiFluX. The typical way to write an update

mation (Figure 4): Stmt updates an original sourcein Flux (and BiFluX) is to define a path on the orig-s of type S with a view v1 of type V1 , producing an

inal source that selects the particular source infor-

′

′

′

intermediate source s , and Stmt updates s withmation to be modified. But to ensure that a bidi-

different view information v2 of type V2 , producing

rectional update is well-behaved, we can not apply

a resulting updated source s′′ .

the same kind of lossy queries to the view. Therefore, apart from very restrictive injective paths,

3. 3 Conditionals and where conditions

views in BiFluX must always be decomposed via

In Flux, conditionals IF Expr THEN Stmt havepattern matching, hence the added optional pat-a single then-statement, and its semantics simply

terns for source and view paths of update opera-

applies Stmt if the condition Expr evaluates to true

tions.

or returns the original source otherwise. McCarthy

This choice enables our language to staticallyguarantee that view information is embedded intoview sequences in order to identify the source ele-

the source, by simply guaranteeing that all viewments to which view updates must be translated.

variables in a pattern are put back to the updated

This alignment problem is well-known in bidirec-

source. (Our pattern matching algorithm follows

tional transformations [3] [2] [15].

familiar lines of XML transformation languages andWe allow users to flexibly specify arbitrary align-is implemented via structural subtyping [13].) To

ment strategies by defining a MATCHING condi-

keep pattern matching as simple as possible, wetion that defines a (not necessarily unique) key thatavoid the use of non-linear variables [12] by sup-intuitively specifies the criteria for source and view

porting only patterns that are sequences of vari-elements to match; if a matching condition is notables. Alternative patterns can still be defined by

specified, a default positional matching is assumed.

using CASE statements, that behave in the same

Then a view statement V Stmt supports three spe-way as multiple patterns in functional languages

cial cases: MATCH for two matching source andsuch as Haskell.

view values; UNMATCHV for unmatched view values for which there is no source value; and UN-

3. 5 Source-view alignment

MATCHS for unmatched source values for which

Thus far, all the update operations in our lan-there is no view. Each of these cases carries anguage perform in-place updates; they iterate over acorresponding statement. For UNMATCHV, since

source sequence (defined as path on the source), up-

there is no original source, such statement must

dating each and every node in the sequence accord-

begin with a special CREATE VALUE Expr up-

ingly. To make it a practical bidirectional updating

date that generates a default source value.

language, we extend BiFluX with a new update op-

UNMATCHS, the statement must either be of theeration UPDATE P athS BY V Stmt FOR VIEW

form DELETE . (that forgets an original source)For

P athV that supports iterating over a view se-or begin with a special KEEP . AS FIRST/LAST

quence. Informally, this combinator applies V Stmt

update (that inserts an “old” source element as the(what we call a view statement) to each node in thefirst or last element in the updated source). As

result of a view path P athV , generating an updated

an additional restriction to use KEEP, program-source sequence that replaces the original source se-mers must ensure manually that the kept source

quence computed by the source path P athS. Thisvalue does not satisfy the where conditions on thekind of behavior can not be done in-place. There-

source. This naturally implies that KEEP can only

fore, we evaluate the source path as a lens from thebe used when a guarding condition is applied tocurrent source focus to the result of the path, andthe source. The reason for this restriction is that,use lens composition to synchronize the updated

when additional elements are added to an updated

sequence with the source focus. (In our implemen-source sequence, the system must clearly know thetation, we interpret the source paths of update op-

underlying motives for programmers to want to re-erations as lenses.)

cover such elements. Note that an automaticallyFurthermore, the view sequence may not have thesame number of elements as the original source se-derived forward transformation must ignore themas long as they do not belong to the view.

quence or original source elements may appear have

By default, if the conditions are unspecified webeen reordered in the view. This forces an update

assume that unmatched sources are ignored fromstrategy to match the elements of the source andthe updated source and unmatched views generatedefault source values generated from the structureof the source type.

<->folder[title[var title as String], var xc]
wherecontents(nc, xc)

4 Bidirectional Updating Examples
In this section, we demonstrate how diverse bidirectional transformation scenarios can be specified
as bidirectional updates, in particular using BiFluX. These examples illustrate the spirit of bidirectional updating, and highlight the power andprogrammability of our bidirectional update language in specifying various update strategies.

We can also write typical bidirectional XML
A fa-mous bidirectional XML transformation language
is biXid [12].

Bidirectional programs in biXid

specify forward and backward conversions between
pairs of XML formats. As an example, consider abidirectional transformation between the Netscapeand XBEL browser bookmark formats, written in
biXid as the following biXid transformation.
relation top =html[head[String],
body[h1[var t as String], dl[var nc]]]<->xbel[title[var t as String], var xc]
wherecontents(nc, xc)
relation contents =(var nb | var nf)*<->(var xb | var xf)*
wherebookmark(nb, xb),
folder(nf, xf)

contain a general title (h1 or title) and a sequenceof bookmarks (dt or bookmark) or folders (dd orfolder), where folders may recursively contain sequences of bookmarks or folders.
The biXid language relies on pattern matching
to decompose the source and target formats, anddefines their conversions in a programming by relation paradigm, that makes critical use of am-

4. 1 XML transformationtransformations as bidirectional updates.

Both bookmark formats are loosely equivalent andbiguity and non-linear variable bindings. Unlike
lenses, biXid transformations do not have a primordial transformation direction and make full useof ambiguity: a document in one side may havemultiple representations in the other side, or data
in any side may not be related in any way to the
opposite side; biXid solves ambiguity by arbitrarily choosing one of many possible representations
or generating arbitrary data when necessary. For
example, in the top relation head elements in the
Netscape format are not related with XBEL, andso a backward transformation will “loose” the original source head for an arbitrarily generated one.
In BiFluX, we can deal with such ambiguity (forthe asymmetric case of lenses) by allowing users tochoose from many possible representations, recover
data from the original source, or create their own
default data.
The above biXid transformation can be encodedin BiFluX as shown in Figure 5. Apart from intricacies bound to the disparate styles of both lan-relation bookmark =dt[a[@href[var url as String],
var title as String]]<->
bookmark[@href[var url as String],
title[var title as String]]

guages, the BiFluX update resembles very muchthe biXid transformation. The top procedure decomposes the source into head and body (with atitle $h1 and a sequence $nc of dts or dds) and theview into a title $t and a sequence $xc of bookmarks

relation folder =dd[h3[var title as String], dl[var nc]]

or folders. Since the head in the source is not re-PROCEDURE top($html,$xbel) =UPDATE html[head[String], body[$h1 AS h1, dl[$nc AS (dt|dd)*]]] IN $html BY{ REPLACE IN $h1 WITH $t ; contents($nc,$xc) }FOR VIEW xbel[title[$t AS String], $xc AS (bookmark|folder)*] IN $xbel
PROCEDURE contents($nc,$xc) =UPDATE $nc BY{
CASE $v OF{ bookmark[@href[$url AS String], title[$title AS String]]-> REPLACE . WITH <dt> <a href={$url}>{$title}</a> </dt>| folder[title[$title AS String], $fxc AS (bookmark|folder)*]-> REPLACE IN h3 WITH $title ; contents(./dl/*,$fxc)}}
FOR VIEW $v IN $xc
図5

BiFluX update for the bookmark example.

lated to the view, we don’t updated it (but the original head is preserved unlike in biXid). (Note thatin BiFlux the same behavior would not be possible
for the view, as view patterns must fully decompose the view into a set of variables that shall beembedded into the source.) Then top replaces thesource $h1 with $t and invokes contents to update<body><h1>my bookmarks</h1><dl><dt><a href="foo.com">Foo’s</a></dt><dd><h3>my folder</h3><dl><dt><a href="stefanzan.com">stefanzan</a></dt></dl></dd><dt><a href="bar.edu">Bar’s</a></dt></dl></body></html>the remaining sequences.
The contents relation in the biXid transformation makes use of non-linear variables, i.e., variables
that are instantiated multiple times, to match dts
and dds in the source with bookmarks and folders
in the view, respectively. Since only support linear
pattern variables in BiFluX, we handle each view
element using a case expression: when it matches
the structure of a bookmark, we generate a source
dt element with the bookmark’s url and title; otherwise, if it matches the structure of a folder, we
generate a source dd element with the folder’s title and a dl with recursively computed contents by
invoking contents with the all the elements under
the dl and the elements from the view folder.
For an execution example, consider a source
bookmark tree represented in the Netscape format<html><head>My Bookmarks</head>

and a different view bookmark tree represented in
the XBEL format:<xbel><title>NII bookmarks</title><folder><title>National Institute of Informatics</title><bookmark href="http://www.nii.ac.jp/en"><title>English</title></bookmark><bookmark href="http://www.nii.ac.jp"><title>Japanese</title></bookmark></folder><folder><title>my folder</title><bookmark href="stefanzan.com"><title>stefanzan</title></bookmark></folder><bookmark href="bar.edu"><title>Bar’s</title></bookmark></xbel>Finally, we can run our BiFLuX program to updatesuch alignment information to refine put behavior.

the source bookmark tree using the view bookmark

Similarly, our UPDATE P athS BY V Stmt FOR

tree:

VIEW P athV update operation allows users to ex-

plicitly declare how to align source and view se<html><head>My Bookmarks</head>quences using arbitrary paths.
<body><h1>NII bookmarks</h1>
For example, suppose that we have a source<dl><dd><h3>National Institute of Informatics</h3>
database that contains two levels of nested struc<dl>dt>
ture: a document is constituted by a list of sections,<a href="http://www.nii.ac.jp/en">English</a><a href="http://www.nii.ac.jp">Japanese</a> that have a title, a paragraph and a list of subsec</dt>
tions, where a subsection has itself a title and a</dl>paragraph:</dd><dd><h3>my folder</h3><sections><dl><dt><section><a href="stefanzan.com">stefanzan</a><title>Grand Tours</title></dt></dl><paragraph><dt><a href="bar.edu">Bar’s</a></dt>
The grand tours are major cycling ...
</dd></paragraph></dl><subsection></body><title>Giro d’Italia</title></html><paragraph>
The Giro is usually held in May ...
After updating, despite the structure of the view</paragraph></subsection>
XBEL tree is fully propagated to the source, the</section>
updated source bookmark tree is not created afresh<section>from the view, unlike in biXid. For example, the<title>Classics</title><paragraph>original header “My Bookmarks” is preserved.
The classics are one-day cycling ...
</paragraph><subsection>
4. 2 Flexible alignment<title>Milan-San Remo</title>
Many bidirectional programming approaches are<paragraph>
The Spring classic is held in ...
state-based, in the sense that put transformations</paragraph>only consider original source and updated view</subsection>
values, as opposed to operation-based where some</section></sections>knowledge of the exact changes that led to the
update result is also recorded.

Since this for-A view definition consists in deleting all para-

mulation provides little knowledge about the ac-graphs and performing some XML-specific struc-tually performed updates, put must align source

tural changes like changing titles from child nodes

and view values in order to guide the propaga-

to attributes. Consider the following updated viewtion of view updates to corresponding source el-document.

ements.

<secs><sec title=‘Classics’></sec><sec title=‘Olympic Competitions’><subsec title=‘2008 Summer Olympics’/><subsec title=‘2012 Summer Olympics’/></sec>

Some existing alignment-based bidirec-

tional lens languages [3] [2] [15] promote parameterizing lens programs with user-specified heuristics
for calculating alignments, and devise particularbidirectional transformation primitives that reuse

PROCEDURE sections($sections, $secs) =UPDATE $section IN $sections/sections/section BY{
MATCH -> subsections($section/subsection,$subsecs)| UNMATCHV -> CREATE VALUE <section> <title/> <paragraph>this section is new</paragraph> </section>}
FOR VIEW sec[$title AS @title, $subsecs AS subsec*] IN $secs/secs/sec
MATCHING SOURCE BY title/text() VIEW BY $title/string()
PROCEDURE subsections($subsections, $subsecs) =UPDATE $subsection IN $subsections BY{
MATCH -> {}| UNMATCHV -> CREATE VALUE<subsection><title/><paragraph>this subsection is new</paragraph></subsection>}
FOR VIEW $subsec IN $subsecs
MATCHING SOURCE BY title/text() VIEW BY @title/string()
図6

BiFluX update for the sections example (local subsection alignment).

<sec title=‘Grand Tours’><subsec title=‘Milan-San Remo’/><subsec title=‘Giro d’Italia’/></sec></secs>ilar way.

In comparison to the original source: the order of<sections><section><title>Classics</title><paragraph>
The classics are one-day cycling ...
</paragraph></section><section><title>Olympic Competitions</title><subsection><title>2008 Summer Olympics</title><paragraph>this section is new<paragraph></subsection><subsection><title>2012 Summer Olympics</title><paragraph>this section is new<paragraph></subsection></section><section><title>Grand Tours</title><paragraph>
The grand tours are major cycling ...
</paragraph><subsection>

the sections “Grand Tours” and “Classics” is reversed; “Milan-San Remo” is now a subsection of“Grand Tours”; and a new section “Olympic Competitions” has been added to the view.
Figure 6 shows the BiFluX program for this example, that contains two procedures. The root procedure sections updates the content of sections inthe source with the content of secs in the view,
matched by their titles. If two sections match, wejust update their subsections by calling the auxiliary procedure subsections, otherwise we create a
new source section with a default paragraph. Notethat we do not need to update source paragraphs
as they are kept unchanged. The subsections procedure updates subsections with subsecs in a sim-

Executing this update with the above source andupdated view documents yields the following updated source:LET $subs := $source/sections/section/subsection[title/text() = $subsec/@title/string()] IN
LET $par := if $subs then string-join($subs/paragraph,’ ’) else ’this section is new’ IN
CREATE VALUE <subsection> <title/> <paragraph>{$par}</paragraph> </subsection>
図7

BiFluX update for the sections example (global subsection alignment).

<title>Milan-San Remo</title><paragraph>this section is new</paragraph></subsection><subsection><title>Giro d’Italia</title><paragraph>
The Giro is usually held in May ...
</paragraph></subsection></section></sections>

The updated source correctly reorders the sectionsin the source according to the view, with updated
subsections and original retrieved from the source
paragraphs for matched sections. However, the behavior is slightly different for subsections: the update has recovered the original paragraph for “Girod’Italia”, but not for “Milan-San Remo”, that was

4. 3 User control over update strategies
A typical query for defining views of databases isselection, which filters rows satisfying a particularcondition. In BiFluX, we can write various updatestrategies for selection queries.
Suppose that we have a source XML documentthat contains persons with a name and a city:<people><person><name>Hugo</name><city>Tokyo</city></person><person><name>Sebastian</name><city>Kiel</city></person><person><name>Zhenjiang</name><city>Tokyo</city></person></people>originally a subsection of “Classics”. This happens

Assuming an updated view database with only the

because view subsections are only locally aligned

names of people who live in ’Tokyo’with source subsections under the same section.

<fromtokyo><name>Zan</name><name>Zhenjiang</name></fromtokyo>

Therefore, a programmer may want to also retrieve the paragraphs of subsections that have been
moved to different sections.

He can do so bychanging the statement after UNMATCHV in thesubsections procedure as shown in Figure 7.
The new code now retrieves every subsection in
the original source that has the same title as thecurrent view subsec, and creates a new paragraphby concatenating all paragraphs of selected source
subsections with the XPath function string − join;
the XQuery if-then-else condition returns the a default paragraph if no source subsections are found.
Running our example again, we would see “TheSpring classic is held in ... ” as the paragraph of“Milan-San Remo” instead of a default.

we can define a BiFluX program that updates theoriginal database with a new view as shown in Figure 8. The people procedure starts by selecting(using a where condition) only the persons in theoriginal source that live in ’Tokyo’ and matches
them with names of people in the view. Then, it
copies matched view tokyolites to the source, creates new view tokyolites with city ’Tokyo’ in thesource (to satisfy the filtering condition) and unmatched source tokyolites are ignored (by default).
This update will yield an updated source as follows when applied to our source and view examples:<people>PROCEDURE people($people, $fromtokyo) =UPDATE $sperson IN $people/people/person BY{
MATCH -> {}| UNMATCHV -> CREATE VALUE <person> <name/> <city>Tokyo</city> </person>}
FOR VIEW $vname IN $fromtokyo/fromtokyo/name
MATCHING SOURCE BY name VIEW BY .
WHERE city/text() = ’Tokyo’
図8

BiFluX update for the people example (delete source tokyolites).

<person><name>Zan</name><city>Tokyo</city></person><person><name>Sebastian</name><city>Kiel</city></person><person><name>Zhenjiang</name><city>Tokyo</city></person></people>

The updated source now contains “Zan” and“Zhenjiang” living in “Tokyo”, as they come fromthe updated view, and “Sebastian” living in “Kiel”,
that existed in the original source and has not been
updated (since he did not live in “Tokyo”). Since“Hugo” lived at ‘Tokyo’ in the original source anddoes not appear in the updated view, he is conse-

also requires a position relative to the updated view
where such persons are to be inserted), with theircity original city (namely “Tokyo”) replaced with
“Kyoto”:<people><person><name>Zan</name><city>Tokyo</city></person><person><name>Sebastian</name><city>Kiel</city></person><person><name>Zhenjiang</name><city>Tokyo</city></person><person><name>Hugo</name><city>Kyoto</city></person></people>quently deleted.
Alternatively, we could have reasonably wanted

5 Conclusion

to keep “Hugo” in the updated source even if he had

Bidirectional transformations play an important

been deleted in the view. For instance, if “Hugo”

role in synchronizing and exchanging information

moved to a different city and has been deleted frombetween different data formats, and have gainedthat city’s municipal records. In fact, he could besignificant attention and applicability in the last

kept in the updated source, as long as he is moved

decade. Despite the currently wide offer on bidirec-

to a different city, say, “Kyoto”.

tional programming languages, research on bidirec-

This alternative behavior is usually difficult totional transformations has still not matured for de-specify using traditional bidirectional language, be-ployment at a larger scale and a unifying framework

cause they assume fixed update strategies for selec-

for bidirectional transformations is yet to emerge.

tion. In BiFluX, we can easily specify it using a

The main reason for this is the still very magi-

KEEP . update operation (Figure 9). In the new

cal nature of existing solutions, what makes users

version, unmatched source people like “Hugo” will

justifiably less confident to use bidirectional tech-

be inserted in the updated source (note that KEEP

nologies.

We believe that a feasible answer toPROCEDURE people2($people, $fromtokyo) =UPDATE $sperson IN $people/people/person BY{
MATCH -> {}| UNMATCHV -> CREATE VALUE <person> <name/> <city>Tokyo</city> </person>| UNMATCHS -> KEEP . AS LAST ; REPLACE IN city WITH ’Kyoto’}
FOR VIEW $vname IN $fromtokyo/fromtokyo/name
MATCHING SOURCE BY name VIEW BY .
WHERE city/text() = ’Tokyo’
図9

BiFluX update for the people example (moved source tokyolites).

these problems lies in put-based bidirectional pro-mates an higher-level BiFluX program by defining

gramming approaches, that enable programmers to

its semantics as lower-level put-based lenses. To

potentially specify the complete behavior of bidi-

be able to read BiFluX programs as bidirectional

rectional transformations by directly writing put

transformations, several static conditions (not fullytransformations, cutting on the magic and unpre-

discussed in this paper) need to be imposed on

dictability at the cost of more responsibility.

paths, patterns, statements and updates; in someIn this paper, we have proposed an hybrid formcases (like view-based where conditions), the de-of put-based programming (that we have named

rived well-behaved put transformations may be par-bidirectional updating) that invites programmerstial.

to write bidirectional transformations not directly

As future work, we plan to clarify the semantics

as put transformations from source to view but asof our language and provide more static guarantees

more intuitive and readable programs that spec-to prove the totality of BiFluX updates for par-ify how to update sources with view information,

ticular domains. We also intend to investigate thewhile preserving the advantages of put-based pro-

design of bidirectional update languages for othergramming (at a reasonable expressiveness cost). To

data domains, such as relational and graph data.

the best of our knowledge, the design and motivation of bidirectional update languages is new, and参 考 文 献unveils a promising style to inspire future bidirec-[ 1 ] François Bancilhon and Nicolas Spyratos. Update semantics of relational views. ACM Transactions on Database Systems (TODS), 6(4):557–575,
December 1981.
[ 2 ] Davi M.J. Barbosa, Julien Cretin, Nate Foster, Michael Greenberg, and Benjamin C. Pierce.
Matching lenses: alignment and view update. In
Proceedings of the 15th ACM SIGPLAN international conference on Functional programming,
ICFP ’10, pages 193–204, New York, NY, USA,2010. ACM.
[ 3 ] Aaron Bohannon, J. Nathan Foster, Benjamin C. Pierce, Alexandre Pilkiewicz, and Alan
Schmitt. Boomerang: resourceful lenses for string
data. In Proceedings of the 35th annual ACM
SIGPLAN-SIGACT symposium on Principles ofprogramming languages, POPL ’08, pages 407–419,

tional transformation frameworks.
As a demonstration of the feasibility of our novel
approach, we have designed BiFluX, a bidirectional update language for XML data. In this paper we have given a general informal overview of
our language through differently motivated bidirectional scenarios. BiFluX is ongoing work andcontains much more under the hood. Our prototype implementation already supports all the examples discussed in this paper: it receives source
and view XML documents and DTDs, and ani-New York, NY, USA, 2008. ACM.
[ 4 ] Aaron Bohannon, Benjamin C Pierce, and Jeffrey A Vaughan. Relational lenses: a language
for updatable views. In Proceedings of the twentyfifth ACM SIGMOD-SIGACT-SIGART symposiumon Principles of database systems, pages 338–347.
ACM, 2006.
[ 5 ] Peter Buneman, James Cheney, and Stijn Vansummeren. On the expressiveness of implicit provenance in query and update languages. ACM Transactions on Database Systems (TODS), 33(4):28,
2008.
[ 6 ] James Cheney. Flux: functional updates forxml. In Proceedings of the 13th ACM SIGPLAN international conference on Functional programming,
ICFP ’08, pages 3–14, New York, NY, USA, 2008.
ACM.
[ 7 ] Krzysztof Czarnecki, J Nathan Foster, Zhenjiang Hu, Ralf Lämmel, Andy Schürr, and James F
Terwilliger. Bidirectional transformations: A crossdiscipline perspective. In Theory and Practice ofModel Transformations, pages 260–283. Springer,2009.
[ 8 ] Sebastian Fischer, Zhengjiang Hu, and Hugo
Pacheco. “Putback” is the Essence of Bidirectional
Programming. Technical Report GRACE-TR 201208, GRACE Center, National Institute of Informatics, December 2012.
[ 9 ] J Nathan Foster, Michael B Greenwald,
Jonathan T Moore, Benjamin C Pierce, and Alan
Schmitt. Combinators for bidirectional tree transformations: A linguistic approach to the viewupdate problem. ACM Transactions on Program-ming Languages and Systems (TOPLAS), 29(3):17,
2007.
[10] Zhenjiang Hu, Shin-Cheng Mu, and Masato
Takeichi. A programmable editor for developing
structured documents based on bidirectional transformations. Higher-Order and Symbolic Computation, 21(1-2):89–118, 2008.
[11] Zhenjiang Hu, Andy Schurr, Perdita Stevens,and James F Terwilliger. Dagstuhl seminar on
bidirectional transformations (bx). ACM SIGMOD
Record, 40(1):35–39, 2011.
[12] Shinya Kawanaka and Haruo Hosoya. bixid: abidirectional transformation language for xml. In
Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming,
ICFP ’06, pages 201–214, New York, NY, USA,2006. ACM.
[13] Kenny Zhuo Ming Lu and Martin Sulzmann. An
implementation of subtyping among regular expression types. In Programming Languages and Systems, pages 57–73. Springer, 2004.
[14] Hugo Pacheco and Alcino Cunha. Generic pointfree lenses. In Mathematics of Program Construction, pages 331–352. Springer, 2010.
[15] Hugo Pacheco, Alcino Cunha, and Zhenjiang
Hu. Delta lenses over inductive types. Electronic
Communications of the European Association ofSoftware Science and Technology, 49, 2012.
[16] Hugo Pacheco, Zhenjiang Hu, and Sebastian Fischer. Combinators for “putback” style bidirectional
programming. Technical report, GRACE Center,
National Institute of Informatics, July 2013.