Representation of overlapping structures

Concurrent markup

Although originally introduced largely with the thought of providing both ‘logical’ and ‘formatted’ views of documents, the SGML feature called CONCUR was specifed with enough generality and abstraction that it is not limited to that original application. Multiple concurrent views of the same document can be provided, without restriction as to number or kind of view. Each view takes the form of a conventional document tree, and all views share the same frontier of character data.

Although seldom exploited by SGML users, concurrent markup has seen something of a revival in recent years, both in linguistic annotation (see for example [Witt 2004], [Hilbert et al. 2005], and [Schonefeld 2007]) and manuscript studies ([Dekhtyar / Iacob 2005]).

A simple example from [Schonefeld / Witt 2006] may illustrate the mechanism:¹

<(L1)div type="dialog" org="uniform">
   <(L2)text>
     <(L1)u who="Peter">
       <(L2)s>Hey Paul! </(L2)s>
       <(L2)s>Would you give me
     </(L1)u>
     <(L1)u who="Paul">
       the hammer? </(L2)s>
     </(L1)u>
   </(L2)text>
</(L1)div>

This presents two trees. First, the L1 tree, whose conventional XML representation would be:

<div type="dialog" org="uniform">
     <u who="Peter">
       Hey Paul!
       Would you give me
     </u>
     <u who="Paul">
       the hammer?
     </u>
</div>

  <text>
       <s>Hey Paul! </s>
       <s>Would you give me
       the hammer? </s>
   </text>

Multi-colored trees

Multi-colored trees are collections of trees, each a more or less conventional XML tree when viewed individually, but stored in such a way as to share structure wherever possible [Jagadish et al. 2004]. A collection of information may thus be addressed in several different XML forms, without having to store the information multiple times (which wastes storage space as well as causing problems when updating the material).

A collection of information about movies, directors, actors, and so on, for example, might in conventional XML be organized either by actor (with <movie> elements appearing as children of <actor> elements), or by movie (with <actor> as child of <movie>), or in some other way. Almost any organizational principle may involve redundancy and may be inconvenient for certain kinds of searches, while making other searches very simple (to find the movies in which an actor has appeared, just find the appropriate <actor> element and then select all of the children named <movie>). The use of multi-colored trees allows the information to be stored and addressed not as a single XML document, but as several documents, each optimized for certain kinds of query and retrieval. In XML databases where traversal of the parent-child or next-sibling links is fast, but value-based lookups of other elements are slow), multi-colored trees can help provide faster retrieval.

Multi-colored trees resemble CONCUR in providing multiple tree structures over the same collection of data. They differ from CONCUR in that they do not require or guarantee that the different trees have the same sequence of characters at the leaves, nor that all character data appear in every tree, nor that shared structures occur in the same sequence in different trees. They do not forbid these things, either, so the example given above for concurrent markup could also be stored as a pair of multi-colored trees.

A more characteristic example, however, might be the movie database described in [Jagadish et al. 2004] (as shown here, the example has been augmented slightly in the interests of verisimilitude with information from the Internet Movie Database). The user may view the database as a set of three different XML documents, one showing actors and their roles:

<actors>
   <actor>
     <name>Bette Davis</name>
     <movie-role id="RB023">
       <!--* Payment on Demand (1951) *-->
       <name id="RB024">Joyce Ramsey (nee Jackson)</name>
     </movie-role>
     <movie-role id="RB117">
       <!--* All about Eve (1950) *-->
       <name id="RB125">Margo Channing</name>
     </movie-role>
     <movie-role id="RB927">
       <!--* Beyond the Forest (1949) *-->
       <name id="RB925">Rosa Moline</name>
     </movie-role>
     <!--* ... *-->
   </actor>
   <actor>
     <name>Audrey Hepburn</name>
     <!--* ... *-->
     <movie-role id="RB097">
       <!--* The Children's Hour, 1961 *-->
       <name id="RB475">Karen Wright</name>
     </movie-role>
     <movie-role id="RB157">
       <!--* Breakfast at Tiffany's, 1961 *-->
       <name id="RB175">Holly Golightly</name>
     </movie-role>
     <movie-role id="RB837">
       <!--* The Nun's Story, 1959 *-->
       <name id="RB975">Sister Luke</name>
     </movie-role>
     <!--* ... *-->
   </actor>
</actors>

