Petr Nálevka's Technology Blog

Sleep as Android at GDD 2011 Prague

2011-10-18T13:08:00.000-07:00

Recently I had the opportunity to present Sleep as anDroid and other apps the Urbandroid team does at Google Developer Day 2011 in Prague as part of the keynotes. Hope you like my sleeping hat.

http://www.youtube.com/watch?v=nwoGhGZ6fc0 (my bit starts at 19th minute 30th second)

Synchronize your IDE with Google Docs for you Google Phone interview

2011-09-19T04:34:00.000-07:00

I had a phone interview with Google recently. When I prepared for the interview I tried to write code in Google Docs and was very much missing all the features of my IDE.

Maybe someone else may find my simple code snippet below useful. It does auto-synchronize you local file with the Google Document shared for you interview. So whenever you save the file in the IDE it gets uploaded to Docs so that you interview can see what you wrote. At the same time you have full code-completion/generation and the code does also syntax highlighting through JHighlight.

Here is the result:

In order to make it working you need to put your self to the sharing list (which you can do), otherwise there would be a permission error. If anyone would like to improve the code, back-synchronization of what the interviewer writes would be great.


package com.urbandroid.gdata;

import com.google.gdata.client.docs.DocsService;
import com.google.gdata.data.MediaContent;
import com.google.gdata.data.docs.DocumentListEntry;
import com.google.gdata.data.docs.DocumentListFeed;
import com.google.gdata.data.media.MediaByteArraySource;
import com.google.gdata.data.media.MediaSource;

import com.uwyn.jhighlight.renderer.JavaXhtmlRenderer;

import java.io.*;
import java.net.URL;
import java.text.SimpleDateFormat;
import java.util.Date;

public class UpdateDocument {


    public static void main(String[] args) throws Exception {
        UpdateDocument updater = new UpdateDocument();
        File file = new File(args.length == 1 ? args[0] : "/home/petr/project/google/src/Interview.java");

        JavaXhtmlRenderer renderer = new JavaXhtmlRenderer();
        SimpleDateFormat dateFormat = new SimpleDateFormat("hh:mm:ss");

        long modified = -1;
        while (true) {
            if (modified != file.lastModified()) {
                modified = file.lastModified();
                System.err.println("File modified...");
                ByteArrayOutputStream out = new ByteArrayOutputStream();
                renderer.highlight("GPhoneInterview by Petr Nalevka, last update: " + dateFormat.format(new Date()), new FileInputStream(file), out, "UTF-8", false);
                updater.update(new ByteArrayInputStream(out.toByteArray()), "Phone Interview");
            }
            Thread.sleep(1500);
        }
    }


    public void update(InputStream in, String titleSubstring) throws Exception {
        DocsService client = new DocsService("PetrNalevka-DocSync-v1");
        client.setUserCredentials("petr.nalevka@gmail.com", PassProvider.PASSWORD);
        URL feedUri = new URL("http://docs.google.com/feeds/default/private/full/");
        DocumentListFeed feed = client.getFeed(feedUri, DocumentListFeed.class);
        DocumentListEntry found = null;
        for (DocumentListEntry entry : feed.getEntries()) {
            System.err.println("Entry: "+entry.getTitle().getPlainText());
            if (entry.getTitle().getPlainText().contains(titleSubstring)) {
                found = entry;
                break;
            }
        }
        if (found == null) {
            System.err.println("Entry not found, exiting.");
            return;
        }

        found.setCanEdit(true);

        MediaContent mediaContent = (MediaContent) found.getContent();
        MediaSource mediaSource = client.getMedia(mediaContent);

        found.setMediaSource(mediaSource);

        String page = InputStreamUtil.read(in);
        mediaContent.setMediaSource(new MediaByteArraySource(page.getBytes(), DocumentListEntry.MediaType.HTM.getMimeType()));

        // shared documents do not provide edit link?
        URL url;
        if (found.getEditLink() != null) {
            url = new URL(found.getEditLink().getHref());
        } else {
            url = new URL("http://docs.google.com/feeds/default/private/full/document%3A"+found.getDocId());
        }
        System.err.println("Updating URL: " + url);
        try {
            client.updateMedia(url, found);
        } catch (Exception e) {
            // ignore, hack because GData returns error on shared documents, but update works
        }
    }

}

Sleep as an Droid

2010-11-03T06:46:00.000-07:00

There is a new android application form our workshop. Sleep as an Droid is a bio-alarm clock tracking your sleep cycles and waking you up in the light sleep phase for a smoother morning experience and more energy during your day. Working with accelerometers is also an interesting research which has many potentially interesting medical applications.

https://sites.google.com/site/sleepasandroid/
https://market.android.com/details?id=com.urbandroid.sleep&feature=search_result

New version of MHDroid

2010-08-30T10:15:00.000-07:00

Me and my colleague Martin, we have just released a new version of the MHDroid application for finding your way through public transport in Czech republic using your Android phone. For more info see https://sites.google.com/site/androidmhdroid/home.

Building my first robot

2010-08-30T10:09:00.000-07:00

No need to clean my floor anymore. Here are my cleaning robots version 1 and 2. The ultimate version 3 is coming soon. The robot uses the PICAXE controller and an analog IR distance sensor.

Version 1

Version 2

Artificial Market Simulations using Multi-agent Systems

2010-05-27T11:20:00.001-07:00

Commodity Market Trader Strategies

Petr Nálevka

University of Economics, Prague Department of Information and Knowledge Engineering ̶ Knowledge Engineering Group

          W. Churchill Sq. 4
          130 67 Praha 3
          Czech Republic
          petr@nalevka.com

Abstract

This paper is an introduction into how to build simple multi agent market simulations. It explains the used approaches techniques and algorithms.
It focuses in particular on a commodity market with double auction price evaluation. Commodity market is studied with different trader/agent types.
Price development is studied for normal utility driven consumer traders as a reference environment. Later different agent types are added to observe how do they affect the market development.

Table of Contents

Parameters
The Reference Model
Price Evaluation
Visualization

Computerized trading

Computer Traders
The Reference Setup
Adding Computerized Traders

Market Failures

Trend Trader
Consumer and Trend Traders
All Trader Types Together

Conclusion

A. Implementation

Bibliography

Introduction

This paper demonstrates how to use multi-agent systems to simulate phenomena emerging from interaction of individuals in market environments. Market is a complex system. It may be studied analytically using formal models but modelling markets in all their complexity is not possible. A model is always highly simplified and thus the observed may significantly differ from the predicted.
As an example, take in consideration all sort of different market failures we observe in every day reality but they are not deduced from the formal models used in classical economy. The reason obviously is, features causing the failures are not included in the model.
With computerized simulation we may observe features which may be lost in traditional formal modelling. With agents we are able to simulate behaviour of every individual agent in every computational step. This corresponds to real markets, where individuals and their asynchronous interaction form bottom-up the aggregated market behaviour. With computerized simulation we are able to process a state space which is bigger than what we would be able to study analytically.
On the other hand this comes with a trade-off. In contrast to formal models which may be completely understood, proved and which may be used to predict future development, simulation is partially a black box for the observer. We only define parameters of the agents and we set the state space frontiers and we let features to emerge. But analysing why are things happening in a certain way or predicting further development is not as straightforward [1] [2].
This is caused because of the huge state space the simulation is working with. All paths can hardly be followed by the observer. Of course some visualization techniques may significantly help understand the processes in deep, but usually we have to deduce the cause of a certain behaviour from the initial parameters and some highly aggregated output data.
The aim of this paper is to use the simulation techniques to examine a commodity market with different kinds of traders and how do their strategies influence the overall market price evaluation. The objective is to find some interesting consequences of those strategies especially in respect to market failures which are difficult to deduce from formal models and thus a computerized simulation is an interesting alternative to study those phenomena.

Commodity Market

The commodity market is an interesting candidate to be studied using simulation techniques. Apart from the additional complexity we may introduce using those techniques, the commodity market is not studied so intensively as most of the published papers focus on different market types mostly on the stock exchange. This means it is more likely to find some interesting discovery.
Another reason are the moral concerns regarding commodity markets which are closely related to market failures. Commodity markets trade raw commodities including raw agricultural output which are essential for basic human survival^[1]. Consequences of a massive commodity market failure may be fatal including starving, riots, political instability, war etc...
A recent example of the threats of the commodity market is the 2008 rice price rise, where the prices went up 50% in two months and they doubled since 2004. This affair threatened political stability in many developing countries.
The moral dimension is especially emphasized when we realize that some traders enter the market to deliver goods to their customers who need it for their living, but others may only use the market itself as a way to generate profit. Interesting questions arise especially when we ask how does the second group of traders influence the market and what are the consequences for the first group.

Double Auction

Double auction is one of the market models for price evaluation which is based on the classical market demand and supply model. Nowadays it is a common model for all sort of different markets [1]. Sellers and buyers both submit their bids. Based on the demand and supply, the auctioneer chooses a price which clears the market. This is the market price of the commodity at the time and also the price which is used to process all the trade transactions.
Due to large multiplicity of equilibria, analytical studies of the double auction markets are quite difficult [2]. That's why simulation is a good alternative for studying this type of markets. The multi-agent simulation described in this article uses the double auction mechanism for determining price and executing trade transactions.

The Simulation

The simple multi-agent commodity market simulation has been implemented as part of this paper. This section describes generic principles on the simulation environment and main parameters. Implementation details are described in Appendix A, Implementation.
The simulation consists of a collection of traders who may become buyers as well as sellers. There may be different kinds of traders in the simulation as they may differ in how they convert market signals into bids.
The simulation executes in rounds. Each round starts with harvest. The current harvest level is the only exogenous variable in the system. It is determined randomly. One of the trader types participating in the simulation are considered to be farmers and harvest is divided between them randomly.
In the next phase, the generated commodity is being traded using the double auction model. The market is cleared in one computational step. Each commodity unit offered for a price lower than the clearing price for the current round is sold to someone offering more.
After the market gets cleared agents may consume their commodities or keep them for further trading and another round begins. During the execution of a round, statistical mostly aggregated data are collected and visualized to give an overview what is going on it the market and how are different trader types doing.

Parameters

The commodity market simulation is parameterizable. Different parameters may significantly influence the simulation execution and the behavior of the market. Parameters may be set either globally for the simulation environment as a whole or for individual trader types.

Global Simulation Parameters

Number of traders: For each trader group number of traders who participate in the simulation may be set. Important is the ratio of different trader groups participating but also the absolute number. The more traders participate the more complex market we simulate. With more traders the date get smoother and our model is less vulnerable to random deviations of parameters. On the other hand more traders means less performance and slower computation.
Harvest: Harvest is a strong exogenous factor which influences equilibrium prices. In the simulation, harvest is a purely random variable which is controlled through 4 boundary parameters. Those define interval for the lowest and the highest possible number of commodities each farmers may become every round. The intervals are determined each round. In case the intervals are larger, the total harvest amount may fluctuate significantly.
In case we choose the same minimum and maximum amount of commodity for each round the harvest total is more or less stable culminating around an average^[2].
Budget: The budget parameter sets an interval for initial budgets for each traders which is determined randomly.

The Reference Model

The reference model is a simulation setup which is used as starting point. It is composed of only one trader type which is called the Consumer Trader. This trader is driven only by it's marginal utility function which determines it's preferences for the given commodity.
The reference model simulates the market the way it would be if it is free of any profiteers. The participating traders are all interested in the commodity for their own consumption. Each of the traders has a different marginal utility function. It is a linear descending function determined by two parameters which are randomly generated for each agent at the beginning of the simulation.

Equation 1. Utility function

MU = - P₁ . Q + P₂

MU stands for marginal utility, P₁ and P₂ are the parameters which determine the trader's preferences and Q is the amount of the commodity the trader is holding.
Each Consumer Trader is a farmer at the same time. He gets an random amount of commodity each round. Next he buys or sells commodity units on the market and finally all his commodity stock gets consumed.
The marginal utility function is the base for determining each Consumer Trader bids. The algorithm is based on the basics of the customer preferences theory [7]. The price, traders are willing to pay for an additional unit of the commodity Q equals to the MU calculated for Q + 1. The price, which needs to be paid to buy the last commodity unit from a trader equals at least to MU calculated for Q.
An agent places sell bids for all the commodity units he possesses^[3] and at the same time he places buy bids until he reaches his budget limits^[4]. The process is demonstrated in Example 1, “Customer Trader 1 Bidding”.

Example 1. Customer Trader 1 Bidding

Imagine a Consumer Trader with marginal utility function MU = - 2 . Q + 35 and a budget of 100 currency units and 5 commodity units on stock. See the trader's bids he is placing in the current round in Table 1, “Trader 1 Buy Bids” and Table 2, “Trader 1 Sell Bids”.

Figure 1. Marginal Utility Function for Trader 1

Trader 1 Buy Bids

Buy Bid	1	2	3	4	5
Price	23	21	19	17	15^[a]
^[a]The next bid (number 6) would exceed the available budget.

Trader 1 Sell Bids

Sell Bid	1	2	3	4	5
Price	25	27	29	31	33

Price Evaluation

After each trader places his bids, the sell bids are ordered ascending and buy bids descending based on the bid price. Such value series are basically a discontinuous demand and supply function.
The algorithm for determining the equilibrium price is simple. It iterates both series until the sell price gets above the buy price for a certain amount of bids. Because the function is discontinuous, the price is determined as if the function were continuous at their intersection.
This price is used to clear the market satisfying all the bidders who sell above the price and who buy under it.

Example 2. Price Evaluation

Beside Trader 1 shown in Example 1, “Customer Trader 1 Bidding” imagine there is another trader (Trader 2) on the market. His marginal utility function is different MU = - 8 . Q + 58, he has a budget of 175 currency units and 2 commodity units.

Figure 2. Marginal Utility Function of Traders 1 (blue) and Trader 2 (green)

Trader 2 Buy Bids

Buy Bid	1	2	3	4	5	6
Price	42	34	26	18	10	2^[a]
^[a]This is the last possible bid with a positive price.

Trader 2 Sell Bids

Sell Bid	1	2
Price	42	50

Demand for Both Traders

Trader	2	2	2	1	1	1	2	1	1	2	2
Quantity	1	2	3	4	5	6	7	8	9	10	11
Price	42	34	26	23	21	19	18	17	15	10	2

Supply for Both Traders

Trader	1	1	1	1	2	2
Quantity	1	2	3	4	5	6
Price	25	27	29	33	42	50

Figure 3. Resulting Demand and Supply "Curve"

The price is determined as the intersection point if we consider the demand and supply series as continuous curves. In Figure 3, “Resulting Demand and Supply "Curve"” the join line for point A and B is a function P = 2 . Q + 23 and for C and D it is P = -8 . x + 50. The intersection happens for P = 28.4 which is rounded to P = 28.
To conclude, in this round traders will exchange two commodity units, both for 28 currency units. Trader 2 will buy 2 units from Trader 1. This will decrease his budget and increase the budget of the other trader by 56. His commodity pool will contain 4 units and the pool of Trader 1 will decrease to 2 units.
The total utility TU of Trader 2 will increase by 20, which is the difference between the utility brought by the two additional units and the price he paid for them. The utility gain of Trader 1 may be calculated in a similar manner. The utility gains are in fact equivalents to the supplier and consumer surplus.

Visualization

After inventing a good simplification of the reality for the simulation model, visualization is probably the second most important feature of the simulation. Simulation data need to be properly visualized in order to provide the observer with relevant feedback.
Omitting some important aspect of the simulation by not visualizing it means threat of misinterpretation of the outputs. On the other hand, we need a suitable level of aggregation. As an example consider we would be displaying all states of all agents in every round, this would produce huge amount of data very difficult to be analyzed.
Choosing the right properties and the right level of aggregation is crucial for the simulation success. The simulation application implemented by the author of this paper uses mostly visual charts — the line chart and the bar chart — for visualization of aggregated data.
The visual elements of the commodity market simulation are described in the following sections.

The Utility Gain Chart

The utility chart displays the increase in the overall utility of all participating traders after the trade transactions are processed. The utility increase depends mostly on the random distribution of harvest each turn. The more inappropriate (in terms of marginal utility functions of the individual traders) it the harvest distributed between traders before trading each round the bigger is the potential utility increase.
This chart is not crucial for understanding the processes in the market. It is more a debugging tool. For example if this chart shows negative numbers, it is an obvious sign that there is a significant problem in the model implementation, as this situation may not occur under normal conditions. On the other hand it may be used as a means of how efficient is the market in fulfilling one of it's essential goals, increasing the utility of participants.
The Y axis shows utility increase due to the current trading round and X shows time (the trading round).

Figure 4. Total Utility Increase for All Traders

The Price Chart

The price chart is the most important chart in the visualization layer. It shows the development of price in each trading round (see the section called “Price Evaluation” for details about how is this price determined).
Current price on the Y axis is displayed for each trading round on X.

Figure 5. Price Development in Time

The Harvest Chart

Harvest directly influences price. The importance of this chart is to show how is price correlated with the level of current total harvest. Some trading strategies may significantly influence price evaluation so that the price development becomes very much independent on current harvest level.
The quantity on the Y axis show total harvest assigned to all traders (farmers) and the X axis means rounds.

Figure 6. The Total Harvest Chart

Demand and Supply Curve

For each round the visualization layer draws the demand and supply curves. Construction of those curves has been discussed in the section called “Price Evaluation”. This chart has an overlap which the price development chart, but it shows only the current round price without capturing the development. It is more useful to see how healthy the market is, how is the ability of the supply to meet demand and also what quantity of transaction has been traded in the market in each step.
Different trader strategies influence significantly the shape of the demand and supply curves as discussed further.
The chart shows quantity on the X axis and price on Y.

Figure 7. Demand and Supply

Commodity Distribution Chart

This chart show distribution of the commodity before and after the trade round takes place. The usual pattern shows a more equal distribution which is turned into less equally distributed commodity. The random assignment of harvest is turned into a state where commodity is concentrated in hands of those traders who have more utility from each unit.
The chart displays the amount of commodity on the X axis and the amount of traders who own exactly this amount of commodity on Y. It is basically a distribution function. It shows how gets the commodity redistributed after each trading round and whether there is some long-term development in the curve shape.

Figure 8. Commodity Distribution

Budget Distribution

The budget distribution shows where is the budget mostly concentrated. It is divided per trader type. It shows which trader strategy is more successful in concentrating budget. The depicted chart is highly aggregated. It shows the number of traders for each type who holds only units, tens, hundreds, thousands and more of currency units.

Figure 9. Budget Distribution

Computerized trading

Computerized trading is becoming more and more popular. Some of the markets today are already mostly computer driven and trading resembles a fight between algorithms. Algorithms may try to predict what effect do algorithms of others have on the market and thus using this information to better react on the development to generate bigger profit .
Computerized trading may introduce potential risks into the commodity market environment. It raises questions as for example: “What happens when most of the traders start to use computerized algorithms to trade on the market?” “Is the market still about demand and supply or is it becoming more a virtual environment which has just little to do with the commodity itself?”
Another aim of this paper is to study what happens if we introduce computerized traders into the reference model — an environment where so far only farmers with different consumer preferences traded.
Constant price fluctuations enable automatic profit generation. One of the simplest models for automatic trading is the channel breakout [3] [4] [5]. This trading strategy basically means buying at n-day minimum and selling at n-day maximum.
In fact this model has many modifications and extensions, but the simplified approach above is easy to implemented into the commodity market simulation environment.

Computer Traders

To simulate effects of computerized trading on the commodity market a Computer Trader agent has been introduced into the simulation environment.
The bidding strategy of the Computer Trader is completely different than for the Consumer Trader explained in the section called “The Reference Model”. Computer Traders observe the market and keep track of the maximum and minimum price for a certain number of rounds. Each round they generate buy bids for the minimum price and sell bids for the maximum. Sell bids are constrained by the available commodity units owned by the particular trader and buy bids are limited by the traders budget.
To enforce simulation heterogeneity Computer Traders as well as Consumer Traders have parameters which are set randomly within specified boundaries before simulation rounds start. One of the parameters is budget^[5] and the other is number of rounds traders observe the market price to establish the minimum and maximum price used for their bidding.

Example 3. Computer trader bids

