[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: RE : Comparison of Xml documents

• To: GARNIER Pierre <pgarnier@m...>
• Subject: Re: RE : Comparison of Xml documents
• From: Bob Foster <bob@o...>
• Date: Sat, 22 Nov 2003 04:21:21 -0600
• Cc: "'bob@w...'" <bob@w...>,'Alaric B Snell' <alaric@a...>, xml-dev@l...
• In-reply-to: <AE1FF313D41ED411B36600508B6DA517047EDF24@RIO>
• References: <AE1FF313D41ED411B36600508B6DA517047EDF24@RIO>
• User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.5) Gecko/20031007

GARNIER Pierre wrote:

> The original problem is the comparison of two XML documents of the same
> class defined by a schema.
> The question is : could we compare two documents by using the schema
> defining the class of documents.
> 
> Especially, knowing that two instances documents are of the same class, that
> their elements are the same, except that the order is not the same, is the
> schema give us enough infos to determine wether the instances documents are
> the same or not.
> 
> It is why I evoked three kind of ordering :
> 
> 1) order in a document according to the tags name (without specifying for
> tags with the same name)
> 2) order in a document according to a feature of tags with the same name
> Those two informations contribute in the definition of a class of documents
> (but is it enough to compare the documents on the order criteria?).
> 
> 3) order in the instances themselves. I explain :
> We have two tags that containing only one type of sub-tags with no order
> specification of type 1 or 2 in the schema, and those two tags contain the
> same sub-tags (ordered in the same way or not), how to specify a comparison
> information that permits to determine wether the tags are the same or not.
> Example :
>   A: <e1><e2 att="1"/><e2 att="2"/></e1>
>   B: <e1><e2 att="2"/><e2 att="1"/></e1>
> Tags e2 are not ordered because order info in the schema is "not ordered",
> but are they the same in this case?
> The one who design the class of documents should know.
> It depends on a semantic feature that is not possible to give in a schema
> with the different specs existing (XSD, relaxNG...) :
> as I know there is no schema spec allowing this (no "comparison" spec?).
> 
> Conclusion:
> When defining a class of XML documents, it should be nice if we could give
> "comparison" infos (two instances of the class are the same?) in association
> with "validation" infos (is the instance in the class?) that are, sometimes,
> not sufficient for the comparison.

Two excellent points!

We already have attributes, for which order is defined to be 
insignificant. Suppose that a regular grammar-based schema language 
extended this idea to elements, essentially adding a "set" operator to 
the regular model.

(This would be in addition to any existing unordered sequence operator, 
such as SGML's &, RELAX NG's & or XML Schema's 'all'.)

Then you could define that two documents are equivalent iff they contain 
the same elements with the same attributes, attribute values and 
contents after whitespace (and possibly Unicode) normalization, in the 
same order, except that order of attributes and "sets" is insignificant.

The naive approach to determining equivalence between two documents 
would be to define a recursive procedure that normalizes and collects 
element contents into sequences or sets, as appropriate, then compares 
the result for equality.

Is the naive algorithm sound, or are there deeper waters here?

Bob Foster

• Follow-Ups:
  • RE: RE : Comparison of Xml documents
    • From: "Bob Wyman" <bob@w...>

• References:
  • RE : Comparison of Xml documents
    • From: GARNIER Pierre <pgarnier@m...>

• Prev by Date: Re: Microsoft FUD on binary XML...
• Next by Date: RE: RE : Comparison of Xml documents
• Previous by thread: RE : Comparison of Xml documents
• Next by thread: RE: RE : Comparison of Xml documents
• Index(es):
  • Date
  • Thread