2. Related Work

2.1.1.1 Imperative Languages

Imperative programs can roughly be described as sequences or blocks of instructions/assignments. These sequences can be grouped into procedures. The entities that values are assigned to, are called variables and can be compared to named memory areas. Instructions can be computations or procedure calls. Most imperative languages provide support for primitive data types, like strings, numbers and boolean values, and also for structured values and pointers to values.

Conditions can be expressed through IF-THEN-ELSE or CASE constructs, forking the sequence of assignments. Sequences can be repeated, WHILE a condition holds, or UNTIL a condition is reached. It is usually possible to iterate over a sequence of values -- FOR every pass the value of a variable is set to an actual iteration value (e.g. a number) and can be accessed in the block that is iterated.

Procedures may be defined to require parameters and they may return a result value. When a procedure is called, the control flow in the calling sequence is suspended and the block of the procedure is executed. When a procedure returns (this happens when its sequence of assignments is done) the calling block continues its execution.

VIPR [citrin94design] is a visual imperative and object oriented language. The fact that the language is object oriented is irrelevant here, because this property is orthogonal to the imperative nature of this language. In "The design of a completely visual OOP language" [citrin94design] the visual imperative object-oriented programming language VIPR is presented. VIPR's semantic is inspired by C++, but it can be understood in terms of a small amount of graphical rewriting rules. Features like continuations and dynamic dispatch, which exist implicitly in C++, can be made explicit for the sake of a better program comprehension. The static view of programs as well as the visualisation of dynamic execution can be presented with the same visual metaphors.

In VIPR, programs are represented as nested circles. The notation can be seen as viewing a flowchart from the point of a bead moving along the control flow lines. The nested circles can also be interpreted as segments of a pipeline with a point of view inside this pipeline. VIPR defines objects and classes by aggregating definitions of data and procedures visually. Interfaces are defined by hiding all the private methods and data. A dynamically dispatched method contains branches to all the appropriate implementations of the method, and the correct branch is selected dynamically based on the type of the object being called.

Procedures and functions are represented as sets of nested rings outside the ring of the main procedure. A procedure call is an arrow pointing to the procedure, with nodes attached representing the arguments. Nodes attached to the outermost ring of the procedure represent parameters. Each procedure must have at least one parameter, representing the continuation or the return address. The assignment of arguments to parameters is done through positional matching.

Figure : VIPRmethod

This illustration shows a VIPR method. It is called "moveTo" and accepts two arguments: newX and newY. First newX is assigned to the object member x (the object is not shown here), then newY to y. The method returns a void or null value. The arguments and the return argument are attached to the outer ring.

Classes and objects are shown as aggregations of methods. In essence, a VIPR class is a grouping of individual methods, each of which looks like a strand of fibre being viewed head-on. Subclasses are enclosed inside the aggregate representing the superclass. This is contrary to the usual way of modelling class hierarchies, where subclasses indicate their superclass. This implies that the superclass is modified when a subclass is defined, but the system environment can automatically deduce this for the user. Thus only single inheritance is supported (see figure VIPRcomplete).

Figure : VIPRcomplete

Three VIPR classes are presented here. The class named point is the base class of shape. square and circle are subclasses of shape. All of them share the moveTo method and the coordinates. square and circle have further class members.

The use of arrows in a visual environment usually leads to scalability problems concerning readability. Thus VIPR programs may be enriched by text when it simplifies the representation. Nevertheless, the semantic of the programs is fully determined through non textual components. Therefore the textual elements may be seen as documentation or syntactically restricted comments (the textual representation of visual elements is the syntactical C++ equivalent)

2.1.1.2 Functional Languages

The main difference between pure functional and imperative programming is that functional variables do not represent storage or memory areas, but represent values or functions. Once a value is assigned to a variable this value may not be altered any more. Hence the result of evaluating a function or querying a variable has no side effects, which means it will always return the same result. Therefore the control flow -- the order of evaluation -- is no longer explicitly determined in a program. Optimisation based on restructuring the evaluation order and reducing duplicate calculations can automatically be deduced. Lazy evaluation and caching of results as well as automatic parallelisation with syncronisation are advantages of modern functional languages.

Most functional languages have functions and data types as their basic constructs. A function is defined in terms of other functions and constructors. A constant is a function of arity 0. Inside a function, local functions (and therefore also variables) can be defined using so called LET or WHERE clauses. There are various ways to express conditions, e.g. pattern matching. Other features found in many functional programming languages are currying (aka. 'Schoenfinkeln') and higher-order functions.

While people concerned with imperative programming often argue that the lack of side effects is of disadvantage for optimisation, it is easy to emulate by sequencing functions taking state objects and returning state objects. This programming pattern is known as monadic programming [jones93imperative].

The success of visual programming in the field of digital signal processing (mentioned in the introduction of this section) is strongly related to functional programming. A simple, non technical entertainment oriented and high level system is the open source software called BEAST. BEAST can be used to build sound synthesiser networks based on simple synthesiser components. Each of those components has input and output slots that are connected by edges. Each instance of such a component can be seen as a function without side effects. This methodology emulates the classical construction of analogue synthesisers.

Figure : BEAST

A screen shot of a synthesiser network in BEAST. The arguments passed through filters are signals. Signals are time based values. The two constant values on the left are used to influence the sample player BseWaveOsc-1. A virtual amplifier further modifies the signal before the output audio bus is fed with it.

A general purpose visual programming language is Visual Haskell [john94visual]. The roots of the project also originate from the signal processing community.

Visual Haskell is a visual functional programming language based on the textual functional language Haskell. It is very tightly bound to Haskell. This way Haskell programs can be seen or edited in the textual and in the visual representation. The goal is to provide a visual representation to all constructs found in Haskell.

The main concept behind visual Haskell is the data-flow diagram. This seems to be generally the widespread visual view for functional programming languages. A function is defined as a box labelled with its name and optionally an icon or a visual representation. Those icons are used to provide new graphical elements for application-specific data types and functions. This way a visual metaphor is provided for a function. The visual metaphor. At one of the outer sides of the boxes bound (usually the right side) there are slots for the input arguments, at the opposite side (usually the left side) a slot for the output is available. At the inner side of the input argument slots' side, visual patterns can be attached with further slots to pass the pattern variables to concrete function bodies. This is done through arrows. Different patterns and different corresponding bodies can be stacked (separated by a line) inside the function definition box.

