The official record of the Irish Houses of Government - A High volume XML success story   Table of contents   Indexes   OASIS - interoperability, conformance and standards for structured information
 

XML-Constraints with Scheme
 Erik   Meißner
  ZGDV e.V. (Computer Graphics Center) 
Email: meissner@zgdv.de
Phone: +49 6151 155-150
Fax: +49 6151 155-450 Web: http://www.zgdv.de Rundeturmstr. 6
 64283 Darmstadt   Germany
 
Biographical notice:
 
Erik Meissner studied Computer Science at the "Technische Universität Darmstadt" (Technical University Darmstadt), Germany. Since 1992 he is a member of the scientific staff of Computer Graphics Center (ZGDV) in Darmstadt.
 
ABSTRACT:
 workflow 
 
In actual documentation projects many authors are involved. They are organized in several teams, each with its own capabilities and knowledge. The work is defined in some kind of “workflow”. In most cases this is done on paper, because of the lack of tools organizing the work in a flexible way.
 
In complex authoring environments the usage of XML with its richer structure is a real advantage. But there is an almost infinite number of possiblities for our structure. If we add a DTD (like in SGML) to our XML-environment we can control the almost infinite number possibilities. The author of our multimedia documents can then only build multimedia documents belonging to one DTD by paying attention to their rules. But sometimes there are some more complex rules for our multimedia documents that we cannot describe in the DTD.
structure rules
 
If we think about the complex world of a XML-web with several different multimedia-entities, authored and maintained from a distributed authoring team, we see a lot of complex rules behind this XML-web, but there is a lack in describing these rules.
 
Therefore we built a graphic interactive system to describe such rules of the logical structure and the content of the element structure in a XML-web with additional multimedia content.
workflow trigger
 
Workflow-actions can then be build upon the finer granularity of XML-documents. Each elements can be a trigger or a destination for a workflow-event.
 

Motivation
 
In a complex authoring environment is the usage of XML a real advantage. The multimedia documents can have a richer structure than in a traditional texteditor (a.o.) or publishing system. This is because we can have a free hierarchical structure in the multimedia documents.
 
Furthermore we can describe rules for the structure. If we add a DTD (like in SGML) to our XML-environment we can control the almost infinite number possibilities. The author of the multimedia documents can then only build multimedia documents belonging to one DTD by paying attention to their rules. He can only insert elements and attributes defined in this DTD and he is responsible that these Elements are in the defined order and hierarchy of the DTD.
 
But sometimes there are some rules for our multimedia documents that we cannot describe in the DTD. For example there is no way to describe that the attribute of a given element has a value that is greater than the value of the same attribute of the parent element. Or we cannot check whether the number of chapter is the same as the number of authors in the author attribute.
 constraint 
 
There is a need for more complex rules to describe such constraints. If we think about the complex world of a XML-web with several different multimedia-entities, authored and maintained from a distributed authoring team we see a lot of these constraints behind this XML-web, but today there is no general way to describe these constraints.
graphic interactive
 
Therefore we built a graphic interactive system to describe constraints of the logical structure and the content of the element structure. In these constraints we can use the names of the elements, their structure, their attributes, and the content of the element like text or multimedia entities.
 
Another usage is the integration of a workflow management process. If the multimedia documents are created over several projects or several teams of authors we can inform another team or author if the content of an element is changed or a special constraint is violated. So we can build a very flexible and powerful distributed workflow/groupware solution and support with this solution the distributed cooperative work necessary for complex web-environments.
 
To handle these constraints it is necessary to integrate an extension in a number of tools. At first we need an integration in the authoring tool. The XML-editor must watch over our constraints and trigger some actions if they are violated. This can be done during editing time or during saving the multimedia document. These actions can contain sending an e-mail to another author or sending a workflow event to the workflow management system. Therefore is an integration of web-services like e-mailing or web-document creation useful. Then the editing process can be spread over the intra-/internet.
 
Another useful tool for the constraint watching is the multimedia document database. The database can allow only the check-in of correct multimedia documents. And if timebased contraint is violated, the database can trigger a complex workflow action. This is interesting for distributed cooperative work. Other authors, working on the same project, get instantly messages about new authoring task depending on the work of other authors.
 
Some goals for such a constraint system are:
  •  Consistency of multimedia documents and their document parts in a set of documents
  •  More quality in and between related multimedia documents. This means, for example, correct linking in and between document parts and multimedia objects can be integrated with special behaviour depending on their object-type
  •  Aspects of integration between different tools in an authoring environment
  •  Workflow, triggered by multimedia documents and their multimedia document parts, can be used to control the authoring environment. The document can control, with an integrated behaviour, the authoring process of itself and of other, related documents.
 

Constraints
 constraint 
 
