Compositional algebra for interactive data access

Vol. 25, No. 5, pp. 367–391, 2000  2000 Elsevier Sciences Ltd. All rights reserved Printed in Great Britain 0306-4379/00 $20.00 + 0.00

,QIRUPDWLRQ6\VWHPV

COMPOSITIONAL ALGEBRA FOR INTERACTIVE DATA ACCESS

‚

GIANLUCA MORO1, ANTONIO NATALI1, and CLAUDIO SARTORI1,2 1

Department of Electronics, Computer Science and Systems, University of Bologna, Viale Risorgimento 2, I-40136 Bologna, Italy 2CSITE-CNR,

Department of Electronics, Computer Science and Systems, University of Bologna, Italy 5HFHLYHG0DUFKLQILQDOUHYLVHGIRUP-XQH

$EVWUDFW  An important issue for the success of a database application is the effectiveness of its interface. Frequently a relevant part of the programming effort is devoted to the generation of interfaces. The visual programming environments reduce only partly this effort, and in particular, things become more complicated when data coming from different sources (different views in the same database or even views from different databases or systems) are to be related and must cooperate in the data navigation and manipulation task. To overcome this problem we present a new database access paradigm based on an algebra on the domain of computational abstractions called "services" which include both dimensions: the data access computation and the user interaction. This means that the interaction is not implemented by using separated constructs as happens for traditional computational models; on the contrary, as the interaction is an integral part of the service paradigm, the user interaction is computed starting from the declarative specification of the data access itself. The combination of services in a service expression through the operators defined by the service algebra makes it possible to generate cooperating user interfaces for complex data navigation and manipulation. Through algebraic properties, which hold both from the data and user interface point of view, the service expressions can be simplified and optimized guaranteeing their initial semantics. The paper shows the application of the service algebra to the relational environment by means of a simple extension to SQL. Finally, the paper describes a tool based on a three tier architecture and on Java technology for developing and distributing services in Web environment. Services and combination of services expressed with the service algebra are automatically translated into Java objects, allowing the rapid development of platform independent data access services. © 2000 Elsevier Science Ltd. All rights reserved .H\ZRUGV

Interactive Data Access, Service, Algebra, SQL, Relational DBMS, Java, Middleware

1. INTRODUCTION An important issue for the success of a database application is the effectiveness of its interface, and frequently a relevant part of programming effort is devoted to the generation of user interfaces. At present, many front-end database tools provide browsing capabilities according to a relational view, at the cost of very low (or virtually zero) programming effort. But things become more complicated when the data from different sources are to be combined, for instance in a master-detail relationship. Some tools can do this quite simply in a single database environment, but this is the actual limit. Let us consider, as an example, that a purchasing office has available a couple of applications for browsing mail-order catalogues and for computing parcel service fares, given the size and the weight of the item to ship. Let us suppose that a new purchasing procedure requires that an employee selects an item from a couple of mail-order catalogues, then orders item to be shipped using the parcel service with the cheapest fare, based on the size and weight of the item. Provided that the catalogues and the parcel services make available a relational view of their data, the present technology would allow two different solutions: • the old applications are simple SQL queries to be issued through a front-end; the user has to analyze the result of the catalogues queries and issue a query to the parcel service, depending on the result of the previous one; • the old applications are ad hoc programs and a new ad hoc application is to be generated, possibly with an integrated user presentation. The first solution does not imply programming effort; the queries are reused, but leaves to the user the †

Recommended by Maurizio Lenzerini 367

368

GIANLUCA MORO HWDO