An icon representing a function may have a special grey box representing a visual variable for the first argument of the function. The special focus on the first argument of the function is due to a wide spread functional methodology called currying - with currying a n-ary function may be applied to m (<n) arguments resulting in an (n-m)-ary function (Thus compilers or virtual machines can break down every function application into a series of unary function applications). Functions in functional libraries are often designed so that applying something to the first argument results in a very practicable specialised function. This can be done in a cheerful way in visual Haskell, because of the visual variables inside iconic function representation.

Figure : visualHaskellMap

The classical map function in visual Haskell. Right beside the name there is an icon used to depict the function. It is used (for purposes of recursion) in the function itself with f as argument (the last occurrence of f). Function arguments are represented by the external triangles on the right, the external triangle on the left is the result of the function. Two patterns are used: the first for mapping f to the empty list -- the empty list is returned, another for the recursion case. The list constructor is the vertical white bar used twice in the second pattern -- once for deconstruction into head x and tail xs, another time for construction of the mapped list right before the functions output.

2.1.1.3 Logic Languages

In classical logic programming neither functions nor procedures exist, only rules and facts are known. A fact is a predicate followed by an n-tuple of terms. A term can contain variables. Prolog is a widespread logic programming language. In Prolog rules are restricted to a subset of Horn clauses, disjunctions of facts with exactly one positive fact. A more popular view of the Horn clauses used in Prolog is an implication from a body (which consists of a conjunction of predicates) to a head (consisting of exactly one predicate). A special Horn clause is called fact; this Horn clause has an empty body interpreted as true. Program execution of logic programs is a kind of reasoning on the facts and rules the program consists of. The result of a program execution can be seen as proof of the rules and facts. It can be true or false, and free variables can be interpreted as being bound to the facts that fulfil the program.

Alike to the implementation of the imperative paradigm that has been presented in the section about functional programming, the implementation of functions in logic programming will be presented now. To implement functions in logic programs, rules are needed that relate the result to the arguments. To represent f(x)=y in a logic program, one may use a relation f(x,y). From the point of view of a relation, it is irrelevant which parameters are the input of a function and which are the output, thus functions implemented in logic programming languages can often be evaluated in both directions.

The execution of logic programs is usually based on resolution, which itself uses unification to either check equality of terms or provide variable bindings. A runtime system for logic programs is an inference system.

In logic programming there is no explicit control flow specification, only rules and facts. For visual programming, this means that only formulas and terms need to be visualised. Visual logic programming languages appear rarely to provide visual metaphors of those very abstract concepts, but provide domain specific concept visualisation. A visual logic language [puigsegur97from] with expressions based on acyclic graphs and sets is presented.

The visual language presented in "From Queries to Answers in Visual Logic Programming" [puigsegur97from] is comparable to Prolog in its expressiveness.

Terms are represented through directed acyclic graphs consisting of labels and variables. Variables are anonymous and are represented by circles, the parts of terms with explicit names are represented by labels written in a round box. If a term f is composed of other terms or variables, an arrow is drawn from the corresponding member to f. Sharing a variable by using multiple arrows pointing away from it, is used to represent multiple occurences of the same variable in a term representation. Because there is no explicit order for arrows pointing to a term node, terms could be interpreted as having unordered application of arguments, but this is not explicitly noted in [puigsegur97from]. The examples seem to indicate an implicit order for arrows from left to right.

Figure : puigsegurTerm

This graph represents a term. Because the variables are unnamed, there are ambigous textual representations, but f(X,g(X,a),Y) is one of them.

Predicates are interpreted to represent set inclusions. Therefore one argument of a predicate is omitted in arrow based application and is represented by the visual extension of the predicate visualisation. A predicate is visualised as rectangle with its name written in the top left corner. All further predicate arguments not treated as the set representing argument are applied with arrows as mentioned earlier. No explicit order is given for the occurence of the set representing variable in a textual transcription of predicates, but examples indicate that the first position is used for the implicit set representation variable. To express a subset relationship, nesting the box that represents the subset into the box representing the superset can be used. To express intersection of sets, the boxes that represent the sets are layed out in an intersecting way.

The smallest complete unit of description in this language is a diagram. A diagram is composed of various predicates and terms connected to one graph. A diagram represents a visual equivalent to a textual formula. Queries to a program (a set of formulas) can be expressed through use of explicitly marked variables. The variables are labelled by a questionmark to indicate that their bindings are to be returned as result.

Figure : puigsegurAncestor

In this example predicates and variables are used. It models the ancestor predicate: the left variable has its parents as ancestors (through inclusion in the big ancestor box) as well as the ancestors of its parents.

The use of abstraction over one predicate argument for set representation reminds of currying in functional programming. To some extent this language supports a blend of functional and relational programming style.

visXcerpt, the query and transformation language proposed in this thesis (in the next chapter), is also a visual logic programming language. Expressions in visXcerpt are based on a visualisation of XML data, the program evaluation is based on an unification algorithm called simulation unification.

2.1.2.1 ER Diagrams

A popular diagrammatic modelling language is the Entity Relationship diagram. It is based on the Entity Relationship model. The ER model combines ideas of the network model, the relational model and the entity-set model. The main concepts of the ER model are called entity set and relationship set. Two or more entity sets are related through a relationship set. The relationships can be quantified as 1:1, 1:n or m:n relationships.

In ER diagrams, an entity set is visualised as a rectangular box and the relationship set is shown as diamond shaped box. The name of entities or name of relationships is placed inside its box. Associating entities to relations is performed by connecting them through lines. Beneath those lines the optional quantifiers 1, n or m can be placed. A later extension introduced attributes. Attributes are ovals containing names and are associated to exactly one entity set. They represent the atomic members of an entity set.

Figure : ERVendorProductCategory