Imagine a Computer Trader with budget of 100 currency units and 5 commodity units on stock. He observers the market price for 10 rounds and the maximum price in that period was 15 and minimum was 10. This particular agent places 5 sell bids for 15 and 10 buy bids for 10.
Bidding heterogeneity is encouraged with the number of rounds different traders observe the market which may cause different maximum and minimum prices for each trader. Imagine another trader who observers the market only for 5 rounds his maximum and minimum would be somewhere between 10 and 15. This means, Computer Trader supply will never meet another Computer trader demand. They will only be involved in transactions with Consumer Traders.

The Reference Setup

First we observe the market behaviour when only the Consumer Traders are involved. Table 7, “Reference Simulation Setup” shows the parameter setting.

Reference Simulation Setup

Simulation	The Reference Setup
Rounds	1000
Budget	1000 – 10000
Harvest	1 – 5, 10 – 40
Consumer Traders
Number	30
P1	1 – 10
P2	50 – 200

In the reference setup we observe significant price culminations, but it is basically a random walk around a central value, see Figure 10, “One Run of the Reference Setup” . This may be easily proven. When setting a fixed amount of harvest each turn for each trader, price gets settled on a certain number without any culminations as shown in Figure 11, “Price Development with Stable Harvest” .

Figure 10. One Run of the Reference Setup

The reference simulation has been run for 20 times to avoid random fluctuation. In all runs, the price starts at a quite high level (more than 25) and slowly declines each round. The closing price after 1000 rounds was in the space of 8 to 12 for the 20 runs.
The price decline is caused by the random conditions at the beginning of the simulation. During each run budged is iteratively transferred from traders who relatively prefer commodity over money to traders with reverse preferences. Every round new commodity is harvested and divided between traders. The demand and supply curve and the amount traded depends how is the commodity distributed within those two distinct groups.
This is demonstrated on the budget distribution chart where most of the traders are within the 10^3 bar (they are having thousands of currency units) when the simulation starts and as the simulation proceeds a less equal distribution is formed. Most traders are either having little budgets or on the contrary huge budgets, see Figure 10, “One Run of the Reference Setup” . The middle class slowly disappears.

Figure 11. Price Development with Stable Harvest

Adding Computerized Traders

Now we are ready to simulate Computer Trader agents' influence on the reference market model described in the section called “The Reference Setup”.

Computerized Trader Market Setup

Simulation	Computer Trader Market Setup
Rounds	1000
Budget	1000 – 10000
Harvest	1 – 5, 10 – 40
Consumer Traders
Number	30
P1	1 – 10
P2	50 – 200
Computer Traders
Number	30
Round Observed	5 – 30
Start Trading	after round 150

In this simulation setup, we add another 30 Computer Trader agents. They keep track of the market price for 5 - 30 rounds to determine the maximum and minimum price of their bids. Traders start trading after 150 rounds when market gets more stable.
Again the simulation has been run 20 times with this setup to avoid random fluctuation to see if some patterns of behaviour will proof to be stable.

Figure 12. Market Simulation Run with Computer Traders

In Figure 12, “Market Simulation Run with Computer Traders” you see a snapshot of one of the runs. It clearly demonstrates the effect of Computer Trader presence in the simulation on the price development which is significant. First the price development shows the same pattern as in the reference simulation. After round 150 Computer Trader agents start trading. The price development gets immediately affected. Its oscillation weakens each round until it gets nearly stable -/+ 1 currency unit.
Even harvest has the same characteristics as in the reference simulation, price is no more affected by the current harvest level. The presence of the new agent strategy in the market did stabilize price and made it less dependent on harvest development.
The rationale lies in the way Computer Traders react on the price development. When price is rising due to a lower total harvest level and it starts reaching agent's n-round maximum they react by selling their stock commodities. This brings more commodity to the market causing price to fall. Analogically, higher harvest causing the price to fall reaching agents' minimum price makes agents buy and thus turning the fall into growth again.
Constraining price fluctuations over time causes the n-round maximum and minimum to shrink. This makes the agents buy and sell earlier when price fluctuates and thus shrinking the price oscillation more and more until is gets bounded on a certain price.
Computer Trader strategy is definitely a profitable one in the reference market model. As price fluctuates the agent budget increases. But less oscillations over time means less profit for the traders.
The demand and supply curve shape is affected as well. In Figure 12, “Market Simulation Run with Computer Traders” you see large horizontal segments of the demand and supply curve. They correspond to the n-round maximum (supply) and minimum (demand) prices the agents did establish. This horizontal segments start to emerge after the 150^th round. First there is a significant gap between both curves but it shrinks with each round as the agents' n-round maximum comes closer to the minimum.
The average price after 1000 rounds measured in 20 runs tend to end between 10-11 currency units which is basically the same as in the reference simulation runs. This means, the average price was not affected by the new type of trader introduced to the market but standard deviation got significantly lower.
To conclude, computerized traders did not cause any significant market failures. In fact they did stabilize the market, making price less dependent on the exogenous harvest factor.

Market Failures

One of the popular aims of automated market simulations is to simulate different market failures. For example [2] simulates market price bubbles using near zero-intelligent agents.
Market bubbles do not occur with rational traders. From various studies [1] [2] it seams bubbles are related to some kind of cognitive failures of traders. Zero-intelligent agents are basically traders who act nearly randomly. It simulates real life traders with minimum background knowledge who do not act rationally and their behaviour resembles random decisions.
This paper focuses on another frequently mentioned reason for market bubbles which is groupthink and herd behavior. Yet another trading strategy has been introduced into the simulation described in this paper — the Trend Trader.

Trend Trader

In contrast to zero-intelligent agents, the Trend Trader agent is a representative of a trading strategy which actually makes sense in some situations. This type of agent expects the market to follow certain stable trends. In case price is a random walk this trader is going to loose money over time. But in case there is a significant trend factor in the price development, this trader may be involved in profitable transactions.
The Trend Trader keeps a history of prices and calculates a trend out of it. According to the trend he predicts the price in the following round. In case the trend is positive the agent places buy bids on the market as he expects the trend to continue. In case trend is negative the agent sells.
This strategy is closely related to groupthink or herd behaviour as agents simply expect others to behave similarly which will cause the trend to continue. In case there is a positive price trend the prospects are positive and everyone is buying, the agent predicts the price to continue to rise. He is buying, as he expects he can sell for even more later. As soon as the trend changes, the agent expects the market just passed a peak and he starts selling while price is still high.
Analogically to Computer Traders, Trend Traders observe market price for a certain period (one of the parameters) and each turn they calculate trend out of the recent price history. Expected price P_e is calculated as an the current price P and the n-round trend T_n.

Equation 1.

P_e = T_n + P

Trend T_n is calculated as average ΔP for rounds r - n .. r - 1, where r is the current round number^[6].

Equation 1.

T_n = ( ∑_{i ∈ { r - n + 1 .. r -1 }} ΔP_i ) . ¹/_{n - 1}

Example 4. Trend Trader Bidding

Image a Trend Trader who observers the price market for n = 6 rounds. He has a budget of 150 currency units and 5 commodity units on stock.

Observed Price History

Round `r`	200	201	202	203	204	205	206
Price `P`	20	25	34	36	30	40	-
`ΔP`	-	5	9	2	-6	10	-
Trend	20	24	28	32	36	40	44
ΔTrend		4	4	4	4	4	4

T_n = 20 / 5 = 4, expected price in round 206 is 44 currency units. Trend is positive, the trader expects price to increase and thus he is buying.

Trend Trader's Demand

Quantity	1	2	3
Price	44	44	44

Consumer and Trend Traders

In the next simulation series we place Consumer Traders together with Trend Traders in the commodity market.

Trend Traders with Consumer Traders Simulation Setup

Simulation	Trend and Consumer Trader Setup
Rounds	1000
Budget	1000 – 10000
Harvest	1 – 5, 10 – 40
Consumer Traders
Number	30
P1	1 – 10
P2	50 – 200
Trend Traders
Number	30
Round Observed	5 – 30
Start Trading	after round 150

As discussed earlier, price development in the solely Consumer Trader market is basically a random walk correlated with harvest which is a random function. There are no trends for a purely random variable, there is just noise. This causes Trend Traders to mistakenly recognize trends where there are non.
As a result Trend Traders really cause short-term bubbles to occur on the market, but they are incrementally loosing money on them. As their budget decreases, their ability to place bids lowers until the market starts behaving as if no other agents than Consumer Traders where present on the market.
Figure 13, “Simulation Run with Consumer and Trend Traders” demonstrates the behaviour explained above on a simulation snapshot. Even harvest is a random walk, price development depicts significant bubbles. The price starts dramatically rising reaching its peak in circa 20 - 30 rounds. Than it falls straight down again in less than 10 rounds. The budget distribution chart already shows Trend Traders starting to loose their budgets. The most frequent category has only 10s of currency units so they are unable to influence the market significantly.
As Trend Traders loose money, bubbles tend to weaken until finally the price returns into a random walk correlated only with the harvest. The supply curve shape is significantly influenced by the agent behavior. As trend is currently negative in the snapshot, most Trend Traders bid to sell for a similar quite low price.

Figure 13. Simulation Run with Consumer and Trend Traders

During the upward trend agents start buying and thus reversely the demand curve shape is affected showing a large horizontal segment as seen in Figure 14, “Upward Trend”. In the same figure we see how is price development turned from a random walk into bubbles as soon as Trend Traders start to trade (after round 150).

Figure 14. Upward Trend

Figure 15, “Back to Random Walk” depicts how is the “bubbled” price development incrementally turned back to random noise. The budget distribution chart shows the majority of Trend Traders having just 10s of currency units so they do not affect price evaluation anymore.
The presence of Trend Traders affects average price during simulation runs. Even finally average price in 20 runs turns to be 12 which is similar to the previous setups, it is probably because of the relatively short period Trend Traders have to affect the market. During the time Trend Traders are active on the market, average price gets up to 30 currency units.

Figure 15. Back to Random Walk

All Trader Types Together

The highpoint of this paper is the following setup where all trader types are put together into the same simulation environment.

Simulation Setup with All Agent Types

Simulation	Consumer, Computer and Trend Traders
Rounds	1000
Budget	1000 – 10000
Harvest	1 – 5, 10 – 40
Consumer Traders
Number	30
P1	1 – 10
P2	50 – 200
Computer Traders
Number	30
Round Observed	5 – 30
Trend Traders
Number	30
Round Observed	5 – 30

With all three trader types involved the simulation becomes complex and difficult to interpret. Testing experiences have shown with all trader types together even a very little change in the behaviour of one trader could be multiplied in combination with some features of other agent types causing unpredicted results.
Figure 16, “Simulation Run Snapshot — All Traders” depicts one of simulation run snapshots. The price development shows very interesting patterns. Price is extremely unstable in a longer run but showing segments of stability for shorter time periods. It seems as if Computer Traders would compete with Trend Traders over who is causes the major influence on price and some developments are more favourable to either the first or the second group.
An important discovery conducted from this simulation setup is: Trend Traders actually become profitable if accompanied with Computer Traders on the market. The budget distribution chart shows many Trend Traders still with budget of 1000s currency units even the round did already pass 450. This is a stable phenomenon observer in many different runs with this setup.
The cause may likely be explained by the Computer Trader's effect on price reducing random walk which is harmful for Trend Traders. Shifts between periods where price is mostly influence by one or the other trader group may be explained by budget fluctuations between trader groups.
Imagine Trend Traders rule the market and a steep price increase has just begun. More and more traders start to realize a positive trend and they buy causing the price to rise even more. After a while Trend Traders consume most of their budget for commodity, less buy bids are issued and price increase starts to slow down. This continues until the peak is met and Trend Traders loose their ability to cause further increase.

Figure 16. Simulation Run Snapshot — All Traders

At this time, price reaches ridiculous proportions with no relation to harvest which is the only price maker in the reference model. As a result, price starts to fall down quickly to it reference model natural average around the value of 10. Trend Traders who first notice the trend^[7] shift have opportunity to earn as they start selling at high prices, others will loose because of the bubble. At this point Trend Traders start to cumulate budget again and they are accelerating the price fall.
Bubbles are less advantageous for Computer Traders who benefit especially in the random walk environment. They were selling to the Trend Traders during the price increase in the first phase of the bubble. Now when price decreases they wait until it reaches their n-round minimum. Those with higher n are better off as they start buying later for less. The Computer Trader's behaviour is likely responsible for the stair-like effect during the price fall phase.
As price falls more and more, traders reach their minimums and they start buying. They cumulated budget during the rise phase so they are strong enough to stop the fall for few rounds. This creates the distinctive horizontal segments in the price curve.
It is important to note that the partial explanations above are only speculations. There is no evidence that the price development was really significantly influenced by the mentioned causes. The simulation already reached the point where it mostly resembles a black box and deeper understanding of the model would require better diagnostic tools and much deeper insight.
In 20 runs the average price during this simulation setup was stable around 18 currency units which is nearly the double of the average price measured in the reference model.
Different price bubbles are very frequent during this simulation setup as demonstrated by Figure 17, “Captured Price Bubble Gallery”. They basically appear constantly during the whole run. No trader groups tends to get out of budget during simulations.

Figure 17. Captured Price Bubble Gallery^[8]

Conclusion

This paper demonstrates how to build an automated simulation environment from scratch and how to simulate complex real life patterns which are very difficult to be studied analytically.
Complexity has been introduced iteratively. First, each trader strategy has been studied separately causing predictable and clearly explainable results. After all three very simple trader strategies described in this paper were put together into the same simulation setup, very complex patterns emerged.
This demonstrates a synergic effect known from the system theory. Adding few simple elements into the system influencing each other is causing complex results which are difficult to predict or analyze.
There are also other consequences of the observed simulation runs. The commodity market has it's moral dimension as availability of the commodities traded on the market are essential for people's basic survival. Different simulation setups allowed as to study the influence of different trading strategies on the reference model which is composed solely of traders who are in fact also consumers of the commodity.
This paper has shown that some trading strategies may be neutral or even beneficial for the consumers, but other may cause unpredictable developments and price bubbles which are very dangerous especially on the commodity market for reasons mentioned in the section called “Commodity Market”.
Simulation involving the computerized traders made the market less vulnerable to seasonal influences^[9], which was beneficial to consumers as it gave them a stable environment with price less dependent on random factors. At the same time, the long term average price was nearly the same as in the reference model.
On the other hand, the final simulation setup with all three trader types involved has shown an hostile environment for the consumers. Trend Traders cause price bubble which increases price for regular consumers up to 700% during peaks and Computer Traders preserve them so bubbles last longer. Bubbles even longer than 100 rounds has been observed during different simulation runs.
The average price during the 1000 simulation rounds has shown to be double of the average price in the reference model.

A. Implementation

The simulation environment described in the previous sections has been implemented from scratch by the author of this paper. No simulation framework has been used. The whole system has rather been implemented specifically in Java programming language using a specific object model, see Figure A.1, “The Simulation High-level Object Model”.
JFreeChart library for rendering different chart types has been used for the visualization layer which is basically a Swing application.
The main Simulation class is the place where to setup different parameters of the simulation run. Each round is calculated in Market which holds collections of traders. Buy and sell Bids are collected for each trader, ordered ascending and descending to form the demand and supply series. After equilibrium price is determined the market is cleared and transactions between traders are processed.
Each round during calculation the Market notifies all registered IMarketListeners about development in commodity, budget, price, demand, supply and utility. There is just one implemented listener which is the Dashboard. It is a Swing JFrame and it contains all the charts described in the section called “Visualization”. Some charts are updated before the round starts^[10] and all are updated after the round finishes.
Any trader who implements the ITrader interface may be easily plugged to participate in the simulation. If the trader extends the AbstractTrader class, it only needs to implement the following methods: getBuyBids(), getSellBids(), priceUpdate(), consumeCommodity(). The different trading strategies (Consumer Trader, Trend Trader and Computer Trader) differ only in the implementation of those 4 methods.
The abstract class executes all the functionality the agents have in common, for example updating the commodity variable in can agents did buy some or updating the budget in case transactions are made etc...

Figure A.1. The Simulation High-level Object Model

To demonstrate how easy it is to bring a new trader into the simulation, lets assume we intend to introduce a Random Trader who acts randomly ignoring price signals from the market. Example A.1, “Random Trader Implementation” shows the implementation code^[11].

Example A.1. Random Trader Implementation

public class RandomTrader extends AbstractTrader {

    public RandomTrader(long budget, long commodity) {
        this.budget = budget;
        this.commodity = commodity;
    }

    public Collection<IBid> getBuyingBids() {
        Collection<IBid> bids = new ArrayList<IBid>();
        long totalPriceBid = 0;
        while (totalPriceBid < budget) {
            long bidPrice = getRandomPrice();
            totalPriceBid = totalPriceBid + bidPrice;
            bids.add(new Bid(this, bidPrice));
        }
        return bids;
    }

    public Collection<IBid> getSellingBids() {
        Collection<IBid> bids = new ArrayList<IBid>();
        for (int i = 0; i < commodity; i++) {
            bids.add(new Bid(this, getRandomPrice()));
        }
        return bids;
    }


    public void priceInfo(long price) {
        // ignore
    }

    public void consumeAll() {
        //ignore
    }

}

Bibliography

[1] Gil-bazo, J., Moreno, D., Tapia, M.:Price dynamics, informational efficiency, and wealth distribution in continuous double-auction markets. Universidad Carlos III. Spain. 2007.

[2] Duffy, J., Unver, U.:Asset price bubbles and crashes with near-zero-intelligence traders. Economic Theory Journal. Berlin. 2005. ISSN 0938-2259

[3] Brooks, A.:Trading techniques. Futures. Chicago. 2009.

[4] Mayers, D.:Applying The Noise Channel System to IBM 5min Bars. Futures. Chicago. 2001. URL: http://www.meyersanalytics.com/papers.php

[5] Katz, J., McCormick, D.:Encyclopedia of Trading Strategies. McGraw-Hill. 2000. ISBN: 00-70580-99-5

[6] Mach, M.:Macroekonomie pro Inženýrské studium. Melandrium. 1998. ISBN: 80-86175-03-0, 80-86175-04-9

[7] Soukupová, J., Hořejší., B., Macáková., L., Soukup, J.:Microekonomie. Management Press. 2005. ISBN: 80-7261-061-9, 80-86175-04-9

^[1]Raw agricultural commodities traded on the commodity markets include corn, oats, rough rice, soybeans, soybean meal, soybean oil. wheat, cocoa, coffee, cotton, sugar.

^[2]The average value is ( min + max / 2 ) multiplied by the number of farmers involved.

^[3]Obviously each unit is bid for a different sell price. With a diminishing marginal utility function, the last unit is the cheapest and every previous unit is offered for more. Similarly when buying units, one unit would be bought for less than the next unit.

^[4]Another obvious limit for bids: price needs to stay positive.

^[5]This is the very same budget parameter used to setup initial budgets for Consumer Traders.

^[6]Of course more sophisticated statistical methods may be used as for example regression or interpolation but this simple method does its job just fine for the simulation objectives.

^[7]Depends on the n in their n-round price observing parameter.

^[8]Note the Prague Castle-like shape of many of the simulated price bubbles.

^[9]They did smoothen the harvest fluctuation and their effect on price.

^[10]For example the commodity distribution chart shows distribution before trading starts (after harvest) and how did the distribution change because of trading.

^[11]To simplify the code, the getRandomPrice() method has not been implemented in the example.

Critical analysis of MMDIS concepts

2010-05-27T11:18:00.001-07:00

Comparing Agile with MMDIS Approaches to Information System Development

Petr Nálevka

University of Economics, Prague Department of Information and Knowledge Engineering ̶ Knowledge Engineering Group

          W. Churchill Sq. 4
          130 67 Praha 3
          Czech Republic
          petr@nalevka.com

Abstract

This paper analyses the Multidimensional Management and Development of Information Systems (MMDIS) methodology contribution to information system development in the context of other commonly used methodologies, especially methodologies which are commonly referred to as Agile.
The aim is to find out what are their similarities and where do those approaches differ especially with respect to software development. The author's aim is further to highlight possible risks and weak points of the MMDIS methodology based on study of articles by prestigious international software engineering authorities and based on authors own over 10 years experiences with real life software projects.

Table of Contents

Introduction

Agile Methodologies

MMDIS

Dimensions
The User Perspective
Implementation dimensions

Main principles

From development to management

Conclusion

Bibliography

Introduction

