Lists Home |
Date Index |
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?).
> 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?