responsibility of transferring the results of one query as selection conditions of the subsequent one. The second solution, on the contrary, thanks to a (possibly visual) programming language implements the necessary links, at the cost of losing flexibility: the data flow is hard-coded and the program can be reused only at the cost of additional programming effort. At this level, reuse means, for instance, to assemble and specialize objects from the object library of the existing applications (if available). At an abstract level, reuse of data access should mean aggregating and integrating existing user interfaces with a quite standard presentation logic: for instance, to obtain the union of the two catalogues above and to automatically generate a query to the parcel service with the appropriate size and weight values. Our idea is to exploit this abstract view of data access and to introduce a new database access paradigm, the VHUYLFH, with the following logical characteristics: • a service has an interface automatically generated starting from a data access declarative specification • some mechanisms for the combination of services are available; the combined service implements a sort of cooperation among the original services and automatically generates a combined interface, according to a precise semantic grounded on an algebraic structure. A second important issue in database applications is that of software architecture. At present most solutions rely on the client-server architecture, and the client applications are compiled for a specific software environment and LQVWDOOHG in the user machine. Our claim is that the service should be resident in the server machine, being part of the database (like the stored procedures) and have the capability to migrate on the demanding machine without installation or configuration. Examining the current technology, we realized that neither the traditional technologies nor the most recent ones such as World Wide Web [4] (in short Web) and Java, are able to fully satisfy the requirements above. Mainly there exists no computational environment able to support the composition semantics at the user interface level. The access to a database occurs usually through SQL, a declarative language not computationally complete based on the relational algebra [33]. SQL does not provide for any grammar construct for the user interaction with data, so it cannot be considered an interactive language. In order to overcome this limitation, SQL can be used together with a programming language such as C++, Pascal, Java etc. At this low abstraction level, data access means providing code for accessing remote and heterogeneous databases, code for manipulating results, code for presenting results, including code for obtaining cooperating behaviors between several user interfaces. At a higher abstraction level it means navigating through data for exploring them independently from their location. There are several commercial tools for data access (JDesignerPro [6], Powerbuilder [28], Ms Access [18] etc.) which may reduce some difficulties due to the low abstraction level. Using all of them, the user visually builds user interfaces for displaying a query result. Some of them allow visually associating at most two user interfaces in a master-detail relationship. Two or more user interfaces aggregated through relationships become cooperating when the user interaction on an interface may produce effects on the others. For more complex aggregations with respect to the two master-detail level, these tools require the user to write code with an imperative language for implementing the desired cooperation. So they are nearer to a low level abstraction rather than to a higher one, because the user must deal with both SQL and an imperative language. Moreover, programming the cooperation between user interfaces prevents new automatic aggregations, because their cooperation logic is hard-coded. Therefore, new data access can be obtained only through new programming effort. What is needed is a computational environment able to support the composition semantics for automatic aggregation of user interfaces independently from their specifics display contents. This means that new applications, developed with current tools, cannot cooperate at the interface level with existing ones, unless the cooperation has been designed in advance. Moreover, these tools are usually limited to a single database model, mainly the relational one. Another limitation of the model employed by these data access tools regards the software architecture. All of them store applications for data access, including user interfaces, into a file for a specified operating environment. This makes it impossible to use the applications in a world-wide network of heterogeneous machines like the Web. To obtain concurrent remote execution, the applications, and

Compositional Algebra for Interactive Data Access

369

possibly their run-time environment, are to be stored and properly installed in the client machine. The recent technology, based on Web and Common Gateway Interface standard (CGI) [24], provides a way to access remote DBMS through HTML pages called Forms. With respect to the above mentioned tools, a Form has only a better capability to migrate on demanding machine, but it has several limitations because the HTML formalism is by far too poor for the definition of an interactive user interface [5]. Our main objectives is to make interaction an integrating part of the computational process for data access. In addition, a set of operators for the combination of interactive data accesses is provided. We define the VHUYLFHas a computational abstraction which include two dimensions: data access computation and user interaction. We also introduce the VHUYLFHDOJHEUD as a set of operators for the combination of services, with a precise semantics for both the above dimensions. In this way, it becomes possible to combine interactive accesses in a fashion similar to the combination of algebraic expression, and thus reuse user interactions without any programming effort. We point out that the ideas introduced in this work are mainly related to the VHPDQWLFV of interactive data access and of combination of different interactive data accesses. Minor attention is devoted to the presentation aspects which can be dealt with independently as a third dimension. For this reason, the implemented tool described in Section 0 is mainly a “proof of concept” and its actual user interface has only basic features. Nevertheless, it is currently used for developing and distributing in Web environment some administrative services of our department. This work, which is based on the idea presented in [22], introduces formally in Section 2 the notion of service grounded on a service algebra, and presents in Section 3 a declarative compositional language for services in relational environment, by extending the syntax and semantics of SQL. As this compositional process satisfies the closure property with respect to the service set, it is possible to define complex services with arbitrarily nested compositions. Section 0 describes the implemented tool (called JAccess) from two points of view: the usage and the architecture. The solution proposed is able to overcome the limitations above mentioned: • the data access services are stored on server machines, as they are part of the database, like stored procedures; • services are able to migrate on the demanding machine without installation or configuration, and, being autonomous, they do not require any software support, except for a Java enabled Web browser. Therefore each service may be used concurrently by more than one user in a world-wide network of heterogeneous machines like the Web environment. Section 5 describes the related works and Section 6 concludes the paper. 2. THE SERVICE AS A NEW DATABASE ACCESS PARADIGM In order to show the usefulness of a new paradigm for database access, let us suppose we are interested in finding out the address of a parcel service who requires the minimum fare for a given distance. Let us assume we have two available functions: • JHWBDGGUHVVQDPH retrieves the address of the parcel service by means of its QDPH; • JHWBQDPHBZLWKBPLQLPXPBIDUHVL]HZHLJKW retrieves the name of the parcel service which offers the minimum fare for the given LWHPVL]HDQGZHLJKW. Both functions have an argument for which they expect a single constant value; in the first case it is a string of characters, while in the second case it is a number. To accomplish our task, we might compose the first function with the second one, that is JHWBDGGUHVVJHWBQDPHBZLWKBPLQLPXPBIDUHVL]HZHLJKW . Now let us suppose that more than one parcel service name is available for shipping our goods at the same minimum fare for the given parameters. In this case, a FDUGLQDOLW\ PLVPDWFK occurs between the two functions because JHWBDGGUHVVQDPH receives more than one expected value. To solve this problem, we may think of correcting the code of the functions to handle the mismatch. If we change our approach in handling this situation without considering it an error to correct, we might observe that the end-user itself could resolve the cardinality mismatch by letting her/him to select a value from the intermediate result in such a way to supply the first function with a single value, as expected. On the other hand, if only one parcel service results from the first function, we do not want to annoy the user with a useless interaction.

