Schema Algebra

[Joe English <jenglish@flightlab.com>]

A few comments on Jonathan Borden's "Schema Algebra" framework,
<URL: http://www.rddl.org/SchemaAlgebra >:

Definition [4] "schema equivalence" is a particularly elegant
formulation.  However, to make it truly useful you'll probably want
to place some sort of restriction on the kinds of transformations
allowed.  Under the current definition almost any pair of
schemas can be shown to be equivalent, for example:

    Take the list of all finite sequences of Unicode characters,
    and filter out those which are not well-formed XML documents
    conforming to the XHTML DTD; this gives you a bijection between
    Instances(XHTML) and the natural numbers.  Do the same for
    DocBook.  Now define t : XHTML -> DocBook as the function
    which takes the Nth XHTML document to the Nth DocBook document,
    and define t' : DocBook -> XHTML similarly.  <t,t'> exhibits
    an equivalence between DocBook and XHTML. [*]

One possibility is to restrict <t,t'> to "data-preserving" transformations,
where a transformation T is "data-preserving" iff for all documents D
Data(D) = Data(T(D)) and 'Data' is the function from XML documents
to sets of strings defined (in terms of the XPath data model [**]) as:

    Data(D) = { s : s is the value of a text or attribute node in D }

I think this restriction should rule out pathological cases like [*],
while still allowing transformations that reorder content,
change elements to attributes, et cetera.

([**] or in terms of the Infoset as "... s is a maximal contiguous
sequence of Character information items", or something like that).


Definition [10] ("Two URIs are equivalent when they map to the
same set of entities") is problematic.  There are plenty of URIs
which do not map to any entity at all (uuid: URNs, un-RDDLed
XML namespace names, etc.); under this definition all of them
are equivalent.  I think the only workable definition of
URI equivalence is the one used by RDF: "two URIs are equivalent
iff they are textually identical".  Any attempt to compare
URIs by examining the things they identify leads to trouble.

I don't quite understand the formula for Definition [12]:

    schema(URI<sub>S</>) := exists schema S such that
    	Entities(URI<sub>S</> <= Instances(S)

Is the subscript 'S' in 'URI<sub>S</>' the same as the
'S' bound by the existential quantifier?  Is 'schema'
supposed to be a predicate defined on URIs, a predicate
on Schema-subscripted-URIs, a function from URIs to schemas,
or something else?  The prose description speaks of "the"
schema whose instances include all entities corresponding
to the URI, but any entity is valid with respect to
an infinite number of schemas; which one is distinguished?


--Joe English

  jenglish@flightlab.com