NOTE-xptr-infoset-liaison-19990224 24.9 KB

Raw Blame History Permalink

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE>XPointer-Information Set Liaison Statement</TITLE>
<LINK rel="stylesheet" type="text/css" media="screen"
   href="/StyleSheets/TR/W3C-NOTE">
</HEAD>

<BODY>

<DIV class="head">
  <P><A href="http://www.w3.org/">
    <IMG height="48" width="72" alt="W3C"
    src="http://www.w3.org/Icons/WWW/w3c_home"></A></P>
    <H1>XPointer-Information Set Liaison Statement</H1>
    <H2>W3C Note 24-Feb-1999</H2>
  <TABLE>
    <TR valign="baseline"><TD>This version:
      <TD><A href="http://www.w3.org/TR/1999/NOTE-xptr-infoset-liaison-19990224">
             http://www.w3.org/TR/1999/NOTE-xptr-infoset-liaison-19990224</A>
    <TR valign="baseline"><TD>Latest version:
      <TD><A href="http://www.w3.org/TR/NOTE-xptr-infoset-liaison">
             http://www.w3.org/TR/NOTE-xptr-infoset-liaison</A>
    <TR valign="baseline"><TD>Editor:
      <TD>Steven J. DeRose (Inso Corp. & Brown Univ.) &lt;<a
href="mailto:Steven_DeRose@Brown.edu">Steven_DeRose@Brown.edu</a>&gt;
  </TABLE>

<p><small>
<A HREF="http://www.w3.org/Consortium/Legal/ipr-notice.html#Copyright">Copyright</A>
&#169;1999 <A HREF="http://www.w3.org">W3C</A> (<A HREF="http://www.lcs.mit.edu">MIT</A>,
<A HREF="http://www.inria.fr/">INRIA</A>, <A HREF="http://www.keio.ac.jp/">Keio</A>)
, All Rights Reserved. W3C <A HREF="http://www.w3.org/Consortium/Legal/ipr-notice.html#Lega
lDisclaimer">liability,</A>
<A HREF="http://www.w3.org/Consortium/Legal/ipr-notice.html#W3CTrademarks">trademark</A>,
<A HREF="http://www.w3.org/Consortium/Legal/copyright-documents.html">document
use</A> and <A HREF="http://www.w3.org/Consortium/Legal/copyright-software.html">software
licensing</A> rules apply.</small></p>
</DIV>

<HR>

<H2><A name="status">Status of this document</A></H2>
<p>This is a W3C Note produced as
a deliverable of the <a href="http://www.w3.org/XML/Activity#linking-wg">XML
Linking WG</a> according to its charter and Published as a W3C NOTE February 23 1999. A list of current W3C working drafts and notes can be found at
<a href="http://www.w3.org/TR">http://www.w3.org/TR</a>.</p>

<p>This document was originally a portion of the XPointer Requirements
document. It was separated out by decision of the XML Linking WG taken at
the meeting of November 21-22, 1998 in Chicago, to become a liaison
statement to the XML Information Set Working Group.</p>

<p>Comments on this document should be sent to <a
href="mailto:Steven_DeRose@Brown.edu">Steven_DeRose@Brown.edu</a>.</p>

<div><h2>Related documents</h2>

<p><a href="http://www.w3.org/TR/NOTE-xptr-req">
XPointer Requirements,</a> produced by the XML Linking Working Group. This
document provides requirements governing the work of this WG on the
XPointer specification.</p>

<p><a href="http://www.w3.org/TR/1998/WD-xptr-19980303">
XML Pointer Language (XPointer) Working Draft,</a> prior WDs produced by
the former XML Working Group, and now under the XML Linking WG. Provides a
simple yet powerful mechanism for addressing data portions in XML
documents. It is very closely based on a multiply-implemented and
widely-used technology, <a href="http://etext.virginia.edu/bin/tei-bigger.sh?id=1198411">extended pointers,</a> defined by the <a href="http://etext.
virginia.edu/TEI.html">Text Encoding Initiative.</a></p>