From the very beginning of Information Technologies as a field, people are facing ongoing failures of the developed software to satisfy original requirements. Projects are getting late, over budget and meet only a small portion of the requirements or in the worse case they are not suitable for the tasks intended at all.
As a result, experts started to impose all sort of very detailed step-by-step development processes to better manage risks of the software projects. Those processes are commonly known as methodologies.
First methodologies in 70s and 80s were inspired by processes taking place in other industries. The production line [AL], a highly effective and manageable manufacturing model, has become inspiration for IT.
Methodologies derived from the production line model break software development into a series of stages where each stage is dependent on the output of the previous one. A typical example is the Waterfall technique first published in 1970 [WF]^[1]. The aim is to lower risk by putting every single stage of the project under tight control and define and plan the whole progress in advanced. That's why such methodologies are commonly referred to as plan-driven^[2].
Unfortunately, soon, plan-driven approach to software development has shown it's drawbacks when applied in IT. Software projects are in their very nature unpredictable. No fixed plan may be created for them in the first place.
Plan-driven methodologies assume requirements for a particular project may be set in stone in advance, but this has shown as not being satisfied in IT. Developed software could not adapt to the ever-changing business reality and in many cases became outdated already at the release date. Moreover, applying a pre-planned process in a field where creativity and ideas are so important made developers become frustrated and less productive.
Object oriented methodologies brought a breath of fresh air into the field in the 90s. They allow better mapping between real world entities and modelled entities in the information system. They do better reflect the fact that the business domain is changing very quickly and the developed software needs constantly adapt to the reality.
OO methodologies were mainly based around UML modelling techniques. See [OOM] for a comprehensive analysis of different OO methodologies.
The object oriented approach allows (if well designed) to encapsulate peaces of functionality in separate components, so that changes in one component do not necessarily impose changes in other components^[3]. Also objects allow to define extensibility points for easier change management.
Even the object oriented approach brought more flexibility into the field and maybe even saved the industry from a massive failure, experiences has shown, that it still does not save software projects from missed deadlines and requirements.
It seems as if the problem with object oriented methodologies is they tent to be too focused on the design itself^[4]. The main thread is, creating a perfect design may become more important for developers and architects than delivering actual value for the customer.

Agile Methodologies

Recent methodologies are heading to overcome some of the above mentioned issues. Such methodologies are commonly called agile^[5] to express that they are intended to respond quickly to the ever changing needs and that they are in the very nature designed for flexibility.
Doing agile development means thinking agile. It requires a complete shift in the way we think about software development. Rather than searching for analogies in other industries, agile methodologies propose to approach software development uniquely as it is really a unique human activity [MF]. They learn their lessons directly from real world successful or failing IT projects.
Although agile methodologies are the latest evolution in how we approach software development, they don't automatically mean better results, see [APM]. Even they had addressed many limitations of their predecessors (the plan-driven methodologies) they do not guarantee success. They do shift a lot of responsibility from rigid rules to the actual people involved in the project. This inevitably means the project outcome highly depends on the quality of the people involved.
No methodology can ever replace highly qualified experts. It can only help the experts not to be burdened too much with unnecessary bureaucracy, rigid processes and purely political decisions [AL].
To quickly summarize the main message of the agile methodologies, we can use the four values of the agile manifesto [AM]^[6].

Agile Manifesto

Individuals and interactions over processes and tools
Working software over comprehensive documentation
Customer collaboration over contract negotiation
Responding to change over following a plan

MMDIS

The MMDIS methodology which is maintained at the University of Economics has been introduced in 1992 [MMDIS1]. It differs from the production line methodologies as it does not insist on a strict order of detailed steps. It rather is a proposed way of thinking about the software project. It defines each steps of the project life cycle in several dimensions but rather that explicitly describing what needs to be done in each step, it proposes several topics to think about at each step^[7][MMDIS1].
Since 1992 MMDIS evolved from a methodology which primary focus is on software development to a methodology which tries to cover overall IS/ICT performance management [MMDIS2]. Although its scope is much larger, in this paper the author will focus primarily on aspects related to software development and especially on the traditional custom software development model ignoring some of the latest currents in the field as for example outsourcing, SaaS or parametrized generic purpose software bundles. For more information on those topics, please see [MMDIS2].
Even new software distribution method appeared and become popular recently, software development and its quality is still very important. Whatever distribution approach is used to deliver software to its users whether it is SaaS or any other approach the delivered software had to be developed using some software development methodology. Eligibility of the selected methodology is crucial for the software quality and influences essential parameters as for example flexibility which determines how easy it is to accommodate the developed software to the ever changing business reality.
Even different distribution methods do not lower the importance of software development methodologies, they do shift their target audience. In the era when custom software development was predominant on the market, development methodologies where important also for the larger enterprises who did frequent self-made software customizations in their IT departments [MMDIS2].
New trends as for example outsourcing made companies focus more on their core businesses and thus software development methodologies are more targeted on those companies whose core business is related to software development.

Dimensions

The main principle of MMDIS as a software development methodology is multidimensionality. Multidimensionality means seeing the IT project from all views relevant to it's efficiency. MMDIS distinguishes two main groups of dimensions.

First group of dimensions

level of abstraction
the time dimension
level of IS/IT integration
Integration of
- visions
- outside environment
- business processes
- technology

Second group of dimensions

information and data (inf)
processes and functions (pro)
economic and financial (eco)
organizational and legislative (org)
labour, social and ethical (lab)
software (sw)
hardware (hw)
methodical (met)
document (doc)
management (mng)

The second level of dimension demonstrates one of the interesting characteristics of MMDIS. Technology (sw, hw) is just one of many other dimensions. MMDIS scope is much larger than only technology, it focuses on all aspects of the entire company to integrate them well with the technology.
This is in contrast to some agile methodologies which focus mainly on the technology and how to encourage IT people to be more productive^[8].
Also when compared to other methodologies MMDIS sees the software projects from the perspective of the company which actually needs the software — from the customer perspective, rather than from the perspective of an IT consultancy or a software house which is doing the implementation. The second is probably a more common point of view in software methodologies as it corresponds to a common model in the software market where software development is being outsourced [VOR3].
The multidimensional approach shows the IT project is it's whole complexity. There are several very different dimensions which all influence the success of a IS/IT project and they even influence each other.
Note that dimensions are not a rigid enumeration. [MMDIS2] views multidimensionality rather as a generic problem solving principle where each dimension is solved first separately and later the separate solutions are integrated into the overall solution.

The User Perspective

MMDIS emphasises the difference between the user and the implementation perspective. During the implementation process the user perspective gets transformed into the implementation perspective. This transformation helps not only to implement user requirements but it also allows to validate the requirements in terms of feasibility and consistency between all the implementation dimensions.
In terms of software development methodologies, gathering requirements and transforming them into a software project is the crucial and one of the most tricky tasks. To meet the prime objective of the agile methodologies — to satisfy the customer, it is important to understand his needs. This is difficult as in most cases even the customer/user does not know what he needs or he is unable to express it in words understandable to someone who is not heavily involved in the customer's domain.
It seems the process of transforming the user requirements to implementation perspective is in many cases accountable for project failures . Agile methodologies do not give detailed guidance in this case. They rather leave it to interpersonal communication. They emphasis the importance of the adaptive customer [MF] on side and constant feedback on iteratively added features.
MMDIS on the other hand bets on a precise project plan which is validated against the high-level strategic goals of the company, the overall IT concept, which has to be consistent across all the dimensions and in all stages of the project life-cycle and which is shaped by the company management, partners, customers as well as by individual users^[9]. Before implementation takes place, the whole complex space of requirements is transformed into the feasibility study document and into detailed conceptual design.

Management

One of the most important user perspectives in MMDIS is the management perspective. MMDIS is explicit about the role of management in terms of constraining time and financial budget and defining the target business processes which shall be supported by ICT. As nobody else is eligible to do this kind of decisions, management user perspective has the highest priority and it is very important to clearly understand aims of the management.
An important aspect is involvement of management in the whole implementation process. Without management involvement the project would soon end lacking decisive power.
Agile methodologies especially highlight the fact that gathering the requirements from the management user perspective is not a one time activity. This is something which needs to be evaluated constantly and management needs to be constantly confronted with the current progress of the system^[10] . If management is not able to make the needed decisions on-time, delegation of power is highly required. It is especially important to have an eligible customer representative on side with a sufficient level of decisive power [XP] [SCRM].
One of the models for transforming customer requirements is the quite common fixed price contract where requirements are specified in the beginning of the project and price bids are accepted [MF]. This model seems very much vulnerable to failure but it is also the model which seems as a natural choice for MMDIS, as it emphasises the role of the feasibility study and gives the management the obligation to set not only requirements, but also to allocate resources and financing.
This model may be sufficient for the production line industries, but not for software development which (as we already stated) has a highly unpredictable process^[11].
In today turbulent markets it is very likely that the requirements change significantly before the end of the project. Also some requirements become obvious not sooner than during the project implementation. That's why the agile approach rather recommends an iterative approach where in each short-time stages management may evaluate the progress and change direction of further development (including changes in time and resources allocation). This is in contrast to fixed price contract and it requires both an adaptive customer [MF] as well as an adaptive IT supplier.
Although requirements are high, there is a chance that the project will end in a satisfactory manner for both parties, in contrast to the fixed price contract where both parties usually end as losers [MF].
The MMDIS methodology emphasises how important it is to understand the management aims, but it is not very verbose on how to do that. Also it does not stress what agile methodologies are stressing very intensively, that understanding the aims in an on going process which involves constant reevaluation during the whole project progress.

The end-user

In MMDIS the end-user is a source of valuable very detailed (in comparison to the management user perspective) information. As they expect the IS to support their every day activities, the implementation experts are encouraged to gather all sort of important knowledge from the end-users.

End-user knowledge [MMDIS1]

processes on the particular user level
who is responsible for a particular stage in the process or for the process as a whole
what activities are candidates to automation
what data needs to be collected and persisted

The agile methodologies add one more role (but a crucial one) to the end-user. The end user is a valuable source of evaluation whether the current prototype is of any customer value to the particular users. The end-user is seen as a first class tester of the system and implemented features are consulted on a regular bases with the involved users.

Implementation dimensions

the section called “MMDIS” describes two different groups of MMDIS dimensions which are relevant from the implementation point of view. The first group of dimensions defines characteristic phases of implementation.

By separating implementation into phases MMDIS aims to [MMDIS1]

separate work into projects for better planning and management
allow some form of incremental development or prototyping
divide tasks based on the level of abstraction to be solved by different experts
ensure compliance with the high level strategic aims of the enterprise

The main phases [MMDIS1]^[12]

Feasibility study
Global analysis
Detailed analysis
Implementation
Installation
Production and maintenance

Incremental development

The most important statement from the agile point of view is the MMDIS's emphasise on prototyping and incremental development. But in the same time MMDIS introduces very detailed and sequential phasing of the project's life-cycle. Phases may be misleading as people may immediately thing about phases as sequentially executed steps where the next step may be executed only after satisfying all the prerequisites of the previous step.
Because another significant source of IT project failures is misinterpretation of methodologies [AL], it is important that methodologies state clearly their intentions to forgo such misinterpretations. This is a double-edged issue, as making the methodologies too explanatory makes them on the other hand too rigid and less applicable on different projects.
Because of the danger of misinterpreting phases as being something fixed, agile approaches usually tent to either recognize only the very high level phases or explicitly and clearly explain that phases are in their very nature highly parallel, iterative with huge overlaps and executed in a very short time periods (rather days or weeks rather than months and years).
From this perspective MMDIS reminds some of the plan-driven methodologies which define a rigid waterfall-like process but as of the influence of agile they try to extend the same rigid process with agile elements like prototyping and iterations just to keep their methodology trendy.
The problem with this approach is, the iterative and parallel nature of the development processes has to be embedded into the very essence of the methodology. The whole methodology should be build up around this idea^[13], otherwise there is a risk the individual phases will be executed in a long run sequential manner and thus making the project miss the requirements which will change or become more clear in the mean time.
Modern methodology needs to have mechanism which will constantly challenge the achieved, constantly reassure the requirements and constantly deliver software increments in the shortest possible integrations.
In the section called “Introduction” we described three types of methodologies, the plan-driven (manufacturing, production line), object oriented (oriented on design) and agile (customer-oriented). In [AL] different methodology types are mapped to people's three fundamentally different ways of thinking about software development. Having well described sequential stages is very appealing especially to people of the manufacturing group as it creates an illusion of software development as an predictable process which it is not at all.
In [MF] Martin Fowler says: “This leads to people using a methodology in the wrong circumstances, such as using a predictable methodology in a unpredictable situation.” This is exactly what happened with the plan-driven methodologies of 70's and 80's. Allowing people to process the methodology in a rigid way (and not shielding them from this seductive option) will inevitably increase the project risks as predictability in software development is only an illusion.

Implementation roles

Even more dangerous is to explicitly bind the project stages with a certain group of experts as suggested in MMDIS. [MMDIS1] suggests to “Clearly divide individual levels of abstraction when implementing an IS/IT solution... and thus determine position for individual experts during implementation...”.
This is very dangerous as it may be understood as dividing people strictly into managers, architects, analysts, developers and testers. In the worst scenario, those groups are disjunct and hierarchical.
This idea is again very appealing especially to people with the manufacturing and partially also design mentality. The manufacturing mentality would like to see involved people as replaceable units (see [MF] and [AC]) as only with such people the project plan is predictable. In their eyes projects dependent on individuals are highly vulnerable to risk.
This is in a direct contrast with what agile methodologies claim. One of the four main statements in the agile manifesto [AM] promotes “Individuals and interactions over processes and tools”. In general many of the agile methodologies are strictly people-centric. The idea is, if managers treat people as replaceable units, they also end up with replaceable units [MF] and this will inevitably influence the quality of the results.
Replaceable units are of very little use in a field such as software development which is highly creative and dependent on the intellectual capacity of involved people. Such approach would lower morale and commitment of people. This approach resembles Taylor's scientific management and it may be useful in a factory at the production line, but it can hardly bring any good for software development.
Even substitutability of people may help managers to feel safer, it also inevitably lowers productivity to a fraction. A company practicing such approach may hardly survive in an highly competitive market segment as IT.
Rather then anything replaceable, software developers should be treated more as artist or scientists [AL]. They usually are highly knowledgeable professionals with a high level of self discipline. The role of the managers is not to control those people but to help them get the required competences and to overcome political and organisational barriers which hider them from being able to execute.
In contrast to creating replaceable workers, Agile methodologies propose to hire the best professionals and give them competences and the power so that they can use all their potential.
Making time and resource planning by the managers, conceptual design by the architects, detailed analysis by the analysts, code writing by the developers and testing by testers is the shortest way to a very inefficient process.
Managers will never have the necessary technical information to do any time estimates. Architects can hardly create a perfect design without feedback about the underlaying implementation details. Analysts will never realize all the low level implementation difficulties without touching the code physically. Developers will be frustrated with the design which forces them to create ridiculous code, to implement structures which looks nice in the high level concept but do not have any meaning and only complicate things on the implementation level. Testers will create tests which pass and which are easy to maintain rather than test capable of finding errors. They will never test all the functionality intended by the developer because it is not their code they test, they don't see all the nuances and all the intentions behind.
The morale of the above example is — ideally project management, design, analysis, development and also testing shall be done by the same people. This is of course highly resource demanding and it can hardly be imposed in the real world. But at least the aim is to make larger overlaps within those categories so that designers are also involved in project management and they also do at least some programming and they are familiar with the most important peaces of code. Developers are heavily involved not only in analysis but also in design and they write tests for their own core.
This approach also leads to use of rather smaller teams as IT professionals are a highly non-scalable resource [AL] [MF].
Some may argue that overlaps and small teams may hardly be achievable for large projects where too many people are involved and the overall picture of the project can hardly be kelp in minds of all of them. On the other hand we need to clarify what is actually a large project and how we recognize one. Definitely we can't use a circular definition and claim that large projects are those where a lot of people are involved. The author of this article has witnessed and participated in few “large projects”^[14] which had been implemented in very small teams composed of highly knowledgeable self-disciplined professionals. There is an immense efficiency gain in this model when compared to producing the same result with replaceable over-specialized workers. Achieving same result with them would be either highly inefficient or even impossible.
In same cases software projects really need involvement of more people to get them done in a reasonable schedule. Then it is really an issue how we approach scaling of resources. Rather than structuring people vertically into subordinate roles it may be more efficient to divide big projects into small partially independent sub-projects driven by small highly capable teams with responsibility overlaps and execute them in parallel. Consistency of the overall project is than maintained by intensive communication of the teams responsible for the components who have mutual dependencies.
With small agile teams managers may feel not having control over the project risk management. That's probably one of the reasons why they seek predictability through a rigid process and replaceable human resources even they have to pay for it with immense productivity drop.
There may be a more efficient way of controlling risk using agile teams. For mission critical projects two or even more competitive teams may be established to achieve the same goal. Results of all teams are evaluated and finally the better result is used in production. This approach makes people highly motivated and it may also serve as a way of evaluating teams productivity.
Still there are many companies on the market capable to survive with the inefficient replaceable unit model. It is difficult to find reasons for that but let's just mention few possible causes:

The lack of knowledgeable self-disciplined professionals.
The distortion on the market which is very strong in case of IT. The customer is not capable to accurately evaluate the quality of purchased software especially in short term.
The replaceable unit model may be slightly more predictable which could be crucial for some business models. Also it may be appealing to customer with the manufacturing mentality.

At this spot it is worth mentioning offshoring as a popular method to lover costs of software development. From what has been stated above it is questionable if offshoring may bring the same benefits it brings for other fields also in IT. Again we observe the IT field is really unique and very different from other models. What works well in manufacturing may fail terribly in IT. Even cost of human resources in some countries may be a fraction of the costs in the developed world, the success of offshoring very much depends on the human capital you are getting for that cost; on their knowledge, creativity and attitude to work.

Levels of abstraction

The MMDIS methodology further proposes to clearly divide individual levels of abstractions of the IS/IT to make it better understandable [MMDIS1]. This may sound nice, but it also may be quite risky. We need to keep in mind that the more abstract constructs we define the more blurred picture of reality we get.
Over the last decades Business informatics has establish a whole new language which helps non-technical people in IT to communicate with non-technical people in other areas in order to sell IT services and software licenses to them. This language composes of trendy words^[15]and diagrams describing the IT/IS at the highest level imaginable (the highest level of abstraction). Such diagrams have nothing to do with what is the IS/IT really composed of and how do the individual components interact with each other.
The purposes of the business IT language is to evoke in non-technical people who make IT purchase decisions that they have some understanding of their IT system internals (but this is of course a pure fiction). If managers get an delusive feeling they understand the IS architecture they may start managing it; moving boxes/components all around and filling missing gaps in the diagrams by buying new components and “enhancing” their current IS/IT architecture.
What they are doing is not enhancing their company information system, but they are enhancing the appearance of the high level diagrams which are so far from the real information system, that they have nothing to do with it any more. As a by-product they are paying huge money to IT businesses.

Figure 1. Building block of information systems^[16]

Figure 1, “Building block of information systems” shows one of the semantically empty diagrams commonly used in Business IT. The level of abstraction is so high the diagram contains no information about the actual architecture of the IS/IT. It is rather a psychological tool which shall address the fears and desires [AL] of the management deciding about purchases of new IS/IT components.
It displays the information system as a hierarchical entity which reflects the organisational hierarchy in the company which the management desires to preserve. The IS/IT may be viewed as a tool to preserve their superiority as it provides specific components which are aimed only for their hierarchical level and the other components intended for the lower management or non-executive staff are somehow subordinate to the monumental EIS (Executive Information System) top of the pyramid.
Also the IS/IT is viewed as composed of many different building blocks magically related to the different activities and departments present in the company organisation structure. This again addresses the management fears and desires. The fears that the construction is imperfect and some building blocks are missing which may disrupt all the magnificent building. Or the desire to have a perfect pyramid with all blocks nicely placed at their intended position, to have a better and more stable pyramid than the competitors.
The real quality of the IT/IS, how it is integrated with the business processes, how it is useful in everyday tasks of the company departments is hidden in a tiny sarcophagus deep inside the pyramid where no manager can see.
There are more Business IT examples of diagrams which are misleading or even creating a false view of the IS reality which may be highly unhealthy if we forget about how abstract is the level of our real understanding^[17].
Loosing touch with the reality because of being in a too abstract level is not related only to non-technical people. The very same issues may be experienced with architects which have lost contact with developers and the code. They are living in an artificial world of their UML or other design diagrams. They suffer a delusion that any entity they draw in their diagram gets automagically implemented in the very same scale as they have intended.
They are constantly surprised that some aspect of the system diverges from their design and blame the developers for that. On the other hand, developers feel the architects are completely out of picture and their contributions bring more obstacles than help to the project progress.