A database with vendors, products and categories is modelled here. The vendors sell products and products belong to categories. It is possible to find out which vendors sell which products and which products are sold by which vendors. The same applies for the isA relationship. Vendors and categories have a name. Products have a description and a name. The attributes are considered to be of primitive type, like e.g. string.

The Entity Relationship model has not been implemented in any database system, but it is commonly used during the database design phase, because it provides less restrictions and higher abstraction than most widely implemented database models. For the relational database model (and also for other models), methodologies translating the entity relationship model into the implementation model exist. Although those translations can be derived automatically, it is common to refine the translations manually.

2.1.2.2 UML

UML is the abbreviation for the Unified Modelling Language, a standart managed by the OMG. UML is used to model object oriented software (or in general object oriented architectures). Programming is not in the scope of UML. An UML model is used as plan for implementation, it can be compared to blue prints for house construction.

UML is a diagrammatic language with various diagram types. The topics covered by each of those diagram types are mostly non-overlapping, so as to make clear which diagram type to use for which aspect of the model.

The different diagram types will be presented now. A following description is based on [omg01uml] and [rumbaugh98uml].

/

<^>

2.1.2.2.1 Static structure diagrams -- class and object diagrams

Those diagrams are used to model object oriented aspects of the project. These diagrams are widely accepted for applications implementing UML partially. While a class diagram represents relationships and properties of classes, an object diagram is used as example for concrete instantiations.

First of all objects and classes are modelled as boxes. Some visualised aspects are contained inside the boxes, others use lines and arrows between boxes. The aspects modelled are:

• Inheritance/generalisation: This is shown as a line with a big arrow head pointing towards the superclass. Usually those lines use vertical and horizontal components only. If a class generalises many classes the same arrow head is usually shared.
• Attributes/operations: Primitive attribute members and operations are contained as vertical list inside the class box.. Primitives are usually strings, boolean values and numbers. For other members, association or composition is used. Operations may contain parameter lists enclosed in parentheses. It is a purely textual feature.
• Types: The type of parameters, attributes and operations is appended, separated by a colon. It is a purely textual feature.
• Visibility: The visibility of a member is modelled by prepending a textual symbol like + for public and - for protected. Standard colour icons for the visibility attributes exist. It is questionable if those icons make the visibility aspect a non textual aspect, just because they happen not to be part of the usual font sets, after all it does not provide a new dimension.
• Association/composition/aggregation: Those features are used for non primitive members of classes. They are mainly represented as lines between two classes. They may be directed and a name must be associated to such a line. The name is usually written below the line. Composition and aggregation are special cases of associations and are shown through diamond arrow heads either filled (composition) or hollow (aggregation).
• Multiplicity: On both ends of an association the relations multiplicity may be written in textual form..

Figure : UMLstatic

A static UML class diagram. Every box represents a class. Circle and Rectangle are derived from Shape which is derived from Point. A Shape has an Outline and a Filling aggregated to it (they may not be shared between instances of shapes). Outline and filling have both a Colour associated to them.

/

<^>

2.1.2.2.2 Use case diagrams

Use case diagrams are used to model relationships between use cases and actors. They are only for documentation purpose, no automatic program generation is known that benefits of use case diagrams.

A use case diagram is a graph with use cases and actors as nodes. The arcs are so called use case relations and actor relations. Actors are drawn as stick-figures with labels below, use cases are abbreviated by ovals with labels inside.

Figure : UMLusecase

This use case diagram is about the relationships between vendor, boss and customer. The use cases are the three ovals in the middle.

/

<^>

2.1.2.2.3 Interaction diagrams

Interaction diagrams are realised through sequence diagrams. A sequence diagram is used to model the life line of an object, the activation and the message passing. Sequence diagrams are two-dimensional diagrams: one dimension (usually the vertical) is used to display evolution through time, the other to distinguish between different objects. Therefore an object is a vertical line with a thick bar on the line indicating the life line of the object. Message passing is modelled by arrows pointing from one object to the next at a certain state transition on the life lines of both objects. When message passing is instantaneous, the arrows are horizontal.

Figure : UMLsequence

With this sequence diagram, the process of making a phone call is described. The objects involved are caller, phoneNetwork, the person who is called and an accounting system. Various messages are passed between the objects.

/

<^>

2.1.2.2.5 State chart diagrams

A state chart diagram can be used to describe the behaviour of an object. It is a graph of states as nodes and state transitions as directed edges. A state is displayed as rectangle, an edge as arrow. A node is labelled with the state name inside the bounds. It may also be divided in two areas where the first contains the name and the other an activity in process while in this state. Edges are labelled with a name and optional preconditions (in textual form). A special state, the start state, is a little empty circle. An end state is a double bordered circle. State diagrams can be nested hierarchically, indicating sub state machines. Entering a sub state machine begins at the starting state of the sub machine. Reaching an end state means leaving a sub state.

A special case of a state chart diagram is the activity diagram. An activity diagram has mostly actions (a UML-term) as states. It represents some kind of flow diagram and has therefore some visual constructs for handling conditions, like a diamond shaped box for conditionals and plates for merging control flow.

Figure : UMLstatechart

Here, a state chart diagram is used to model the procedure of making a phone call. Opposed to the previously presented sequence diagram, the involved objects are not obvious. Hence the states and the events responsible for state changes are modelled here.

/

<^>

2.1.2.2.6 Implementation diagrams

Implementation diagrams show aspects of the concrete implementation. There are two types of implementation diagrams:

• Component diagrams: They show the dependencies of implementation components. A component diagram is a graph of components connected through edges representing simple dependency, containment and implementation relationships
• Deployment diagrams: They represent the configuration of runtime objects like processes, and objects that are part of them. A deployment diagram is a graph of nodes representing processes with communication associations as edges. The processes are displayed as bevelled boxes containing component diagrams.

Figure : UMLdeployment

A deployment diagram is used here to model the relationships of physical instances and processes involved in a telephone network system.

2.1.2.3 UML's four layer meta model

All those different visual diagrammatic languages in UML are based on the same four layer meta model. It consists of:

• meta meta model: The infrastructure used to model meta models. It is mostly the definition of a graph
• meta model: Meta models are the languages described above (like class/object diagrams, collaboration diagrams,...)
• model: A model is the output of the concrete use of the former meta models, or in terms of programming languages: modules and classes.
• user objects: User objects are instances of former classes.

UML itself mostly covers meta models. Research work about visual meta- meta modelling can be read in [fishwick00aesthetic].

2.1.3.1 Kaleidoquery

The short description given here is based on [murray98kaleidoquery].

Kaleidoquery is a visual query language for object databases. It is a visual syntax that is back-ended by the textual query language OQL. The main philosophy behind Kaleidoquery is a filter flow metaphor. This can be compared to a functional paradigm. Kaleidoquery is modelled towards the needs of casual users that want to create ad-hoc queries. The iconic nature is useful for users not aware of the database schema -- they can deduce it from the visualisation.

A query can be explained as a chain of filters, with all database extends passing through this chain and being successively reduced until the intended result is left. The first element of this filter chain is an icon representing a certain class in the database. The database author is urged to provide icons to database classes. The chosen icon is the lowest member of the filter structure. For a projection of some attributes, a vertical arrow is used pointing to an oval with the attributes that should be projected. A filter network without projection as last filter step has no output. This is useful for joins, that are explained later.

Figure : KaleidoProjection

This Kaleidoquery example queries all objects in the class People and returns their name and age as result projection.

Further simple constraints (like less, equal,...) can be placed in textual notation on this uprising filter path. To express conjunction of constraints, all constraints are attached vertically by arrows. For disjunctions, the filter flow is split into many parallel vertical filter flows, each strand representing one disjunct. Horizontal arrangement of disjuncts and vertical arrangement of conjuncts is quite common in visual languages. Negation is expressed by inverting the corresponding simple constraints colours.

Figure : KaleidoConstraints

All people that are either named Smith or are between 16 and 20 years old are queried and returned. This explains the use of constraints, disjunction and conjunction.

Joins are expressed by parallel filter expressions sharing a simple binary constraint, like equality. One side of the equality is then located in one filter while the other side is in the other subfilter. A self-join is also possible, when two arrows are drawn from one class oval.

Figure : KaleidoJoin

An equi-join is expressed over two databases. All names of instances in the left database which have the same salary as instances in the right database are returned.

Object oriented databases may store complex structures where objects may contain other objects as members. Refining a query based on certain members of selected objects along the filter flow is a common operation. Shifting the selection to the members of an object is called navigation. Navigation is represented by a horizontal arrow with the name of the member written above it.

In object databases a common operation is checking for membership of objects. For this purpose a curly horizontal arrow with the word member is used. The same curly arrow is also used for the for all and the exists quantifiers found in OQL.

Figure : KaleidoAll

In this example navigation and a quantifier is used. The boxes with checked pattern represents companies. This query returns company names where all employees are either older than 60 years or have a salary of more than 25000.

Further expressions like functions, grouping and ordering constructs are expressed by wrapping the ovals with further ovals. The corresponding operation is included in the wrapping oval. This corresponds to the nested term structure of the textual OQL counterparts.

Figure : KaleidoFunction

An aggregation function is used to count the people in the database. Functions, grouping and ordering constructs are nested according to their corresponding term structure in OQL.

Kaleidoquery has a very imperative nature in the sense that the queries are refined step by step. The user has to be aware of query optimisation while using constructs like conjunction. For example using more restrictive constraints at first is better than using them later in the filter flow. Generally, the use of edges (arrows in Kaleidoquery) tend to render cluttered views for big programs, because of line crossing. However, even big Kaleidoquery programs do not seem to get cluttered. A reason could be that edges are not used to express structure.

2.1.3.2 Query by Example

As example for a visual descriptive query language QBE will now be explained. The description is based on [zloof77query].

QBE (short for Query-by-Example) is a database management language. The base idea is that the user fills in examples of the data he/she intends to modify or query. The underlying data model for QBE is the relational data model. Because relational databases can be seen as a set of tables, the example queries edited by the user are tables.

QBE is a visual query language language, because it relies on tables which provide arrangement of information in two dimensions. Except underlined text (to indicate variables), further constructs of QBE are purely textual.

Figure : QBEemptyTable

An empty table skeleton in QBE consists of (any number of) rows with a table row name and an area for values.

In QBE a query starts with an empty table skeleton based on the schema of the data. The user may now fill in fixed values for constraints of the result data. For different alternative constraints, more (implicitly OR-ed) cells are filled into the table. The result of executing such a query is a table containing only tuples found in the database fulfilling the constraints. The result schema is the same. To return data in different schemata, the user may use the keyword P. (for print) in columns relevant to the result.

Figure : QBEgreenItems

This example queries all green items in the database. The queried database consists of at least one table with at least two columns -- Item and Colour.The result table presented to the user only has one column -- Item.

Variables have a name and are represented by the underlined name. A P. can be prefixed to the variable name if the table is also to be printed. In QBE it is considered good programming style to choose names that can be seen as example instances of the desired variable bindings. The same variable can also be used in different database tables within a query - this pattern is called link. Thus joins over different relations can be formulated. Temporary result tables can be introduced. They may contain only variables of queried tables occurring in the same query.

Figure : QBEjoin

An example that uses the apple variable to join over two tables. The result is a list of all vendors (and their phone numbers) selling green products. The Ralph's variable is unused, but this doesn't matter. Unused variables may be introduced as examples for in-code documentation purpose.

For further qualification of variables or constant values, inequality operators and negation can be used, as well as arithmetic expressions. There is also a so called Conditions box: expressions over variables, arithmetic expressions, equations and AND and OR concatenated expressions can be placed here. It is intended to be used when conditions are difficult to express in table cells.

Figure : QBEimplicitOR

An example using implicit OR to query for products that cost 0,79 or 0,89.

Figure : QBEimplicitAND

This shows the implicit AND. An item is only printed to the result table, if it costs more than 0,79 and also less than 4,50.

Figure : QBEconditionBox

