XML Spaces

----
XML Spaces
URL:http://monkeyfist.com:8080/morgue/technology/linda-cms/xmlspaces
Subject: 
----

                         XML-Tuples and XML-Spaces, V0.7

              David "Uncle Dave" Moffat, ATN ITD, UNC-CH, 25 Mar 99

 [This research paper, and the terms "XML-Tuple" and "XML-Space" are ©1999 David
                                   V Moffat.]

                        Specifications development path:

                      Version 0.5 - no attributes, no DTDs;

                       Version 0.7 - attributes, no DTDs;

                         Version 0.9 - attributes, DTDs;

                              Version 1.0 - final.

                     Overview of Tuple Spaces and XML-Spaces

Introduction

This paper describes an implementation of tuples and tuple-spaces using XML.
Tuple spaces were first described by David Gelernter [1], long before the advent
of XML.

In general, a "tuple" is simply a list of values, such as (12, 7, 48) or ("ra",
"gg", "mo", "pp") or ("Karl", 33, 125.7). A tuple-space is a public repository
or buffer that can contain tuples. The tuple-space serves as an associative
memory, in that tuples in the tuple-space can be accessed by matching some or
all the elements of the tuples to values or types presented in a "template",
which is simply a tuple set up for this matching. Client programs can register
to be notified of changes in a tuple-space.

Current implementation of tuples--"JavaSpaces" [2], by researchers at Sun
Microsystems, and "T Spaces" [3] by researchers at IBM--build upon the generic
concept of tuples and tuple-spaces in various ways: the tuples are Java objects;
there are more sophisticated ways to match and to access the tuples (IBM); the
tuples can be stored in databases for persistence (IBM). The work in the present
paper is inspired by the more sophisticated approach of the researchers at IBM.

To anticipate this paper's summary, using XML for the tuples and for
commands--that is, using XML, not the objects of a particular language, as the
"native" representation--brings tuple-spaces to new heights of generality and
flexibility.

Some Definitions

An XML-tuple is just a list of data fields expressed in XML. The list can have
one, two, three, or any number of fields. A data field or field is simply
XML-tagged data. For example, this:

   <name>Ralph</name>

is a field; therefore, this:

   <name>Ralph</name>

   <age>33</age>

   <weight>190.7</weight>

is an XML-tuple--but, then, so is a single field. The syntax and names are
important, but they can be on one line or spread across lines, indented, and so
on.

In generic tuples, the type of a field and the value of the field are its
significant properties. In XML-tuples, the field tag name replaces the field
type in function, and the value property has the same significance. Of course,
all XML-tuple field values are just strings.

The value of a field is the collection of all its free-form text, with no
leading or trailing white-space. This is true regardless of whether or not there
are sub-fields interspersed with the text within the field.

An XML-space is a tuple-space made up only of XML-tuples--that is, a public
repository or buffer that can contain XML-tuples. An XML-space has a name, by
which it is referenced, and it is hosted on a server, along with any number of
other (and other-named) XML-spaces.

Overview of XML-Spaces

XML-tuples can be written into, and read from, XML-spaces. Writing is done
simply by sending an XML-tuple to the XML-space. Reading is done by presenting
the XML-space with a "template", which is an XML-tuple whose tags and values are
to be matched against XML-tuples already in the XML-space. If the template
matches a stored tuple, a copy of that tuple is returned. There is also a read
operation that actually removes the matched tuple from the XML-space.

The normal read operations return empty-handed if the template does not match
anything that is stored in the space; other read operations will not return
unless the template matches, actually waiting, if necessary, for a matching
XML-tuple to be written.

Another read operations, called a scan, returns copies of all the tuples that
match a template, instead of returning just the first one to match, as the
normal reads do. And there are operations for database-like queries, even using
boolean matching conditions.

XML-spaces can be used for communications buffers. A client application can
register with an XML-space, giving it a template to be matched, and an
operation, such as write. If any other client application writes an XML-tuple
that matches the template, the XML-space notifies the registered application,
sending it a copy of the new XML-tuple. This feature can be used to implement
distributed or collaborative applications.



                    Basic XML-Space and XML-Tuple Operations

Creating and Communicating with an XML-Space