The project life-cycle

MMDIS describes the project life cycle as repetitive iteration of the main project phases, see The main phases [MMDIS1]. It does not explicitly say that the phases are sequential but it is also silence about how parallel and interwoven those phases are.

Feasibility Study

From the agile point of view it is ok to recognize difference in the activities during project implementation but it needs to be clarified that those phases are highly parallel and they constantly influence each other and their outputs need constant reevaluation. Otherwise there is a risk that manufacturing mentality people [AL] will tent to set requirements in stone during feasibility study, or that design mentality architect will tent to capture persistent design schemes during global analysis.
Although it is not explicitly stated, the whole MMDIS project life-cycle approach feels like a plan before you build approach (see [MF]). For example, even MMDIS proposes an iterative approach in case the project tents to be too large, the incremental subprojects shall be planned in advanced in the feasibility study.
Plan before build is a good approach in mechanical engineering but according to years of experiences it is completely inappropriate [AL] [MF] for IT. One of the issues is the IT project design may actually look very good on paper but because of the issues with abstraction partially described in the section called “Levels of abstraction” the real implementation issues and drawbacks cannot be predicted in the design stage and they will most probably emerge afterward not earlier than during implementation.
Also in engineering areas (as e.g. bridge building) , the design phase is only a fraction of the overall time, resources and cost of the whole project. But according to [MC], in IT the cost of design is highly over 50%. That's why design and implementation (actual coding) in IT is a parallel interwoven process which can hardly be separated. Of course those processes can be forced to be separate, but the only achievement will be a more time and money consuming project with loads of design documentation as a by-product. Such documentation will anyway be — in the better scenario — ignored and — in the worse scenario — forced to be followed.
In their seek for predictability, companies often use the fixed price contract business model with fixed requirements agreed on in advance as mentioned before in the section called “The User Perspective”. On one hand it gives the illusion of predictability but it is one of the most common reasons for IT failures. Usually the victims are on both sides. The development company losses the contractual money for not satisfying the requirements and the business company looses time and maybe even market position as their core business processes are not adequately supported with the IT system as they require it [MF].
Fixed price contract is a proper solution in building industry or workmanship^[18], but it is inappropriate in IT which has completely different characteristics.
The agile answer to this problem is you simply can't fix all properties (time, cost and scope) of the project in advanced [SA]. Usually you fix the budget and time and keep the scope flexible (but controlled).

Figure 2. The iron(y) triangle [SA]

This approach is accompanied by incremental development with a heavily involved customer providing constant feedback. Such model has many advantages for the customer. Especially very early production results and constant feedback about the project state. On the other hand, this model is not compatible with fixed planning in advanced. We would experience constant diverging from the fixed plan, similar to what will be experienced in the fixed price contract scenario but with fatal consequences.
In contrast, this model is constantly adapting to the ever changing project state. This means even we can spot stages as feasibility study or global analysis highlighting them as phases may be misleading as those are constantly questioned and reworked during the whole project progress.

Global and detailed analysis

MMDIS explicitly separates the phase of conceptual design analysis and detailed analysis. This division may seem artificial and there is very little advocation for it in [MMDIS1]. It seems like this division has been made only because traditional software development methodologies (especially the object-oriented methodologies, see the section called “Introduction” ) do it also.
As stated above the section called “The project life-cycle” , design is more than 50% of the project cost. We have to decide if we really can afford the luxury of a separate conceptual design phase. Also as we already state, design is not a one-time activity, it needs to be updated constantly during the project life cycle. This means our conceptual design needs to be constantly maintained and kept synchronized with the ever changing requirements.

The question we have to ask at this stage

What extra resources will it cost?
What benefits it brings?
Does conceptual design bring more quality to the project?
Are the benefits outreaching the costs?

According to the authors experience conceptual design is usually an overhead even in large scale projects. After a while when deadlines get tight, conceptual design brings only frustration as everybody in the team can clearly see how far did it diverge from current state of the project. As such it can hardly be used as a reliable source of documentation. It becomes purely a burden.
Although not very useful for the project itself — to be fair — it needs to be stated that there are political reasons why conceptual design may be useful. Especially to proof the customer we use a well-planned development methodology which may be very much appealing to customers with the manufacturing and design mentality^[19].
In contrast to MMDIS, Agile approaches are usually quite strict about discouraging people from doing too much documentation^[20]. For example in XP a complete conceptual design is exactly the kind of think you should avoid [XP]. Although there may be some exceptions, for example a quick design meeting, but in this case you should:

keep them short
don't try to address all details
treat the resulting design as a sketch, not as a final design

Martin Fowler [MF2] claims: “When you do some up-front design, you'll inevitably find that some aspects of the design are wrong, and you only discover this when coding. That's not a problem providing that you then change the design. The trouble comes when people think the design is done, and then don't take the knowledge they gained through the coding and run it back into the design”.
The author of this article has witnessed several projects where tuns of documentation has been produced by IT constancies in years without actually producing any line of code. Such L'art pour l'art approach to design is a pure disaster for the customer who may be spending a fortune for nothing useful.
Traditional plan-driven methodologies (see the section called “Introduction”), with a similar project life-cycle to MMDIS, are to be blamed. The ever changing requirements do not allow teams to ever leave the conceptual design stage. Designing consumes all their time. They keep adjusting the design so it is never finished to be handed over to implementation and in a plan-driven methodology developers can't really start their job unless the design is perfectly polished.

Implementation

In contrast to the agile's detailed focus on implementation techniques, MMDIS is not very verbose about this phase.
It seem as if MMDIS would anticipate all the difficulties and issues are concentrated in the preceding stages but implementation is only a workmanship activity which mechanically translates the all-explanatory design into code.
The author of this article has seen brilliant designs turned into junk by non-professional developers. Even with a perfect design (and this is really an utopia, see the section called “Feasibility Study”) still, most of the technical problems need to be solved during implementation. If they are solved in a unsatisfactory manner the perfect design as well as the whole project may very easily get ruined.
That's why developer's quality, their creativity, commitment, team spirit and knowledge is absolutely crucial to the IT project's success. In the real world, implementation is very often perceived similarly as presented in MMDIS as a mechanical activity. Those are the roots of a huge underestimation of the role of developers and importance of code quality.
This leads to a very unhealthy situation in the IT industry where coding is seen as an inexperienced activity which is proceeded by students, brigadiers or junior people in general. Everybody tries to skip this disdainful sage of their career as quickly as possible and they are heading to become more respected as analysis, architects or project managers.
The most important product of the software development becomes the most marginalized element of the project. As a consequence, the quality of software in general is declining^[21].

More dimensions

There is a second group of dimensions which according to MMDIS has to be taken to consideration in every stage of the project life-cycle, see Second group of dimensions. At this stage MMDIS is basically enumerating all sort of essentially disparate knowledge which shall not be omitted to achieve an successful project and which is glued together into entities called dimensions.
MMDIS aim is probably to demonstrate how complex an IT project domain really is and what all different aspects we need to take in consideration. This may have a Wow-I-did-not-think-of-that effect on IT beginners, but on the other hand, most of the highlighted points are common knowledge to IT experts or they are very high-level to have major impact on the way IT projects are managed.
For example in the data and information dimension MMDIS highlights the notorious definition of data, information and knowledge, although it provides some useful insight on different information characteristics which shall be kept in mind and on the cost of keeping a certain information in a the system.
As part of the process and function dimension MMDIS proposes to define hierarchical decomposition of functions of the IT/IS from the high-level functions to elementary functions and to define inputs, outputs and control data for each function. The same is true for processes which may be modelled in a hierarchical manner.
As mentioned in the previous sections, such detailed documentation may be a big overhead for most projects^[22] and it may be very costly to keep such documentation in sync with the changing reality.
That's why Agile methodologies usually propose much more lightweight approaches to capture customer requirements.
For example Scrum works with the product backlog which contains detailed description of the high-level required features and wish lists which are prioritized by business value [SCRM]^[23]. Such documentation is much easier to synchronize with the ever changing requirements than heavy-weight UML diagrams which needs to be synchronized first before changes may be propagated into the code.
A very significant portion of Agile methodologies focus on methods to capture user requirements in the code directly and how to manage constant requirement changes there. The relevant techniques are [AL2] [XP] [SCRM]: refactoring, unit and functional testing, keeping the design clean when refactoring rather than hacking new features in etc...
Another reason for detailed documentation is the risk of loosing important people on the project and the need to train new stuff. Again in this case functional and process diagrams would be of any use only if they are perfectly in sync with the reality. Much more useful in this situation is verbal guidance from the team members, customer requirements and of course the code is the ultimate documentation for the professionals.
The management dimension assigns role, resources, responsibilities and does the overall planning. It defines participation of IT specialists, top management and end-users in the project.
In general MMDIS defines the aims of the management dimension as to optimize resource (people, financial...) consumption to achieve the planed IT/IS requirements on time.
The Agile methodologies are much more verbose on the role of management in IT projects. The relationship between management and developers is very fragile and crucial to the project success. As a result of many examples of hostile management [AL] Agile often emphasises that management shall not interfere into matters which are only up to the IT professionals such as choice of technology^[24] (hardly any manager may understand the technology better than IT professionals) or time estimates to develop a certain feature [MF].
On the other hand, even managers shall not interfere into the matters of the development team whey shall not play a passive role. Only managers have the authority and power to help the team in matters where their power is insufficient. [AL] says: “ Here, the manager uses their authority and political clout to ensure that those outside the team play fair, to give the team every chance of succeeding. For example, tackling bureaucracy, boosting insufficient budgets, and repelling stubborn competitors and saboteurs. That is, rather that directing their authority inwards to command and control the team, the manager-as-referee directs their power outwards to support the team, removing obstacles that the team is powerless to address themselves.”
For example, most of the Agile is based on communication and development teams need constant access to business domain experts for consultation. The role of management is to arrange such communication channels [MF].
Another important role of the management is leadership. The role of the team leader is helping the team find shared beliefs around which to gel, and helping the team succeed repeatedly in their work [AL].
Further dimensions described in MMDIS highlight some facts about IT systems which are obvious to people who participated in few IT projects. For example:

For labour, social and ethical dimensions MMDIS emphasizes the importance of training. Even a superb IT/IS has no value for the business if there are no employees able to operate the system [MMDIS1].
There needs to be sufficient hardware to run the IT/IS with an appropriate number of users [MMDIS1].
The software dimension teaches us that software is composed of software components. The choice has to be made whether to use standard components which are already there or to develop them from scratch^[25].
The economic dimension is really crucial as it asks the question whether the gains of the IS/IT really dwarf the costs.
The methodical and documentation dimension defines tools and techniques which shall be used in the project and the kinds of documentation which is produced during implementation and maintenance.
One of the methods used during software development is in fact the methodology itself. [MF] emphasises the importance of accepting a methodology by the team rather then imposing it by the management. Accepting a methodology needs commitment but this can hardly be achieved through imposing anything. This will only lead to a stage where the methodology will be violated whenever possible^[26].

Dimensions summary

According to MMDIS various dimensions in various stages of the project life-cycle do have stronger or weaker dependencies on each other and their importance in a particular stage varies.
To achieve a consistent and integrated IT/IS, no dimension may be ignored, all the dimensions need to be taken in account in all the project life-cycle phases [MMDIS1].
On the other hand this may be very difficult to achieve and all the multidimensional approach stands and falls with the fact whether the idea of propagating the high level strategic goals through all the life-cycle phases, through out all the dimensions is really something which is achievable in a real life project. There are so many levels, so many abstractions on the way that one has to ask whether the strategic visions don't get somehow distorted on the way down to implementation.

Main principles

[MMDIS2] further generalizes some of the MMDIS concepts mentioned in previous sections into 11 main principles of information system management.

Priciples

Multidimensionality
Integration
Layering
Flexibility
Openness
Standardization
Cooperation
Process Management
Learning and growth
Resource localization
Measurability

Principles as a new concept introduced in [MMDIS2], seem to the author of this text as an aim to generalize different MMDIS aspects into high level commonly applicable approaches. This makes MMDIS less controversial and more flexible. As stated in [AL] a common issue in methodologies is to find the proper level of specificity.
A methodology being too specific can never cope with the complexity of the real word. All possibilities can never be enumerated and the methodology can never be made suitable for all sort of different applications. Methodology maintainers trying to predict any possible situation and provide guidance are creating methodology monsters which are supposed to be suitable for all sort of very different tasks but failing to do any of them in satisfactory manner.
On the other hand being too generic means the methodology can provide hardly any guidance in any specific situations. Telling only generally accepted facts can hardly be questioned, but such methodology isn't very useful either.
Some of the statements in [MMDIS2] explaining the principles tend to be quite high level and thus showing characteristics of being pretty obvious or even tautologic in some situation.
For example in order to succeed in creation of an information system the multidimensionality principle tells you not to omit any of the dimensions critical for succeeding.
Integration principle basically says that the a system is not just the sum of its parts.
Layering is a common principle in IT. It is hard to imaging any IS without layering applied so it is really questionable if this is worth highlighting as a main principle of any methodology.
On the other hand the flexibility principle mentions an very important and controversial issue in software development. Beside the two possibilities mentioned in [MMDIS2] there are other options to gain flexibility.
Some Agile methodologies as XP for example propose to keep code specific and only implement the required features (features which have a relevant customer value) at a time, but keep the code clean so that refactoring and changes are possible in the future without being too painful.
Object oriented methodologies (as mentioned in the section called “Introduction”) on the other hand propose to define extensibility points designed by architects featuring prophetic abilities. But this approach did not show itself as being effective as prophetic architects are quite scare on the IT labour market.
Making the IS flexible through parameters (as proposed in [MMDIS2]) is definitely an option but extremely expensive. Also the aim of parameterizing every aspect of the IS conducted one of the most unhealthy phenomenon in IT history^[27]; parametrized software monsters such as products made by SAP, Siebel, Portal, Oracle and others. According to author's experience such software products are common cause of software project failures^[28].
Parameters are great at presentations. They create an illusion of flexibility. With few mouse clicks it is possible to completely change the behaviour of the system to better suit the customer's business needs. This usually does impress non-technical people who start to believe that changing parameters of their company ERP is like configuring their Outlook. They see more control over the software and less cost on IT experts, but they are terribly wrong.
The opposite is true. Control over the software shrinks only to aspects which are configurable through parameters and changing those parameters may have unpredictable results as the functionality influenced by the parameters is a black-box^[29] for the customer who now solely depends on the vendor's documentation provided.
The quality of documentation is usually very bad as there is no incentive for the software vendors to reveal any details which could help third parties to configure their software. On the contrary, they wish only themselves or their certified partners are able to customize the software which is lucrative service.
Where source code is written in a standard language and thus understandable to a wide range of IT experts, parameters are a proprietary knowledge and experts need to pay to the software vendor to gain such knowledge through certifications and trainings.
This helps to creates an well thought encapsulated ecosystem where the customer gets enslaved in after he makes the purchase decision. Every time he needs to accommodate the IS to his changing business needs he pay for it either to the software vendor himself or to somebody appointed by the vendor who did already pay for this privileged and now he wants to get his investment back.
The whole system is supported by big consultancy companies (e. g. Garner) who recommend such software vendors as market leaders. At the same time their recommendation serves as advocacy for bad purchase decisions on the customer side. No matter the customer replaced their previous software solution which he had full control over with something which did not bring any additional business value, no matter it is now twice as costly to maintain the software and expensive external consultants need to be paid to do so, but we did choose a market leader so our decision can't be questioned!
Parametrized software is not only good business for all involved parties except the customer, it is also a an ugly technical solution. Object oriented paradigm gave us the tool to model our domain directly using objects so that our solution is understandable, clean and flexible to changes. With parametrized software this principle gets distorted. We do not create a domain model directly but rather a generic meta model which is intended to interpret the actual domain model expressed in a proprietary language. This introduces additional complexity, makes implementation much more difficult and the overall solution less transparent just to chain the customer to the vendor.
To conclude flexibility can hardly be achieved through a parametrized software but rather through a good design and availability of the source code and this is related to another MMDIS principle - openness.
With respect to openness [MMDIS2] does not mention the important role of open source software. Having full source code of your IS component gives the company flexibility and freedom of choise. In contrary using a closed source solution may bring better software quality in some cases, but as mentioned earlier it means high risks of being too dependent on the vendor.
On standardization [MMDIS2] claims: “a software solution gets cheaper and less complex when standards are used”; but this statement can hardly be generalized. It definitely depends on the problem and mainly on the standards involved and their quality.
For further information on MMDIS principles, see [MMDIS2].

From development to management

At the end of 90's MMDIS transformed from a methodology which primarily focuses on development of information systems to a methodology which has a larger scope [MMDIS2]. Development is seen as only a fraction of the overall effort to manage an information system and IT services within companies.
On the other hand it is important to emphasis that the quality of the developed software highly depends on the development process. Moreover the software's quality highly influences the quality of the overall information system and how it is capable to support the company processes. Using the MMDIS language, software development process is one of the most important dimensions which can't be omitted when taking about information systems. Marginalizing software development and it's importance may have similar effects as underestimating the implementation phase as discussed in the section called “Implementation”.
[MMDIS2] did not bring any significant updates to the software development aspects of the methodology depicted in [MMDIS1]. It only generalizes some of the approaches as for example the high level principles of the methodology (see the section called “Main principles”). This means a company willing to practice MMDIS who is doing also software development (not outsourcing it) needs to adhere to principles which haven't been significantly updated for years and which ignores most of the recent development which has especially been set on in the Agile camp.
Anyway the management extension to MMDIS it out of scope of this article which primarily focuses on software development methodologies in the narrow sense. For more information, see [MMDIS2].

Conclusion

The uniqueness of using MMDIS for software development originates from structuring aspects of IT projects into dimensions and focusing on aspects which according to [MMDIS1] has been neglected in other software methodologies such as the organizational, labour and economic dimension. But the question here is: Is this really a sufficient value added to form and maintain yet another methodology?
MMDIS is ignoring many aspects which has been researched in the Agile camp over the last two decade. Although agile inventions such as prototyping or incremental development are mentioned within the scope of MMDIS, they are mentioned independently on the rest of the methodology only as an extension, not an integral part of the project life-cycle.
Even MMDIS is not a typical plan-driven methodology there is a risk of potential practitioners to understand it as such. On the other hand the plan-driven essence gives it an interesting marketing bonus as it may sell well to people with the manufacturing and design wordview. Even MMDIS could be possibly executed in an Agile manner, there is very little in the methodology itself which would encourage users to do so.
Ignoring the above, MMDIS is still an interesting reading. It is a nice compilation of advice and precepts which obviously have their roots in practical IT experiences.
Also MMDIS holistic approach to IS/IT is quite rare and interesting. Where other methodologies focus on the development process or on the software itself, MMDIS tries to see the Information System as a whole in all its complexity (dimensions) within the organisation structure of the company.
It is interesting to state that the Agile and MMDIS share one of the main principles. The holy grail of Agile is customer satisfaction which is embodies in MMDIS through the ubiquitarian effort the keep the developed system at every stage and in every detail conforming to the high-level strategic vision of the company.
MMDIS is trying hard to explain how high level strategic visions along with other customer requirements get transformed from one project stage to another, from abstract constructs to the detailed ones through all dimensions, so that finally every elementary function in the system is in sync with the global strategic vision of the top management.
This sounds really amazing, but also it is difficult to believe that something similar is possible in everyday IT projects. On the other hand again it is great marketing. What may sound better to the ears of managers than a methodology which is somehow able to encode their beautiful visions in the very genetic essence of their company Information System.
To conclude, even MMDIS brings some interesting ideas the author of this article would recommend it as additional knowledge to be read but not to be used in most of the every day software development projects (even this depends on the scale and scope of the projects and on how fixed are the requirements)^[30].
On the other hand MMDIS is a perfect marketing methodology^[31]. It is common routine for IT companies to have two or more methodologies. One which they really practice and other methodologies which they use as a marketing tool for certain type of customer, because they know they will appeal to their type of thinking or they are required by the customer.
Practicing Agile helps the company to be competitive and to create software efficiently, but for customers with the manufacturing mentality [AL], Agile is a synonym for anarchy and chaos^[32]. Knowing the IT supplier practices a nice well-defined methodology with comprehensive planning and detailed design documentation such as MMDIS may be a big benefit in their eyes.
That's exactly the way many plan-driven methodologies survived until now. The only issue with MMDIS is, it is not know on a world-wide scale. Managers usually don't read software methodology books. Usually they find their way through unknown using buzzwords and MMDIS won't probably ring a bell.

