Re: [xml-dev] An element that contains itself

[Michael Kay <mike@saxonica.com>]

In all of this you're assuming a concept of node identity.

XML itself has no such concept. For example, if the entity reference &e; occurs twice in a document, and &e; expands to an element, it doesn't say whether the two occurrences of &e; give you the same element or different elements. However, entity declarations cannot be recursive, so even if you treat the two references as identical elements, an element can't contain itself by virtue of entity references.

If you defined a concept of node identity based on lexical equivalence, then an element could only contain itself if the element was infinite. Although I don't think XML formally prohibits infinite documents, you are unlikely to find many of them on your disk drive.

XDM does have a concept of node identity. It mandates that the graph of nodes is a tree, and this can be taken to imply that a node cannot contain itself as a child or descendant. In practice this is automatically ensured by the mechanisms for constructing XDM nodes in XSLT and XQuery; when you add a child node to a parent, the child node is copied, which means the parent and child can never have the same identity. This is true even in XQuery Update.

Michael Kay
Saxonica
mike@saxonica.com
+44 (0) 118 946 5893




On 3 Aug 2014, at 20:09, Costello, Roger L. <costello@mitre.org> wrote:

> 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
> 
> 
> 
> _______________________________________________________________________
> 
> XML-DEV is a publicly archived, unmoderated list hosted by OASIS
> to support XML implementation and development. To minimize
> spam in the archives, you must subscribe before posting.
> 
> [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
> Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
> subscribe: xml-dev-subscribe@lists.xml.org
> List archive: http://lists.xml.org/archives/xml-dev/
> List Guidelines: http://www.oasis-open.org/maillists/guidelines.php