<p><a href="http://www.w3.org/TR/NOTE-xlink-req">
XLink Requirements,</a> produced by the XML Linking Working Group. This
document provides requirements governing the work of this WG on the XLink
specification.</p>

<p><a href="http://www.w3.org/TR/1998/WD-xlink-19980303">XML Linking
Language (XLink)
Working Draft,</a> prior WDs produced by the former XML Working Group, and
now under the XML Linking WG.</p>

<p><a href="http://www.w3.org/TR/1998/NOTE-xlink-principles-19980303">
XML Linking Language (XLink) Design Principles,</a> produced by the former
XML Working Group, and now under the XML Linking WG. This document provides
general design principles governing the work of this WG, involving both the
XLink and XPointer specifications.</p>

</div>

<div><h2><a name="Abstract">Abstract</a></h2>

<p>This document is a liaison statement from XML Linking Working Group to
the XML Information Set working group. Because the XPointer specification
under development in the XML Linking WG must refer to structural parts of
XML documents, the structure it addresses must be explicit. Document
structure specifications such as DOM and the XML Information Set may wish
to consider the XPointer requirements in order to insure interoperability
when used with XPointer and XLink. Thus we have set out in this document,
some constraints we believe XPointer has, for its use with a system
representing XML information structures.</p>
</div>

<div><h2>Table of Contents</h2>

<ul>

<li><A HREF="#VAST">Requirements for a virtual abstract structure tree</a>
<ul>
<li><A HREF="#V.completeness">A: Completeness requirements</a></li>
<li><A HREF="#V.robustness">B: Robustness requirements</a></li>
<li><A HREF="#V.syntax">C: Mechanical and syntactic requirements</a></li>
<li><A HREF="#V.non">D: Non-requirements</a></li>
</ul>
</li>

<li><A HREF="#Bibliography">Bibliography</a> </li> </ul>
</div>


<!--
==========================================================================
-->

<div>
<H1><A NAME="VAST">Requirements for a virtual abstract structure tree</A></H1>

<p>The abstract information structure of an XML document defines the
components that links
address into using XPointers. This structure must be explicit and
unambiguous for XPointer to
work, because:</p>

<ol>

<li> <p>Otherwise an XPointer would be ambiguous: two conforming
implementations could
interpret the same XPointer as pointing to two different places. Questions
as simple as "What is
the element with id='foo'?" (is id a name or a type?), and "Which node is
the third child of
this other node?" (do PIs count?) would become unanswerable.</p></li>

<li> <p>Otherwise XPointers could not achieve robustness even against
trivial, non-structural
changes in syntax (such as inserting spaces around "=" in start-tags). Such
robustness is
highly desirable, especially when XML is generated automatically or
dynamically. It would be
very bad if XPointers could be broken by such semantically insignificant
changes, and far worse
if they could make XPointers quietly point to different places. </p></li> </ol>

<p>Given this, some requirements on that abstract structure tree
representation are laid out
below. Merely to have a term in this document, we refer to any XML
information representation as a Virtual Abstract Structure Tree, or "VAST".
We choose such a generic term to prevent tieing
these constraints to any particular model, API, or implementation. These
requirements should be
considered liaison information for DOM and especially for the XML
Information Set WG, but are not intended to constrain the details of any
API or implementation, beyond the need to somehow support the aspects of
functionality needed by XPointer.</p>

<div>
<H2><A NAME="V.completeness">A: Completeness requirements</A></h2>

<ol> <li> <p>An information structure to support XPointer (call it "VAST"
for the moment) must
represent elements, attributes, characters, PIs, and unparsed entities. The
treatment of comments is still under consideration by the XML Linking
WG.</p>

<p>All these things might be needed link targets for someone. Although an
end user may only
rarely want to link to a PI or comment, there is no principled reason they
should not, and
there are real cases already where crucial information (such as scripts) is
buried in comments.
User annotations in document authoring and review applications must be able
to point to all
these things in order to comment on them. Also, XPointer is not only for
end-user navigation
links. Programs can use it to represent internal connections; in such
scenarios they certainly
may want to refer to a particular processing instruction to attach further
data to it, connect
it to workflow, version control, or other meta-information, and so on. In
short, any structure
XML defines is a real object in XML documents, and needs to be supported;
syntax details such
as whitespace within start-tags are on quite a different level from whole
events such as
PIs.</p></li>

