[prev in list] [next in list] [prev in thread] [next in thread] 

List:       xml-dev
Subject:    Re: [xml-dev] An element that contains itself
From:       Michael Kay <mike () saxonica ! com>
Date:       2014-08-03 19:47:52
Message-ID: CEB4FD4E-0945-44E4-BE4B-70E6C2C0859B () saxonica ! com
[Download RAW message or body]

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


_______________________________________________________________________

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


[prev in list] [next in list] [prev in thread] [next in thread]