370

GIANLUCA MORO HWDO

[_N · · [Q_NQ

6

GUI U6

X6

Fig. 1: The Service Model

In other words the interaction, which has been considered as a simple means for taking input from external sources, now becomes the harmonizer for bringing back the computation on traditional basis as well, while offering a way to make software more flexible and less vulnerable. Since as the IXQFWLRQ of traditional computational models does not offer such behavior, we introduce the concept of VHUYLFHas a base for building a new paradigm able to include the interaction as an integral part of the model itself. In other words, the interaction should not be forced through specific programming constructs, but should be explicitly considered as a first class concept and dealt with according to a limited set of standard schemes. Our main goal is to provide a new model for data access which allows working at a high level of abstraction by simply taking care of the navigation through data for exploring them. This means that once the data demands and the navigations are declaratively specified, the low level functionalities and the cooperating user interfaces could be automatically generated. In this section we formally define this new paradigm by introducing the concept of VHUYLFH. A service has a specific task to perform and a user interface with a behavioral logic implied by the task specification itself. The service may get tuple sequences from input parameters and return a tuple sequence as a result. The composition of two or more services generates a service with a new common user interface providing both the original individual behavioral logic and a new collaborative behavior for carrying out a new composite task. This means that existing services are able to cooperate also at interface level although the cooperation was not designed in advance. In Section 2.2 we show that this paradigm is based on an algebraic structure (the service algebra) made up of several operators, including the composition. Since all of these operators satisfy the closure property with respect to the service definition, we are able to build complex services by writing service algebra expressions. This model explicitly takes into account user interaction and is based on a well formed semantic as will be shown later. Explicit treatment of user interaction provides a more powerful computational model [19, 34]. In addition, by means of a set of algebra properties, we are able to simplify and optimize service expressions into a minimal form guaranteeing the same semantic of initial expressions.  'HILQLWLRQV Let D 1D n be n constant terms, we call WXSOH the vector τ = (D 1D n ) where DULW\τ = n is its arity. A WXSOHVHTXHQFHσ = [τ1 ,..,τm] makes up an ordered set of tuples and FDUGσ = m denotes its FDUGLQDOLW\. [] denotes an empty sequence, therefore FDUG[] = 0; let τi ∈ σ be the tuple (or tuples) with highest arity in σ, that is arity(τi) = n, then JUDGHσ = n denotes the arity of sequence σ. We define a service 6 (Figure 1) as an “agent” provided with computational capability and with the following properties: 1. the result of 6 indicated with U6 , is always a tuple sequence, possibly empty; 2. J6  is the graphical user interface (GUI) of service 6, which may be either visible or invisible; the general structure of J6 is a window presenting a sequence of tuples and letting the user select (or insert) some of them; 3. X6 indicates the tuple sequence the user may select from U6 by interacting with J6 , X6 ⊆ U6 becomes the final result of 6; 4. 6"[ i_N i   points out the i-th input parameter of service 6 the question mark indicates that the service uses the received values as data; a double question mark indicates that input data are used as instructions to modify the service itself in order to obtain higher level services (see Section 3.2); the single question mark can be omitted; the input parameter accepts only a tuple sequence σi , such that

371

Compositional Algebra for Interactive Data Access

(a)

(b)

Fig. 2: (a) GUI of an Elementary Service, (b) GUI of a Parametric Service

FDUGσi ≤ N i (for 1 ≤ N i ≤ Q - where Q ∞  indicates the maximum cardinality† of the sequence); if FDUGσi = 0, that is σi = [ ], then 6does not start its computation and its result is U6 = [ ]. In other words, no matter what the source is, 6 produces a set of tuples U6 which are presented to the user when its GUI J6 is visible. The minimal requirements for the GUI are to let the user browse the tuples and possibly select a subset X6 of them and to close the service. We should emphasize that we are not proposing a specific model for user interaction, but are introducing an LQWHUDFWLYHDOJHEUDwhose expressions generate LQWHUDFWLRQSRLQWV. These interaction points allow the user to address the final result of an algebra expression addressing indeed the data access result while the expression computation is in progress. This is, in our opinion, a significant breakthrough with respect to other computational models which are mainly oriented only to data access computation (e.g. relational algebra, relational calculus, datalog [33]). This limitation leads to building systems in which it becomes necessary to implement and insert (more or less manually) the interaction between two (or more) data access expressions (e.g. SQL as hosted language within imperative languages). The specific presentation style is a third dimension, orthogonal to user interaction and data access, which can be dealt with independently. Figure 2 shows the user interfaces of two services in the present simple implementation. Figure 2a shows the results of a service called Subjects()which is a simple selection of subjects with their NAME and ID. Figure 2b is a parametric service called Teachers(?x|1)which accepts a tuple sequence of cardinality one: at run time the user is prompted for parameter input. It retrieves NAME and ID of teachers belonging to the board of examiners of a user specified subject ID. A service can have a set of input parameters to influence its execution and its result, and since each parameter accepts a sequence of tuples, according to a maximum cardinality, the result of one or more services can be the input for another one. In other words the combination of services by means of complex expressions gives rise to the combination of their interfaces as well; in this way the model is able to compute the user interaction by automatically generating interfaces with user interaction points.  6HUYLFH$OJHEUD From the definition of service it derives that a service output may be an input for another service; this fact leads us to think of an operators set able to make up an algebra structure. The main advantage an algebra can offer is related to the closure property: it guarantees that each result of an operation on services is a service to which we can again apply algebra operators. We are thus able to build services more and more complex by aggregating (and reusing) simpler existing services through declarative expressions of service algebra. †

For brevity the cardinality indicator can be omitted for Ni = 1.

372

GIANLUCA MORO HWDO

Some results can be found in the literature for the formalization of interaction; for instance, in [10] formal models for the specification of human-computer interaction are described. These models, for the most part, are able to express unambiguously at the design level the behavior of a system from the point of view of its interactions with the external environment. Despite their usefulness, however they do not represent FRPSXWDWLRQDO models that can formalize computational processes (e.g. relational calculus, lambda calculus etc.). In other words, these models are devised to specify, rather than to compute. Wegner [34] and Milner [19] focused more on the investigation of the interaction from a computational point of view by founding the area of LQWHUDFWLYHFRPSXWLQJ. Wegner argues that interactions cannot be described by algorithms, due to the intrinsically non-algorithmic evolution of interaction between user and machine. A main feature of the service model is that of having user interaction as an integral part; the service algebra operators are devised as a computational framework able to drive the interactive behavior of the graphical user interfaces of services and, according to Wegner, this feature in some way improves the classic computational model based on the Turing Machine [31]. In fact, the user, being part of the computation of a service expression, may address the computation itself by interacting with the graphical user interface of the service generated by an algebraic expression. Moreover, the service algebra satisfies several properties, as shown in Section 2.4. In the following we define the algebra operators and then show an example of combined service by using several operators. Since the service model deals with tuples, some operators are directly inspired by relational algebra [33]; however, in addition to the computational aspects, they have a specific impact on the user interaction.  $OJHEUD2SHUDWRUV Let 3 be an infinite set of parameter names, and let [\] range over parameter names. Let ,be a set of service identifiers, each one with its own arity. Let $ % &  range over service identifiers. Let 4 56range over services or service expressions, which are of six kinds as follows. &RPSRVLWLRQ Let 56 be two services such that 5has arity n > 0, that is 5"[ 1_N 1"[ n_N n  where [ i (for 1≤ L ≤ Q) is an input parameter, then we define 5"[ 1_N 1"[ i-1_N i-1"6_N i"[ i+1_N i+1"[ n_N n as the composition of 5 o 6 for [ i_N i with the following semantics 1) for each other unbound input parameter [ j of 5(j ≠ i), it displays a graphical user interface, such as an edit box, in order to let the user insert at most N j tuples; 2) and in parallel one of the two following alternatives: a) if FDUGU6 ≤ N i then U6  becomes the input value for [ i in service 5 and J6  the graphical user interface of 6 turns invisible; b) if FDUGU6 > N i then J6  turns visible in order to let the user select at most N i tuples from U6  and then X6 becomes the input value for [ i (we call this situation &DUGLQDOLW\ 0LVPDWFK). The temporal order is not significant, in fact (2a) or (2b) may occur in parallel to (1). In general, the composition is a n-ary operation; in fact if 5 has arity > 1 then we are able to compose 5 with n > 1 services. 6XPPDWLRQ A summation

∑S

i

, where i < ∞ , is a service whose result U is equal to a tuple sequence

i∈Ν

containing the union of results of each service, that is

U U6 . We write ∅ for the empty summation, L

L

∈Ν

and call it empty service as the service which can do nothing. The binary summation can be thought as a service "[ 1_Q "[ 2_Q  with two input parameters whose cardinality is unlimited therefore 6 1 6 2 = "6 1_Q "6 2_Q . By the definition of composition both 6 1 and 6 2 do not make visible their user interface because a cardinality mismatch cannot occur. For this reason, 6 1 6 2 generates a single user interface, J6 1 6 2  displaying the summation result U6 1 6 2 

Compositional Algebra for Interactive Data Access

373

&DUWHVLDQ SURGXFW Let 6 1 ,..,6 n be n services and U6 1 U6 n  their results; then we define the &DUWHVLDQ SURGXFW 6 1 ×  × 6 n as a service whose result is the cartesian product of U6 1 ×  × U6 2 displayed by a unique graphical user interface JU6 1 ×  × U6 2 for the same reason described in the previous operator. 'LIIHUHQFH Let 6 1 , 6 2 be two services; then we define the difference 6 1 -6 2 as the service whose result U6 1 -6 2 contains the tuples of U6 1  which are not contained in U6 2  a single user interface J6 1 -6 2 displays the result as in the summation operator 3URMHFWLRQ Let 6 be a service and σ = [(K 1), ...,(K i )] a tuple sequence such that JUDGHU6 S ≥ FDUGσ = i and K j ∈ {1, ..., S} ∩ N (for 1 ≤ j ≤ i)then SURM6σ is a service with JUDGHUSURM6σ = FDUGσ and the attributes of 6 which are in the positions indicated by K 1, ..., K i become the only attributes available for U6 . Nevertheless, JSURM6σ is the same as J6 . In other words, the projection modifies the result but not its presentation. +LGH Let 6 be a service whose JUDGHU6 S and let σ = [(K 1 ), ...,(K i )] be a tuple sequence such that S ≥  card(σ) = i and K j ∈ {1,..., S} ∩ N (for 1 ≤ j ≤ i) then KLGH6σ  is the same as 6 but it does not display the attributes in the positions K 1, ..., K i; in other words this operator hides the presentation of a set of service attributes but its result remains unchanged (UKLGH6σ U6 ). The syntax of services can be summarized as follows: 



6 ::= ∅ | 61 o 62 | 61 + 62 | 61 × 62 | 61 - 62 | SURM6, | KLGH6,

The priority among operators is the following in descendent order from left to right: {

o , KLGH, SURM } > { × } > { + } > { - }.

Let Ω be the universe set of services, then (Ω, o , KLGH, SURM, × , +, -) is an algebraic structure, since the operators satisfy the closure property with respect to the set Ω. In fact, applying these operators to services as illustrated above, the result is always a service to which these operators are again applicable. Figure 3 shows an example of the combined usage of FRPSRVLWLRQSURMHFWLRQand KLGH, starting from the two independent services of Figure 2. The purpose of this service is to retrieve the teachers’ names belonging to the board of examiners of a user-selected subject. It can be obtained by combining the two services of Figure 2 through the following expression: hide(Teachers(proj(hide(Subjects(),[(2)]),[(2)])|1),[(2)])

The first service executed is the inner one, Subjects. Since it retrieves more than one tuple, while Teachers, the outer service, expects only one, a cardinality mismatch occurs and the interface presenting the result of Subject is displayed. The inner hide operator hides the second attribute from the displayed result, that is subject ID, leaving the data result unchanged. The proj operator projects the data result on the second attribute, again the subject ID, leaving unchanged the displayed result. The user does no longer sees the column† subject ID, but when she/he selects a subject tuple, its ID value is the only attribute passed to service Teachers, which retrieves the teachers belonging to that board of examiner. Finally, the outer hide operator hides the column teacher ID leaving the data result unchanged. More details on this example and its specification in a relational environment are in Section 3.4. †

The hide operator works on the display result independently from the kind of presentation style. For instance, by applying the hide operator to a result displayed through a three dimensions graph, the display result can be projected to a two dimensions graph.

374

GIANLUCA MORO HWDO

Fig. 3: Example of Combined Services

 'HILQHG6HUYLFHV Let $\ 1\ n  be a defined service where each \ i (for 1≤ L≤ Q) is either a service or an unbound input parameter. For any service identifier $ (with arity n) there must be a unique GHILQLQJHTXDWLRQ def$[ 1_N 1 ,[ n_N n := 6 where the parameter names [ 1[ n are distinct and are the only parameter names which may be free in 6 Defining equations could introduce recursion, since 6 may contain any service identifier, even $ itself. In order to limit our attention to ILQLWH services, i.e. services with finite behavior, we require that the right side of a defining equation $ may contain calls to service identifiers defined before $ avoiding thus direct and indirect recursion. Of course, this is a sufficient condition for the termination. Additional investigation is necessary to explore the problems of recursive definitions and its impact on the service algebra.  'HULYHG2SHUDWRUV Several operators can be derived on the basis of the previous ones by defining them as new services through def equations. Some examples of derived operators are the ELQDU\ PXOWLSOLFDWLRQ, the HTXDO for testing whether two services return the same result, the FRQFDWHQDWLRQ to concatenate two tuples selected by the user from the results of two services, and the GLVSOD\GDWDYDOXH to manage lookup tables. All of them can be used to simplify expressions writing (details in [23]). As an example, the definition of the display data/value operator follows. 'LVSOD\'DWD9DOXH Let 6 be a service with JUDGHU6 S, and \ an input parameter accepting a tuple sequence whose content is an ordered set of natural numbers, that is σy = [τy ,..,τy ] where τy = (D i ) ∈ {1, 1 n i ..., S} such that FDUGσy ≤ S (for 1 ≤ L≤ n). Thus GGY6σy is the service 6 with the following behavior: it hides, on J6  the presentation of the attributes at the positions indicated by numbers belonging to σy ; these hidden attributes only make up the service result set from the data point of view; we can obtain these behaviors by defining the following service:

Compositional Algebra for Interactive Data Access

375

def GGY[_Q\_Q := SURMKLGH[\ \ Sections 3, 3.3.3, 3.4 and 3.5 present some usage examples of this operator.  8VHU,QWHUDFWLRQDQG'DWD$FFHVV&RPSXWDWLRQ7ZR2UWKRJRQDO'LPHQVLRQVLQ'DWD0DQLSXODWLRQ Before presenting the properties of the service algebra we need to highlight the impact of interaction in the algebra itself. In every algebra the properties hold because two or more identical occurrences of the same symbol, being considered of the same value, can give rise to simplifications, and therefore to the application of the relative properties. This means that there must exist a precise way to establish when two occurrences of the same symbol are considered identical. For example, in a math expression of functions such as I[ I[ I[ , the three occurrences of x are considered identical because they assume the same value, conversely for the same reason, the three occurrences of I are not considered identical. In fact, I[ does a computation in general different from that of I[ , while, on the contrary, I[  I[ can be simplified by writing ∗I[  An analogous criterion must also exist in the service algebra in order to establish when two or more occurrences of a service are considered identical. The service algebra together with the computation of data takes into account the user interaction (Figure 4) because the service model subsumes both dimensions. This implies that two occurrences of a service are considered identical when both occurrences are identical on both dimensions. In other words, two occurrences considered identical in a traditional algebra (without the interaction aspect), could be considered different in the service algebra because they could be different from the user interaction point of view. For instance, let us consider the expression 45 65  (Figure 4 lower left) as belonging to a traditional algebra (with the only data computation dimension), then the two occurrences of the same symbol 5 are considered identical because they share the same computed value. If we consider the same expression as belonging to the service algebra, the two occurrences of 5 are identical from the data computation point of view but they could be different from the user interaction point of view. In fact if we rewrite the same expression by changing the expected cardinality, that is 45_ 65_ (Figure 4 upper left), for the two occurrences of the service 5 is expected the same result U5 and two distinct user selections X5  Therefore, in this case U5 is computed just once and if FDUGU5  > 2, then two cardinality mismatches occur and two distinct user interfaces are generated in order to let the user select at most one tuple from the first one and at most two tuples from the second one. Therefore, in this case the two occurrences of 5 cannot be considered identical and they cannot be reduced to one from the user interaction point of view, in other words one interface is not sufficient while one computation is. When two occurrences of the same symbol depend on different service expressions, that is they have different expressions as arguments, they compute different results. For instance let us consider the expression 56 57 (Figure 4 lower right) where 5might represent in a traditional algebra a function with distinct arguments. In this case, the two occurrences of 5 cannot be considered identical from the data point of view because in general two distinct arguments produce two distinct results. Also in the service algebra the same expression generates for the two occurrences of 5 two distinct computations and one interface because the plus operator displays its result in a single interface (see Section 2.2.1). In addition, in the service algebra two distinct computations for two occurrences of 5 can give rise to two distinct interfaces as well. In fact, the expression 456 857 † (Figure 4 upper right) generates for the two occurrences of 5 two computations as in a traditional algebra but also two interfaces because two cardinality mismatches and two distinct user selections can occur. So in the service algebra two or more occurrences of a service 5 are considered identical if they cannot compute two different results and do not generate two different user selections. In other words, two or more occurrences of a service 5 are considered identical if one computation and one interface is generated for all of them.

†

When the cardinality is omitted, it means one tuple expected (see Section 2.1).

376

GIANLUCA MORO HWDO

4 5 |1 + 6 5 |2 Å 1 C o m p u ta tio n , 2 In te rfa c e s fo r b o th 5 ifF D UG 5 !  4 5  6 5 Å 1 C o m p u ta tio n , 1 In te rfa c e fo r b o th 5

4 5 6  8 5 7 Å 2 C o m p u ta tio n s, 2 In te rfa c e s fo r b o th 5 5 6  5 7 Å 2 C o m p u ta tio n s, 1 In te rfa c e fo r b o th 5 

Fig. 4: Data Computation and User Interaction

Finally, the alias can be used to force different interfaces. For example the expression 5[6 5\6 generates for the two 6a single computation and two distinct interfacesAs the two 5may receive two distinct arguments, there will be two distinct computations for 5.  3URSHUWLHVRIWKH6HUYLFH$OJHEUD A description of the algebraic properties of the operators introduced in Section 2.2.1 follows. The properties hold both at the data level and the user interface level, in that the algebraic simplification of service expressions determines the simplification of corresponding GUIs as well. From the data point of view the algebraic operators satisfy some usual properties, such as associative, commutative, reflexive, distributive, and absorbing. These properties are analogous to those of relational algebra, (see, for instance [33]), more details on this are in [23]. The algebraic properties related to the user interface deriving from the algebraic combination of services characterize the service algebra and it is worth considering them in detail. As a general observation, it may be the case that a user produces a complex operation by combining a set of existing services with the algebra operators. The algebraic properties are a tool to simplify/optimize an expression, as happens, for instance, in a relational environment.  $VVRFLDWLYH3URSHUW\ 1a) Composition: since : o ; o < is written in the form :;< independently from left or right association, then only one combination of the corresponding user interfaces is possible; 1b) Summation: ;< : generates an interface for the result of ;< ; as this result is summed to :, then we have only one user interface for the final result; ;