<li> <p>A VAST must represent all the containment <i>and</i> order
relations among the nodes
that constitute information. </p>

<p>For example, the order of paragraphs in a section is normally
information, but the order of
attributes in a tag is not. An unordered model, such as one that would
require retrieving all
children of a node and then sorting by an internal field in order to get
them in order, or one
that would require visiting all descendants in order to reach a sibling, is
unacceptable
(though such an <i>implementation</i> need not conflict with this
conceptual model at
all).</p></li>

<li> <p>A VAST must be able to represent documents in which there are
multiple nodes
surrounding the document root element (comments, PI, DOCTYPE, etc). </p>

<p>This is commonly done by positing a reserved true-root node as parent of
the document
element, which thus contains all this stuff. This is natural because most
of the same methods
are meaningful for this node as for any other. However, many other
implementations and
interfaces are possible.</p></li> </ol>

</div>

<div>
<H2><A NAME="V.robustness">B: Robustness requirements</A></h2>

<ol>
<li><p>The same structure must be generated regardless of whether the
parser was WF or
validating. </p>

<p>This is critical for XPointer, because otherwise links couldn't be
reliably followed when
the link-maker and link-user happened to use different kinds of parsers.
For invalid documents,
of course, a validating parser will stop parsing and therefore result in a
radically different
VAST, or no VAST at all; but for valid documents the VASTs must be the
same. </p>

<p>The XML Linking WG realizes there are considerable difficulties with
completely fulfilling this requirement. We do not see default attributes as
the crucial aspect, since they may be <i>relatively</i> unlikely to be
referenced by Xpointers; more important are distinction of child-counting,
that would throw off geometric pointing into element structure trees, on
which we depend for certain aspects of addressing.</p>

<p>[Implementor note: Since attributes may receive default values based on
declarations in the
internal subset, these must be supported by WF systems that are to fully
support XPointer.]</p></li>

<li><p>A VAST must distinguish the element/attribute relationship from the
element/subelement
relationship. That is, attributes are 'owned' (or some other term), not
'children'; thus they
do not confuse traversals, child counting for linking, etc.</p></li>

<li><p>A VAST must include all whitespace in content from the parser.</p>

<p>As with attribute internals, a WF parser cannot determine which
whitespace is insignificant,
and so interoperability of XPointers appears to require this.</p></li>

</ol>

</div>

<div>
<H2><A NAME="V.syntax">C: Mechanical and syntactic requirements</A></h2>

<ol>

<li><p>A VAST must permit efficient implementations for reaching a complete
resource given a
sub-resource of it, and for reaching intermediate-scope nodes between the
two. </p>

<p>For example, if a link results in references to one or more P elements,
it is usually not
user-useful to retrieve the individual P elements in isolation, and be
unable to display them
in context. The interpretation of text requires context. There are certain
scenarios where
information portions out of context suffice but in far more scenarios
context is required. For
example:</p> <ul>

<li><p>In nearly all style languages, even a P element cannot be formatted
correctly without
knowing where it lives in the larger tree context, due to style
inheritance, auto-numbering
algorithms, and so on.</p></li>

<li><p>In many applications the user must be able to move up or down to
read the preceding and
following contexts, or to identify the current node in a more global view
such as a table of
contents.</p></li>

<li><p>Intellectual property issues may impose requirements that
information be displayed with
certain context. One obvious piece of contextual information is a copyright
notice on the
document out of which the linked data is drawn.</p></li>

<li><p>In general, the content one gets by discarding markup is not the
correct text; this is
because some tags imply a word-break (ITEM) and some do not (I); some tags
imply much more,
such as a digression to a completely different text (FOOTNOTE). So
returning "the content" may
simply produce the wrong result.</p></li> </ul> </li>

