Formal and Conceptual Models for XML

Erik Wilde

ETH Zürich

http://dret.net/netdret/docs/wilde-lmu05-xml-models

Outline

• About me
• Why a conceptual model for XML?
• What is a formal/conceptual model?
• Existing approaches and their shortcomings
• Requirements for an XML conceptual model

About Me (1)

• 50% ETHZ, 30% Lectures, 20% Self-Employment
• 50% ETHZ → Project Leader ShaRef
  • XML-based system and service for bibliographic data
  • Integration with ETHZ CMS and publication database
• 30% → XML Lectures at ETH Zürich and FH Aargau
  • XML and related technologies (XML Schema/XPath/XSLT)
• 20% → Consulting for ISB/eCH
  • Standards and best practices for e-government
  • XML, XML Schema, XML Namespaces, XML modeling

About Me (2)

• History: Document Processing, Computer Communications, Web Technologies, Information Management, Hypermedia
• General interest: Web Technologies
• Activities in different areas:
  • Information Management: ShaRef Project
  • Hypermedia: Text Fragment Identifiers (HT 2005 paper)
  • Content Management: Help/Documentation Tool (HSG)
  • XML for e-Government: Best Practices (eCH-0018)

Abstract

Today, XML is primarily regarded as a syntax for exchanging structured data, and therefore the question of how to develop well-designed XML models (in the sense of abstract descriptions of XML-based data models) has not been studied extensively. However, since applications are increasingly penetrated by XML technologies (Web Services), and because query and programming languages increasingly provide native XML support (XQuery and E4X), it would be beneficial to use these features to work together with well-designed XML models. In order to better focus on XML-oriented technologies in systems engineering and programming languages, an XML modeling language should be used, which is more focused on modeling and structure than typical XML schema languages, which tend to focus on details of the XML syntax. Currently, there is no well-established XML modeling language, but there are several approaches which could be used as a foundation for XML modeling, the two most important developments being formal models of XML, and ER-inspired conceptual modeling languages for XML. In this talk, we give an overview of existing formal and conceptual models for XML, and present a list of requirements for a language which would be close to the ideal XML modeling language.

Model Views of Potential XML Users

1. Document Processing
   • Modeling documents as XML documents
   • XML schema languages are made for this
2. Information Management/Database Design
   • Mostly relational models (ER and derivations)
   • Mismatches between ER and XML's hierarchical model
3. Software Engineering
   • Software engineering combines data and behavior
   • Classes are more than just documents

Usages of XML

1. Document Processing
   • Many document-oriented systems are XML-based
   • XML import/export are a must
   • XML's restrictions are (in most cases) acceptable
2. Information Management/Database Design
   • XML support in DBMSs (SQL/XML), XDBMS are available
   • "Modeling" using XSD or DTDs (or simply well-formed)
   • No good support for combining RDBMS/XDBMS
3. Software Engineering
   • XML as a way for persisting objects
   • UML as a way to model software systems
   • CASE tools for generating classes and their attributes

Missing: XML Conceptual Modeling

• XML schema languages are not conceptual models
  • They are primarily for validation (or type annotation)
  • Many logical-level issues (e.g. elements vs. attributes)
• XDBMSs need a conceptual model
  • Better abstractions than schema languages
  • Bigger scope (database-wide instead of document-wide)
  • Ideally providing an RDBMS mapping as well
• XML-centric software needs a conceptual model
• Creating XML schemas should become a mapping problem
  1. Define the XML conceptual model
  2. Choose the schema language (the logical model)
  3. Have an assisted process for deriving the schema(s)

Example: XML in Programming Languages

• In the early days: plain text files with many brackets
  • No support whatsoever, not even for parsing
• XML as add-on: DOM/SAX/JAXP libraries or classes
  • Data binding is cumbersome and error-prone
• Integrated data binding: mapping between XML and objects
  • in many languages it is hard to find a good mapping
  • for example, JAXB generates Java classes from XML Schemas
• XML-based languages: XML access as part of the language
  • XJ for Java: WWW2005 paper by Harren et al.
  • ECMAScript for XML (E4X): E4X Specification
• Currently based on XML Schema
  • Implemented in XJ, planned for E4X
  • An abstraction would be helpful for software designers