Bibliography

[MMDIS1] Voříšek, J.:Strategiské řízení informačního systému a systémová integrace. 1999. ISBN 80-85943-40-9

[MMDIS2] Voříšek, J.:Principy a modely řízení podnikové informatiky. Praha, 2008. ISBN 978-80-245-1440-6

[VOR1] Voříšek, J.:Principy strategického řízení informačního systému. 1998. URL: http://nb.vse.cz/~vorisek/FILES/Clanky/1998_Principy_strategickeho_rizeni_IS.htm

[VOR2] Voříšek, J., Bruckner, T.:Outsourcing IS/IT z hlediska zadavatelského podniku. 1998. URL: http://nb.vse.cz/~vorisek/FILES/Clanky/1998_Outsourcing_IS.htm

[AM] Manigesto for Agile Software Development. 2001. URL: http://agilemanifesto.org

[EA] Gelperin, D.:Exploring Agile. 2008. ISBN:978-1-60558-021-0

[AL] Lauther, A.:Software Project Cultures. 2008. URL: http://anthony.lauder.googlepages.com/SoftwareProjectCultures.pdf

[AL2] Lauther, A.:Selling agile to CEO. 2008. URL: http://anthony.lauder.googlepages.com/sellingagile

[WF] Royce, W.:Managing the development of large software systems. 1970. URL: http://www.cs.umd.edu/class/spring2003/cmsc838p/Process/waterfall.pdf

[AS] Ambler, S.:Agile on a fixed budget. 2007. URL: http://www.ddj.com/architect/201202925

[MF] Fowler, M.:The New Methodology. 2005. URL: http://martinfowler.com/articles/newMethodology.html

[MF2] Fowler, M.:Is Design Dead?. 2005. URL: http://martinfowler.com/articles/designDead.html

[XP] Beck, K., Andres, C.:Extreme Programming Explained. 1999. ISBN: 02-01616-41-6

[SCRM] Schwaber, K., Beedle, M.:Agile Software Development with Scrum. 2001. ISBN: 01-30676-34-9

[OOM] Ramsin, R., Paige, R.:Process-Centered Review of Object Oriented Software Development Methodologies. 2008. ISSN: 0360-0300

[MFM] Maurer, F., Melnik, G.:Agile methods: moving towards the mainstream of the software industry. 2006. ISBN:1-59593-375-1

[APM] Hochmüller, E., Mittermeir, R.:Agile process myths. 2008. ISBN:978-1-60558-021-0

^[1]Even already the original article by W. Royce claims that the waterfall technique is not intended for large projects, the waterfall approach become very popular in many methodologies which omitted the iterative nature proposed in the original article. This demonstrates that misinterpretation is the biggest enemy of any methodology.

^[2]Such methodologies include for example Structured Analysis and Design Techniques (SADT), The Yourdon Systems Method (YSM), Specification and Description Language (SDL), Information Engineering and Jackson System Development (JSD), Capability Maturity Model (CMM), some approaches based on Rational Unified Process (RUP) and other methodologies which involve a waterfall-like approach.

^[3]This approach is referred to as loose coupling between objects.

^[4][AL] explains why focusing on the design may be wrong and [MF2] shows how design is still present in Agile but in a slightly different embodiment.

^[5]Methodologies such as XP, Scrum, Crystal, FDD and other are commonly considered as agile, see [XP] or [SCRM].

^[6]Although those are very high-level principles which may be very easily misinterpreted as stated in [EA]

^[7]Note that this is true if we compare MMDIS with the plan-driven methodologies, but from the agile point of view MMDIS seems much more strict and rigid.

^[8]One of such methodologies is Extreme Programming [XP], which on one hand makes customer satisfaction the main aim of the development process and adjusts all the proposed best practices to achieve it, but it is not too much focused on whether the customer requirements are really in sync with their strategic goals which is let to the company to judge.

^[9]This is a nice goal, but it may be very difficult to achieve. It seems as MMDIS is not very verbose on how to achieve such kalokagathic state of the project.

^[10]Ideally they shall be confronted with a running prototype application.

^[11]Some methodologies work with a predictable process (especially the plan-driven methodologies). As predictability is a very desirable feature for management it is always very tempting to use a predictable methodology. But using a predictable methodology on a unpredictable field is very likely to cause project failures.

^[12]According to MMDIS, all of the phases need to be compliant with the global enterprise strategy and IT strategy.

^[13]As in XP where phases are iteratively executed at the scale of days and weeks or the sprint in Scrum as the smallest unit of usable software increment.

^[14]Large in terms of functionality covered and internal complexity of the system. Those projects basically involve implementation of very large systems similar in scale to what has been developed by hundreds or even thousands of people for several years by the competition.

^[15]Those are commonly referred to as buzzwords. The set of terms to describe the same thing in IT usually completely changes over a year so that same things are described with completely different words but those words are trendy and appealing. The aim is to achieve an impression of innovation and high tech even the only novelty came from the marketing teams.

^[16]This diagram was taken from [MMDIS1]

^[17]Another example are the famous Garthner magic quadrants. From the authors personal experience the more is a certain product judged as being visionary and the more as being able to execute the more ugly is the technical solution of the product, the more non-standard components are used, the more time will it require to integrate the solution into the company's IT infrastructure and of course the more money will be spent on the licenses and the more will cost the consultations.

^[18]It is in interesting coincidence that [MMDIS1] really demonstrates the project life-cycle on a building industry metaphor.

^[19]They automatically assume that if the plan-driven processes work fine in their industry they are in a similar manner applicable in IT.

^[20]Although there are some examples of a co-existence of conceptual design with agile. Also [MF] argues that documentation is not automatically the source of all evil.

^[21]This is the author's personal opinion, there can hardly be any proof for that as software quality is highly intangible. But from the authors experience many companies started as geek's undertaking which a perfect product with a very high ratio of technical people. But as a result of a typical life-cycle of such start-ups, the ratio of technical people starts to decrease in favour of management, marketing and sales, who are taking more and more superior role in the business.
As a result the product quality decreases, innovation stops and the only thing which persists are the business people who try to exploit the original idea to the limit, but they are of course unable to bring any new ideas in.
Fortunately for the industry there is usually already another bunch of geeks grounding another brand new start-up. If they are lucky enough the business spongers won't occur too early. Let's keep fingers crossed for them.

^[22]MMDIS actually does not give a project scope and scale when it is relevant to do such detailed documentation. This may lead to an impression that it is proposed in any scope and scale which would be ridiculous.

^[23]The backlog is constantly updated and synchronized with the customer by the product owner - one of the Scrum roles which represent the interest of the stakeholders, usually working on the customer side. The development team on the other hand assigns estimated development effort to the backlog. The features with the highest business value first and the shortest effort estimate are implemented first. The customer requirements - called also user stories (small pieces of papers containing 1-2 sentences of captured requirements edited by customer representatives) are directly transformed into code and both serve as the project's ultimate documentation.

^[24]The choice of technology can easily become a political decision. This leads to a huge risk of project failure. Only the IT professionals are capable of deciding whether the requirements can or cannot be fulfilled through a certain technology [MF].

^[25]An important question is also whether to use open source components which are usually more transparent, customizable and maintainable or whether to use third party components and rely on the third party support and loose control over the particular component.

^[26][AL] has a similar opinion. We already mentioned his division of people mentalities into manufacturing, design and customer cultures. Further more he states — it is difficult to use an agile methodology in a camp with dominant manufacturing or design methodology as well it would cause incredible issues to apply a waterfall process in the customer culture camp. The reason is, people won't be committed to a process which is in contrast to their worldview. Changes of the culture in a company is possible but very painful and risky.

^[27]This is author's personal opinion, based on his IT industry experiences.

^[28]The author's claim is among others based on his own experiences with a tiny Sibel project which did at least 10 times exceeded it's original budget and time-frame and after 3 years of implementation it is still under development. A similar project could have been implemented from scratch in few week time.

^[29]Because the provided software is closed source.

^[30]At this point it is important to recall that MMDIS is not restricted to software development but has a wider scope which has not been examined in this text.

^[31]The author of this article calls a marketing methodology the one which is not to be followed but which is to be announced to be followed for obvious reasons.

^[32]They don't realize how disciplined in fact Agile is [AL2]. For example XP is a highly disciplined process which is very demanding in terms of the practitioners.

NVDL — a Breath of Fresh Air for Compound Document Validation (XTech2007)

2010-05-27T11:16:00.001-07:00

Jirka Kosek

University of Economics, Prague LISp (Laboratory for Intelligent Systems Prague)

W. Churchill Sq. 4
130 67 Praha 3
Czech Republic
jirka@kosek.cz

Petr Nálevka

University of Economics, Prague Department of Information and Knowledge Engineering

W. Churchill Sq. 4
130 67 Praha 3
Czech Republic
petr@nalevka.com

Abstract

Compound document is a document that consist of elements andattributes from different mark-up vocabularies (namespaces). Thisapproach to document engineering is very effective because it allowsreusing existing markup technologies in a novel ways. Howevervalidation of such documents is a big challenge. It is very hard tocreate complex combined schemas in RELAX NG or W3C XML Schema forvalidation of compound documents. Instead advantages of using NVDL asa validation language are explained in this article. Further, our ownimplementation called JNVDL is introduced. The second part of the articledeals with problems of recognizing different versions ofa single XML vocabulary. Finally, an extension of the NVDL language able tosolve this problem is introduced.

Table of Contents

Introduction

Compound documents

The Web environment
Examples of application

Validation of compound documents

XML Schema or RELAX NG is insufficient
NVDL is the right solution

JNVDL

Implementation issues

Impact on a Web architecture

Namespace is not a document type
Versioning namespaces
Extending NVDL to support versioning

Introduction

This article deals with compound document validation. In thethe section called “Compound documents” advantages and the current usageof compound documents is described. The next part (the section called “Validation of compound documents”) shows insufficiency of classical schemalanguages for validation of compound documents. NVDL language isproposed as a solution to this problem in the section called “NVDL is the right solution”. Thesecond part of this article introduces our implementation of NVDLcalled JNVDL (the section called “JNVDL”) and problems which were solvedduring implementation of the NVDL standard. The last part of this article(the section called “Impact on a Web architecture”) deals with the problem of versioningdocument types and proposes some NVDL extensions which can be used tosolve problem of several different document types residing in onenamespace.
Open-source implementation of NVDL validator and proposed NVDLextensions could be considered as the main contribution of our workdescribed in this paper.

Compound documents

Compound document is a modern name for XML documents thatconsist of elements and attributes from different mark-upvocabularies. In other words, by combining two or more different XMLlanguages in a single document we create a compound document. This wasmade technically possible thanks to XML Namespaces. In general, theNamespaces in XML recommendation[NS] solvesproblems of collision and recognition of elements and attributes fromdifferent mark-up vocabularies within one XML document. This isachieved through qualified names, that make different vocabularyelements or attributes distinguishable even they use the same localnames.
At first, some people considered namespaces to be a hostileelement polluting XML with additional complexity without anyreasonable need for it. At this time, the world of mark-upvocabularies has been dominated by over-grown monolithic languages,but soon they faced serious extensibility issues. The set of problemsa language addresses is growing and evolving over time. To keep-upwith the changing requirements, the monolithic approach constantlypollutes the vocabulary with new closely specific mark-up. Asa result, we see extensive, difficult to learn and difficult tomaintain languages, which are intended to solve all sort of problems,but not solving any of them in a satisfactory manner.
Recently, it is more and more obvious that some extensibilityproblems may be solved smarter using composition of more differentsingle-purpose languages rather than further extending the monolithiclanguage. If there already exists a widely adopted and understoodvocabulary, which solves part of our problem, it makes a good sense toreuse it rather than introducing something new. With this approach,we gain an immense flexibility, as for every specific problem, we canadopt a specific combination of vocabularies.
Isolated single-purpose languages are easier to maintain andwhat is even more important, they can be easily reused in distinctapplications. The domain of such languages is narrow and their aim iswell defined, which helps to keep the language free of indiscreetextensions.

The Web environment

HTML is a good example of a shift from a standalone language tothe use of compound documents. At first, HTML was a simple format forpublishing mostly scientific articles and for linking themtogether. Soon the Web became incredibly popular and widelyadopted. It didn't serve just as a standard for publishing electronicdocuments, but it also become a standard way to create distributeduser interfaces for various information systems.
The tendency to use or misuse HTML to solve all sorts ofdistinct problems slowly polluted the language with various indiscreetproprietary extensions. Browser and other software vendors werepromptly introducing new user-oriented features to gain a competitiveadvantage, without having a long term vision of the languagedevelopment in mind. All those issues slowly caused the Web wasloosing one of its main advantage; cross-platforminteroperability.
The situation has significantly improved after standardizationof the language (under W3C). The language has been purified from mostof the presentational aspects and HTML has been made fully XML based(XHTML). But the major improvement was modularization of XHTML (see[XHTMLMOD]). The language became more flexible andadaptable in various environments for various tasks. Modularizationallows to use a subset of HTML features that most reflects ourparticular needs. Logically related aspects of the language aredecomposed into modules such as e. g. structure module with the mainHTML structure, table module for expressing tabular data, text modulefor organizing texts into headings and paragraphs, forms module todefine user interfaces, meta-information module to attach meta-data todocuments, image module for images, link module to hyperlink ourdocuments etc.
For addressing different problems, we can use different XHTMLmodules. For example, it doesn't make sense to use the forms modulewhen publishing a simple electronic document. Moreover, we may look atmodules as default vocabulary fragments with limitedexpressiveness. They can be left out completely (if not needed), butthey can also be replaced by a whole different specialized andfeature-rich language. This can be clearly spotted as the currenttrend in Web standards. Instead of the forms module, we can useXForms, RDF can replace the meta-information module, link module canbe overridden by XLink, instead of images we can directly embed SVGvector graphics and so on.
To conclude, compound documents make Web more flexible andpowerful. It makes it suitable for all sort of very differentapplications. Every specific problem can be addressed by a customcombination of highly specialized languages. If we follow this line ofthinking, at some point we realize, there is no need for HTML anymore.The only think needed is a parent language to embed all thevocabularies which best suit our intentions. The XHTML structuremodule is a good candidate, but a completely different language canserve this purpose as well. As an example, imagine a Web application,where SVG takes the role of the parent language and embedded XForms isused to define the user interface. As SVG is a powerful presentationallanguage and XForms is the latest declarative and feature-rich userinterface standard, such combination of languages may be considered asthe best solution to a particular problem.

Examples of application

There are many different applications of compound documents inmany different areas. When once adopted, composition of differentvocabularies seems as a natural and convenient approach to manyproblems. One of the first application of compound documents ever weretemplating languages. The W3C XSL Transformations recommendation hasbeen published just few months after Namespaces in XML. XSLT is apopular templating language, which can express rules for transforminga source XML tree into a result tree. The particular rules areexpressed using the XSLT vocabulary and they contain embeddedfragments of the result tree vocabularies. This means XSLT stylesheetsare basically compound documents.
In addition, XML is widely used as a data exchange format. Innon-trivial cases, there is a protocol such as for example SOAP toexchange structured XML messages. SOAP messages are again compounddocuments as they consist of an envelope (SOAP vocabulary) whichencapsulates the actual message payload (arbitraryvocabulary).
Compound documents are perfectly applicable also for officedocument formats. In this case, various differently structured data asstructured text, tables, graphs, diagrams, spreadsheets need to beincorporated into one document. This is the right task for XML, as itfeatures the right combining mechanisms and there are many specializedand mature XML vocabularies ready to be reused within the officedocuments. Lets mention the Open Document Format (ODF) as an exampleof XML being successfully used in various office bundles as the nativedocument format.
As mentioned previously, the Web offers huge opportunities forcompound documents and those haven't been really exploited yet. One ofthe problems is the lacking client support for the new standards. Thesituation is far better among the mobile device clients than on thedesktop. Despite those issues, there are already some interestingcompound document solutions, which may be used with some compromisesin most today's mainstream browsers. Among of all, a good example ofa Web compound document concept is the xH language, presented at theWWW2006 conference[XH]. It is basicallya synthesis of XHTML and several other well-know standard XMLlanguages; mainly XForms, SVG and MathML. Interaction of thedifferent language blocks is achieved through JavaScript.
All the languages recommended by xH are widely used andwell-known. But the value added and the major intention of xH is toencourage people to use those languages in combination to build a newgeneration of rich and flexible Web application with enhanced userexperience.

Validation of compound documents

XML namespaces technically allow presence of multiplevocabularies inside one XML document, but there are many other issues,which need to be addressed, before we can adopt a compound documentsolution. Having descriptions of syntax and semantics of theparticular vocabularies is insufficient for the client applicationto handle compound documents correctly. In addition, we need to havealso syntax and semantics defined for the compoundlanguage.^[1]
Different vocabulary fragments can be combined in many differentways and even the isolated fragments are meaningful (in respect totheir language semantics) and they are syntactically correct, thecombination of such fragments can be difficult to interpret or it canbe even semantically empty.
As an example, imagine we have an XHTML document which consistsof a head section, used to place document relatedmeta-data, and a body section, intended to berendered. Placing an RDF meta-data fragment into thebody section would cause interpretationdifficulties, as meta-data are not intended to be rendered. The correctplace to put the fragment is of course the headsection.
This implies, there are two major issues concerning compounddocuments. First, we need to create semantics for different compoundlanguages to make them correctly interpretable by differentapplications. Second, we need to constrain the way different languagesare combined together by allowing just meaningful combinations. Thisrequires some kind of a “meta-schema” to express suchconstraints.
Today, automated validation is absolutely essential forstandalone XML languages to ensure their syntactical correctness andthus interoperability. But this is even more important for compounddocuments, as they bring additional interpretation complexity. To makecompound documents applicable in a heterogeneous environment (as theWeb environment for example), it is absolutely essential to providepowerful compound document validation tools and techniques. Thisrequires schema languages able to cope with multiple namespaces andvalidation engines able to check document instances against suchschemas. In the following sections we will discuss two distinctapproaches to compound document validation.

XML Schema or RELAX NG is insufficient

One approach to face the compound document validation problem isto use namespace support included in today's mainstream schemalanguages; e. g. in RELAX NG or XML Schema. Those namespace-awareschema languages use qualified names to define elements andattributes, thus compound document schemas can be created easily justby specifying the appropriate namespace for elements from differentvocabularies.

Example 1. Allowing RDF inside the XHTML head section (RELAX NG)

<element name="head" 
         ns="http://www.w3.org/1999/xhtml">          
  <element name="title" 
           ns="http://www.w3.org/1999/xhtml">
    <text/>
  </element>
  <interleave>
    ... other XHTML head elements ...
    <optional>
      <element name="RDF" 
               ns="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
        ...
      </element>
    </optional>  
  </interleave>
</element>