An object-constraint consists of a constraint expression and a constraint action. The expression has one free parameter, instantiated with the actual object. The expression can become true or false in case of evaluation with the actual object as parameter. If the expression is true, everything is in order, if it is false, the object-constraint action is started. The object-constraint action must correct the world of objects to turn the false expression into a true one by changing the properties of the actual object. While the action changes the object world, other constraints can become false.
 
In some cases the system cannot find a constellation with all constraints expressions true. In this case the system can be in a stable state, but with some constraints false. This case can be checked by the system itself. Then it can be necessary to get an action from the user of the system.
 
In another case it can be, that the system gets in an oscillating state. One action turns a former true expression false, the depending action of this false expression turns the first one into a false expression and so on. This case must be prevented form the constraint designer. There is (until now) no way for the system to check this case.


Constraints and Constraint-Solver


The constraint-solver cycles through the document looking for violated constraints. Each constraint has an action assigned. This action is performed if the constraint is violated.

The designer of the constraint set must take care that the constraint set will turn the document into a stable state. This is necessary because two different constraints can trun each other into a false state and the document will oscillate between two document-states. In most cases the action is atrigger for a wokflow-event involving human tasks. So the problem of an “oscillating-document” is a rare one.
  
constraint-solver
 

Usage
 
Constraints are used in different areas of computing. They describe the correct solution of a problem by discarding the wrong solutions. In some cases this is easier to do than to describe an algorithm.
 

Computer Graphics
 
In the area of computer graphics constraints are used to describe the relationship between some graphical primitives and graphical objects. We can, for example, connect two objects and if one object is moved, the connection constraint is solved so that the second object is moved too.
 
With more complex constraints we can build “working” graphics or simulations, an engine can be moved like in reality, because the different parts are connect directly or with complex joints together.


Constraint in a Graphic Environment


In this picture we see a model of a mechanical device. This device is described with several parts. Each part results in a graphic object. Between these objects there are some constraints describing the behaviour of the joints. Now if we move one part, the other parts will follow moddeling the real behaviour of this device.(From )
  
 

Artificial Intelligence
 
Some artificial intelligence systems using constraint mechanisms to get a possible solution for a problem. With a set of constraints we discard more and more wrong solutions.
 

Optimization
 
Many optimization problems contain a difficult combinatorical problem. Constraint logic programming can be used to find a good solution for the problem, but it might be that this solution is not the best one. We have a set of possible solutions and we remove subset for subset from this set. At last we have a subset of good solutions. In this subset there is the best solution, but it can be, that a numerical computation to find the best solution is to expensive.
 
In the area of optimization problems we need obviously a rating function for each possible solution. This function can then be used to judge between two or more solutions.
 

Multimedia Documents
 
In the area of multimedia document formatting it is useful to describe the relationship between different multimedia document parts. In structured multimedia documents (for example XML) these constraints can be bound to the elements.
 

Addressing
 
In a set of constraints for an object (for example a graphical object or a XML-element) we have the object for itself and need other objects to describe some relationships between the objects. Therefore it is important for us to get addressing mechanisms. This can be, for a simple example, the id of an object (in XML the element id), or in a more complex example the answer to a question (we have a relation to all blue boxes or to all chapter-titles).
 

Properties
 
If we have the own object and the related objects then we need access to the properties of these objects. With the objects and their properties, describing the constraint expression is easier.
 
If the system needs some temporary data, we must add some temporary properties to the object. Sometimes we need persistence properties holding some data from one editing session to the next. Then it is necessary to define these properties in the object model itself. XML-elements can have these properties as attributes for example.
 

Language
 
Constraints can be expressed and defined in almost any computer language. A constraints system consists of the set of constraints and a constraint solver. The constraint solver cycles through the set of constraints searching for an unsolved constraint. It is possible to build an event driven constraint solver. The solver is activated for example from user input.
 
If the constraint solver finds an unsolved constraint he looks for an action bound to this constraint. This can be an user alert or it can be an algorithm changing some properties of an object to make the unsolved constraint a solved one.
 
Also we can use almost every computer language there are some among them that are used more than the other. For example there are special dialects of prolog or lisp/scheme in this area used. These languages have the possibility to be extended at runtime to describe new sets of constraints. This is useful if our object world can be extended (new graphical objects can have new constraints, new element-types in a structured multimedia document can use a new set of constraints).
 

Implementation
 
In our demo implementation for constraints in a XML-environment we need a way to describe the set of constraints, an authoring tool and perhaps some other XML-tools.
 

Scheme
scheme
 
To describe the contraints we looked for different languages. There are some languages to describe constraints in a programming environment such as OCL (object constraint language). For practical reasons we want to describe the constraints in a language that can be interpreted from our system. At this time we choose scheme, a special kind of lisp. Scheme is also used in DSSSL, the style language of SGML.
 
We can add functionality at runtime and there are some implementations as library. These libraries can be added to other tools. We chose a library with a small footprint in our system and with no need for a special environment or resources, so we can build this library to most of the systems.
 