Conceptual Models for XML

• What is a Conceptual Model?
  • Usable for abstractions of real-world entities
  • Facilitates communicating about these abstractions
  • Provides help for implementing software systems
• What is a Conceptual Model for XML?
  • It is not a new schema language
  • Maps well to XML-like structures (hierarchical/referential/mixed)
  • Has features to control XML-specifics (element vs. attribute)
  • Conveys the essential information about XML-oriented models

XML Conceptual Modeling Languages

• Conceptual XML (C-XML), ER2004 paper by Embley/Liddle/Al-Kamha
  • Under development, claims to be "model-equivalent" with XML Schema
• ER extended for XML (EReX), XSym 2004 paper by Mani
  • Supports hierarchies and order, but does not support mixed content
• ER for XML (ERX), ER2003 paper by Psaila
  • Derivation of ER Models from DTDs (not for XML modeling)
• X-Entity, WIDM 2003 paper by Lósio/Salgado/Galvão
  • No support for hierarchies, order, or mixed content
• Extensible ER Modeling (XER), XML 2003 paper by Sengupta
  • Mixed content supported (without relations), no wildcard support
  • Heterogeneous Nested Relations (HNR) successor, technical report by Sengupta

Example XER Schema (1)

Example XER Schema (2)

• Relationships are associations between attributes and entities
  • Notable departure from ER's symmetrical model
• purchase is an Ordered Entity (Sequence)
• company is an Unordered Entity (All)
• item is a Mixed Entity
  • Allows mixed content (text mixed with elements)
• contactnum is a Generalization
  • Entity having several sub-entities (Choice)

Weaknesses of Conceptual Languages

1. Targeted on specific schema language
2. No or weak support for mixed content
3. Lack of formal foundation
4. No support for reference/hierarchy mix of XML
5. No support for multi-document scenarios
6. Non-deterministic Content

Formal Models for XML

• What is a Formal Model?
  • Usable for reasoning and proving properties
  • Defines a formally sound model
  • In most cases only used by specialists and under the hood
• What is a Formal Model for XML?
  • Captures the essentials of the XML data model
    • often disregards features such as namespaces and mixed content
  • Has features to model essential XML-specifics (sequences, recursion)
  • Can be used to formally test for properties of XML models
    • e.g., WWW2005 paper by Bex/Martens/Neven/Schwentick about XSD's EDC/UPA constraints
  • Not necessarily (extended) context-free grammars
    • MLTP paper by Rizzi about CFGs and exceptions

XML Formal Models

• Hedge Grammars, proposed by Murata and widely used
  • RELAX NG has been built around the model of hedge grammars
• (Extended) Context-Free Grammars, paper by Berstel/Boasson
  • proven to be equivalent to hedge grammars
• XGrammar (foundation of EReX), XSym 2004 paper by Mani
  • Status and relationship to other formal models unclear
• Heterogeneous Nested Relations (HNR), technical report by Sengupta
  • still under development
  • attempt to merge tree and relational models

Weaknesses of Formal Languages

• No graphical notation
• Not usable for non-experts
• No appropriate abstractions for modeling
• Not nicely embedded into real-world scenarios
  • User-friendly modeling language on top of the formalism
  • Investigation of mappings to established schema languages
• No combination of hierarchical/referential models

State of the Art

• First experiments for conceptual modeling
• Foundations of XML formal model have been laid
  • These need to be extended to cover relational aspects
• Opportunity to design an XML conceptual modeling language

List of Requirements (1)

1. Formal Foundation
2. Graphical Notation
3. Hierarchical and Referential Structures
4. Schema Language Mappings
5. Exceptions (Inclusions and Exclusions)
6. Non-deterministic Content

List of Requirements (2)

7. Treating XML Nodes Consistently
8. Model Groups
9. Reuse of Content
10. Generalized Mixed Content
11. Open Content
12. Intra- and Inter-Document Relationships

Conclusions

• XML conceptual modeling will become increasingly important
• There are a number of conceptual/formal approaches for XML
• But so far there is no established language
• A promising research area with "guaranteed" relevance

Thank You! Questions?

• BXML 2005 paper
• My Web page: http://dret.net/netdret/
• My Email: net.dret@dret.net