<li><p>XPointer's abstract structural requirements must permit varying
implementations of how
children are attached to parents, how attributes are attached to element
nodes, and so on, but
need not closely mirror any of them. </p>

<p>[Implementor note: There are many well-known and efficient data
structures for representing
structure trees: arrays of children at each node, doubly-linked sibling
lists, threaded arrays,
and so on. Any are fine so long as they provide the necessary context
access.]</p></li>

<li> <p>Characters must be accessible just as other nodes are.</p>

<p>This is critical for XPointer because it is extremely common to point to
characters,
especially with the ever-popular "select/create link" interfaces. </p>

<p>If characters could not be
treated as easily as other nodes, the XPointer definition would have to
become more
complicated. It could not simply state that the result of evaluating an
XPointer is just a
node, or a list of nodes or locations, or even a list of start/end pairs.
Instead, a pointer to a
character would have to consist of 3 things together: some pointer to a
nearby node (say, the
one to the right, or the parent), plus a bit to say that this time it's
pointing to a character <i>associated with</i> that node instead of to the
node itself, plus something to say
<i>which</i> associated character. For example,

<pre>     Node 378 (say, a P node)</pre>

<br>versus

<pre>     Text preceding node 378, character 12</pre>

<p>Note: This obviously does not constrain how particular implementations
allocate or arrange their internal data structures. But XPointer needs to
be able to access and count positions without regard to how particular
implementations may or may not "chunk" things. Propogating such
distinctions into XPointer would hugely complicate implementations.
Accessing and counting characters without concern for possible intermediate
text-chunk nodes
is the <i>conceptual</i> model needed by XPointer, though we fully
understand that  using some form of strings or chunks may often be the best
<i>implementation</i> approach. Our
constraints are specified in terms of a <i>conceptual</i> model for
determining how things
are counted, and so use characters. So long as we can do that, we are not
concerned about the underlying implementation method(s), from
storing internal text nodes, to forwarding-pointer-enhanced linked lists,
to indexed arrays;
these could all present things consistent with the way our abstract model
counts.]</p> </li>
</ol>

</div>

<div>
<H2><A NAME="V.non">D: Non-requirements</A></h2>

<ol>

<li> <p>A VAST need not represent the internal structure of attributes
(such as tokenization).
</p>

<p>One reason for this is that it follows from the requirement that WF and
validating parsers
provide the same tree: since WF parsers do not in general know whether an
attribute is NMTOKENS
or CDATA, they cannot determine what the internal structure is.</p>

<p>Also, since schemas will likely provide internal structuring capability
for attribute
values, anything put in now for this will be soon obsolete. Applications
can interpret
attributes however they want (such as interpreting them as quantities and
doing math on them).
However, we do know that attributes will continue to be strings, and will
not contain true
elements or other nodes, so we can leave them at that for now.</p></li>

<li> <p>A VAST need not represent DTD structures at this time.</p>

<p>If schema efforts using XML syntax are successful, then VAST can clearly
be used for DTDs.
If not, an abstract representation of DTDs can be added in a later
revision. The abstract tree,
however, must be able to represent the DOCTYPE reference <i>to</i> a DTD,
so the DTD can be
found by any applicable process.</p>

