abstraction, a view update translation strategy that gives rise to a well-behaved BX.
As future work, we are still seeking to extend BiFluX so as to further increase the flexibility of BiFluX programming. We also plan to provide more static guarantees to BiFluX by incorporating existing path-query static analyses, implement more powerful pattern type inference algorithms to avoid excessive annotations, and extend the class of bidirectional updates that can be written by integrating user-defined lenses for defining source and view focuses. We also plan to improve the efficiency of our prototype for large XML databases by exploring optimizations to the underlying BiGUL language, including incremental update translation.
4.6 Discussion
The project of designing and implementing BiFluX has been lasted for more than three years. Since it is our first attempt to design such a complex but user-friendly language for real world data, we encountered many problems (not only because of the XML details, but also the mixture between XML and bidirectional transformation.) which also pushed us to improve the BiFluX language as well as think how to build a clean and concise core for putback-based programming.
BiFluX evolves overtime from February 2013, and our first design of Bi -FluX [73] was published at the domestic conference of Japan Society for Soft-ware and Science (JSSST). After that, we implemented the language based on putlenses [64] and published at the 16th International Symposium on Principles and Practice of Declarative Programming (PPDP) [65]. While the underlying putlenses is complex and hard to maintain, so we directly implemented the bidirectional semantics of the core XML update language (Section 3.2). During the implementation, we found that the core language is a mixture of bidirec-tional updates (replace, fail, skip, etc.) and XML related features (expressions, and paths) which makes the bidirectional semantics hard to implement clearly since we need to handle the XML details at the same time. So we decided
94 4 A Bidirectional Functional Update Language for XML to extract a clean and concise core language for putback-based bidirectional programming from this core XML update language that completely has nothing related to XML but it is powerful enough that the bidirectional semantics of the core XML update language can be implemented easily. The core language is called BiGUL [46] which is short for bidirectional generic update language that has a clear bidirectional semantics and it is formally verified in Agda by Josh Ko to guarantee that any program written in BiGUL satisfies the well-behavedness properties. Based on this new putback-based core language, we finally reimple-mented our BiFluX by compiling the core XML update language to BiGUL and published as a journal article [75] to the Computer Software of Japan Society for Software Science and Technology (JSSST).
Chapter 5
A Putback-Based Library for Updatable Views
In this chapter, to explore the powerfulness of the putback-based bidirectional programming, we implement a library for the user to write the put function with flexible update policies easily; what is more, a uniquegetfunction can be derived automatically from the putfunction.
5.1 Motivation of Design
In work on relational databases, the view-update problem is about how to trans-late update operations on the view table to corresponding update operations on the source table properly. The problem is that the update translation policies are not unique in many situations. For example, suppose the view is the result of joining two source tables, and we delete one record on the view, we can choose to delete the related record on either source table or both of them. This indicates that it is not possible to determine a proper update policy for this deletion without the user’s choice since there are three update (deletion) policies.
As we introduced before, a lens is a well-behaved pair of getandput func-tions. Bohannon et al. designed relational lenses [12], whose getfunctions are database queries and put functions reflect updates on query results back to
95
96 5 A Putback-Based Library for Updatable Views
name email location
John [email protected] Tokyo Mary [email protected] NewYork Stan [email protected] Tokyo
(a)Source table
name email location
John [email protected] Tokyo Stan [email protected] Tokyo
(b)View table Figure 5.1 Updated view and source table
name email location
Stan [email protected] Tokyo Jeff [email protected] Tokyo
(a)Updated view table
name email location
Mary [email protected] NewYork Stan [email protected] Tokyo Jeff [email protected] Tokyo
(b)Updated source table Figure 5.2 Updated view and source table
databases. Specifically, they designed three basic lenses, called selection,drop andjoin. Thegetsemantics forselectionandjoinare the same as the ones in SQL, and thegetsemantics ofdropremoves one column from the source table. Their putsemantics are carefully formalized in order to satisfy the well-behavedness properties. The lenses can be composed in order to create larger programs.
Relational lenses have a SQL-like syntax, which let the programmers sim-ply write a bidirectional program as a SQL program. This get-based design (meaning that the lens programs look likeget functions) reduces the burden of writing bidirectional programs, but the putbehavior is not controlled by the programmers, and may not satisfy their real needs (even they provide several specific join such as join dland join drthat specify to delete on the left table or right table, but it still only has limited flexibility.).
To explain the problem, let us look at an example: suppose that a company keeps a table of employee information shown in Figure 5.1a, in which each record gives a person’s name, email address, and current location. We can write
5.1 Motivation of Design 97 a program with relational lenses as follows :
select from s ✇❤❡r❡ location = "Tokyo" as v
It looks exactly the same as writing a SQL query that selects only those people located in Tokyo. Running the getdirection of this program on the source table in Figure 5.1a yields the view table shown in Figure 5.1b. Now we do some modifications on the view table: We delete the person John because he moved to another city Kyoto, insert a new person Jeff, and update Stan’s email address.
After that, if we run theputdirection of this program, the source table will be updated by deleting John, inserting Jeff, and updating Stan’s email address with the one in the view, while Mary is left unchanged. The resulting table is shown in Figure 5.2b.
This backward behavior is acceptable in some cases, but it is not what we want here. What we want is updating John’s location instead of deleting him, since he just moved to Kyoto and still belongs to the company. Relational lenses cannot describe this behavior as this is more about controlling update policies in theput direction. Theput behavior provided by relational lenses is well-behaved, but the programmers are not given the freedom to customize that behavior.
In order to give the programmers more control over the put behavior, we provide a new library Brul(bidirectional relational update library) that follows our previous work [65, 46] on putback-based bidirectional programming. In-stead of letting the programmers write the forwardgetfunction and implicitly deriving a backward putwhich might not satisfy the programmers’ real needs, we carefully define the library in a way that allows the programmers to specify the update policies flexibly as aputfunction, from which the necessarily unique forward transformation is derived. Our contributions can be summarized as follows:
• We design a library Brul that provides basic put combinators that can 1) let the programmers directly describe the put behavior, and 2) give the programmers full control of the bidirectional behavior of their programs, since theputbehavior uniquely determines thegetbehavior [26].
• Brul is implemented on top of BiGUL [46], which is a fully formalized
98 5 A Putback-Based Library for Updatable Views putback-based language. The well-behavedness of Brul can thus be easily proved. The source code of the implementation is available at the Brul website1.
• We demonstrate Brul’s expressiveness by encoding in Brulall the operations of relational lenses and giving examples of more flexibleputs that cannot be described with relational lenses.
The rest of the Chapter is organized as follows: Section 5.2 shows the design of the Brullibrary, Section 5.3 gives two typical examples which are described in the relational lenses paper, Section 5.4 explains the implementation of Brul in detail, Section 5.5 reviews the related work in both relational database and bidirectional transformation, and Section 5.6 gives a conclusion of our work.