The previous example is quite straightforward, but it is notreally flexible indeed. Reusing the definition for a differentcombination of vocabularies would be very painful as it would requireus to use the copy and paste technique. The definition can besignificantly improved by modularizing the schema. Having modules foreach vocabulary would allow us to create schemas for various compoundlanguages simply by including the right subset of modules.
Despite the namespace-aware schema language approach is verysimple, it has several drawbacks. Imagine we like to allowa foreign vocabulary in some contexts of XHTML. This is a simple taskfor someone who is familiar with the implementation details of theXHTML schema (knowing the structure of the schema's definition andmodules). But it is not as straightforward for someone who doesn'thave the right insight.
Moreover, in most cases we cannot simply reuse the existingschemas for vocabularies we like to combine. Standalone languageschemas aren't often well prepared to be combined with other schemas.Usually they don't have the right level of modularity and abstractionwhich is needed for their seamless integration. In addition, they arefrequently written in different schema languages or even in languageswhich aren't namespace-aware at all (for example DTD). This implies,schemas for different vocabularies first need to be converted to thesame namespace-aware schema language and slightly modified before theycan be used as modules of the compound definition.
Such approach would not only require deep knowledge of theparticular schemas and a long implementation time, but it also leadsto maintenance issues. As different languages evolve over time, weneed to keep our modified or converted schemas constantly up-to-date.For complex compound languages this may be an essential problem.
To demonstrate the issues, lets consider the following example.We would like to create a compound document schema for XHTML withembedded SVG and MathML in all block level and inline elements and RDFin the head section. When we decide to use a namespace-aware schemalanguage (for example XML Schema) to achieve that, we run intoproblems. First, we need to convert the official XHTML DTDs into XMLSchema. This needs to be done in a specific way, as we need to haveabstract classes prepared for the head section and block and inlineelements to make them easily extensible through additional modules.Further we can reuse the XML Schema for MathML, but such schema cannotbe used as it is. First, we need to modify it to make it a module ofour parent XHTML schema. The module needs to be further tailored in aspecific way to allow MathML just in the context of the block andinline elements. A similar task needs to be done also for SVG andRDF.
Basically, every time a new vocabulary needs to be incorporatedinto the compound definition, its official schema first needs to beconverted and modified. Moreover, different vocabulary modules needsto be constantly synchronized with new versions of the languages. Thisis an error-prone approach, because the different definitions arebeing duplicated. Another problem arises, when for example SVGshould displace XHTML as the parent language. In such case, differentvocabulary modules cannot be simply reused. On the contrary, they mayneed to be again duplicated and slightly reworked.
To conclude, the namespace-aware schema language concept isapplicable in simple cases, but it is not a solution which can beconsidered for complex scenarios. Reusability of existing schemas isan important requirement which is not satisfied at all within today'snamespace-aware schema languages. Different approach to compounddocument validation is needed to allow schema reusability. Suchapproach has to be independent of the particular schema'simplementation details and the schema languages used.

NVDL is the right solution

NVDL, which means Namespace-based Validation DispatchingLanguage, is “Part 4 of ISO/IEC 19757 DSDL” (DocumentSchema Definition Languages) international standard. NVDL is a simple“meta-schema” language which allows to control processingand validation of compound documents. Figure 1, “NVDL validation process at a glance” demonstrates a particular validationdispatching process decomposed into several phases. An NVDL schemaand a compound document instance shown in Example 2, “NVDL validation process” are potential participants of such process.
The essence of NVDLis dividing XML document instances into sections each of whichcontains elements or attributes from a single namespace. A section tree is first constructed for every instance (see Example 3, “Decomposing sections”). Sectionsare further combined or manipulated in various ways to createso called validation candidates.
Manipulation of sections is achieved through rules andtheir corresponding actions defined in an NVDL script. Actionsare executed on a particular section whenever they match a certainrule; usually in case the sections namespace matches the rule'snamespace wildcard.
There are several actions defined in NVDL;e. g. attach for attaching sections back totheir parent, unwrap to handle wrappedsections and validate to send a particular validation fragment to a particular validator.
After executing actions, we usually obtain single namespacevalidation candidates which are further filtered for redundancyinto validation fragments. Such fragments are finally independently send for validation against differentsubschemas^[2] (see Example 4, “Dispatching validation fragments to validators”).
The ability to create single namespace fragments allows us not to careabout namespaces in our subschemas at all.Single namespace schemas are easier to write and what is important alsoeasy to reuse for various different compound languages, wherethe same vocabulary may be used in a different contextor in combination with different vocabularies. Moreover, NVDL is schema language transparent, thus subschemas maybe written in any preferable schema language e. g. RELAX NG, XMLSchema, Schematron or DTD. For detailed information about the NVDL validation dispatchingprocess, refer to [NVDL].

Figure 1. NVDL validation process at a glance

Example 2. NVDL validation process

The following example shows an NVDL schema and a compound document instance which relates to Figure 1, “NVDL validation process at a glance”. In this case, NS1 represents the XHTML namespace and NS2 stands for the XForms namespace. The following instance is an XHTML document with a simple form for retrieving stock quote information.

<html xmlns="http://www.w3.org/1999/xhtml" xmlns:xf="http://www.w3.org/2002/xforms">
<head>
<xf:model>
  <xf:instance><stockquote><symbol/></stockquote></xf:instance>
  <xf:submission xml:id="form" method="post"  action="getStockQuote.do"/>
</xf:model>
</head>

<body>
<xf:group ref="stockquote">
<xf:input ref="symbol"><xf:label>Symbol</xf:label></xf:input>
<br />
<xf:submit submission="form"><xf:label>Get Quote</xf:label></xf:submit>
</xf:group>
</body></html>

To achieve behavior consistent with Figure 1, “NVDL validation process at a glance”, the following schema is applied to the previous compound document instance. Using such schema, the NVDL dispatcher first sends the root XHTML fragment for validation after filtering any descendant XForms fragments and attaching any descendant XHTML fragments. XForms sections are handled in a similar way by filtering any descendant XHTML. For any XHTML document instance with embedded XForms, the following NVDL schema causes one pure XHTML fragment to be send for validation against xhtml.xsd and one or more pure XForms fragments to be validated using xforms.rng.

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0">
<namespace ns="http://www.w3.org/1999/xhtml">
  <validate schema="xhtml.xsd">
    <mode><namespace ns="http://www.w3.org/2002/xforms">
      <validate schema="xforms.rng">
        <mode><namespace ns="http://www.w3.org/2002/xforms"><attach/></namespace>
          <namespace ns="http://www.w3.org/2002/06/xhtml2"><unwrap/></namespace>
        </mode>
      </validate>
      <unwrap>
      <mode><namespace ns="http://www.w3.org/2002/xforms"><unwrap/></namespace>
        <namespace ns="http://www.w3.org/2002/06/xhtml2"><attach/></namespace>
      </mode>
      </unwrap>
    </namespace></mode>
  </validate>
</namespace>
</rules>

Example 3. Decomposing sections

The instance shown in Example 2, “NVDL validation process” is decomposed into the following section tree after applying the NVDL schema from the same example.

ES1 <html><head>ref to ES2</head>
<body>ref to ES4</body>
</html>

ES2 <xf:model>...</xf:model>

ES3 <br />

ES4 <xf:group ref="stockquote"><xf:input ref="symbol">...</xf:input>
ref to ES3
<xf:submit submission="form">...</xf:submit></xf:group>

Example 4. Dispatching validation fragments to validators

After executing attach and unwrap actions on the section tree shown in Example 3, “Decomposing sections”, the following resulting fragments are created and send independently for validation.

<html><head></head>
<body><br /></body>
</html> -> xhtml.xsd

<xf:model>...</xf:model> -> xforms.rng

<xf:group ref="stockquote"><xf:input ref="symbol">...</xf:input>
<xf:submit submission="form">...</xf:submit></xf:group> -> xforms.rng

Namespace-aware schema languages force us to convert all ourschemas to the same schema language. In contrast, when using NVDL, weare free to choose any languages we prefer and we may also combinedifferent schema languages during a single validation process. NVDLdoes not force XML language designers to use mainstream schemalanguages. On the contrary, they are encouraged to choose the schemalanguage which best suits their vocabulary needs. NVDL is alsocompletely isolated from the implementation details of the particularsubschemas. The vocabulary designers can fully focus on the schemaimplementation without even thinking about how can their vocabularypossibly be combined with a different one. NVDL schema designersdo not need any knowledge of the particular subschemaimplementation details. Moreover, they don't even need to understandthe different subschema languages when designing their NVDL scripts.
In the previous section we have seen how difficult it is tocreate a compound definition using a namespace-aware schema language.Lets use NVDL to create the same compound schema: XHTML with embeddedSVG, MathML and RDF. In this case, there is no need for severalexperts to work on that for days. One person can create such NVDLscript in a matter of minutes (see Example 5, “NVDL schema for XHTML with embedded SVG, MathML and RDF”). The reason is, existing schemas canbe fully reused without making any changes to them.

Example 5. NVDL schema for XHTML with embedded SVG, MathML and RDF

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0" startMode="root">
  <mode name="root">       
    <namespace ns="http://www.w3.org/1999/xhtml">
      <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
        <context path="head" useMode="head"/>
        <context path="div|li|p...all block level elements" useMode="block_inline"/>
        <context path="a|em|span|...all inline elements" useMode="block_inline"/>
      </validate>
    </namespace>
  </mode>  
  <mode name="block_inline">
    <namespace ns="http://www.w3.org/2000/svg">
      <validate schema="http://www.w3.org/TR/2002/WD-SVG11-20020108/SVG.xsd"/>
    </namespace>
    <namespace ns="http://www.w3.org/1998/Math/MathML">
      <validate schema="http://www.w3.org/Math/XMLSchema/mathml2/mathml2.xsd"/>
    </namespace>
  </mode>
  <mode namne="head">
    <namespace ns="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
      <validate schema="http://www.w3.org/2000/07/rdf.xsd">
        <mode><anyNamespace><attach/></anyNamespace></mode>  
      </validate>
    </namespace>
  </mode>
</rules>

In the NVDL script in Example 5, “NVDL schema for XHTML with embedded SVG, MathML and RDF”, subschemas are referenced directly at their original locations usingURLs. The script tells the NVDL engine that the only acceptable parentlanguage is XHTML and other vocabularies are forbidden in thatcontext. Plain XHTML is extracted from the validated document and sendfor validation against the official DTDs. RDF sections may only occurin the context of the head element. Any foreignvocabulary contained inside the RDF fragment is attached to it beforebeing send for validation. SVG and MathML fragments are allowed onlyin block and inline elements. Any other vocabulary in any othercontext of the document is rejected.
This simple example demonstrates the power of NVDL. Modifyingthe NVDL script to allow any other vocabulary in some context is asimple and straightforward task. In addition, the script contains onlythe required information about the compound language. Anything relatedto the grammar of the particular vocabularies is encapsulated in thesubschemas where it really belongs. This makes NVDL schemas not onlyeasy to design, but also easy to read and understand.
Note that Example 5, “NVDL schema for XHTML with embedded SVG, MathML and RDF” demonstrates the use ofan NVDL context construct which allows to apply a specific handling to sections in a given path within their parent section.Several paths separated by | may be used within one context condition. Paths used in the example are relative, but absolute paths may be used as well. For example an HTML head context can beaddressed also using the /html/head path.

JNVDL

JNVDL isa Java-based implementation of the [NVDL]specification and it was developed by our team. JNVDL uses the newJAXP validation API, which has been introduced in Java 5. This isa standard way to invoke validation processes and it makes JNVDL easyto use for the end user as well as simply reusable in otherapplications.

Example 6. Invoking NVDL validation using the JAXP validation API

Schema schema = 
  SchemaFactory.newInstance(
    "http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0")
      .newSchema(new File("schema.nvdl"));

schema.newValidator().validate("instance.xml");

The validation API is also used by JNVDL to invoke furthervalidation processes for particular subschemas. This makes JNVDLtransparent to different schema language validator implementations.Enabling JNVDL to validate against a new schema language is just thematter of adding the appropriate validator's jar library on the Javaclasspath. No changes to the JNVDL code are required.

Implementation issues

One of the issues the JNVDL implementation faced is related tothe fact that validators tend to report error locations using line andcolumn numbers. When parsing the validated instance and turning itinto validation fragments, the original position of elements andattributes is inevitably lost. There are two reasons for that. First,today parsers are lacking round-tripping support, thus somewhitespaces which are considered to be irrelevant aren't reported andpreserved. Second, different validation fragments are taken fromdifferent places within the original document. As they are send tovalidators separately, the original position is lost.
Such behavior may confuse users as the error line numbersreported by the particular validators aren't related to the originaldocument but to the particular fragment context. To interpret theinformation correctly, users would need to deduce the line numbersfrom the original position of the validation fragments created byJNVDL.
To overcome those difficulties, JNVDL provides a proprietaryround-tripping extension. Such extension preserves whitespaces fromthe original document and before validation fragments are being sendto the particular validators, they are modified so that elements andattributes occur on the same lines as in the original document.Further, if an XML fragment is extracted from the middle of thedocument, JNVDL adds the appropriate number of empty lines before itto keep the fragment at the same location.
The problem of irrelevance of some whitespaces within XMLdocuments makes the use of line numbers to locate elements andattribute problematic or even error-prone. Validation API designersshould consider using a different mechanism to locate errors. Forexample XPath is a good candidate, as it is whitespace independent andprecise.

Impact on a Web architecture

It is evident that compound documents are used more and moreoften. At this time NVDL is the best available technology forvalidation of compound documents. Still NVDL has some limitationswhich make it not very usable for some document types that are widelyused on the Web. On the other hand the most popular container format forcompound documents—XHTML—is not designed with this usage scenario inmind and breaks many principles of a Web architecture.

Namespace is not a document type

It is a quite common misconception that for each namespace there isa single schema defined somewhere. This assumption might hold for somesimpler specialized XML based languages, but for many languages usedon the Web, namespace works just as a basic semanticidentification.
Very often, there are multiple different variants of vocabularyin one particular namespace. These vocabularies could be subsets ofthe “base” language—for example, this is a case of XHTML1.0 Transitional and its derivates like XHTML 1.0 Strict, XHTML Basicor XHTML Print. The second case is newer version of vocabulary whichdoes not change meaning of original elements so there is no need tochange namespace. Both XSLT 1.0 and XSLT 2.0 share the same namespace,but XSLT 2.0 defines dozen of new elements and attributes, it evenchanges content model of some elements. Similar situation is true alsofor XHTML—XHTML 1.1 defines several new elements for Rubyannotations.

Versioning namespaces

Several different approaches for recognizing document types ina single namespace are in a common use. One of the easiest is usage ofdedicated attribute for holding version information; for example in case of XSLT.

Example 7. Version information inside XSLT 2.0 stylesheet

<xsl:stylesheet 
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  version="2.0">
  ...
</xsl:stylesheet>

This is almost ideal way of conveying versioninformation. Attribute value can be easily accessed in almost allprocessing tools. What is even more important, you can embed XSLT intoother XML vocabulary and you are still able to identify a version ofXSLT used by using the versionattribute.
The only problem is that XSLT allows versioning attribute to occur onlyon a top element of a stylesheet. So you are unable to extract for exampleone template from stylesheet and add versioning information to thistemplate.
XHTML uses legacy way of specifying versioning information whichis depending on presence of a document type declaration (!DOCTYPE) atthe start of the document.

Example 8. Version information in XHTML document

<!DOCTYPE html 
  PUBLIC "-//W3C//DTD XHTML-Print 1.0//EN"
  "http://www.w3.org/MarkUp/DTD/xhtml-print10.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  ...
</html>

Strictly speaking, document type declaration is not versionindication, it is just reference to DTD which can be used forvalidation and definition of entities used. But public or systemidentifier could be used as a version identifier albeit quite long andverbose.
Unfortunately document type declaration can occur only at thebeginning of an XML document. It can not be embedded in the middle of thedocument—this disqualifies it from being used in the Web of compounddocuments. This for example means that you can not embedded an XHTML pageinto SOAP message and identify version of XHTML used.
Moreover, current specifications of several XHTML flavors (forexample XHTML Basic and XHTML Print) make public identifier optionaland allows specification of a private system identifier as long as itpoints to a copy of original DTD. This means that in order to reliablydetect version of XHTML used, you have to download DTD, normalizeline-end characters inside it and then compare it to one of originalDTDs provided by W3C as a part of respective specification. It isevident that such process is overkill. Moreover, requests for downloadof private copy of DTD could be misused as attack against the Webagent—this DTD could be very long or it could use a big amount of entitydeclarations to congest the XML parser.
There is also not very well known feature of XHTML that could beused for specifying version information instead of document typedeclaration. It is possible to use the profile attribute on thehead element. Profile identifies particular profile(version, subset) of the language used and it has form of URI.

Example 9. More robust way of labeling document as XHTML Print

<html xmlns="http://www.w3.org/1999/xhtml">
  <head 
    profile="http://www.w3.org/Markup/Profile/Print">
  ...
  </head>
  ...
</html>

Again, profile attribute isnot a perfect solution—it can be specified only on thehead element and thus can not be used forspecifying flavor of XHTML used for just a small fragment of XHTMLcode.
Previous examples show a very sad conclusion that the currentstate of XML vocabularies and their specifications were not designedin order to make it possible to fully exploit possibilities ofcompound documents. We think that W3C should extend current Webarchitecture [WEBARCH] and update olderspecifications to support robust and flexible way of attaching versioninformation to arbitrary fragments of XML vocabularies. It seems thatallowing version or similarattribute on all elements which can be used as root elements of XMLfragments is a simple and sufficient solution. At the same time,a document type declaration should be made an optional part ofa conforming document.

Extending NVDL to support versioning

In the previous text we explained why we think that namespaceitself is not sufficient for a document type identification. As NVDLvalidation dispatching is based solely on namespaces, we have a problemhere—the current version of NVDL is not able to recognize differentflavors of XHTML or XSLT and route validation to appropriate versionsof the schema. To overcome this limitation, we designed few extensions tothe NVDL language. Their utility is being evaluated using JNVDL (ourimplementation of the NVDL standard).
Our extensions allow better control over the dispatchingprocess. Validations candidate (usually XML fragment from a singlenamespace) is being validated only if corresponding rule in NVDLscript matches both namespace and additional condition. This conditioncan be expressed in XPath language. Example 10, “Validation dispatching based on XPath expression”shows NVDL script which can differentiate between XSLT 1.0 andXSLT 2.0 and use the correct schema for validation.

Example 10. Validation dispatching based on XPath expression

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0"
       xmlns:jnvdl="http://jnvdl.sf.net">
  <namespace ns="http://www.w3.org/1999/XSL/Transform" 
             jnvdl:useWhen="@version = '1.0'">
    <validate schema="xslt1.xsd"/>
  </namespace>
  <namespace ns="http://www.w3.org/1999/XSL/Transform" 
             jnvdl:useWhen="@version = '2.0'">
    <validate schema="xslt2.rng"/>
  </namespace>
</rules>

The appropriate rule in an NVDL script is used for dispatching onlywhen expression in the useWhenattribute is true. Context for XPath evaluation corresponds to the elementsection to be dispatched. For attribute sections, dummy element withattached attributes is expected.
Although we previously stated that document type declaration isnot a robust way for specifying version information, it is worth tosupport this way for legacy documents. The past practice was todifferentiate document types using system and public identifier. JNVDLthus supports also additional parameters useWhenPublicId, useWhenSystemId, useWhenPublicIdRegex and useWhenSystemIdRegex to control when aparticular rule will be used for dispatching based on content ofsystem or public identifiers. If there is more then one“useWhen…” parameter on a single rule, it is sufficientif just one of them matches. Example 11, “Extended NVDL script which handles various flavors of XHTML” shows how to use these JNVDL extensions forhandling various kinds of XHTML in a single NVDL script.

Example 11. Extended NVDL script which handles various flavors of XHTML

<rules xmlns="http://purl.oclc.org/dsdl/nvdl/ns/structure/1.0"
       xmlns:jnvdl="http://jnvdl.sf.net"
       xmlns:html="http://www.w3.org/1999/xhtml">
  <namespace ns="http://www.w3.org/1999/xhtml" 
             jnvdl:useWhenPublicId="-//W3C//DTD XHTML 1.0 Strict//EN"
             jnvdl:useWhenSystemId="http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
    <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"/>
  </namespace>
  <namespace ns="http://www.w3.org/1999/xhtml" 
             jnvdl:useWhenPublicId="-//W3C//DTD XHTML 1.0 Transitional//EN"
             jnvdl:useWhenSystemId="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"/>
  </namespace>
  <namespace ns="http://www.w3.org/1999/xhtml" 
             jnvdl:useWhenPublicId="-//W3C//DTD XHTML-Print 1.0//EN"
             jnvdl:useWhenSystemId="http://www.w3.org/MarkUp/DTD/xhtml-print10.dtd"
             jnvdl:useWhen="contains(concat(' ', normalize-space(html:html/html:head/@profile), ' '), 
                                      ' http://www.w3.org/Markup/Profile/Print ')">
    <validate schema="xhtml-print-1.rng"/>
  </namespace>
  <!-- Unrecognized flavors of XHTML are validated as XHTML 1.0 Transitional -->
  <namespace ns="http://www.w3.org/1999/xhtml">
    <validate schema="http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"/>
  </namespace>
</rules>