<movie-genre>
   <name>all</name>
   <movie-genre>
     <name>comedy</name>
     <movie id="RG012">
       <name id="RG015">All about Eve</name>
       <movie-role id="RB117">
         <!--* Bette Davis *-->
         <name id="RB125">Margo Channing</name>
       </movie-role>
       <movie-role>
         <!--* Anne Baxter *-->
         <name>Eve Harrington</name>
       </movie-role>
       <movie-role>
         <!--* George Sanders *-->
         <name>Addison DeWitt</name>
       </movie-role>
       <!--* ... *-->
     </movie>
     <movie-genre>
       <name>slapstick</name>
       <!--* ... *-->
     </movie-genre>
   </movie-genre>
   <!--* ... *-->
   <movie-genre>
     <name>drama</name>
     <movie>
       <name>Breakfast at Tiffany's</name>
       <movie-role id="RB157">
         <!--* Audrey Hepburn *-->
         <name id="RB175">Holly Golightly</name>
       </movie-role>
       <movie-role>
         <!--* George Peppard *-->
         <name>Paul 'Fred' Varjak</name>
       </movie-role>
       <movie-role>
         <!--* Patricia Neal *-->
         <name>2-E (Mrs. Fallenson)</name>
       </movie-role>
       <movie-role>
         <!--* Buddy Ebsen *-->
         <name>Doc Golightly</name>
       </movie-role>
       <!--* ... *-->
     </movie>
   </movie-genre>
</movie-genre>

A third document shows awards won by movies:

<movie-award>
   <name>Oscar</name>
   <movie-award>
     <name>1950s Oscars</name>
     <movie id="RG012">
       <name id="RG015">All about Eve</name>
       <votes>14</votes>
     </movie>
     <!--* ... *-->
   </movie-award>
</movie-award>

The nodes shown with id attributes are shared among the different trees: the movie-role element whose ID is “RB117”, for example, appears both in the actors tree and in the movie-genre tree, as does its name child.² This redundancy makes queries against the XML easier to specify (exploiting the fact that XML query languages typically make specification of parent : child or ancestor : descendant relations especially convenient), and (at least in the test implementation) also faster (presumably because traversal of parent : child links is highly optimized).

When a node is shared between trees, it may have different children in the different trees; in the example, element RG012 illustrates this phenomenon. When several trees of different colors do share a great deal of structure, with elements in different trees having the same children in the same sequence, then (notionally, at least) multi-colored trees will store the information about the parent : child and previous : next sibling relationships several times.

Goddag structures

Goddag structures are directed acyclic graphs in which the directed arcs represent a parent/child relation. They were developed to aid in the understanding, markup, and processing of documents with overlapping structures; they are rooted especially in work on manuscript transcription, where important phenomena (deletions, marks in the margin, paragraphs) often overlap each other. As in the trees used to represent XML documents, the children of any node in a Goddag are ordered (or typically so; there are exceptions). Unlike XML trees, however, Goddag structures allow any node to have multiple parents.

Several forms of Goddag structure may be distinguished:

• Normal Goddags are those in which the containment relation (calculated on leaf nodes) and the dominance relation (the transitive closure of the parent/child relation) are almost entirely the same: if the leaf nodes contained by a node N1 are a proper superset of the leaf nodes contained by another node N2, then N1 dominates N2 directly (as parent/child) or indirectly (as ancestor/descendant). In a normal Goddag structure, the children of a node are either totally ordered (this is the usual case) or not ordered at all (this is the case when the element corresponds to an element written <|e|| ... ||e|> in TexMecs notation).
  To any non-normal Goddag structure, there correspond one or more normal Goddag structures, which can be constructed in a relatively straightforward way. For any node x, let “leaves(x)” denote the set of leaves dominated by x. Now, for any pair of nodes (a, b),
  • If leaves(b) ⊂ leaves(a) and leaves(b) ≠ leaves(a), then ensure that a dominates b, directly or indirectly.
  • If leaves(a) ⊂ leaves(b) and leaves(b) ≠ leaves(a), then ensure that b dominates a, directly or indirectly.
  • If leaves(a) = leaves(b), then ensure that one of them dominates the other, directly or indirectly.