A condition box is used here to express that items are used that cost more that the items with ID 0815 and 7987 together. Item, Price and ID are returned as result.

For grouping and aggregation further keywords are provided:

• ALL. prevents omission of duplicate elements in the result,
• CNT. counts the matching tuples,
• SUM. adda all matched numeric values together,
• MIN. and MAX. get the minimum/maximum of the matched values and
• AVG. calculates the average of the matched numeric values.

To be able to fully manage a database, not only querying but also inserting, deleting and updating is necessary. The keywords for this are D. for delete, U. for update and I. for insert. I. can also be used to create new tables in conjunction with keywords describing the valid database types. These operations are used similar to the print operation.

QBE has been used as conceptual framework for many successful commercial database systems like MS Access. For a measure of feature completeness and for the sake of comparability, the expressiveness of query languages for relational databases are compared to the relational algebra or to the tuple calculus (which provide the same expressiveness) : QBE can directly be translated into the tuple calculus and is hence as expressive as for example SQL, but it is much easier to use especially for casual users -- the knowledge about filling in forms is wider spread, than the knowledge about textual database languages.

2.2.1.1 W3C's Standardisation Process

The W3C's standardisation process is transparent and can publicly be followed by everyone on the WWW. Only members are allowed to contribute to the standardisation process. A recommendation is the final and stable version of the standard emitted by the W3C. Such a recommendation is likely to be integrated in various related commercial products, because often the leading companies working on concerned topics are members of the W3C and are also the main contributors. The W3C's recommendation process passes through the following stages (as defined in the W3C Technical Reports and Publications page)

• Note : A Note does not represent commitment by W3C to pursue work related to the Note
• Working Draft : These are draft documents and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to use W3C working drafts as reference material or to cite them as other than "work in progress".
• Candidate Recommendations : A Candidate Recommendation is work that has received significant review from its immediate technical community. It is an explicit call to those outside of the related Working Groups or the W3C itself for implementation and technical feedback.
• Proposed Recommendation : A Proposed Recommendation is work that
  1. represents consensus within the group that produced it and
  2. has been proposed by the Director to the Advisory Committee for review.
• Recommendation : A Recommendation is work that represents consensus within W3C and has the Director's stamp of approval. W3C considers that the ideas or technology specified by a Recommendation are appropriate for widespread deployment and promote W3C's mission.

2.2.1.2 XPath

The navigational aspect of XSLT and XQuery is expressed through XPath expressions. XPath has reached the state of a W3C recommendation. XPath should not be seen as a language on its own, but rather as query expression for hierarchical data, like regular expressions for textual data. Although simple query tools for evaluation of XPath expressions on XML data [FOOTNOTE] : Xmllint's shell mode can be used for this purpose. Xmllint is part of the libxml library, hosted at exist, it is usually considered to be a component of a host language. XPath is part of XSLT and XQuery.

An XPath expression is applied to so called XML contexts and returns a (maybe empty) list of XML contexts. An XML context is a node or location inside an XML document. An XPath is a sequence of selection primitives and conditions, each applied to the selected contexts of the preceding selection primitive. The primitives are instances of the so called Axis and are the simplest possible XPath expressions. Those axis provide the ability to select

• named children or any child of a context node
• the parent node of a context node
• the previous/following nodes of a context node in document order [FOOTNOTE] : Document order describes the order in which the nodes -- or least their closing tags -- occur in a textual XML representation. For a tree view of XML data this corresponds to the order of a depth-first left-to-right traversal of the tree.
• the previous/following sibling nodes of a context node
• named (or any) children or descendant at any depth below a context node
• a context node itself

If a path primitive (or a whole XPath expression) is applied to a list of contexts, the results of applying the XPath to each context are concatenated. Conditions are either boolean functions operating on contexts or further XPaths. If a condition is an XPath it is interpreted as successful if the XPath's result is not the empty list.

/html/body//a[    contains(./text(),"Xcerpt") 
              and starts-with(./@href,"http:")
             ]

Although XPath is defined to process tree structures, nothing enforces an implementation to work on physical tree structures. There is ongoing and very promising research [olteanu02xpath] about processing XPath expressions on streams of XML events -- known as SAX streams. This has the advantage of not having to manage an in-memory representation of the XML document. This is highly relevant for processing very large databases. It is even possible to support approximated queries on infinite streams.

2.2.1.3 The transformation language XSLT

XSLT is the first XPath based language proposed by the W3C and has reached the state of a W3C recommendation. XSLT is intended to be used for transformation of XML documents into other XML, HTML or even plain text documents. A template based approach is used. An XSLT stylesheet is applied to a document [FOOTNOTE] : Although applied to only one document, it is possible to specify the use of further documents either as input through an appropriate XPath-function, or as included templates. and returns a new document.

Some major components of the visXcerpt prototype have been implemented using XSLT. For the reader unfamiliar with XSLT and interested in studying the implementation of the prototype, XSLT is explained in more detail here. Nevertheless, XSLT is mostly irrelevant for the design of the visXcerpt language itself.

The whole process of transformation is driven by recursive application of templates. The selection of the context and the restriction to the template to apply to the context selected is expressed in XPath. Every template has an XPath expression that has to match with a context in order to be applied. If many templates match the same context, various precedence rules determine wich template is actually chosen. The template consists mainly of a portion of XML content [FOOTNOTE] : A portion can be plain text, or any number of elements. It is not necessary that there is only one root element, but all elements have to be well formed. It is therefore not possible to open tags in one template application and close them in another one. which may contain hooks for further template application. Those so called apply-template elements establish the recursion step. They have an XPath expression for selection of the next recursion step's context. The syntax of the XSLT language itself is XML based.

With the recursive template mechanism, generating new XML content based on existing content is defined. Further aspects of XSLT are:

• Including data from the input document: Textual data can be included with the value-of element. An XPath expression is supplied to select the context that is to be included. If the expression evaluates to more than one context, only the first one is considered. If the context is not a text-node or an attribute, nothing is copied. To copy an element with all its attributes, the copy element is used.
  Example : XSLT-1

  ...
  <xsl:template match="a">
    <xsl:copy select=".">
      <apply-templates select="*|text()"/> 
      (see <xsl:value-of select="./@href"/>)
    </xsl:copy>
  </xsl:template>
  ...
  

  This example promotes the template, apply-template, value-of and the copy elements of XSLT. A template is presented that extends HTML hyperlinks with a textual representation of the URL they point to. The a-element is copied with all its attributes, the content is recursively processed and a "(see http://...)" is appended.
• Variables and parameters: To be able to transfer data from one template invocation to a subsequent template application, templates can be parametrised. Therefore in a template, named parameters with default values can be defined. A template application can then set those parameters to other values, but it is not forced to. Assignment to parameters is restricted to the template application, and further applications of the same template are not affected by the assignment. It is therefore considered to be a side effect free assignment, comparable to let expressions in pure functional programming languages.

  Variables are similar, but may only be defined and used inside of templates, or globally inside of the stylesheet. Template variables are not accessible outside their containing template; global variables are accessible in the whole stylesheet.

  Example : XSLT-2

  <xsl:stylesheet version="1.0" 
             xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:variable name="TITLE">
      <xsl:value-of select="/html/head/title/*"/>
    </xsl:variable>
  
    <xsl:template match="/">
      <xsl:variable name="COUNT">
        <xsl:value-of select="count(//h1)"/>
      </xsl:variable>
      <h1>Index</h1>
      <xsl:apply-templates select="//h1">
        <xsl:with-param name="COUNT">
          <xsl:value-of select="$COUNT"/>
        </xsl:with-param>
      </xsl:apply-templates>
    </xsl:template>
  
    <xsl:template match="h1">
      <xsl:param name="COUNT">???</xsl:param>
      <xsl:apply-templates select="*"/>
      ( <xsl:value-of select="position()"/> 
        of 
        <xsl:value-of select="$COUNT"/>
      )
      in <xsl:value-of select="$TITLE"/>
    </xsl:template>
  </xsl:stylesheet>
  

  Parameters and variables are used to transport values accross contexts. TITLE is a global variable. It is invoked in the third template by its name $TITLE. The second template passes the parameter COUNT to the third template. COUNT has the default value "???" if the template is called without parameter.
• Further conditions: The template application according to an XPath selection and the template choice according to a matching XPath is a powerful conditional. It can be compared to the guard based conditional of modern functional languages like Haskell or Clean [FOOTNOTE] : Haskell's guards are described in the "gentle introduction" in the section about pattern matching semantics at http://www.haskell.org/tutorial/patterns.html#sect4.1. Nevertheless, it is sometimes useful to be able to restrict template application, and therefore have the application hooks surrounded with conditional constructs. For this purpose the if conditional can be used. The test is either a boolean test or an XPath expression that has to be productive to be interpreted as true expression. There is no else to choose between two alternatives. For choices there is a choice conditional with the same semantic as the widely known switch/case conditional in C or Java.
  Example : XSLT-3

  ...
  <xsl:template match="h1">
    <xsl:copy>
      <xsl:if test="contains(text(),"Xcerpt")">
        <strong>[RELEVANT] </strong>
      </xsl:if>
      <xsl:apply-templates/>
    </xsl:copy>
  </xsl:template>
  ...
  

  This template can be used to prefix an annotation "[RELEVANT]" in h1 headings containing the ord Xcerpt.
• Namespaces and XML abstraction: XSLT is an XML based language, therefore it uses XML elements as syntactical elements. The construction patterns are also in XML syntax. To be able to distinguish between construction patterns and XSLT elements the XML namespace mechanism is used. To be able to use XSLT-elements as construction patterns, there exists a so called namespace-alias element that defines a namespace to translate into the XSLT namespace in the output element. This mechanism was widely used for the prototypic implementation of visXcerpt, which is partly implemented using XSLT.

  When it is inconvenient to use XML patterns, because e.g. an element name is parametrised, or because only attributes are to be created in a template, there exists an abstraction over XML elements. The XSLT elements attribute, element, text, comment and processing-instruction are defined for this purpose. The content of all of those elements is interpreted as the corresponding child content or value, attribute and element have an attribute name for the corresponding names of the constructed components.

  Example : XSLT-4

  ...
  <xsl:element name="a">
    <xsl:attribute name="href">
      http://www.xcerpt.org/
    </xsl:attribute>
    <xsl:text>
      The Xcerpt Homepage
    </xsl:text>
  </xsl:element>
  ...
  

  This is the part of a template. It produces a HTML hyperlink to the Xcerpt homepage by using the XML abstraction of XSLT.
• Defining functions: Functions as known in programming languages are very similar to templates. Applying templates is in fact like having a function applied to some XML content from the input document and having the return value transferred to the output document. To be able to call functions from inside other functions, it is possible to give templates a name attribute and to use the call-template element with the name of the template to call. This feature is mostly used to centralise functionality used in different places of the transformation stylesheet.
  Example : XSLT-5

  ...
  <xsl:template match="body">
    <xsl:apply-templates/>
    <xsl:call-template name="footer"/>
  </xsl:template>
  
  <xsl:template name="footer">
    <hr/>
    (c)2003 - Sacha BERGER.
  </xsl:template>
  ...
  

  A function named footer is provided to insert a copyright note in various situations. The first template calls the function defined in the second template.
• The for-each element: The for-each element has a select attribute containing an XPath, and a construction pattern as content that is applied to the data matched by the XPath expression. It can be compared to an anonymous function (a lambda function) in functional programming languages. The for-each expression is an anonymous template applied to the Xath expression of its select attribute.
  Example : XSLT-6

  ...
  <xsl:template match="body">
    <body>
      <h1>Index</h1>
      <ol>
        <xsl:for-each select=".//h1">
          <li>
            <xsl:apply-templates select="*"/>
          </li>
        </xsl:for-each>
      </ol>
      <hr/> <!-- CONTENT -->
      <xsl:apply-templates="*"/>
    </body>
  </xsl:template>
  ...
  

  This template may be used to enrich the body of a HTML document with an index list containing all h1-headings found in the original document.