We think that without extensions similar to what we propose,usage of NVDL is somehow limited when considering the real Web compound documents inuse. On the other hand, only XPath enabled matching (useWhen) could be potentially added intoa future revision of NVDL. Matching done on system and publicidentifiers needs information, which is not available in the NVDL datamodel. JNVDL is thus using an augmented data model to support thoseextensions.

Related work

NVDL could be used not only for validation, but also as a genericmechanism for associating schemas to XML documents. This feature isnecessary in many scenarios, including XML editors or loosely coupledinterfaces for accepting incoming XML messages.
NVDL is an international standard and builds on many precedingtechnologies. Some XML editors, for example nXML mode for Emacs andoXygen, use similar approach for association of schemas for documentbeing edited. But as far as we know, none of those systems supportsusage of full XPath to manage associations. In this regard our NVDLimplementation offers unique functionality which we believe will beincorporated directly into NVDL standard in a future.
Currently there are two other NVDL implementations—oNVDL and enovdl. Advantagesof our implementation include seamless integration with Java XML APIsand extensions for working with multiple different schemas for thesame namespace.
Our implementation holds all validation candidates in memoryin a tree representation. This allows us to do fancy things likeevaluating full XPath before dispatching takes place. oNVDL usesstreaming approach which is more memory efficient and can be used forprocessing of a very large datasets. But it is impossible to supportfull XPath in a streaming mode.

Future work

One of the future plans for JNVDL is to incorporate it into theRelaxed Web document validation project, see [RLX].Relaxed consists of comprehensive HTML 4.01/XHTML 1.0 schemas and avalidation framework. The schemas were created using RELAX NG withembedded Schematron rules. This combination of languages is verypowerful. It allows to express more constrains than the official W3CDTD-based schemas. Relaxed validates also some of the WCAG 1.0constrains and it has a compound documents validation support. Usersmay choose to allow foreign namespaces inside their documents or toban them completely. They may also validate against a set of predefinedcompound schemas e. g. XHTML+SVG, XHTML+MathML etc.
In terms of compound documents, the Relaxed project is limitedto RELAX NG namespace support. As described previously, this makes itdifficult or even time consuming to create compound document schemas.To overcome those difficulties, the new version of Relaxed, which iscurrently being developed, will use JNVDL as the core validationengine. Such step will make NVDL validation publicly accessiblethrough a Web based interface.
Moreover, JNVDL will help to create and maintain new compounddocument schemas easily. Part of the future work is to enrich thecurrent Relaxed schema repository with NVDL scripts for differentcombinations of the standard and widely used vocabularies, especiallythose intended to be used in the Web environment.

Conclusions

This article has shown that validation of compound documents is besthandled using the NVDL validation language, which has many advantages overother similar approaches (e. g. namespace support in Relax NG or XML Schema).We disclosed a problem of having different versions of document type in asingle namespace and we have shown how to fix this problem by extending NVDLin our implementation called JNVDL. We will use the acquired knowledge fromdeveloping JNVDL and using NVDL when building new version of the Relaxed validator.

Bibliography

[NVDL] Document Schema Definition Languages (DSDL) — Part 4:Namespace-based Validation Dispatching Language — NVDL.ISO/IEC 19757-4. 2006. Available at: http://standards.iso.org/ittf/PubliclyAvailableStandards/c038615_ISO_IEC_19757-4_2006(E).zip

[XH] Birkbeck, M: xH: The new language you alreadyknow. Presented at WWW 2006 conference, Edinburgh.

[XML] Bray, T., Paoli, J., Sperberg-McQueen, C., Maler, E., Yergeau, F.: Extensible Markup Language (XML) 1.0 (Fourth Edition).W3C, 2006.Available at: http://www.w3.org/TR/2006/REC-xml-20060816

[NS] Bray, T., Hollander, D., Layman, A., Tobin, R.: Namespaces in XML 1.0 (Second Edition).W3C, 2006.Available at: http://www.w3.org/TR/REC-xml-names

[WEBARCH] Walsh, N., Jacobs. I: Architecture of the World Wide Web,Volume One. W3C, 2004. Available at: http://www.w3.org/TR/webarch/

[RLX] Kosek, J., Nálevka, P.: Relaxed—on the Way Towards True Validation of Compound Documents.In: WWW 2006 Proceedings. WWW 2006. May 23–26, 2006. Edinburgh, Scotland.Available at: http://www2006.org/programme/files/pdf/4508.pdf

[HTML4] Ragget, D., Le Hors, A., Jacobs, I.: HTML 4.01 Specification.W3C, 1999.Available at: http://www.w3.org/TR/1999/REC-html401-19991224/

[XHTML1] XHTML™ 1.0 The Extensible HyperText Markup Language (Second Edition).W3C, 2002.Available at: http://www.w3.org/TR/2002/REC-xhtml1-20020801/

[XMLSCH-ST] Thompson, H.S., Beech, D., Maloney, M., Mendelsohn, N.: XML Schema Part 1: Structures Second Edition.W3C, 2004.Available at: http://www.w3.org/TR/2004/REC-xmlschema-1-20041028/

[XMLSCH-DT] Biron, P., Malhotra, A.: XML Schema Part 2: Datatypes Second Edition.W3C, 2004.Available at: http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/

[RNG] Clark, J., Murata, M.: RELAX NG Specification.OASIS Committee Specification, 2001.Available at: http://www.relaxng.org/spec-20011203.html

[XHTMLMOD] Altheim, M., McCarron, S., Boumphrey, F., Dooley, S., Schnitzenbaumer, S., Wugofski, T.: Modularization of XHTML™.W3C, 2001.Available at: http://www.w3.org/TR/2001/REC-xhtml-modularization-20010410/

[RDF] Beckett, D.: RDF/XML Syntax Specification (Revised).W3C, 2004.Available at: http://www.w3.org/TR/rdf-syntax-grammar

[SVG] Ferraiolo, J., Fujisawa, S., Jackson, J.: Scalable Vector Graphics (SVG) 1.1 Specification.W3C, 2003.Available at: http://www.w3.org/TR/SVG11

[MTHML] Carlisle, D., Ion, P., Miner, R., Poppelier, N.: Mathematical Markup Language (MathML) Version 2.0 (Second Edition).W3C, 2003.Available at: http://www.w3.org/TR/MathML2

^[1]Compound language is a term used within thistext to describe a language composed of two or more different XMLvocabularies. Such a composition is considered to be a languageitself, as it has its own syntax and semantics in addition to thesyntax and semantics of the particularvocabularies.

^[2]Subschema is defined in the NVDLspecification as a schema referenced by the NVDLscript.

New version of NVDL available

2010-05-27T11:14:00.001-07:00

JNVDL 20071112 ..download latest version here.

I have created a new version of the JNVDL suite for compound document validation. The new version reflects the latest Murata Makoto's chnages in the NVDL specification including big changes in attribute section handling.
A major usability enhancement was validation debug outputs. Now the outputs correspond to how examples are shown in the specification. You will find in he output only what you are really interested in. Using the -d for validation the XFroms example from the specification shows the following output. You see exactly what JNVDL did, all the element and attribute sections it has created, interpretations it assigned to each section and finally fragments and what schema has been used to validate them. This may significatly help with debugging of your validation but also of JNVDL.

Example 1. Example JNVDL debug output

