Measuring Complexity of Domain Standard Speci cations using XML Schema Entropy

Abstract

XML schemas are used extensively in e-commerce standardization initiatives. Such XML-based standards de ne the structure and the semantics of messages that are used to implement business transactions in a particular industry domain (e.g. travel). The design of the document structures that form the message payloads is of key importance as once the speci cation is published it is di cult to re-design the documents without impacting on existing applications. Furthermore, such domain standards need to be maintained and evolved over long time periods, typically decades, without unduly increasing the complexity of the speci cation. The concept of software entropy has been used in the literature to estimate complexity and to express decline in quality, maintainability and understandability of software though its lifetime. In this paper we propose a Message Software Entropy (MSE) metric that estimates the complexity of XML message structures and we use this metric to study the complexity of a subset of the Open Travel Alliance Speci cation as it evolves over time.

Keywords

• complexity metrics
• XML schema evolution
• software entropy

-

XML schemas speci cations are used extensively in both vertical domain (e.g. Open Travel Alliance [ 1 ]) and horizontal domain (e.g. ebXML [ 2 ]) e-commerce standardization initiatives. Such XML standards de ne the structure and the semantics of messages that are used to implement business transactions in a speci c domain of interest (e.g. travel). The messages are typically delivered using SOAP [ 3 ] or REST [ 4 ] web services, so that in e ect the speci cation forms a basis for a large and complex SOA (Service Oriented Architecture) software system. The design of the document structures that form the message payloads is of key importance as once the speci cation is published it is di cult to redesign without impacting on existing applications. Furthermore, the longevity of domain standards requires that the design of the standard documents allows graceful evolution over a very long time period, typically decades, without unduly increasing the complexity of the speci cation. Many existing standard speci cations were designed to overcome the limitations of the Internet as it was at the end of the last century (i.e. high latency, poor reliability and slow response time) rather than with focus on software maintainability and evolution. This typically resulted in speci cations consisting of large complex messages suited for stateless communication, but di cult to maintain and evolve. Standard XML speci cations (e.g. OTA) typically contain hundreds of complex XML message schemas and thousands of schema elements. As these speci cations evolve over time incorporating new requirements their complexity further increases. For example, the OTA message schema that de nes the structure of the ight availability requests (OTA AirAvailRQ) contains 428 elements with multiple levels of nesting. Design of such XML schemas typically follows the Document Engineering approach [ 5 ] or a similar methodology that produces XML documents by aggregating data elements based on pre-de ned simple and complex types. For example, OTA message level schemas are constructed by aggregation of simple (OpenTravel Simple Types) and complex (OpenTravel Common Types, and Industry Common Types) schema elements [ 1 ]. This design approach while ensuring uniform structure and semantics of data elements can result in overlapping message schemas and excessive complexity, reducing the maintainability of the speci cation [ 6 ].

Evaluation of the quality of the design of XML schema has been the subject of recent research interest. In our previous work we have proposed data coupling metrics that evaluate interdependencies among of a set of XML message schemas by estimating the level of data coupling [ 7 ]. In this paper we focus on estimating the complexity of message schemas using the concept of Schema Entropy [ 8 ]. In the following section (Section 2) we review related work that addresses the problem of design quality of XML schemas. We then describe our proposal for the Message Schema Entropy (MSE) metric and an XSD Analyzer tool that we developed to compute the MSE metric (Section 3). In Section 4 we present experimental results obtained by analysing OTA Air (Airline) schemas. We note that the OTA message schemas were chosen as an example of open industry domain speci cations, and that we do not imply any criticism of the OTA schema design in this work. Section 5 presents our conclusions and outlines directions for further work. 2

Related Work