• Colored Goddags are Goddags in which each parent/child arc is associated with one or more colors. Taking the subset of the graph including just the arcs labeled with a given color, with the nodes incident to them, results in a normal Goddag. Colored Goddags are similar, though not quite identical, to the multi-colored trees of [Jagadish et al. 2004].
• Mecs graphs or restricted Goddags are normal Goddag structures in which nodes which are children of multiple parents are ordered in the same way by all parents; there is thus a global ordering of leaf nodes and any node N1 adjacent to another node N2 among the children of any parent is adjacent to N2 according to any parent which has both N1 and N2 as children.

For example, consider the following TexMecs document, which has two roots, one for the scene (the dramatic view) and one for the embedded haiku.

<* The dramatic view *>
<scene|
<sp who="HUGHIE"|<p|How did that translation go?|p>
<lg type="haiku"|<l|da de dum de dum,|l>
<l@frog|gets a new frog,|l>
<l|...|l>|lg>
|sp>
<sp who="LOUIS"|<p|Er ...|p>
<lg|<l@new|it's a new pond.|l>|lg>
|sp>
<sp who="DEWEY"|
<p|Ah ...|p>
<lg|<l@pond|When the old pond|l>|lg>
<p|Right.  That's it.|p>
|sp>
|scene>

<* The embedded poem *>
<haiku|
<lg|<^l^pond><^l^frog><^l^new>|lg>
|haiku>

For further details, the reader is directed to [Sperberg-McQueen / Huitfeldt 2000].

Notation

Each relation is specified in the form

relation-name ( column-list )

For example

nodes(node_id nID,
node-type type)

Some conventional column names are used repeatedly with the same meaning:

• nID (of type node_id) is a node identifier and serves as the key, or part of the key, of the relation
• nPar, nReuben, nBenjamin, nL, nR are node IDs (values of type node_id) which are the parent, first child, last child, left sibling, and right sibling, respectively, of the current node (the one whose ID is the key of the relation).

For most column names, a simple form of ‘Hungarian notation’ is used: some names have a short prefix indicating the domain from which the values are drawn:

• n = node_id
• ln = list of node_id
• nm = xsd:NCName
• ns = xsd:anyURI (‘namespace name’)
• s = xsd:string

When the type of a column is clearly indicated by its name, the explicit type indicator is often omitted. For example, the following two expressions specify the same relation:

child_parent(node_id
nCh, node_id nPar)
child_parent(nCh, nPar)

Domains

The values in the relations sketched here are drawn from the following domains:

• the primitive simple types of XML Schema 1.0 (for the moment, only a few of these are actually used)
• ns: a URI used as a namespace name (restriction of anyURI to require scheme name; intent is to require full URIs)
• node_id: a unique value used to identify a node within a document. Not further analyzable; the only operation allowed is testing for equality. The initial implementation uses positive integers for this purpose.
• node_list: a list of node_ids.
• node_type: one of document, element, attribute, pcdata, comment, or pi (‘processing instruction’).

Individual nodes

The data structures described here have in common that they represent the document as a graph, i.e. as a set of nodes and a set of arcs connecting those nodes (with nodes and arcs possibly ordered in different ways). We postulate several kinds of node: documents, elements, attributes, comments, pcdata (‘text nodes’), and processing instructions.

The representation of these basic nodes is the same for XML, concurrent XML, colored XML, and Goddag structures. It uses the following relations:

• node(nID): identifies nID as a node in the document. (Strictly speaking, redundant with the following relations.)
• node_type(nID, node_type type): indicates that nID is a node of the given type. Redundant with the relations document, element, attribute, comment, pcdata, and pi.
• document(nID): indicates that nID is a document node.
• element(nID, ns, nmLocal): indicates that nID is an element, whose element type name is the expanded name (ns, nmLocal).
• attribute(nID, nElement, ns, nmAtt, sValue): indicates that nID is an attribute, on element nElement, with name nmAtt in namespace ns, and with lexical form sValue. The normal rules for attributes have as a consequence that the columns nelement, ns, nmAtt form a second candidate key.
• comment(nID, sData): indicates that nID is a comment whose contents are sData.
• pcdata(nID, sData): indicates that nID is a text node whose value is sData.
• pi(nID, nmTarget, sData): indicates that nID is a processing instruction with target notation is nmTarget and whose value is sData.

For example, the nodes in the example of section 2-1 could be represented thus (trimming whitespace, for convenience, using “-” to indicate null values, and omitting the uninformative node relation for brevity):

