This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 24568 - Is the type system really a lattice? Or just a partially ordered set?
Summary: Is the type system really a lattice? Or just a partially ordered set?
Alias: None
Product: XPath / XQuery / XSLT
Classification: Unclassified
Component: Data Model 3.0 (show other bugs)
Version: Proposed Recommendation
Hardware: PC All
: P2 normal
Target Milestone: ---
Assignee: Norman Walsh
QA Contact: Mailing list for public feedback on specs from XSL and XML Query WGs
Depends on:
Blocks: 24569
  Show dependency treegraph
Reported: 2014-02-06 21:26 UTC by C. M. Sperberg-McQueen
Modified: 2014-10-20 12:28 UTC (History)
1 user (show)

See Also:


Description C. M. Sperberg-McQueen 2014-02-06 21:26:47 UTC
Section 2.7.4 Type system of the XDM PR draft [1] reads in part:

  Item types in the data model form a lattice rather than a hierarchy: 
  in the relationship defined by the derived-from(A, B) function, 
  some types are derived from more than one other type. Examples 
  include functions (function(xs:string) as xs:int is substitutable 
  for function(xs:NCName) as xs:int and also for function(xs:string) 
  as xs:decimal), and union types (A is substitutable for union(A, B) 
  and also for union(A, C).


The text is correct to say that the set of types does not form a hierarchy.  But do they form a lattice?  

My understanding (such as it is) is that a partially ordered set forms a lattice if and only if for any two members a and b of the set, there is a unique least upper bound of a and b, and a unique greatest lower bound for a and b.  

In section 19.2 [2], XSLT 3.0 says that two items do not necessarily have a unique  least upper bound (join):

  In some cases the above entries require computation of the least 
  common type of two types T and U. Since item types form a lattice 
  rather than a hierarchy, there may be a set of types V such that 
  T and U are both subtypes of every type in V, and no type in V 
  is unambiguously the "least" common type in the sense that all 
  the others are subtypes of it. In this situation the choice of 
  which type in V to use as the inferred static type is 


I'm not sure what pairs of items the XSLT spec has in mind, but if they exist, then it may be wrong to say that our types form a lattice.

Unions are perhaps a sufficient example.  Since XSD's union types are ordered (so the unions (A, B) and (B, A) are both supersets of both A and B), and there will be no other types definable in XSD which are intermediate between them and A or B, so they are both least upper bounds for the pair A and B.

Functions (to take the other example named in the paragraph quoted from XDM) are described by XPath as forming a hierarchy -- but if we accept A and B as subtypes of both union(A, B) and union(B, A) then functions don't form a hierarchy, either.

If the sequence of membertypes in the definition of unions is NOT considered significant for these purposes, then perhaps it is correct after all to say that the type system forms a lattice.  But before deciding that all is well, it would be a good idea to find out why XSLT 3.0 says there may not be a unique least common type (which I am taking to mean least upper bound, or join) for two item types.
Comment 1 Norman Walsh 2014-10-13 16:36:37 UTC
The minutes of XML Query WG Face-To-Face Meeting #563 Minutes -- 2014-02-17 DAY ONE (

J4.1.1 Bug 24568 - Is the type system really a lattice? Or just a 
partially ordered set?

Mike: I think that if you look at it certain ways the types may form a 
lattice, but if you look at just the types you have syntax for they 
don't. Propose removing the claim that it is a lattice.

No objections.

DECISION: Make the editorial change to remove the description of the 
type system as a lattice, adding a note that the type system is not a 

In addition, I see that the 3.1 data model now says, in part:

"Item types in the data model form a directed graph, rather than a hierarchy or lattice: ..."

I propose that this bug can be closed as overtaken by events.