• Reordering data: Using the sort element inside an apply-template or a for-each element it is possible to sort the items matched by the XPath. It is possible to sort lexically, numerically and language dependent. Using the select attribute it is possible to specify an XPath expression relative to each item, based on which the sorting has to be done.
• Modularising templates :The import element is used to import templates defined in external stylesheet documents. In case of conflict with locally defined templates, the local ones have higher precedence. The apply-imports element is used inside templates as application hook restricted to imported templates. It has no XPath expression and therefore is only applicable to the actual context.

XSLT is a widely accepted W3C recommendation with several implementations available. It has reached the W3C status of a recommendation which means that the standard is considered to be stable. The expressiveness of XSLT is comparable to the expressiveness of a general programming language, because it is Turing complete [FOOTNOTE] : The Turing machine markup language TMML (found at http://www.unidex.com/turing) can be processed with XSLT, which demonstrates the turing completness of XSLT. A further proof for Turing completeness can be found in . Nevertheless, it is not convenient to use XSLT for general programming tasks, because of the rigid information flow from input document to output document. The Turing completeness of XSLT ensures that all transformation requirements can be achieved with XSLT, but the drawback is that there is no termination guarantee for the transformation process.

2.2.1.4 The XML query language XQuery

Like XSLT and XPath, XQuery [w3c02xquery-wd] is a language definition maintained by the W3C. It has not yet achieved the state of a recommendation, it is filed as a working draft. This indicates that XQuery is work in progress.

From a sloppy point of view, XQuery looks like a mix of XPath and SQL [fatdog01quick]. From an academic point of view "XQuery is a typed, functional language for querying XML" [wadler02xquery]. Opposed to XSLT, XQuery does not use an XML syntax exclusively, although construction patterns can be written as XML portions. As proven in [kepser02proof] XQuery is Turing complete.

for $b in document("http://www.bn.com/bib.xml")//book
  let $e := $b/author[contains(string(.), "Suciu")]
  where exists($e)
  return
    <book>
      { $b/title }
      { $e }
    </book>

define function toc($e as element )
  as element*
{
  let $n := local-name( $e )
  return
    if ($n = "section")
    then <section>
             { toc($e/*) }
           </section>
    else if ($n = "title")
    then $e
    else ()
}

<toc>
  {
    toc( document("book.xml")/book )
  }
</toc>

2.2.2.1 Xcerpt's syntax

Xcerpt, like XQuery, has two different syntaxes: one XML based and another textual syntax. Both can be used to represent query programs, input and output documents. In fact the pattern description parts of the non XML syntax are derived from the semi-structured formalism and have more expressiveness than the XML core standard, as it supports the specification of ordered and unordered content [FOOTNOTE] : XML only supports ordered content. This is useful for document oriented data. Database applications usually do not imply any order on its content (see below). Because the non-XML syntax is easier to read, it will be used in the examples in this section. For the implementation of visXcerpt it turned out more appropriate to work based on the XML syntax. This is a hint that the use of different syntaxes for one language as in XQuery and Xcerpt is a useful innovation.

Xcerpt's data notation are terms representing XML data. They are called database terms. An XML element is represented by its name followed by braces with the content, separated by commas. Text nodes are quoted in double quotes. There are four different kinds of braces : square brackets [], double square brackets [[ ]], curly braces {} and double curly braces {{ }}. To represent XML data the double square brackets are used. XML was at first tailored for the document management community. In documents, the order of elements is usually relevant. The XML formalism is useful as database formalism as well, but databases usually do not impose an order on its element. XML does not provide a mechanism to represent unordered information. In Xcerpt the different bracket types are used therefore: curly braces represent unordered data and square brackets represent ordered information.

greengrocer {
  products {
    product {
      type { "vegetable" },
      name { "cabbage" },
      price {
        unit { "piece" },
        value { "0.59" }
      },
      vendor { "DeRuiter" }
    },
    product {
      type { "fruit" },
      name { "cherry" },
      price {
        unit { "kilo" },
        value { "2.19" }
      }
    },
    vendor { "Lafayette" }
  },
  vendors {
    vendor {
      country { "holland" },
      name { "DeRuiter" }
    },
    vendor {
      country { "france" },
      name { "Lafayette" }
    }
  }
}

e difference between single and double brackets is mainly relevant for query patterns and will therefore be described in the section about Patterns.

greengrocer {{
  products {{
    product {{ }}
  }}
}}

greengrocer {{
  products {{
    var PRODUCT -> product {{ 
      name { var NAME }
    }}
  }}
}}

rule {
  cons {
    product-list [
      all var PRODUCT
    ],
  },
  query {
    in [ "file:database/greengrocer.xml" ],
    greengrocer {{
      products {{
        var PRODUCT
      }}
    }}
  }
}

rule {
  cons {
    product-list [
      all var PRODUCT
    ],
  },
  query {
    in [ "file:database/greengrocer.xml" ],
    desc var PRODUCT -> product
  }
}

rule {
  cons {
    product-list [
      all var PRODUCT
    ],
  },
  query {
    in [ "file:database/greengrocer.xml" ],
    desc var PRODUCTS -> product {{
      or {
        vendor { var DUTCHVENDOR },
        vendor { /Van.*/ }
      },
    greengrocer {{ vendors {{ vendor {{
      country { /[hH]olland/ },
      name { var DUTCHVENDOR }
    }} }} }}
  }
}

2.3.1.1 About Sara Comai - "Graphical Query Languages for Semi-Structured Information"

Sara Comai's PhD Thesis [comai00graphical] presents two graphical query languages called XML-GL and WG-LOG. XML-GL presented here is not equal to the language XML-GL presented in [ceri99xmlgl], but it is likely to be an evolutionary step due to the continuing research on this language. Furthermore, this article is condensed and thus covers less details than the older paper [ceri99xmlgl]. Both languages are based on graphs.