Evaluation of the quality of design of XML schemas has been the subject of recent research interest [ 9-11 ]. Ensuring XML schema design quality for industry domain speci cations presents a particularly di cult problem as the schemas are often developed in the absence of a domain data model [ 9 ]. Current work in this area includes research that focuses on identifying dependencies among schema elements and developing tools for automating the propagation of schema changes to all dependent components. Necasky, et al. proposed a ve-level XML evolution architecture with the top level Platform-Independent Model (PIM) that represents the data requirements for a particular domain of interest. PIM model is mapped into a Platform-Speci c Model (PSM) that describes how parts of the PIM schema are represented in XML. PSM then maps into Schema, Operational and Extensional level models. Atomic operations (create, update, and remove) for editing schemas are de ned on classes, attributes, and associations, and a mechanism for propagating these operations from PIM to PSM schema is proposed. Composite operations are constructed from atomic operations to implement complex schema changes [ 12-14 ]. Numerous XML schema quality metrics have been proposed primarily with the objective to measure various aspects of schema complexity. McDowell et al. proposed eleven metrics and two composite indexes to measure the quality and complexity of XML schemas. These metrics are based on counts of complex type declarations, derived complex types, number of global type declarations, number of simple types, element fanning (fan-out { number of child elements that an element has, and fan-in { number of times that an element is referenced by), etc. [ 9 ]. The authors formulate a Quality Index and a Complexity Index that estimate the quality and complexity of XML schemas based on a weighted values of the metrics. A metric analysis tool is provided for developers to verify the validity of the metrics in the context of speci c projects. The concept of entropy [ 15 ] has been adapted to the measurement of complexity of software and was initially applied to procedural software [ 16 ] and later to object-oriented design [ 17,18 ]. Ruellan [ 19 ] used an entropy measure to assess the amount of information contained in XML documents (information density) with the objective to reduce the size of XML documents and to improve processing speed of XML messaging applications. Thaw et al. .[ 20 ] proposed entropy-based metrics to measure reusability, extensibility, understandability of XML schema documents. Basci et al. [ 11 ] proposed and validated XML schema complexity metric that evaluates the internal structure of XML documents taking into account various sources of complexity that include recursion and complexity arising from importing external schema elements. The authors used the concept of Schema Entropy (SE) to assess XML schema complexity. SE is evaluated based on the complexity of schema elements as measured by fan-in and fan-out, and the number of simple elements that constitute individual schema elements. The SE metric was empirically validated using publicly available XML schemas, and the authors conclude that the metric provides a useful feedback when comparing schemas with equal number of elements [ 8 ]. In [ 21 ] Tang et al. apply an entropy-based measure to assessing the structural uniformity (structuredness) of XML documents. Two metrics are de ned: PathBased Entropy and Subtree-Based Entropy that attempt to measure the level of diversity of a set of XML documents. Unlike Basci et al. [ 8,11 ], the authors base the entropy calculation on XML documents, rather than XML schemas. Pichler et al. [ 6 ] developed a set of metrics to analyse the complexity of business documents with the objective of estimating the e ort involved in data element mapping between di erent business document standards.

Our proposal di ers from the above approaches in two important respects. Firstly, we estimate schema entropy by adapting an entropy-based metric originally developed for object-oriented design [ 17 ], and secondly our focus is on the evaluation of the changes in complexity of domain speci cations as the speci cations evolves over time. 3

Proposed Message Schema Entropy (MSE) Metric

The concept of software entropy has been used in literature to express decline in quality, maintainability and understandability of software though its lifetime. In our formulation of the Message Schema Entropy (MSE) metric we adapt the Class De nition Entropy (CDE) metric for object-oriented design described in Bansiya et al. [ 17 ]. The CDE metric calculates the frequency of occurrence of name strings in a given class. Calculation of MSE metric involves computing the frequency of occurrence of complex schema elements (i.e. schema elements that contains other elements and attributes) using the formulae: where: N = total number of unique complex elements in the message schema ni = number of occurrences of the ith complex element in the message schema

M = total number of non-unique complex elements in the message schema Pi = ni/M

Figure 1 shows a fragment of the schema of the OTA AirAvailRQ message illustrating the Speci cFlightInfo element. The OTA AirAvailRQ message is used to implement (web) service for ight availability inquiry and includes 428 elements with multiple levels of nesting. Elements are based on simple types (e.g. FlightNumber) or on complex types, as is the case with the Speci cFlightInfo element, which is based on the Speci cFlightInfo Type (extension of Speci cFlightInfo Type). MSE calculation is based on counting complex schema elements (i.e. elements based on complex types) and represents an approximation, as the internal complexity of individual elements is not taken into account. 3.1

XSD Analyzer Tool We have developed an XSD Analyzer tool that calculates the values of the MSE. XSD Analyzer allows the selection of message schemas for analysis and produces an output that includes the total number of non-unique complex schema elements (N1), the number of unique (distinct) complex schema elements (N2), the value of MSE, and counts of occurrences of complex schema elements. 4

Experimental Results

The OTA Air messages are a subset of the OTA speci cation and are used to implement services that support various business functions related to airline travel such as checking ight availability, ight booking, etc. For example, the Search and Availability of ights business function is implemented using the Air AvailabilityRQ/RS (request/response) message pair. OTA de nes common data types (OTA AirCommonTypes) for the airline messages that form a global type repository of XML Schema components (i.e. simple and complex type de nitions) used in the construction OTA Air messages. OTA di erentiates between complex types (types that contain multiple data elements) and simple types (types that contain a single data element). We use a subset of OTA Airline (Air) message schemas for our calculations. Open Travel Alliance typically publishes two (A and B) schema speci cations each year. We have used air message schema speci cations for our evaluation of schema complexity. Table 1 shows MSE values for 26 OTA Air message schemas for versions 2010B to 2013B. The total value of the MSE for the entire set of messages is also shown at the bottom of the tables. It is evident that MSE increases monotonically for all message schemas (with some minor exceptions) as new (enhanced) schema versions are released, indicating that the complexity of the OTA speci cation is increasing. The total MSE increases from a value of 143 for the 2010B OTA Speci cation to 154 for the 2013B OTA Speci cation, representing a 7% increase. This increase in MSE over the period of four years is probably not signi cant and indicates relative stability of the OTA messages schemas. The interpretation of the signi cance of the MSE values and the increase in MSE as new versions are released requires further analysis. Some insight into the relative complexity of the message schemas can be gained by comparing the MSE of individual messages schema with the value of MSE computed for the global schema elements (OTA AirCommonTypes) that include all the common elements shared across OTA Air messages. The MSE value for the OTA AirCommonTypes schema for the 2013B version of the OTA Speci cation equals to 7.55. It can be noted that the MSE value for the some of the message schemas (e.g. OTA AirAvailRQ, OTA AirBookRQ, OTA AirBookRS) exceeds this value, indicating that the complexity of these schemas is of similar magnitude as the complexity of the entire global schema. In addition to globally de ned schema elements individual message schemas include locally de ned elements that contribute to MSE, explaining this apparent inconsistency. 5

Conclusions and Further Work

Complexity of domain standard speci cations is a major factor inhibiting the evolution of speci cations and increasing the maintenance costs of domain applications. There is a need for reliable metrics that estimate the complexity of XML-based standard speci cation and can be used to identify excessively complex schema design early in the design cycle. In this paper we have proposed a Message Software Entropy (MSE) metric that estimates the complexity of XML schemas and we have used this metric to study the complexity of a subset of the Open Travel Alliance Speci cation as it evolves over a period of four years and seven version releases. The results indicate monotonic increase in schema complexity as measured by MSE, with the total MSE increasing from 143 for the 2010B OTA Speci cation to 154 for the 2013B OTA Speci cation, representing a 7% increase. This increase is probably not signi cant and indicates relative stability of the OTA speci cation. We have also noted that the MSE value for some of the message schemas is of similar magnitude as the value of MSE for the global schema elements OTA AirCommonTypes (7.55), indicating that the complexity of these schemas (e.g. OTA AirAvailRQ, OTA AirBookRQ) is similar to the complexity of the entire OTA Air global schema. The current version of the MSE metric is purely based on complex element counts and does not take into account the complexity of the individual elements or the number of levels in the message schema. This makes it easy to interpret the metric, but it also reduces the accuracy of the estimates of schema complexity. MSE metric represents only a rst approximation of the complexity of XML schemas, and we are working on re ning the MSE metric to take account a range of XML schema structural features.

Acknowledgments. George Feuerlicht wishes to acknowledge the support of Research Centre for Human Centered Technology Design at the Faculty of Engineering and Information Technology, University of Technology, Sydney, Australia.

References

1. OTA. OTA Speci cations . ( 2010 ) Available from: http://www.opentravel.org/ Specifications/Default.aspx

2. ebXML. ebXML - Enabling A Global Electronic Market. ( 2007 ) Available from: http://www.ebxml.org/

3. WC3. SOAP Speci cations . ( 2007 ) Available from: http://www.w3.org/TR/soap/

4. Pautasso , C. , Zimmermann , O. , Leymann , F. : Restful web services vs. big'web services: making the right architectural decision . in 17th international conference on World Wide Web . Beijing, China: ACM ( 2008 )

5. Glushko , R.J. , McGrath , T. : Document Engineering for e-Business . in Proceedings of the 2002 ACM symposium on Document Engineering (DocEng'02) . McLean, Virginia , USA: ACM Press New York, NY, USA ( 2002 )

6. Pichler , C. , Strommer , M. , Huemer , C. : Size matters!? measuring the complexity of xml schema mapping models . in Services (SERVICES-1) , 2010 6th World Congress on, IEEE ( 2010 )

7. Feuerlicht , G. : Evaluation of Quality of Design for Document-Centric Software Services . in Service-Oriented Computing-ICSOC 2012 Workshops . Springer ( 2013 )

8. Basci , D. , Misra , S. : Entropy as a Measure of Quality of XML Schema Document . The International Arab Journal of Information Technology , 8 ( 1 ): pp. 75 { 83 ( 2011 )

9. McDowell , A. , Schmidt , C. , Yue , K.B. : Analysis and metrics of XML schema ( 2004 )

10. Visser , J.: Structure metrics for XML Schema . Proceedings of XATA ( 2006 )

11. Basci , D. , Misra , S. : Measuring and evaluating a design complexity metric for XML schema documents . Journal of Information Science and Engineering , 25 ( 5 ): pp. 1405 { 1425 ( 2009 )

12. Necasky , M. : Conceptual Modeling for XML, ser . Dissertations in Database and Information Systems Series , IOS Press/AKA Verlag ( 2009 )

13. Necasky , M. , Mlynkova , I. : A Framework for E cient Design, Maintaining, and Evolution of a System of XML Applications . Proceedings of the Databases, Texts, Speci cations, and Objects, DATESO. 10: pp. 38 { 49

14. Necasky , M. , Mlynkova , I. : Five-Level Multi-Application Schema Evolution . Proceedings of the Databases , Texts, Speci cations, and Objects, DATESO 9: pp. 213 { 217

15. Shannon , C.E. : A mathematical theory of communication . ACM SIGMOBILE Mobile Computing and Communications Review , 5 ( 1 ): pp. 3 { 55 ( 2001 )

16. Mohanty , S.N. : Entropy metrics for software design evaluation . Journal of systems and software , 1981 . 2 ( 1 ): pp. 39 { 46

17. Bansiya , J. , Davis , C. , Etzkorn , L. : An entropy-based complexity measure for object-oriented designs . Theory and Practice of Object Systems , 5 ( 2 ): pp. 111 { 118 ( 1999 )

18. Olague , H.M. , Etzkorn , L.H. , Cox , G.W.: An Entropy-Based Approach to Assessing Object-Oriented Software Maintainability and Degradation-A Method and Case Study . in Software Engineering Research and Practice. Citeseer ( 2006 )

19. Ruellan , H.: XML Entropy Study . in Balisage: The Markup Conference ( 2012 )

20. Thaw , T.Z. , Khin , M.M. : Measuring Qualities of XML Schema Documents . Journal of Software Engineering and Applications 6 : p. 458 ( 2013 )

21. Tang , R. , Wu , H. , Bressan , S. : Measuring XML structured-ness with entropy , in Web-Age Information Management . Springer. pp. 113 { 123 ( 2012 )