node_type(L1,document).
node_type(L2,document).
node_type(n1,element).
node_type(n2,attribute).
node_type(n3,attribute).
node_type(n4,element).
node_type(n5,element).
node_type(n6,attribute).
node_type(n7,element).
node_type(n8,pcdata).
node_type(n9,element).
node_type(n10,pcdata).
node_type(n11,element).
node_type(n12,attribute).
node_type(n13,pcdata).

element(n1,-,div).
element(n4,-,text).
element(n5,-,u).
element(n7,-,s).
element(n9,-,s).
element(n11,-,u).

attribute(n2,n1,-,type,"dialog").
attribute(n3,n1,-,org,"uniform").
attribute(n6,n5,-,who,"Peter").
attribute(n12,n11,-,who,"Paul").

pcdata(n10, " the hammer? ").
pcdata(n10, "Would you give me ").
pcdata(n6,"Hey Paul! ").

XML

The different data structures described here differ in the graph structures in which they embed the nodes of the document. This and the following sections describe the representation of those structures.

XML defines a single tree over the document. Conventionally, n-ary trees like those of XML are often described as trees in which each node as a variable-length sequence of children. A straightforward translation of this idea into our notation would give us

• parent_children(nID, node_list lnChildren): identifies nID as a node whose children are the nodes in lnChildren.

For our purposes here, however, it is more convenient to factor the information into two relations, each simpler:

• node_firstchild(nID, nReuben): identifies nID as a node whose first child is nReuben.
• node_next(nID, nR): identifies nID as a node whose next sibling is nR.

Cycles involving any mixture of these two relations are forbidden. And there must be exactly one document node (per XML document).

Various refinements and controlled redundancies are possible, which may make different operations or traversals of the tree more convenient. For example

• node_relations(nID, nPar, nL, nR, nReuben, nBenjamin): identifies nID as a node with the specified parent, left sibling, right sibling, first child, and last child.

For example, given the node identities specified above for the examples in section 2-1, the L1 tree could be described thus using node_firstchild and node_next:

node_firstchild(L1,n1).
node_firstchild(n1,n5).
node_firstchild(n5,n8).
node_firstchild(n8,-).
node_firstchild(n10,-).
node_firstchild(n11,n13).
node_firstchild(n13,-).

node_next(L1,-).
node_next(n1,-).
node_next(n10,-).
node_next(n11,-).
node_next(n13,-).
node_next(n5,n11).
node_next(n8,n10).

node_relations(L1,-,-,-,n1,-).
node_relations(n1,L1,-,-,n5,n11).
node_relations(n5,n1,-,n11,n8,n10).
node_relations(n8,n5,-,n10,-,-)
node_relations(n10,n5,n8,-,-,-)
node_relations(n11,n1,n5,-,n13,n13).
node_relations(n13,n11,-,-,-,-).

Concurrent documents

Concurrent XML constructs several trees over the same character data. Each of those trees may be described in the same way as any XML tree; for simplicity and regularity we assume here that all pcdata nodes in the document are shared among all trees, and that no other nodes are shared.³ The first change needed is to change some of the constraints on the relations by specifying that:

• There may be more than one document node. The nodes reachable from a given document node by traversing the node_firstchild and node_next relations are said to appear in the given document.
• Every pcdata node appears in every document.
• Each other node appears in exactly one document.

The second necessary change is to specify, in the node_next relation, an additional column to indicate which tree the relation applies to. For convenience, we use the identifier used in the start- and end-tags of elements in that example. (In SGML, this is the identifier of the root element of that tree; in XCONCUR it is the arbitrary identifier used for the document node.):

• node_next(nID, nmTree, nR): identifies nID as a node whose next sibling, in tree nmTree, is nR.

No similar change is needed for the node_first relation, since the only nodes which appear in more than one tree are PCDATA nodes, which have no children and thus no first children, in any tree.

The concurrent trees for the example in section 2-1 are represented thus:

/* document L1 */
node_firstchild(L1,n1).
node_firstchild(n1,n5).
node_firstchild(n5,n8).
node_firstchild(n8,-).
node_firstchild(n10,-).
node_firstchild(n11,n13).
node_firstchild(n13,-).

node_next(L1,L1,-).
node_next(n1,L1,-).
node_next(n5,L1,n11).
node_next(n8,L1,n10).
node_next(n10,L1,-).
node_next(n11,L1,-).
node_next(n13,L1,-).