Most communication with an XML-space is by way of a single entry point, the "do"
method, using commands and parameters expressed in XML. However, a client must
first create or connect to the XML-space. The way to do that is:

   XMLSpace xs = new XMLSpace("MySpace", "server.mine.org");

where the parameters are the name of the space, which is created if it does not
exist, and the location (host and port) where the XML-spaces server resides.
From then on, the returned object's "do" method is used for most communication.
There are a few other methods for managing the XML-spaces.

Writing XML-Tuples to an XML-Space

Commands to an XML-space are formatted as XML-tagged entities enclosing the
parameters. To write an XML-tuple, use the "write" tag to enclose the data
fields--the XML-tuple--like this (this has been formatted to highlight the
structure of the XML):

   String strTuple = "<write>" +

                      "   <name>Ralph</name>" +

                      "   <age>33</age>" +

                      "   <weight>190.7</weight>" +

                      "</write>";

   String strResult;



   strResult = xs.do(strTuple);

The string returned, if the operation is successful, is the same as the XML that
is sent, except that the "write" tag is replaced by the "tuple" tag. Otherwise,
an error will be returned, as XML, in a format like this (specific messages will
be described in an appendix):

   <error>

      The tuple could not be written.

   </error>

In all further examples, assume that the XML must be put into a string, and that
xs.do is called to communicate with the XML-spaces server.

Writing Several XML-Tuples at Once

You can write several XML-tuples with a single call; just concatenate them into
one string:

   <write>

      ..the three fields

   </write>

   <write>

      ...the three fields

   </write>

   <write>

      ...the three fields

   </write>

It is an error to have any tags other than "write" in the batch of tuples.

Matching XML-Tuples

To match an XML-tuple, you create a template that describes how the matching is
to be done. A template is simply an XML-tuple, again, but the data fields might
or might not have values in them.

If the template has the fields "name", "age", and "weight" in it, then another
tuple must have those fields if it is to match.

Furthermore, if the template has a value in any of the fields, then a tuple will
match only if it has the same value or values in the corresponding field or
fields. The template fields that have no values are like "wild cards", matching
fields with the same tags, regardless of their values.

For convenience, an empty tag, such as <abc/>, will match either another empty
tag like itself, or a tag element that has no value, such as <abc></abc>.

If a tag in a template has an attribute name and value, then a tuple will match
only if its corresponding tag has the same attribute name and value. But if a
tag in the template has only the attribute's name, then a tuple will match if
its corresponding tag has either the attribute name alone, or the attribute name
and value. The attribute name without a value in the template's tag is a
presence test for that attribute.

An empty tag with an attribute, such as <abc xyz=23/>, will match either another
empty tag like itself, or a tag element that has the attribute but no tag value,
such as <abc xyz=23></abc>.

Finally, note that the fields in tuples are not order dependent; the tuple
<a/><b/><c/> will match the tuple <c/><a/><b/> and all other combinations of the
three fields.

Reading XML-Tuples from an XML-Space

To read a copy of an XML-tuple that matches a given template, use the "read"
command tag to enclose the template like this (showing just the XML) in the call
to xs.do:

   <read>

      <name/>

      <age>33</age>

      <weight/>

   </read>

The example will match any stored XML-tuple that has the fields "name", "age"
and "weight", where the age is equal to (the string) "33". A copy of that tuple
is returned by the call to xs.do; if there are no tuples that match, an empty
tuple is returned. The copy of the tuple will be returned as a tuple enclosed in
the "tuple" tag, like this:

   <tuple>

      <name>Karl</name>

      <age>33</age>

      <weight>135.2</weight>

   </tuple>

If no matching tuple was found, the returned "tuple" will be "null":

   <tuple>

      null

   </tuple>

In case there was actually an error while reading, an appropriate message will
be returned, enclosed in the error tag, as described earlier.

There is no way to know how many XML-tuples matched the template, what order
they were written, whether another application has also read the one copied, or
which one was copied.

To read a copy of an XML-tuple that matches a given template, and remove that
tuple from the XML-space, use the "take" command tag to enclose the template,
like this (showing just the XML):

   <take>

      <name/>

      <age>33</age>

      <weight/>

   </take>