<p>[Implementor note: The effect of attribute defaults declared in the
internal subset is
represented, but the VAST need not include a representation of the
declarations that created
that effect.</p></li>

<li> <p>A VAST may, but need not for XPointer, provide information about
CDATA marked sections
and entity boundaries. It must, however, easily provide a view without this
information. </p>

<p>If such information is included in an implementation, there must still
be access to a
simpler view in an extremely simple, fast way, equivalent to mere deletion
of nodes from the
more complex view: no re-parenting, reordering, promotion, demotion, or
merging of other node,
etc. This is so that node counting and traversal will not be adversely
affected by whether the
user is in an application that requires such information for other
legitimate purposes, such as
editing.</p>

<p>As always, any of the countless possible implementations that can
provide these external
requirements is fine; the requirement for XPointer is that its task not be
made unduly costly
or painful because in consequence.</p>

<p>[Implementor note: One way to do this is to define "raw" and "cooked"
views, where the raw
view includes the extra nodes. Editors and some other applications would
probably need the full
raw information internally, but XPointer and some other applications can be
defined strictly in
terms of the (subset) cooked view. This is crucial because only a cooked
view can be guaranteed
identical across applications whether or not they support raw views.]</p></li>

<li> <p>A VAST need not directly represent derived relationships such as
the connection between
IDREFs and the like-keyed ID, or the relationship between all elements with
the same element
type, so long as it does not make it impossible to associate such
information in other
ways.</p>

<p>For example, the conceptual model does not impose any requirement that
implementations embed
hard pointers to resolve all IDREFs, as opposed to building some other
method to get from an
IDREF to the corresponding ID. Strictly speaking, such information is
semantic rather than
purely syntactic: XML syntax determines a tree; semantic relationships (the
most obvious example being IDREFs) may determine arbitrarily more complex
structures (this is also clear from the fact that such semantic information
cannot affect well-formedness).</p>

<p>[Implementor note: Putting such information directly into a VAST would
pose several
problems:</p>

<ul>

<li> <p>It would add great complexity to the specification, and would
introduce subtle
questions about just <i>which</i> derived relationships to represent (for
example, should
attributes containing XPointers be connected just as IDREF attributes
are?). </p></li>

<li> <p>It could mislead implementors to believe they must implement such
relationships via
direct pointers in the VAST, when we know that differing implementations
have proven useful in
established applications with varying user requirements (separate ID
indexes, serial search,
hard internal pointers, etc.). </p></li>

<li> <p>A VAST that included such relationships <i>on par with the primary
syntactic
element/sub-element structure</i> would not be a tree. It would not even be
a directed acyclic
graph, but would be a fully general cyclic graph structure. Cyclic graphs
are far more
sophisticated and subtle to deal with, and many implementors are not
familiar with them. Even
such an everyday task as traversing the structure is hard (and is often
done by creating a subset of the graph that <i>is</i> a tree, and
traversing that "spanning tree" -- <A HREF="#Liu77">see Liu 1977</a>). Many
operations, such as order comparisons, traversals,
import/export, and so on, are far easier to define on a tree.</p></li>

</ul>

<p>Such relationships clearly exist, and can be handled just fine (many
systems have done so
for a long time); indeed representing them is much of the purpose of
XPointer. Problems only arise from describing  them as on par with the
basic syntactic node relationships of the defining structural model. Doing
so would complicate implementing and teaching the model:</p>

<p>On the one hand, structure trees have repeatedly proven easy to teach
and to motivate.
Describing the element/text tree is easy; adding PIs and comments is easy
from there; and
describing attributes as properties rather than children still leaves the
structure a tree,
and is not difficult. Perhaps this ease of teaching is because this model
fits the HTML
and XML overall models so clearly. </p>

<p>On the other hand, we know from many attempts that drawing all the other
(semantic)
relationships on top of the tree structure obscures it. When told the
conceptual structure
isn't "really" a tree, less-technical users' eyes quickly glaze over, while
implementors are
quickly tempted to discard well-known and extremely efficient algorithms
that they know apply
only to trees.</p>

<p>[Note: Most implementations <i>of</i> trees are not themselves trees
anyway. One of many
examples is a useful representation of n-ary trees (mentioned in Knuth
1973) that uses a
doubly-linked list of children for each node. Obviously this is not a tree
if you "count" all those back-links; but what defines a data structure as a
tree representation is its conceptual topology, not its implementation. <a
HREF="#Knut73">Knuth's</a> formal definition is simply:</p>

<blockquote>a finite set T of one or more nodes such that
<br>a) There is one specially designated
node called the <i>root</i> of the tree, root(T); and
<br>b) The remaining nodes (excluding the
root) are partitioned into m>=0 disjoint sets T1,..., Tm, and each of these
sets in turn is a
tree. The trees T1,..., Tm are called the subtrees of the
root.</blockquote>

<p>In simpler terms, this just means that as long as there is a root with
no parent and every
other node has one parent, it's a tree. It quite simply doesn't matter how
many other pointers,
links, arcs, or whatever else you have floating around, as long as each
node but the root has
exactly one connection that you call "parent". ]</p>
</li>