Another aspect of the constraint language is the possibility to get a graphical visualization of the different constraints, the depending multimedia documents their data and the following actions in case of violation of these constraints.
 
In a graphical representation of the set of constraints we can visualize the addressing scheme and the properties of the addressed elements.


Graphical Representation of the Related Objects


The document-tree contains each document object. In case of XML these are the XML-elements. Between these elements the constraints build some relationships. These relationships can be graphically represented.
  
 

FrameMaker+SGML
 
The implementation of a demonstrator of the contraint system is based on the FrameMaker+SGML sgml-editor. The application programming interface allows us to build new functionality to the editor. With this programming interface we added a scheme library to the editor and defined a set of new scheme-functions to address the multimedia document and to implements some action in case of violated constraints.
 
The constraints and their relationship to the different elements are declared in the EDD, the special implementation of the DTD in FrameMaker+SGML.


Constraint-Action bound to an Element


In our demonstrator we build a scheme expression out of the graphical constraint-description. This expression is bound to a FrameMaker+SGML-element. The constraint solver cycles through the document searching such expressions.

The main part of this expression is hidden in a data-file. This data-file is interpreted at startup-time.
  
 
In a different implementation we have the set of constraints in a separate file.
 

XML-/SGML-Database
 database 
 
The second demonstrator on the way is based on astoria, a sgml-database. In astoria the constraint system watches the check in, the check out and the timeline of the multimedia documents.
 workflow 
 
In this environment we can handle the set of constraints in the database itself. The database can then be used as a central control station for some kind of workflow activities in a computer supported cooperative work environment.
 

Usage
 
The system or parts of the system can be used for different purposes or environments. We test the constraint system in different areas. The first test is an authoring environment based on FrameMaker+SGML.
 

Authoring Environment
 
The system can be used for different purposes. First we can check the consistency of the multimedia document, the multimedia document-structure and the multimedia document-content. It is possible to look if an element-content is correctly dated and timed. And we can look, if a term is described in another multimedia document.
 
Another usage is to check cross-references and hyperlinks more consequent. Perhaps we want only cross-references to multimedia documents of a given author. Or we need to check if cross-references does not have their source and destination in the same chapter.
 
If we add date and time attributes to some elements we can check if the chapter with the reference is created or changed after the destination element of the reference element. To handle the violation of such a constraint it is possible to send an e-mail over the net with an action request. Or we can create a new web-page with a todo-list for another author.


A Violated Constraint


If the demonstrator finds a violated contraint (with its expression false) it can mark the section. We can also add some complex action, but this cannot be shown in a simple screenshot...
  
 

Web-Management
 
In a web-environment based on a XML-database we can handle the constraints in the database itself. With the database we can also address multimedia document objects in other multimedia documents. So we can build constraints to check the linking from an to other multimedia documents for example.
 

Workflow
 
With such an integration of the web, we go straight forward to a system with workflow-management capabilities. It can be used in a distributed authoring environment to manage multimedia document data in a smaller granularity.
 

Outlook
 
On base of the experiences from our demonstrator we will build in the next steps a complete authoring environment. The tools in this environment will handle different action requests from violated constraints. A workflow management system will also be integrated.
 
Furthermore we think about the integration of constraints to/from other data, like multimedia content. In this area it is interesting to integrate vrml and XML. In VRML it is possible to address single graphical objects in the object scene. If this graphical object scene is expressed in XML we can use some of the work directly for VRML. In this area the development of XML3D is very interesting for us.
 
Other work will be done to integrate more kind of tools in an environment and to add a real workflow-management-engine.
 
Bibliography
GRUBOLS1
Thomas R. Gruber and Gregory R. Olsen, Theory PARAMETRIC-CONSTRAINTS, http://www-ksl.stanford.edu/people/brauch/demo/parametric-constraints/index.html
GRUBOLS2
Thomas R. Gruber and Gregory R. Olsen, Theory COMPONENTS-WITH-CONSTRAINTS, http://www-ksl.stanford.edu/people/brauch/demo/components-with-constraints/index.html
IBMOCL
IBM, The object Constraint Language,http://www.software.ibm.com/ad/ocl/
SCED
Sced: Constraint Based Scene Design, http://gd.tuwien.ac.at/graphics/sced/sced.html
POUCLP
Pountain, D., Constraint Logic Programming, http://www.byte.com/art/9502/sec13/art3.htm
BOLIMA
Borning, A., Lin, R., Marriott, K., Constraints for the Web, ACM Multimedia 97 - Electronic Proceedings, http://www.acm.org/sigmm/MM97/papers/borning/constraints.html
The official record of the Irish Houses of Government - A High volume XML success story   Table of contents   Indexes   OASIS - interoperability, conformance and standards for structured information