WG-Log is based on G-Log, a database language intended to query complex objects through the use of graphs and pattern matching. The patterns are explicitly based on schemas. A query consists of one or many graphs, each representing a rule. Opposed to other approaches like Xing found in [erwig00visual] and visXcerpt, the query and the construction part are integrated in one structure (a graph), while Xing and visXcerpt separate construction and query parts. The querying graph structure is spanned through thin or red lines, while the construction structure is spanned by green or thick lines. This indicates very clearly the relation of how the information flows between query and construction part -- they share the same nodes, making variables obsolete. A possible drawback is that complicated graphs could tend to be cluttered with many edges, but this has not been further investigated.

Figure : WG-Log

In this WG-Log query a rest-list element is constructed with all Restaurant elements offering menus as query pattern. The triangle aggregates all matched elements it points to. The offers relation is specified in a schema. Schema information could also be expressed in WG-Log.

Due to schema use, the query patterns can be smaller than their hypothetical untyped equivalent. On the other hand, WG-Log is only applicable to schema based data, while semi structured data encourages the use of schema free data. This domain is covered by XML-GL.

XML-GL uses pairs of graphs arranged horizontally and separated by a line to represent rules. Graphs consist of boxes with names inside, representing element names. Complex programs may consist of various rules. The graphs are used as query and construction patterns. Because XML data is tree structured, simple queries can be expressed with trees as query patterns. Graphs are used to model joins. Information is carried from the query side to the construction side by tag name match. This means that an element with a certain name in the query pattern is carried to the corresponding position in the construction pattern, where the same name occurs. Various constructs exist to use unnamed data and to overcome ambiguity. If e.g. a name occurs more than ones in a query graph, a line connecting the relevant query and construction node is used.

XML-GL is explained in more detail in [ceri99xmlgl].

2.3.1.2 About Stefano Ceri et.al - "XML-GL: A Graphical Language for Querying and Restructuring XML Documents"

In [ceri99xmlgl], XML-GL is presented as visual query and transformation language for XML. The use of XML-GL does not rely on the availabilty of schema information. If some kind of schema is available, editing and creating queries becomes easier, but the evaluation model of the language does not rely on a schema.

It is on the other hand possible to express schema information with XML-GL, with more expressive power than the DTD formalism provides, but no primitive type system for the textual information, as in XML-Schema, is available.

An XML-GL program is a set of pairs (at least one pair) of XML-GL graphs arranged horizontally, the left representing the query pattern and the right for the construction pattern. An XML-GL schema is an XML-GL graph enriched with extra constructs for conditions that are not mentioned in the context of query programs.

Figure : XML-GL-DTD1

This XML-GL expression represents the DTD in figure XML-GL-DTD2.

<!ELEMENT BOOK       (title?,price,AUTHOR*)>
<!ATTLIST BOOK
               isbn  CDATA  #REQUIRED>
<!ELEMENT title      PCDATA>
<!ELEMENT price      PCDATA>
<!ELEMENT AUTHOR     (first-name,last-name)>
<!ELEMENT first-name PCDATA>
<!ELEMENT last-name  PCDATA>

A graph consists of labelled boxes representing elements. Their hierarchical structure is modelled by directed edges. Patterns described this way can be used for querying as well as for schema implementation -- a data instance is valid, if it matches with a pattern. To denote the relevance of order for child elements, the first edge is crossed by a short stroke. If the structure is an acyclic graph instead of a tree and it is used as query pattern, it can be interpreted as using a join: the "child node" with more than one ancestor indicate that the ancestors must share identical child nodes. Hence the join is expressed over the shared child node. This is also the case, if two trees share nodes. In a schema graph the edges are labelled with multiplicity information like edges of ER-Diagrams. Another special visualisation is used for nodes containing only textual content -- they are drawn as hollow circles. Filled circles depict attributes. The edges to those circles are labelled with the element name or the attribute name.

Figure : XML-GL-simple

This simple XML-GL query grabs all BOOK elements found in resources in www.polimi.it/ceri/ starting with ord. The construction pattern on the right expresses to return the matched BOOK elements with all sub-elements at all depth. Without the asterisk, only the direct child elements are queried.

A feature used solely in schemas is an xor arch, crossing two edges. To model mixed content of plain text and elements, the elements and a text node circle are xor-ed. The edge to the textnode circle is labelled with "content" to indicate that it is not a text-only element. Therefore in this circumstance it is not possible to construct a text-only element called "content", a namespace mechanism that is actually missing in XML-GL, would be needed.

The base idea for the use of XML-GL graphs for querying has already been explained in the section about [comai00graphical]. Further constructs are explained now. There are three kinds of construction primitives for aggregation purpose:

• Plain boxes: They are used to construct elements. The elements have the same name as the box. For each element the query pattern has matched, an element is constructed by the box the query pattern is attached to.
• Triangles: They simply list all the matched elements from the query part they are attached to explicitly or by name.
• List icons: They react as a kind of combination of both, plain boxes and triangles, by aggregating the matched elements according to an additional grouping condition explicitly related to by an edge.

Figure : XML-GL-aggregate

This XML-GL program aggregates all matched PERSON elements (those having a FULLADDR element) below a constructed element called RESULT. Only firstname and lastname children are projected to the result.

Further constructs are available for nesting and unnesting of content, which are powerful tools to prevent recursive queries that are not expressible in XML-GL. Nevertheless it does not seem to be possible to express queries about the structure of the queried data with the constructs presented, which is usually a simple task with recursion.

2.3.3.1 VXT: Visual XML Transformer

The article [pietriga01xvt] presents VXT in more detail, compared with [pietriga01xvt2]. The additional aspects covered here are related to document type definition, further language constructs and the translation of VXT programs into XSLT.

A very intersting aspect mentioned is, that very little extension is nessecary to use this visualisation mechanism as document type definition formalism. The proposed extensions are:

• conditions or choices: choices are modelled by stacking the different choices vertically.
• zero or one occurence: Those elements are surrounded by a dashed box.
• zero or many occurences: Like zero or one occurence those elements are surrounded by a dashed rectangle, but a second empty dashed rectangle is attached to its right side by a short dashed line.
• one or many occurences: in this case the same notation as zero or many occurences is used, except that the left dashed box is drawn with a solid line.

The schema definition presented this way can be used as translucent overlay or template mechanism inside the editing window to support easier transformation writing.