</ol>
</div>
</div>

<div>
<H1><A Name="Bibliography">Bibliography</A></H1>

<p><a name="Abit97">Abiteboul, Serge et al.</a> 1997. "Querying Documents
in Object Databases."
In <i>International Journal on Digital Libraries</i> 1(1): 5-19.</p>
<p><a name="Andr89">Andr&eacute;, Jacques, Richard Furuta, and Vincent
Quint (eds).</a> 1989.
<i>Structured Documents.</i> Cambridge: Cambridge University Press. ISBN
0-521-36554-6.</p>

<p><a name="Broo88">Brooks, Kenneth P.</a> 1988. "A Two-view Document
Editor with
User-definable Document Structure." Dissertation, Stanford University
Department of Computer
Science. Reprinted as <A
HREF="http://www.research.digital.com/SRC/publications"> Technical
Report #33</a> by Digital Systems Research Center.</p>

<p> <a name="Burk91">Burkowski, Forbes J.</a>  1991.  "An Algebra for
Hierarchically Organized
Text-Dominated Databases."  Waterloo, Ontario, Canada:  Department of
Computer Science,
University of Waterloo.  Manuscript:  Portions "appeared as part of a paper
presented at RIAO
'91:  Intelligent Text and Image Handling, Barcelona, Spain, Apr. 1991." </p>

<p> <a name="Conk87">Conklin, Jeff.</a>  1987.  "Hypertext:  An
Introduction and Survey."
<i>IEEE Computer</i> 20 (9): 17-41.</p>

<p><a name="DeRo89">DeRose, Steven J.</a> 1989. "Expanding the Notion of
Links." In
<i>Proceedings of Hypertext '89,</i> Pittsburgh, PA. Baltimore, MD:
Association for Computing
Machinery Press.</p>

<p> <a name="DeRo95">DeRose, Steven J. and David G. Durand.</a> 1995. "The
TEI Hypertext
Guidelines." In <i>Text Encoding Initiative: Background and Context.</i>
Boston: Kluwer
Academic Publishers. ISBN 0-7923-3689-5. </p>

<p> <a name="DeRo98a">DeRose, Steven and Eve Maler (eds).</a> 1998. <a
href="http://www.w3.org/TR/1998/WD-xlink-19980303">"XML Linking Language
(XLink)."</a> World
Wide Web Consortium Working Draft. March 1998. </p>

<p> <a name="DeRo98b">DeRose, Steven and Eve Maler (eds). 1998.</a> <a
href="http://www.w3.org/TR/1998/WD-xptr-19980303">"XML Pointer Language
(XPointer)."</a>
World Wide Web Consortium Working Draft. March 1998. </p>

<p><a name="Kahn89">Kahn, Paul.</a> 1989. "Webs, Trees, and Stacks: How
Hypermedia System
Design Affects Hypermedia Content." In <i>Proceedings of the Third
International Conference on
Human-Computer Interaction,</i> Boston, MA, September 18-22, 1989.</p>

<p><a name="Knut73">Knuth, Donald E.</a> 1973. <i>Fundamental
Algorithms</i> (2nd ed.). Volume
1 of <i>The Art of Computer Programming.</i> Reading, MA: Addison-Wesley. ISBN
0-201-03809-9.</p>

<p><a name="Liu77">Liu, C. L.</a> 1977. <i>Elements of Discrete
Mathematics.</i> New York:
McGraw-Hill. ISBN 0-07-038131-3.</p>

<p><a name="Yu88">Yu, Clement T. and Weiyi Meng.</a> 1988. <i>Principles of
Database Query
Processing for Advanced Applications.</i> San Francisco: Morgan Kaufmann
Publishers. ISBN
1-55860-434-0.</p>
</div>

</BODY> </HTML>