/* document L2 */
node_firstchild(L2,n4).
node_firstchild(n4,n7).
node_firstchild(n7,n8).
node_firstchild(n9,n10).

node_next(L2,L2,-).
node_next(n4,L2,-).
node_next(n7,L2,n9).
node_next(n8,L2,-).
node_next(n9,L2,-).
node_next(n10,L2,n13).
node_next(n13,L2,-).

Colored XML

Like CONCUR, colored XML defines multiple trees over the document, distinguished by color so that a collection of data may have (for example) a red, a green, and a blue tree sharing nodes. The n-ary representation of multi-colored trees is almost the same as the n-ary representation of XML trees, but adds a color column as part of the key:

• parent_children(nID, color, sequence of nChild): identifies nID as a node whose children, in the tree colored color, are the nChild nodes in the sequence.

The simpler relations are similarly augmented:

• node_firstchild(nID, color nReuben): identifies nID as a node whose first child, in the tree colored color, is nReuben.
• node_next(nID, color, nR): identifies nID as a node whose next sibling in the tree colored color is nR.

The more general description of a node and all of its neighbors is again similar to that for XML trees, with the addition of a color column:

• node_relations(nID, color, nPar, nL, nR, nReuben, nBenjamin): identifies nID as a node in the tree colored color with the specified parent, left sibling, right sibling, first child, and last child in that tree.

It follows from the rules of construction that in a set of n colored trees, any node may have up to n parents, no two of which share a color.

The relational representation of the example of section 2-1 as a set of multi-colored trees would be very similar to the one given above for concurrent trees, if we substitute “red” for “L1” and “blue” for “L2” in the node_next relation, and add a column with the appropriate value to the rows of the node_first relation. The individual node relations remain unchanged.

A more interesting example, however, would be the actors / movies / awards example of section 2-2. It is left as an exercise for the reader.

Goddag structures

Like multi-colored trees, Goddag structures allow nodes to have multiple parents. But there is no requirement analogous to the rule that the parents of a node must have different colors. The n-ary representation of Goddag structures is thus the same as the n-ary representation of XML trees:

• parent_children(nID, sequence of nChild): identifies nID as a node whose children are the nChild nodes in the sequence.

Restricted Goddags have the same parent_children relation, with the constraint that parents who share children are required to have them in the same sequence.⁴

In colored Goddags, as might be expected from the name, the relation is augmented with a color column:

• parent_children(nID, color, sequence of nChild): identifies nID as a node whose children, in the Goddag colored color, are the nChild nodes in the sequence.

The node_firstchild relation is, for normal and restricted Goddags, the same as in XML.

• node_firstchild(nID, nReuben): identifies nID as a node whose first child is nReuben.

• node_firstchild(nID, color nReuben): identifies nID as a node whose first child, in the graph colored color, is nReuben.

The node_next relation for restricted Goddags is the same as for XML: for any node, there is at most one right sibling:

• node_next(nID, nR): identifies nID as a node whose next sibling is nR.

• node_next(nID, nPar, nR): identifies nID as a node whose next sibling among the children of nPar is nR.

• node_next(nID, nPar, color, nR): identifies nID as a node whose next sibling among the children of nPar is nR in the graph colored color.

The more general node_relations relation described above for the other data structures has no single analog for Goddag structures. We could specify

• node_relations(nID, nPar, [color,] nL, nR, nReuben, nBenjamin): identifies nID as a node [in the graph colored color] which has parent nPar, first child nReuben, last child nBenjamin, and whose left and right siblings, among the children of nPar [in the graph of that color] are nL and nR.

• node_reuben_benjamin(nID, [color,] nReuben, nBenjamin): identifies nID as a node which has first child nReuben and last child nBenjamin [in the graph of the indicated color].
• node_parent_siblings(nID, nPar, [color,] nL, nR): identifies nID as a node [in the graph colored color] which has parent nPar and whose left and right siblings, among the children of that parent [in the graph of that color] are nL and nR.

It is useful, although not strictly speaking essential, to record the identifiers used to identify certain nodes:

• id_node(nm id, nID): indicates that the TexMecs notation of the Goddag structure specified id as a unique identifier for node nID.

The nodes of the sample Goddag of section 2-3 could be represented thus, using the relations for normal Goddags. I omit the node_type relation as redundant:

document(DD).
document(DV).

