2

I work for a standards organization that publishes an exchange standard using XSD files.

These XSD files are being generated from a model with a tool, and now we want to change to a new tool.

Because these XSD's are part of a published standard, we can't change them functionally. Every XML that is valid for the old XSD should be valid for the new XSD, and ofcourse every XML that is not valid for the old XSD should be not valid for the new XSD.

Here's an example of a the different styles of XSD's. Both define exactly the same constraints, but in a different way.

The Old XSD tends to define constraints inline, whereas the new XSD defines the constraints on a type.

OLD

...
  <xsd:element minOccurs="1" maxOccurs="1" name="EnumNode">
    <xsd:complexType>
      <xsd:simpleContent>
        <xsd:restriction base="EnumBaseType">
          <xsd:enumeration value="Enum1" />
          <xsd:enumeration value="Enum2" />
        </xsd:restriction>
      </xsd:simpleContent>
    </xsd:complexType>
  </xsd:element>
...
<xsd:simpleType name="EnumBaseType">
    <xsd:restriction base="xsd:token">
        <xsd:enumeration value="Enum1"/>
        <xsd:enumeration value="Enum2"/>
        <xsd:enumeration value="Enum3"/>
        <xsd:enumeration value="Enum4"/>
    </xsd:restriction>
</xsd:simpleType>

NEW

...
<xsd:element name="EnumNode" type="EnumType" minOccurs="1" maxOccurs="1"/>
...
<xsd:simpleType name="EnumType">
    <xsd:restriction base="xsd:token">
        <xsd:enumeration value="Enum1"/>
        <xsd:enumeration value="Enum2"/>
    </xsd:restriction>
</xsd:simpleType>

Now the big question: How do I prove that two XSD's are functionally equivalent?

I'm looking for strategies or design ideas on how to tackle a problem like this.

We are talking about a few hundred XSD's ranging from 500 lines up to 5000 lines, so manual steps should be avoided as much as possible.

Idea 1: Generated sample XML documents

There are tools that can generate samples for a given XSD. A sample generated from the new XSD should be valid for the old XSD and vice versa. I've done that manually for a single XSD I converted, but the problem is that it will be hard to make this type of test exhaustive. It's probably almost impossible to create a sample for every possible testcase.

Idea 2: Compare Generated Code

There are ways to generate code (C#, Java,...) from XML Schema's. If the generated code would be abstracted enough from the actual XSD that might even work. I'm not very familiar with code generated from XSD's, but I'm afraid the code will match the XSD too much, making comparisons as dificult as with the actual XSD

Idea 3: Build an abstract document structure based on the XSD

The idea is to parse the XSD and build an internal abstract document structure based upon this. The document structure would be pretty close to the structure of an XML document that would be valid for this XSD. But instead of values, it would have contraints.

Two functionally equivalent XSD would then result in exactly the same document structure; which we could then compare.

In this example it could be something like

Node:EnumNode
{
   Constraints
   {
        minOccurs: 1
        maxOccurs: 1
        type: token
        values: {"Enum1", "Enum2"}
    }
}
11
  • 3
    If there is a way to generate randomised example documents for a schema, then you could use property based testing to demonstrate that all these examples conform to both schemas. This isn't a proof, but it's often close enough in practice.
    – amon
    Jan 23 at 13:46
  • 1
    I have no experience with xslt, but it might be a way to transform the XSDs into a form that's easier to compare. However, even if it is possible at all the effort might be too high, depending on the number of XSDs that need to be compared. Jan 23 at 13:53
  • 2
    You don't need the negative test, because if there existed a document that is not valid in schema A, but valid in schema B then your proof will fail in the second step where you show that every document in schema B is also valid in schema A. This will fail for the problematic document.
    – Wombatz
    Jan 23 at 14:21
  • 1
    @GeertBellekens: I guess the most promising approach is normalizing both XSDs into a comparable form. With that keyword in mind, I found this SO question from 2015: Normalize/canonicalize XSD schema schema for text comparison. I have no idea if that works for you.
    – Doc Brown
    Jan 23 at 14:31
  • 2
    I think #3 is the 'correct' approach. The other two approaches are more anecdotal evidence than proof, I think. I'm not sure you need to generate a document. You need to create two abstract syntax trees and verify they are the same. How or if you represent that in a file is optional.
    – JimmyJames
    Jan 23 at 16:07

2 Answers 2

1

Idea 1 is not a formal proof. However, most software are still not formally proven, but released after verification based on an extensive test suite. Many standard compliance verification procedures are also done using comprehensive test suites. Therefore it seems a pragmatic and valid approach.

One challenge will be that your generator tool generates representative edge cases. But the main challenge here, is to generate non-compliant documents to be rejected according to both XSD. This seems a relatively difficult topic if the generators on the market do not offer this feature.

Idea 2 looks like a false good idea to me. Indeed, it only shifts the problem to the programming language: there are high chances that the code is not identitical. So how to compare it? And how to mke sure that both code produce the same input for the same output?

Idea 3 looks like giving the most guarantees. Looking at the complexity to build the non-compliant examples in idea 1, this alternative could even be easier to implement.

For the record I also mention Idea 4, which would be to reverse engineer the models at the origin of the XSD and compare thise models. But abstract models are subject to interpretation and two different models could still represent the same reality. With idea 3 you are taking a similar approach but can avoid the pitfalls by "normalizing" the abstract structure (order of notes/attributes/etc...).

0

To prove they are the same you are going to have to write some code which loads the documents and enumerates the effective restrictions per node.

In this case the big question is whether the lower level restrictions add to or overwrite the ones from the type.

You will then have to extend this test to check all the other differences. Maybe you can find a xsd library which makes this easy.

However, I feel this is a bit of a waste of time.

  1. Since you have the current XSD. You could just not change them. Just save them as static files instead of generating each time.
  2. You really only care that the XSD are valid right? If there was a difference and the old one was wrong, presumably you would want to correct the mistake? In which case existing tests, or guarantees of valid generation should be fine.
  3. its 2023 switch to json already
1
  • 1. We don't plan to publish the XSD if nothing has functionally changed, but ff the requirements change, we might need to change the XSD, so we need all of them to be ready to be changed => that means generated in the new format. 2. I need the XSD's to be functionally the same as the previous version. If we need to change something, we only want to change that particular thing, and nothing else. 3. That doesn't really work like that in the real world. We can't simply force a whole industry to switch to JSON just because it's the newest shiniest thing. Jan 24 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.