petr@alfa-pn-3:~/dev/project/nvdl/impl/dist$ ./jnvdl.sh -s ./example/primary/spec-xf-html.nvdl.xml -d ./example/primary/spec-xf-html.instance.xml
Round tripping: false
Keep line numbers: false
Stage 1 - Decomposing Sections -
        <{http://www.w3.org/2002/06/xhtml2} ES1(table)>
                <{http://www.w3.org/2002/xforms} ES2(repeat)>
                  AS{}(id nodeset )
                        <{http://www.w3.org/2002/06/xhtml2} ES3(tr)>
                                <{http://www.w3.org/2002/xforms} ES4(input)>
                                  AS{}(ref )
                                        <{http://www.w3.org/2002/06/xhtml2} ES5(p)>
                                                <{http://www.w3.org/2002/xforms} ES6(label)>
                                                </ES6(label)>
                                        </ES5(p)>
                                </ES4(input)>
                        </ES3(tr)>
                </ES2(repeat)>
        </ES1(table)>

Stage 2 - Building Interpretations -

Interpretation 1

                AS{}(ref )
                                 [ATTACH]
                ES1(table)
                                 [VALIDATE against '../secondary/xhtml2/xhtml2.rng']
                ES4(input)
                                 [ATTACH]
                AS{}(id nodeset )
                                 [ATTACH]
                ES2(repeat)
                                 [VALIDATE against '../secondary/xforms/xforms.rng']
                ES5(p)
                                 [UNWRAP]
                ES6(label)
                                 [ATTACH]
                ES3(tr)
                                 [UNWRAP]

Interpretation 2

                AS{}(ref )
                                 [ATTACH]
                ES1(table)
                                 [VALIDATE against '../secondary/xhtml2/xhtml2.rng']
                ES4(input)
                                 [UNWRAP]
                AS{}(id nodeset )
                                 [ATTACH]
                ES2(repeat)
                                 [UNWRAP]
                ES5(p)
                                 [ATTACH]
                ES6(label)
                                 [UNWRAP]
                ES3(tr)
                                 [ATTACH]

Stage 3 and 4 - Combining Sections and Filtering -
        Validation candidate overwritten by a larger fragment:
 [1 < 4]<table xmlns="http://www.w3.org/2002/06/xhtml2" xmlns:xforms="http://www.w3.org/2002/xforms">  <tr>  <td>  <p>    </p>  </td>  </tr>  </table>

Stage 5 - Validation -

        Schema 'file:/home/petr/dev/project/nvdl/impl/dist/./example/primary/../secondary/xhtml2/xhtml2.rng'
        Namespace 'http://relaxng.org/ns/structure/1.0'
        Fragment: '<table xmlns="http://www.w3.org/2002/06/xhtml2" xmlns:xforms="http://www.w3.org/2002/xforms">  <tr>  <td>  <p>    </p>  </td>  </tr>  </table>'
ERROR: line 1 column 94, tag name "table" is not allowed. Possible tag names are: <html>

        Schema 'file:/home/petr/dev/project/nvdl/impl/dist/./example/primary/../secondary/xforms/xforms.rng'
        Namespace 'http://relaxng.org/ns/structure/1.0'
        Fragment: '<xforms:repeat xmlns:xforms="http://www.w3.org/2002/xforms" id="lineset" nodeset="/my:lines/my:line">  <xforms:input ref="my:price">  <xforms:label>Line Item</xforms:label>  </xforms:input>  </xforms:repeat>'

Grammar vs. Rules

2010-05-27T11:10:00.000-07:00

Diagnostics in XML document validation

Petr Nálevka

University of Economics, Prague Department of Information and Knowledge Engineering

W. Churchill Sq. 4
130 67 Praha 3
Czech Republic
petr@nalevka.com

Abstract

Regular grammars has been used over decades for different formal language validation tasks because of their relative easiness of expression but more important because of their low computing expenses. Validation using regular grammars is commonly used also for XML document validation. In this case human understandable grammar definitions are converted into regular expressions which are evaluated against the input document. This approach is fast, straightforward but it lacks good diagnostics. It is hard for the validator engine to track grammar errors back to the information domain and provide some useful error messages understandable for the author.
An alternative approach tends to be rule-based validation which is closely related to the modelled information domain. Rule-based approach gives very good diagnostics but it is more complicated to express simple parent-child relationships as in grammar-based languages. An interesting way how to gain advantages of both approaches is to support conversion from grammar-based schemes into rule-based schemes.

Table of Contents

Introduction

Validation with Grammar

Grammar-based XML Validation

Hedge
Regular Hedge Grammar
Automata-based Validation

Grammar and Diagnostics

Using Rules

Schematron
Expressiveness

From Grammar to Rules

Conclusions

Bibliography

Introduction

Regular grammar is a formal grammar which is defined by a set of terminal symbols, a set of non-terminals, and a set of production rules.
Production rules need to have the following form.

Regular grammar production rules

X →x; where X is a non-terminal and x is a terminal symbol
X →xY; where X and Y is a non-terminal and x is a terminal symbol.
X →ε; where X is a non-terminal and ε is an empty word.

The previous is also known as right regular grammar. For a left regular grammar the second production rule takes the form of X →Yx.
Regular grammar describes all regular languages. They are in a sense equivalent to the finite state automaton. Form every regular grammar a FSA may be constructed. For each regular language a FSA can be constructed which accepts all words from this language but rejects all other words. A FSA is an algorithmic approach how to decide whether a particular language is generated by a particular regular grammar.
Regular languages may also be described by regular expressions. This task is information common practice in information technologies. There is an algorithmic way to create a FSA from a regular expression and thus a way how to automatically decide whether a word belongs into a regular language or not.

Validation with Grammar

Regular language theory is often used for validation of whether a string (a program or a document) matches a regular grammar. This is a typical task which is done during compilation of a computer program where the compiler checks whether the program has correct syntax and can be compiled. Another example is validation of an XML document against a schema. An XML schema may be converted into a regular grammar and then decided whether a document is generated by that particular grammar or not.
Keeping validation algorithm regular grammar-based is convenient in terms of computational complexity. For example regular expressions may be evaluated in a linear time by converting them into deterministic finite state automaton (DFSA). For any input word N of length n and a regular expression R of the lengthm; N may be matched against R in the time O(n+2^m) .

Grammar-based XML Validation

One of the concepts for XML document validation based on regular grammars is regular hedge grammar. In general, hedge is a sequence of trees. In the XML terminology, we would call them elements. Basically an XML document is an example of a hedge.

Hedge

Hedge over a finite set of symbols S and variables V is either:

an null hedge (ε),
a variable fromV,
s<h> where s is a symbol from S and h is again a hedge,
or a concatenation of two hedges i.j.

This text uses same hedge notation as used by Murata Makoto in [HEDGE].

Figure 1. Example hedge notation

a<b c<f g<χ>> d<ψ> e>

Alternatively we can depict hedges also using diagrams. The same hedge again in a different notation.

Note that symbols occur in hedges only in non-leaf nodes and variables in leafs.

Any XML document can simply be converted into the hedge notation. Tags are represented through symbols and their textual content as variables (In this case we abstract from XML attributes). Such conversion is demonstrated within the next example.

Figure 2. XML document as a hedge

Here is an simple HTML document.

<html>
  <head>
    <title>Example</title>
  </head>
  <body>
    <p>Foo</p>
  </body>
</html>

The following hedge is equivalent to the previous document.

html<head<title<'Example'> body<p<'Foo'>>

In this case the set of symbols S = { html, head, title, body, p } and V = { 'Foo', 'Example' }

Regular Hedge Grammar

Now it is the right time to introduce the Regular Hedge Grammar (RHG) which is a mechanism for generation of different hedges. For a grammar there is an algorithmic way how to decide whether a particular word belongs to a language generated by that grammar.
This process in called validation in the XML terminology and any particular RHG which generates a set of hedges may be understood as a schema which defines all valid XML documents.
Validation of an XML document against a schema is a task of converting a RHG into a hedge automaton and try whether it accepts the input document or not.
Formal definition of RHG is very similar to the regular grammar definition described in the section called “Introduction”.
Regular hedge grammar is a formal grammar which is defined in [HEDGE] as a finite set of terminal symbols S, a finite set of non-terminals N, a finite set of variables V a set of production rules P and r which is a regular expression composed of non-terminals.

RHG production rules

Production rules in P are only of the following form.

n →v; where n is a non-terminal and v is a variable. Applying this production rules means a non-terminal is replaced by a variable.
n →s<r>; where n is a non-terminal, s is a symbol and r is a regular expression composed of non-terminal symbols. If this production rule gets applied a non-terminal is replaced by a terminal symbol which contains a sequence of non-terminals matching the regular expression r.

The language generated by the RHG is a set of hedges generated by applying the production rules to a set non-terminals which match the regular expression r.
The use of RHGs as a schema can be demonstrated on a simple example. Imagine, we like to define an simplification of the HTML language, where the root element is html which must contain one head and one body element in a sequence. Further, there is one title element in head and an unlimited amount of p or img in the body in any order.

Figure 3. Schema in RHG

The verbal definition may be expressed formally in DTD as follows.

<!ELEMENT  html (head, body)>
<!ELEMENT  body (p|img)*>
<!ELEMENT  head  (title)>
<!ELEMENT  title   (#PCDATA)>
<!ELEMENT  p   (#PCDATA)>
<!ELEMENT  img  EMPTY>

The same definition in the RHG notation.

S = {html, head, body, title, p, img }
V = { "#PCDATA" }
N = { N(html), N(head), N(body), N(title), N(p), N(img), N(pcdata) }
P = { N(html)  →  html<N(head), N(body)>
      N(head)  →  head<N(title)>
      N(body)  →  body<(N(p) | N(img))*>
      N(title) →  title<N(pcdata)>
      N(p)     →  p<N(pcdata)>
      N(img)   →  img<ε>
      N(pcdata)→  #PCDATA }

Automata-based Validation

The validation task for a particular schema (RHG) and a particular XML document (input word) is equivalent to a task to construct a Deterministic Hedge Automaton (DHA) and find out whether it accepts the input.
DHA is a finite state automaton (FSA) and as such it is defined with a finite set of symbols, states and transitional function which transit the automaton from one state to another, depending on the input symbol.
DHA have just few slight modifications; there are two transition functions, one for symbols ( Fs) and other for variables (Fv) and the result of Fs depends not only on the current state and the input symbol, but it depends on a set of states which are the target states for the child symbols or values in the hedge.

Here is the formal definition of a DHA taken from [HEDGE]. DHA is a sextuple (S, V, Q, F, Fs, Fv), where:

S is a finite set of symbols,
V is a finite set of values,
Q is a finite set of states,
F is a set of terminal states, a regular set over Q,
Fs is a function from S × Q* → Q such that for every q in Q and s in S, {q1 q2 ... qk | k >= 0, α(x, q1 q2 ... qk ) = q } is a regular set,
Fv is a function from V → Q

Figure 4. Example of the DHA process

Here is the very same HTML document which we created grammar for in Figure 3, “Schema in RHG”.

<html>
  <head><title>Test</title></head>
  <body>
    <img/>
  </body>
</html>

And this is how a DHA evaluates the transition functions.

Fs(html, Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)))

Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)) → Fs(head, Fs(title,Fv('Test')))
Fs(head, Fs(title,Fv('Test')))Fs(body, Fs(img, ε)) → Fs(body, Fs(img, ε))

Fs(head, Fs(title,Fv('Test'))) → Fs(title,Fv('Test'))

Fs(body, Fs(img, ε)) → Fs(img, ε)

Fs(title,Fv('Test')) → Fv('Test')

Fs(img, ε) → ε

Note that validation using RHG is used withing one of the current mainstream validation languages Relax NG, see [RNG].
The Fs function which accepts multiple states as parameters makes it difficult to depict a finite hedge automaton in a diagram, thus in the later text we will use a classical finite state automaton to demonstrate regular grammar-based XML validation process. The expressive power is the same and we may depict such automata more easily and make the diagrams more understandable.

Figure 5. XML Validating FSA

In the diagram you can see a FSA which validates XML documents against the schema described in Figure 3, “Schema in RHG”. For any symbol which has no explicit transition in the diagram the target state is ERROR. ERROR is not part of the final state set and thus any input document which leads the DHA to ERROR is considered to be invalid. Only FIN belongs to F; the set of terminal states.

Note, there are tree different arrows pointing from the B1 state, because body may contain p | img | ε.
The final state for an invalid document doesn't need to be ERROR. For example a document which would be missing the html end tag but otherwise it is correct will finish in the B3 state and thus the automaton won't accept it.
Using FSA we can express many common restrictions within XML trees, thus it is a suitable model for us at this stage. For example a sequence of head and body elements which has a strict order is expressed with the transition from H5 → H6 → B1.
In case we like to express an arbitrary order of child elements withing a parent we can use multiple transitions from one state as demonstrated in the B1 state pointing to P1 and I1.

Grammar and Diagnostics

Regular grammar-based validation is fast and straight forward, but does it really give suitable validation outputs? Experiences from the SGML/XML world shows that not always. With grammars it is easy to find out that something is wrong in the document, but it is more difficult to explain where exactly the problem occurred and extremely difficult to guide the author to resolve the issue or to explain the issue in a human understandable form.
One sort of problems with diagnostics can be explained with a example grammar for a simple Member of Parliament evidence. MPs are identified by name which is required and also each MP must have one assistant. The only exception is the Speaker of the Parliament who has two assistants. The door number of the MPs office is optional.

Figure 6. Schema for MPs evidence

<!ELEMENT  MP (name, (speaker, assistant)?, assistant, office?)
<!ELEMENT  office    (#PCDATA)>
<!ELEMENT  assistant (#PCDATA)>
<!ELEMENT  speaker  EMPTY>

Next we construct a FSA automaton to validate such grammar. Such automaton is depicted in the next diagram.

Figure 7. Validator for the MPs evidence grammar

Next consider several example of instances, their validation flow and the validation results.

Instances and validation

Nr	Document	Flow	Error	Explanation	Result
1	<MP> <name>Miloslav Vlcek</name> <speaker/> <assistant>Petr Mazalek</assistant> <assistant>Veronika Soumanova</assistant> <office>56</office> </MP>	START ↓ Q1 ↓ Q2 ↓ Q3 ↓ Q7 ↓ Q4 ↓ Q4 ↓ Q5 ↓ Q6 ↓ Q4 ↓ FIN			VALID
2	<MP> <name>Petr Bradsky</name> <assistant>Jaroslava Pokorna</assistant> <office>121</office> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ Q5 ↓ Q6 ↓ Q4 ↓ FIN			VALID
3	<MP> <name>Petr Bradsky</name> <assistant>Jaroslava Pokorna</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ FIN			VALID
4	<MP> <name>Miloslav Vlcek</name> <speaker/> <assistant>Petr Mazalek</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q3 ↓ Q7 ↓ ERROR	Expected <assistant> but was </MP>	In Q4, to transit to FIN the only non-error input could have been </MP> or <office>	INVALID
5	<MP> <name>Miloslav Vlcek</name> <assistant>Petr Mazalek</assistant> <assistant>Veronika Soumanova</assistant> </MP>	START ↓ Q1 ↓ Q2 ↓ Q4 ↓ ERROR	Expected </MP> or <office> but was <assistant>	In Q4, to transit to FIN the only non-error input could have been </MP> or <office>	INVALID

In the table above, the diagnostics for instance number 4 is appropriate. The validation engine expected a assistant tag but in the instance the MP tag has already been closed. The fix is quite obvious and clearly explained in the diagnostics. The author shall provide a second sibling assistant element.
A real problem occurs in the instance number 5 validation example. In this case somebody did obviously forgotten to mark the MP as the Speaker of the Parliament as nobody else may have two assistants assigned. The regular grammar-based diagnostics does not help to resolve such issue.
The location of the error is the second assistant element, but in reality the error is the missing speaker element after name. The error message claims we have a redundant assistant element, but in this case we are talking about the Speaker's document and we just forgot to add the speaker element indicator. In this case the validation result gives us no clue how to resolve the issue, as it does not mention the missing speaker element at all.
Moreover, the validation result guides us to delete the second assistant element which is completely wrong and in addition we would loose important information in order to make the document pass the validation.
There are many more examples where regular grammar-based validation diagnostics leads to misleading error messages, but this is not the only problem. As grammar-based validation is completely unaware of the semantics of the validated language there is no way how to attach reasonable domain specific diagnostics which would help the authors resolve issues more easily.

Quality of diagnostics

Compare the following two validation diagnostics

“Expected MP end tag or office but was assistant”.
“Missing speaker element. 'Miloslav Vlcek' has 2 assistants defined but he is not marked as the Speaker of the Parliament using the speaker tag. Only the Speaker is entitled to have two assistants, regular members may have only one. Either add the speaker element as the first child of the MP element or remove one of the assistants.”.

It is obvious that the second error massage gives a reasonable resolution to the user but the first message is completely useless, misleading and wrongly positioned. In the rest of the text we will learn possible approaches to get to the quality of diagnostics demonstrated in the second sentence in Quality of diagnostics.

Using Rules

Fortunately grammar-based validation is not the only validation approach which exists today. Rule-based validation languages are becoming more and more popular.
In principle, rule-based validation matches an input document against a set of patterns which are called rules. The result of such matching is a set of assertions and diagnostics. [RJ] stresses the distinction between the assertion text, which is a positive statement of what should be true in the document, and the diagnostics, which contains specific messages for describing, locating and correcting the problem.
To illustrate the difference, in Quality of diagnostics the Missing speaker element. message is the assertion and the rest of the message is diagnostics.
The rule-based approach is quite double-edged. At one side, when designing the schema we have a more low level control over the validation process and that is the reason we are able to attach domain specific diagnostics, but on the other hand, some definitions which are implicitly expressed by declaring an element in a grammar-based language need to be expressed in the rule-based approach explicitly, sometimes with more rules.
This is definitely error-prone, because forgetting one of the rules means we have an incomplete schema and there is no easy way how to detect it.
Another problem of the rule-based approach is performance. Where grammar-based validation can be performed in a linear time, in rule-based validation the execution time depends on the expressions we use within our rule assertions. We can easily get into the world of context-sensitive tasks and in case, performance is a important factor in a certain application, it is necessary to judge each individual rule in terms of performance. In contrast, schema designers who are using the regular grammar-based approach are free of expression. They may use any language constructs they like and keep their validation tasks in linear time.
Even there are downsides of the rule-based approach, it is worth studying it. Grammar-based validation did already reach its limits in terms of diagnostics and there are many real life validation problems were diagnostics is far more important than performance. For example validation of complex XML languages with hundreds of pages of specification like for example HTML, SVG, DocBook and others. In this case authors validate relatively small documents, but correct diagnostics is very important for them as they did not read the whole specification.
Moreover, there is a huge area of possibilities for future performance optimisation for rule-based languages. In the time when they are used as long as grammar based languages are used now, I sure there will be effective optimisation techniques which will minimize the performance handicap.

Schematron

To demonstrate the rule-based approach on a few examples, in this section we will have closer look into Schematron; the major standardized rule-based validation language.
Schematron is a simple XML-based schema language composed just of a few elements and attribute. There are only six main elements in Schematron which makes it very easy to learn. In this short introduction to Schematron we will mention just the six most important elements and their semantics which will allow us to understand how are rules being constructed.

Four most important Schematron elements

schema: the root container for patterns.
pattern: a named container for a set of rules
rule: a particular rule with a defined context within the validated document. Rules contain mixed assert and report elements.
assert: Assertion contains a statement about the document in a formal language which may be automatically evaluated against the document from within the rules context. In case the assertion is not satisfied, an attached plain text explanation of the problem is displayed to the end-user.
report: Report is equivalent to assertion, but the attached plain text is invoked in case the report's test expression is evaluated as TRUE (opposite to the assertion).
value-of: This element allows to enrich the diagnostics with values from withing the current rule context of the document to enhance the diagnostics with additional guidance for the author to resolve the reported issue.

Although Schematron uses XPath as the preferred formal language to evaluate assertions and reports against XML document, it is possible to use also other languages able to address nodes and values within the XML DOM tree; for example JavaScript is a good candidate.

Figure 8. Schematron rule example

Now we can return to our MP evidence problem and try to reach the level of diagnostics shown in the second message in Quality of diagnostics.

<sch:pattern name="MP Evidence">
    <sch:rule context="MP">
        <sch:assert report="count(assistant) > 0 and not(speaker)">
                Missing speaker element.
                '<sch:value-of select="name"/>' has <sch:value-of select="count(assistant)"/> assistant(s) defined but he is not marked as the Speaker of the Parliament using the speaker tag. Only the Speaker is entitled to have two assistants, regular members may have only one. Either add the speaker element as the first child of the MP element or remove one of the assistants.
        </sch:assert>
    </sch:rule>
</sch:pattern>

Note that in Schematron there is a way how to logically split assertion texts and diagnostics. To simplify the example, those two distinct parts of the error message has been put together as the report text.
In terms of performance optimisation, Schematron features the phases construct. Patterns may be organized into phases and during validation only a certain phase may be evaluated. Just in case there are no errors the next phase gets processed.

Expressiveness

It is difficult to say which approach (rules or grammar) is more expressive. The set of documents able to be described by a rule-based approach (Schematron) and a regular grammar-based approach are two distinct sets with a significant intersection. But there are documents which may be described with one approach but cannot be described with the other.
On the other hand there are many real life use-cases where Schematron can be used to model some restrictions which are really useful but they can't be expressed using regular grammar-based validation. This is caused by the fact that Schematron can operate with multiple contexts across the documents where grammar-based languages usually model just simple parent-child relationships withing the context of the current parent element. With Schematron we may for example condition the occurrence of an element by the values of an attribute in a completely different branch of the document. This is very powerful and has many real life use-cases. For example, using Schematron I was able to formalize additional restrictions expressed in the HTML specification only verbally; thus improving validation results and diagnostics for HTML document validation, see [PN1].

Figure 9. Schematron rule not expressible using a regular grammar-based approach

This example was taken from [PN1] and is based in my Schematron schema for W3C WCAG 1.0 specification.

<sch:rule context="html:abbr">
  <sch:report test="not(@title) and not(preceding::html:abbr[. = string(current())][@title])">
   WCAG 1.0 Checkpoint 4.2 (Priority 3) First occurrence of abbreviation in a document needs to have an title defined.
  </sch:report>
</sch:rule>

When thinking about suitability of grammar or rules for different validation tasks, we can easily come to a conclusion that a mixture of both approaches would bring the best of both worlds. This is the approach proposed in [PN1]. Such approach encourages to use a grammar-based language to enumerate elements and attributes and define their content model easily and to use rules to define advanced multi-context assertions with enhanced diagnostics. This approach was used to model extended HTML schemas in [PN1].

From Grammar to Rules

Another approach to combine rules and grammar is a to convert grammar-based schemas to Schematron rules. Such conversion may slightly enhance diagnostics by keeping simplicity of expression. Also such generated schemas become really platform/programming language independent as we don't need any validation engine for our specific schema language, but validation becomes a simple XSLT transformation and today an XSLT processor is present in vast majority of environments (even a web browser can be used as an XSLT processor).
Converting grammar to rules makes also integration of grammar-based language with Schematron easy as the generated rules may be simply merged with some additional rules defined.
There are clearly advantages to convert grammar-based schemas to rules, but how to achieve that? As we stated, those two approaches are not equally expressive, we already know that this conversion cannot be exhaustive. But in real life this may not be a big problem, because most of the reasonable constructs defined in regular grammar-based schema languages can be expressed using rules. But there is no simple algorithmic way how to convert a FSA into a set of XPath rules. So the task here is to go through different constructs of a particular grammar-based language and invent templates to convert them into Schematron patterns.

Figure 10. Grammar validation using pure rules

The following diagram show the validation process including conversion. A grammar-based schema is first converted to rules, rules are merged with other restrictions already defined using rules, rules are grouped into phases to optimise performance and enhance diagnostics. Finally, an input document is validated against the generated and merged rules.
The conversion as well as the validation process may be nothing else than a standard XSLT transformation.

The most tricky part of the diagram above is of course conversion to Schematron. There is currently no such converter and implementation of such conversion is under research. In the simplest case, [RJ] mentions a straightforward way how to get grammars into XSLT using the XSLT 2 build-in regular expression engine. With regular expressions we can express cardinality, sequence, choice and other constructs common in grammar-based schemas. The advantage is, with such conversion we can do validation tasks using a standard XSLT 2 transformer, but on the other hand, there is no improvement in diagnostics. Again we are just doing a regular grammar-based validation with a FSA.
Another approach is to break individual grammar-based restrictions into different kind or rule types. For example the grammar-based schema enumerates all allowed element and attributes. This may be converted into Schematron rule which checks that for every element and attribute in the input document the element or attribute names belong into a set of allowed names, otherwise an unknown element error is reported.
Also it is easy to extract content models for each element (what different children it is allowed to contain) and for each element create a rule that checks that all children belong to a particular set of allowed child elements for that particular parent.
Having such rules does not really bring domain related explanations, but on the other hand, grammar-based validators are usually not able to show all violated rules in a sub-tree as they already die on the first error occurrence as they move to a ERROR state and there is no way out. In contrast Schematron rules will show all diagnostics of all violated assertions in one validation run which is a diagnostic improvement. Also it is possible to group certain type of checks into phases and systematically point our validation effort at some sort of issues.
As result, we can have phases for validation of mistakes in element or attribute names, for broken content models, for required elements or attribute if whether they are present and for all sort of different groups of problems.
Moreover, one part of our rule-based schema may be auto-generated from a grammar schema, not forcing us doing a lot of implicit rules manually, but another part of the rules may be defined explicitly with domain specific diagnostics. Another big challenge of the converting method is to find effective ways how to merge the generated implicit rules with the explicit one and thus enriching the validation results with highly specific and domain related diagnostics.

Conclusions

This article explains principles of XML document validation. Regular grammar-based validation is explained in detail using examples and diagrams. One of the examples demonstrates limits of regular grammar-based validation diagnostics.
The aim of this article is to show that despite its efficiency, regular grammar-based validation diagnostics is inappropriate for some applications. Error messages may be located wrongly and their explanation may be confusing for the XML document author.
One of the options to overcome such limitations is to use rule-based systems instead. Rule-based languages are more expressive for some sort of restrictions and they have much better diagnostics as they allow to control the error message form by the schema author. On the other hand it is more difficult to model some sort of simple relationships and a big issue is optimization. It is difficult to judge the computing price of different rules. But although there are drawbacks it is necessary to investigate new ways in validation because classical grammar-based approach did reach its limit already long time ago in terms of diagnostics and currently it is insufficient for some sort of tasks.
Very promising seems a hybrid approach exploiting the best of grammars and the best of rules in one validation process. Rules may be directly embedded into grammar-based schemas.
Another way is to get simplicity of expression using the grammar approach but enhance diagnostics through converting grammar definitions to rules before validation.
All approaches have their pros and cons and they are more or less suitable for different purposes. But the lack of good diagnostics in grammar-based validation is an outstanding issue which needs to be coped with. That's why exploring novel ways in XML document validation is important.

Bibliography

[HEDGE] Murata, M.:Hedge automata: a formal model for XML schemata. Fuji Xerox Information Systems. 2000. Available at: http://www.xml.gr.jp/relax/hedge_nice.html

[PN1] Kosek, J., Nálevka, P.: Relaxed — on the Way Towards True Validation of Compound Documents. WWW2006, Edinburg, 2006. Available at: http://www2006.org/programme/files/pdf/4508.pdf

[PN2] Nálevka, P.: Doplňková validate HTML a XHTML dokumentů. University of Economics, Prague, 2003. Available at: http://nalevka.com/resources/thesis.pdf

[PN3] Nálevka, P., Kosek, J.: Advanced approaches to XML document validation. Extreme Mark-up Languages Conference, Montreal, 2007. Available at: http://www.idealliance.org/papers/extreme/proceedings/xslfo-pdf/2007/Nalevka01/EML2007Nalevka01.pdf

[RNG] Clark, J., Murata, M.: RELAX NG Specification. OASIS Committee Specification, 2001. Available at: http://www.relaxng.org/spec-20011203.html

[SCH] Jelliffe, R.: The Schematron Assertion Language 1.5. Academia Sinica Computing Centre, 2002. Available at: http://xml.ascc.net/resource/schematron/Schematron2000.html

[RJ] Jelliffe, R.: Converting XML Schemas to Schematron. O'Reilly XML Blog, 2007. Available at: http://www.oreillynet.com/xml/blog/2007/09/converting_xml_schemas_to_sche.html

[MI] Ivánek, J.: Základy matematické informatiky I: Informace a automaty. Státní pedagogické nakladatelství, 1991, Praha, ISBN: 80-7079-673-1.

Semantics in HTML

2010-05-27T11:07:00.000-07:00

PDF Presentation
semanticHTML.pdf.

HTML (HyperText Markup Language and all it's derivates is probably the most successful and widely used mark-up language ever. In has been used and missused over last decades for variety of very different tasks. This had a destructive effect on the language and significantly influenced it's semantics.
As a result semantics is withdrawing from HTML. Current HTML code is mostly just a sequence of semantically empty div span elements. The difference between those two is purely presenational and may be expressed as display: block/inline.
When talking about semantics in current current HTML, it is probably hiding in the class attribute, although it is mostly only used to map elements to their CSS presentation. Expressing semantics in class is better than no semantics at all, but the model is ill. Why not expressing the semantic category directly using the element name? Putting semantically empty div span sequences is error prone and redundant (this is the approach used by microformats). It more difficult to process such documents using XML tools (XSLT, XQuery...), it is more diffcult to write and maintain schemas for such languages.

Figure 1. Get rid of unnecessary HTML elements

There is something wrong in the following code fragment (a weather box in a HTML document).

<div class=”weather”>
  <span class=”title”>Weather Forecast</span>
  <span class=”city”>Prague</span>
  <span class=”temperature”>25&deg;C</span>
  <div class=”claudy”/>
</div>

We can get rid of redundant div span and express the semantic information directly. Our code becomes nicer and more readable and easier to process. Also it current mainstream browsers it gets rendered the same as the previous fragment, just few very small changes needs to be applied in the CSS.

<weather>
  <title>Weather Forecast</title>
  <city>Prague</city>
  <temperature>25&deg;C</temperature>
  <claudy/>
</weather>

So the lesson is: Today, one language (HTML) is not able to express all the complicated domains which occur in today's Web. There are: Internet shops, company presentations, newspapers, encyclopedias, chats, blogs, online community portals, webmail, online PIM with collaboration, porn-sites and many more applications on the Web and it is ill to map all their complex semantics into two or few more HTML tags. This leads only to unnecessary lost of semantics in the Web documents which makes them diffult to automatically process by machines and less accessible for humans.
Rather than using HTML it makes sense to either our own semantics or whenever possible use a common shared semantics which is understandable also to others. Thanks to XML namespaces and modularization of HTML this is the prefered and technically feasible approach. To keep as much semantics in Web documents use your own cocktail languages which is the best fit for what you are trying to say.
I call this approach Semantical Tagging and in fact it a lighweight approach to Semantic Web. Imagine you will have a shared XML language for estate agencies. Expressing your offert in such laguage makes it possible to run semantics queries against it. See the following example.

Figure 2. Use shared semantic languages in your documents

<r:flat xmlns:r="http://www.reality.com/offer" xmlns:r="http://www.reality.com/offer">
  <r:address>
    <r:street>Raichlova<r:num>2816</r:num><r:secNum>8</secNum></r:street>
    <r:postcode>15500</r:postcode><r:city>Praha<r:city><r:cityPart>Praha
13<r:cityPart>
   <r:country>Czech republic</r:country>
  </r:address>
  <r:rooms>
    <r:room type="bedroom" sq="18"/>
    <r:room type="kitchen" number=”25”/>
    ...
  </r:rooms>
  <r:price currency="CZK" vat="19">7250000</r:price>
  <r:finishDate>03/04/2008</r:finishDate>
  <r:floor>4</r:floor>
  <r:kmToCenter>25</r:kmToCenter>
  <img xmlns="http://www.w3.org/1999/xhtml/image/" src="/232/343434.jpg"/>
  <r:contact>...</r:contact>
  <r:orientation><r:side>north</r:side>...<r:orientation>
  ...
</r:flat>

Having data expressed in the such nice semantic way let you ask semantics queries:

All flats in Prague less than 30 kilometres from the centre with 5 rooms and at least 100 square meters for less than 6000000 CZK
All flats with a terrace at least 40 meters big
All flats in Prague with a garage and windows oriented on the east side which will be finished this year
All flats without annoying neighbours :)

This approach to semantic Web is lightweight and no so feature rich like for exmaple RDF/OWL, but it has several advantages and it may be the preferable approach. Semantic tagging of data is easy, it is similar to what we have now and it is processable with current mainstream browsers so there is not a big issue with backward comapatibility. It have one source of data used for both machines nad humans and this is an advatage. Imagine the price of a realproperty would in RDF (for machines) be two times smaller than in HTML (the version for humans). In such case, when sorting by price, the search engine will list such offer at the top, thus making it more accessed by humans even the price is not such a bergain. In semantic tagging this can't happen so easily. One source of data is also easier to maintain.
Although semantic tagging doesn't allow out of the box reasoning and other advanced features of RDF/OWL, it brings the most critical and most wanted and features of semantic Web and it can be very easily implemented in current Web environment.
For more details about this topic, please read the presentation in semanticHTML.pdf.