The matching occurs as described earlier, and the matching XML-tuple, if any, is
removed from the space as the copy is returned to the client, enclosed in the
"tuple" tag. Again, an error or a null tuple could be returned.

If, for some reason it is not permissible, in the client's logic, for the read
or take command to return without a matched XML-tuple, use the "waitToRead" or
"waitToTake" command tags instead. When these are used to submit the template to
the XML-space, the xs.do call will return (successfully) if it finds a matching
tuple already in the space; otherwise it will wait until another client writes a
matching tuple to the space, then return a copy of that.

Reading Several XML-Tuples at Once

To read copies of all XML-tuples that match a given template, use the "scan"
command tag to enclose the template like this:

   <scan>

      <name/>

      <age>33</age>

      <weight/>

   </scan>

The example will match all stored XML-tuples that have the fields and values
described by the template. Copies of the matched tuples will be sent back as a
list of tuples, each enclosed in the "tuple" tag, like this (imagine that each
tuple has the "name", "age" and "weight" fields:

   <tuple>

      ..the three fields

   </tuple>

   <tuple>

      ...the three fields

   </tuple>

   <tuple>

      ...the three fields

   </tuple>

Once again, one empty tuple or an error message could be returned.

To read copies of all XML-tuples that match a given template, and remove those
tuples from the XML-space, use the "scanTake" command tag to enclose the
template like this:

   <scanTake>

      <name/>

      <age>33</age>

      <weight/>

   </scanTake>

The example will match all stored XML-tuples that have the fields and values
described by the template, and return a list of copies, as scan does, but it
also removes all the matched originals.

Counting the Number of Matching XML-Tuples

To get a count of the number of XML-tuples that match a given template, use the
"count" command tag to enclose the template like this:

   <count>

      <name/>

      <age>33</age>

      <weight/>

   </count>

The example will match all stored XML-tuples that have the fields and values
described by the template, and return how many it found. The value is returned
in this format:

   <count>

      7

   </count>

If an error occurred, an appropriate error will be returned, enclosed in the
"error" tag.

Registering for XML-Space Events

To register to be notified when certain I/O events occur in an XML-Space, your
application needs to implement the XMLSpaceListener interface, then register as
a listener and give the space a template to match the listened-for operation and
XML-tuple format. The interface is:

   interface XMLSpaceListener {

      handleXMLSpaceEvent(String tuple, //matched tuple

                         String space, //XML-space name

                         String host,   //space's server/port

                         long lNum, //# events so far

                         boolean bErr); //true iff an error

   }

When your application's implementation of this is called, the XML in the "tuple"
parameter will be a copy of the tuple you wished to be notified about, but
instead of being enclosed in the "tuple" tag, it will be enclosed in the tag for
the operation that you wanted notification about (as described below).

Since you are likely to be queuing the notifications, the lNum value (which is
monotonically increasing over all notifications) will help you retain the order
in which the notifications to your XMLSpaceHandler occurred.

If the "bErr" parameter is true, no tuple will be returned; instead the XML the
"tuple" parameter will be an "error" tag enclosing an error string that denotes
the specific error (to be described in an appendix).

Given that your application has implemented the XMLSpaceListener interface, it
can register for events with this call:

   xs.addXMLSpaceListener(this, tplt);

The "tplt" parameter shown here is simply an XML template describing a tuple to
match and the operation to be notified about. For example, to be notified every
time any client writes any tuple of the format we have been using, send this
template:

   <write>

      <name/>

      <age/>

      <weight/>

   </write>

Of course, you can give specific values in any of the fields to make matching
more specific, and you can register for as many different operations and
templates as you need.



                        Database Operations on XML-Spaces

XML-Space Queries

The XML-Spaces implementation extends the generic tuple-spaces matching
operation with more sophisticated queries.

The basic query behaves just like a scan, and looks like one, except that the
"query" tag is used instead of the "scan" tag:

   <query>

      <name/>

      <age>33</age>

      <weight/>

   </query>

As for the read and scan, copies of the matched tuple or tuples are returned as
a tuple or list of tuples (each with the "tuple" tag), or else a null tuple is
returned (no match) or an error is returned.

The more interesting and powerful queries are done by nesting two complete query
tuples inside other tags. The other tags are "andQuery", "orQuery" and
"rangeQuery".

ANDing XML-Space Queries

An andQuery matches only if two given query templates match. The format of an
andQuery, assuming the XML-tuples we have been using in all the examples, looks
like this:

   <andQuery>

      <query>

         ...the fields with values or empty (wildcards)

      </query

      <query>

         ...the fields with values or empty (wildcards)

      </query

   </andQuery>

The andQuery is successful only if any XML-tuples in the XML-space match both of
the query templates. If so, copies of the matching tuples are returned, each
enclosed in the "tuple" tags. Of course, a null tuple or an error could also be
returned.

ORing XML-Space Queries

The format of the orQuery is like that of the andQuery, but with a different
meaning:

   <orQuery>

      <query>

         ...the fields with values or empty (wildcards)

      </query

      <query>

         ...the fields with values or empty (wildcards)

      </query

   </orQuery>

The orQuery is successful only if any XML-tuples in the XML-space match either
one or both of the query templates. If so, copies of the matching tuples are
returned, each enclosed in the "tuple" tags. Of course, a null tuple or an error
could also be returned.

The format of the rangeQuery is like that of the orQuery and the andQuery, but
with yet another meaning:

   <rangeQuery>

      <query>

         ...the fields with values or empty (wildcards)

      </query

      <query>

         ...the fields with values or empty (wildcards)

      </query

   </rangeQuery>

The rangeQuery is successful only if any XML-tuples in the XML-space have values
that lie within the ranges established by the query templates. If so, copies of
the matching tuples are returned, each enclosed in the "tuple" tags. Of course,
a null tuple or an error could also be returned.

The matching for the rangeQuery is somewhat more complex than the others. The
first query tuple gives the low limits of the ranges, while the second gives the
upper limits. If a lower or upper limit is not specified (like a wildcard) it
means that there is no limit in that direction.

Nested Queries

The four basic queries can be nested to specify even more specific queries. For
example:

   <orQuery>

      <andQuery>

         <query>

            ...the fields with values or empty (wildcards)

         </query

         <query>

            ...the fields with values or empty (wildcards)

         </query

      </andQuery>

      <rangeQuery>

         <query>

            ...the fields with values or empty (wildcards)

         </query

         <query>

            ...the fields with values or empty (wildcards)

         </query

      </rangeQuery>

   </orQuery>

This example succeeds if either the andQuery or the rangeQuery succeeds.

XML-Space Transactions

To bundle writes and reads into batches such that all commands in the batch must
succeed or else none is executed at all, use transactions. Transaction
operations are specified with the "transaction", "commit", and "abort" commands.

For example, to begin a transaction, simply send an XML expression with the
"transaction" tag:

   <transaction/>

As usual, the command always returns something, and this case it is either the
same "transaction" element, or an error.

After the transaction command returns successfully, you can (for example) write
several tuples to the XML-space, individually or like this:

   <write>

      ..the fields

   </write>

   <write>

      ...the fields

   </write>

   <write>

      ...the fields

   </write>

If everything works as expected, the entire transaction can be committed, using
the "commit" tag:

   <commit/>

However, if any of the writes was not successful, and you wish to withdraw all
the operations in the transaction, then abort it, using the "abort" tag:

   <abort/>

As usual, the commit and abort commands either return themselves or an error.



                     Extended Database Queries on XML-Spaces

Introduction

Because XML notation is very extensible, and because XML-tuples have
user-defined tags instead of primitive types or compiled types (objects),
templates can be manipulated or created at run time to accomplish extremely
flexible and powerful queries.

Matching to Different "Depths"

In unrestricted XML, fields can be nested into hierarchical structures. For
example, a person might be represented as:

   <name>

      <last>Kugelschreiber</last>

      <first>Karl</first>

   </name>

   <address>

      <street>1234 Knochenbruch</street>

      <city>Chapel Hill</city>

      <state>NC</state>

      <zip>27514</zip>

   </address>

   <phone>

      919-962-4325

      <ext>222</>

   </phone>

In discussing this and other examples, we need another definition: the value of
a field is the free-form text, if any, that it contains. In this example, the
"last", "first", "street", "city", "state", "zip", and "phone" fields have
values; the "name" and "address" fields contain sub-fields, but their values are
null; the "phone" field has both a value and a sub-field.

The example shown above is a legitimate XML-tuple, but because some of its
fields have sub-fields, this tuple has a greater "depth" than all previous
examples; thus another definition: a sub-field is one level deeper than its
enclosing field; the depth of an XML-tuple's field is the same as the level of
nesting in that field. So, deeper fields make the overall XML-tuple deeper.

A template to match the example XML-tuple can specify more or less depth for
matching tuples in the XML-space. Here is a shallow template, that specifies
tuples that have any "name" and "address" fields, but a specific "phone" field:

   <name/>

   <address/>

   <phone>

      919-962-4325

   </phone>

Here is a deeper template; it specifies tuples that have any "address" or
"phone" field, but a specific "name"

   <name>

      <last>Ballpoint</last>

      <first>Benny</first>

   </name>

   <address/>

   <phone/>

Partial XML-Tuple Templates

The other feature of XML-tuples and XML-spaces that make them so flexible and
powerful, is the use of "partial" templates, with this definition: a partial
template is a template that does not specify all the fields or subfields that
can exist in the XML-tuples that are to be matched. This implies, of course,
partial matching.

Here is a partial template that will match tuples that have any "name" and
"phone" fields, but must have an address field containing a "city" field whose
value is "Raleigh":

   <name/>

   <address>

      <city>Raleigh</city>

   </address>

   <phone/>

This partial template matches all XML-tuples that contain addresses in the city
of "Raleigh" and phones with extensions:

   <name/>

   <address>

      <city>Raleigh</city>

   </address>

   <phone>

      <ext/>

   </phone>

Note that the upper-level fields must be present in the matched tuples, but that
deeper fields need not be completely specified. The implication of partial
templates, and one effect that makes them so powerful, is that they match any
XML-tuples that have the specified fields and values, regardless of all other
second-level or deeper fields the target tuples might have. In the example just
shown, one implication is that some tuples in the XML-space might have "phone"
fields without "ext" sub-fields.

So partial matching is automatically in effect for all levels of a XML-tuple
below the top level. Use the wildcard notation, explained in the next section,
for partial templates at the top level.

Partial XML-Tuple Templates with Wildcards

The restriction that the upper-level fields of the template must be present in
any tuples that are to match can be overcome using "wildcard" fields in one of
two ways. To match the template's upper-level fields anywhere among the
upper-level fields of the stored tuples, use a format like this:

   <*/>

   <address>

      <city>Raleigh</city>

   </address>

This will match any tuple that has (at least) an upper-level "address" field
that has a "city" sub-field with a value of "Raleigh". So this wildcard notation
allows us to find a given set of upper-level fields among any and all tuples,
regardless of format, that have the same set of upper-level fields.

The other wildcard notation, instead of helping match along the breadth of
target tuples, helps match into the depths of tuples:

   <*>

      <address>

         <city>Raleigh</city>

      </address>

      <phone/>

   </*>

In this case, the match will occur if the target tuples contain the "address"
and "phone" fields at any depth, but both at the same depth, and with the same
parent, anywhere within the tuples, as long as the "address" field has a "city"
sub-field with a value of "Raleigh". This wildcard notation can be nested within
XML-tuple templates, allowing a match to "drill down" to any depth in specified
fields of target tuples.

Note: All the examples used tags with or without values. All would work equally
well if they used tag attributes with and without values, or combinations of tag
values and attributes.



                                 Change History

V0.5 to V0.7

   * Removed "Implementation Notes" section; all algorithms are proprietary.
   * Added a discussion of attributes and attribute matching in the "Matching
     XML-Tuples" section.
   * Clarified some paragraphs in the "Partial XML-Tuple Templates" and "Partial
     XML-Tuple Templates with Wildcards" sections.
   * Corrected various spelling errors.
   * Made <tag></tag> equivalent to <tag/>.



References

[1] Carriero, Nicholas and Gelernter, David, "Linda in Context", CACM 32(4), pp.
444-458, 1984.

[2] Sun Microsystems' JavaSpaces

[3] IBM's TSpaces