element(n01,-,"scene").
element(n02,-,"sp").
element(n04,-,"p").
element(n06,-,"lg").
element(n08,-,"l").
element(n10,-,"l").
element(n12,-,"l").
element(n14,-,"sp").
element(n16,-,"p").
element(n18,-,"lg").
element(n19,-,"l").
element(n21,-,"sp").
element(n23,-,"p").
element(n25,-,"lg").
element(n26,-,"l").
element(n28,-,"p").
element(n99,-,"haiku").
element(n98,-,"lg").
element(n97,-,"l").
element(n96,-,"l").
element(n95,-,"l").

attribute(n03,n02,-,who,"HUGHIE").
attribute(n07,n06,-,type,"haiku").
attribute(n15,n14,-,who,"HUGHIE").
attribute(n22,n21,-,who,"HUGHIE").

pcdata(n05,"How did that translation go?").
pcdata(n09,"da de dum de dum,").
pcdata(n11,"gets a new frog,").
pcdata(n13,"...").
pcdata(n17,"Er ...").
pcdata(n20,"it's a new pond.").
pcdata(n24,"Ah ...").
pcdata(n27,"When the old pond").
pcdata(n29,"Right.  That's it.").

id_node("frog",n10).
id_node("new", n08).
id_node("pond",n26).

The graph structure of the example can be represented thus. For brevity I omit rows for nodes which lack children, or which lack following siblings (except for the PCDATA nodes which have multiple parents):

node_firstchild(DD,n01).
node_firstchild(n01,n02).
node_firstchild(n02,n04).
node_firstchild(n04,n05).
node_firstchild(n06,n08).
node_firstchild(n08,n09).
node_firstchild(n10,n11).
node_firstchild(n12,n13).
node_firstchild(n14,n16).
node_firstchild(n16,n17).
node_firstchild(n18,n19).
node_firstchild(n19,n20).
node_firstchild(n21,n23).
node_firstchild(n23,n24).
node_firstchild(n25,n26).
node_firstchild(n26,n27).
node_firstchild(n28,n29).
node_firstchild(n99,n98).
node_firstchild(n98,n97).
node_firstchild(n97,n27).
node_firstchild(n96,n11).
node_firstchild(n95,n20).

node_next(n02,n01,n14).
node_next(n04,n02,n06).
node_next(n08,n06,n10).
node_next(n10,n06,n12).
node_next(n11,n10,-).
node_next(n11,n96,-).
node_next(n14,n01,n21).
node_next(n16,n14,n18).
node_next(n20,n19,-).
node_next(n20,n95,-).
node_next(n23,n21,n25).
node_next(n25,n21,n28).
node_next(n27,n26,-).
node_next(n27,n97,-).
node_next(n97,n98,n96).
node_next(n96,n98,n95).

Other approaches to overlap

It may be worth comparing the representations given here to some other approaches to overlap.

document(D0,'http://www.example.com/lmnl/hammer',L0).

limen(L0,D0,
   "Hey Paul! Would you give me the hammer?",
   {d1,s1,s2,t1,u1,u2},).

range(u1,L0,-,u,0,28).
range(u2,L0,-,u,28,39).
range(d1,L0,-,div,0,39).
range(s1,L0,-,s,0,10).
range(s2,L0,-,s,10,39).
range(t1,L0,-,text,0,30).

Conclusion and further work

A surprising variety of variations on XML can be described by simple modifications to the sequence relation on nodes of the document.

If we allow multiple document nodes, and make it possible for PCDATA nodes to have following siblings in some but not all documents, then we have concurrent XML.

If instead we add a color value as part of the key for the node_firstchild and node_next relations, then the result is multi-colored trees.

If instead of color we add to the node_next relation a new nPar (parent node) column, again as part of the key, then the result is normal Goddag structures.

Further consideration of the expressive power afforded (and not afforded) by these variations may shed light on the nature of the overlap problem, and may help analyse the problem further. Many discussions of overlapping structures have assumed that overlap is the name of a single problem (or at least have passed in silence over the possible differences among examples of overlap); but if each of the data structures described here successfully handles a different set of problems (not necessarily disjoint), with different degrees of naturalness or redundancy, then it seems natural to suppose that there are different kinds of overlapping structures, and that different mechanisms may be appropriate to different problems.

While that outcome may deal a blow to any dream of a unified solution to ‘The Overlap Problem’, it may also mark a stage in the maturation of our understanding of the problem area.