An element that contains itself

["Costello, Roger L." <costello@mitre.org>]

Hi Folks,

In XML documents we can have recursive elements. 

For example, we can have a <Book> that contains a <Book> that contains a <Book> that contains ... ad infinitum:

<Book>
    <Title>A</Title>
    <Book>
        <Title>B</Title>
        <Book>
            <Title>C</Title>
        </Book>
    </Book>
</Book>

That recursive <Book> element is readily defined in XML Schemas:

<xs:element name="Book" type="BookType" />

<xs:complexType name="BookType">
    <xs:sequence>
        <xs:element name="Title" type="xs:string" />
        <xs:element ref="Book" minOccurs="0" />
    </xs:sequence>
</xs:complexType>

The <Book> element that is nested inside a <Book> element is a different <Book> element:

<Book>
    <Title>A</Title>
    <Book>  <-- This is different than its parent <Book> element
        ...
    </Book>
</Book>

I want the nested <Book> element to be the outer <Book> element.

Allow me to explain.

I will use an abbreviated notation, as it will better show what I mean.

I will refer to the inner <Book> as C, <Title>A</Title> as B, and the outer <Book> as A.

If the nested <Book> is a different <Book> element than the outer, then we have:

A = { B, C }

That is, A consists of B and C.

It is clear that A does not contain itself.

Here I show A containing itself:

A = { B, A }

It's not possible to express that in XML.

We could try to express it using XML Entities:
----------------------------------------
<!DOCTYPE Document [
<!ENTITY A "a">
<!ENTITY B "b">
<!ENTITY Set "&A; &B; &Set;">
]>
<Document>
    &Set;
</Document>
----------------------------------------

This ENTITY declaration:

<!ENTITY Set "&A; &B; &Set;">

says that a Set is an element of itself.

However, such self-references are not permitted in ENTITIES or anywhere else in XML.

Long ago (in the last half of the nineteenth century) some very smart people sought to build a solid foundation for mathematics. They decided to use sets as the foundation. They defined a set as:

	A set is a collection of distinct objects.

However, with that definition a set can contain itself, just like this entity contains itself: 

<!ENTITY Set "&A; &B; &Set;">

A fellow by the name of Bertrand Russell realized the problem with allowing a set to contain itself (the problem he identified became known as Russell's Paradox), so the mathematicians changed the definition of set to this:

	A set of a collection of distinct objects, 
	none of which is the set itself.

So now you know why the creators of XML didn't allow 

<!ENTITY Set "&A; &B; &Set;">

or elements to contain themselves.

Here we see a fundamental finding in mathematics making its way into XML (and into programming and lots of other things).

Pretty cool, aye?

/Roger