What does the category of RDF models look like in Institution Theory?

Question

The Question in short

Here is the question in its pure form. Details of my reasoning can be found below.

The RDF1.1 spec semantics defines a model to consist of a set IR of objects and IP of predicates. The way they define a Model is Isomorphic to the following type definition.

$RDFModel = \mathscr{P}(IR \times IP \times IR)$

Note that any Model is thus a Quiver as can be seen by noticing that for any $M: RDFModel$ the first and third projections give us the functions we need:

$ \pi_1, \pi_3: M \to IR$

so that the graph representation of a model below is justified.

Anyway since RDFModel is a powerset one can look at it as a poset category where the element Models built from a set of Resources R and Predicates P are the objects, and the morphisms are the subset relations. Call this category $\Bbb{M}_{RP}$

Questions:

1. Is such a Poset category $\Bbb{M}_{RP}$ what an RDF Institution would send a Signature $\Sigma$ to? Ie is this the right type $ Mod(\Sigma): \Bbb{M}_{RP}$ ?
2. Since there can be many such categories of different sizes depending on IP and IR (Appendix B: Finite Interpretations), it is likely that these categories of poset can form a category which we could call $\Bbb{M}$. (Somewhat like the category of boolean algebras). Is that the category that the functor $Mod$ has as range? Ie. $Mod: Sig^{op} \to \Bbb{M}$
3. In the category $\Bbb{M}$ what is the smallest category (initial or final object?)
4. Any category $\Bbb{M}$ contains many models so for any such model some sentences will be satisfied others not. In modal logics those are thought of as possible worlds. But in David Lewis' sense those are complete objects. It looks like possible worlds must be fixed points - or final objects - in a category of models of ever increasing size. Is there a way to capture these purely category theoretically? (Also can one call those mini models possible worlds?)
5. Is there a way to state how the open world assumption works in this context?

Context of the Question

The RDF1.1 semantic spec comes with a simple model discussed in a previous Stack Exchange question. The aim of this question is to see how that can be brought into the larger space of Category Theoretical Institutional Theory started by the famous computer scientist Joseph Goguen. The longer term aim is to make sense of modal logic in RDF. For a list of academic papers on Category Theory and RDF as well as institutional theory and modal logic see RDF and Institution Theory (IT) message on ncatlab. These papers are good at locating things in the abstract framework, but don't even get into the detail of what the RDF Models are. I just want to make sureI understand correctly what is going on by developing some simple examples.

Example using RDF1.1 modelling

So here is a simple example Model written out in the structure presented by the RDF1.1 semantic spec. (As we will see a bit further below this can be made a lot easier to understand with arrow diagrams) We need a set of Resources IR, and Predicates IP, so I chose a simple example with 6 objects in IR, 5 Properties in IP and 4 types of relations on IR

I start with predicates in terms of colors to emphasize that we are dealing with models here. Later we move on to syntax, and so it will be natural to have names for the colored arrows. Initially we just want to say the world contains distinctions. Here the colors represents type of relations, grey {0} for is "older than", dark green {1,3} for "shook hands", light green {2,4} for "knows", pink {5,6} for the relation relating a person to a statement written on their T-Shirt, and light blue {7,8} relating a person to their name (another literal).

Making the model simpler using Triple based Graphs

We have shown in a previous Stack Exchange question that way of writing things to be isomorphic to the following definition of $RdfModel$

$RdfModel = \mathscr{P}(IR \times IP \times IR)$

So that we can redraw the above diagram in the much clearer category theoretical diagramatic style. We can justify this mathematically because Category Theory defines a Quiver - which other call a Graph, and other call a Directed Graph - as two sets A and N and two functions $domain$ and $codomain$ such that

$domain, codomain: A \to N$

Clearly we have these here since the first projection of $RdfModel$ could be thought of as the $domain$ and the third projection as the $codomain$ function. Note also that every Quiver gives rise to a free category.

What models add to a Quiver is that it can state that a number of arrows have the same type, which we express here by giving arrows colors.

This image of Vint Cerf shaking hands with Tim Berners-Lee should make it more intutive, and help show why this is useful, as it helps us describe things like Tim meeting Vint.

As practical semanticist we like to have non set elements in the sets of our Models to describe practical stuff like that, and that is fine: we have a category of Sets with Ur-elements we can work with.

Ok, that is for an illustrated background.

Simple Category of Models organised by subset inclusion

Now given that any graph is a subset of $IR \times IP \times IR$ we can draw up a simplified version of the relation between all such models using just the subset Partial Order that stems from such a set of subobject (Category Theory's generalisation of the notion of subsets - do we need to generalise? Who knows: it could be useful...). Because this works with powersets and these quickly explode in complexity I have limited myself to 4 elements of IR, to real objects and 2 literals, and 2 types of relations: "older than" and "has name".

In yellow above are all the models that fit the actual world. The most comprehensive such model is M7. In light blue we have different possible worlds/models (I may be able to have different shades for different incompatible possible worlds there). The biggest graph before Top N8 models worlds where Tim and Vint have the same age, worlds which presumably would require quite a lot of change to the actual one - some complex scenario involving Vint being frozen for over a decade or so before being born... In pink we have models that we don't really want to allow at all, such as model X1 which states that Tim is older than the literal "Vint Cerf", or X2 where Tim is related by the name relation to Vint (but Vint Cerf is a person not a name). X3 is the union of that nonsense (are these what one would term impossible worlds?) RDFS and Description Logic Based OWL vocabularies allow one to exclude those as models, but I think the basic minimal RDF framework does not.

We can see that moving up any arrows into a model (eg M7) is the union of the models into it, which form a logical conjunction or a categorical coproduct. Moving in the opposite direction, say looking at the opposite category we have arrows out of a model such as M7 form its logical disjunctions, or categorical products.

Relating to Institution Theory

This brings us to Institution Theory. The few articles on RDF and Institution Theory (IT) explain as any IT intro does that an institution consists of

1. a category of $Sig$ of Signatures $\Sigma$: For our example we could have a ground graph signature $\Sigma$ containing only a small subset of IRIs and some literals to correspond to the objects in our model. (No existential quantifiers (aka blank nodes) for example). IRIs are just the web equivalent of mathematical symbols, designed so that people can globally coin new symbols without fearing a name clash. They stand for International Resource Identifiers and are specified syntactically by RFC3987. IRI ⊇ URI ⊇ URL ∪ URN
2. a functor $Mod$ from $Sig^{op}$ to $Cat$ the category of categories selecting for each object in the category $\vert Sig \vert$ a category of models. So I guess that a signature with 4 IRIs and 2 literals can give us a signature to the category of Partially ordered models I drew above.
3. a functor $Sen$ from $Sig$ to sets of Sentences in $Set$ (here we need no ur-elements I think, since we can encode the Unicode alphabet with the empty set and sets thereof)
4. A relation $\models_\Sigma \space \subseteq \vert Mod(\Sigma) \vert \times Sen(\Sigma)$

But those papers don't really tell me what such a category of models is. So that's what I am trying to make sure I have understood correctly with the simple example given above.

Now, IT does not state what their set of sentences look like. RDF has so many different syntaxes (RDF/XML, NTriples, Turtle, JSON-LD, ...) to cater to the different (at times religious) fashions that it would be silly to put real syntactic sentences there. Better have sets of Abstract Syntax Graphs as our sentences. As it happens those look very much like our models. If we can distinguish just IRIs and Literals types as defined by IETF and W3C, and just define the type

$GNode = IRI+Literal$

We may want to specialise this to a signature $\Sigma$ which only contains a subset of IRIs and Literals needed for a model (as the RDF1.1 Semantic web syntax hints at in Appendix B: Finite Interpretations). So we could have $\Sigma_{IRI}$ to refer to the set of IRIs used by that signature, $\Sigma_{Literal}$ to refer to the set of Literals used by that signature and $\Sigma_{GNode}$ to refer the disjoint union of the IRIs and Literals of that signature.

Then we can define the type of (syntactic) RdfGraph for a signature as

$Sen(\Sigma) = \mathscr{P}(\Sigma_{GNode} \times \Sigma_{IRI} \times \Sigma_{GNode}) $

which clearly is a subcategory of our Models. It would be interesting to regard that indeed as a category, in which case we could get from those to the Set required by Institution Theory by selecting the set of objects $|Sen(\Sigma)|$ of our signature.

So now I suppose if G7 is the top yellow model in the model Poset category above then given that $ ":" : IRIRef \times String \to IRIRef$

is the append operation on the string component of a IRIRef, and we have defined the strings

foaf = <http://xmlns.com/foaf/0.1/>
timbl = <https://www.w3.org/People/Berners-Lee/card#i>

where surrounding a string with angle brackets turns it into a IRI reference (as opposed to a literal string)

$ G7 \models \text { { timbl foaf:name "Tim Berners-Lee" . }}$

but so does the top green model $J7$ where Tim and Vint have the same age

$ J7 \models \text { { timbl foaf:name "Tim Berners-Lee" . }}$

So I guess now that the category which is the range of the $Mod$ functor - which remember maps each signature $\Sigma$ to a category of models - must be a category with growing number of objects in IR and PR, up to something like infinity. The morphisms in this category would relate one poset category to the next, in a way that is faithful to the poset structure in some way - presumably by keeping the same types of distinctions. (I am not quite sure what this is yet)

Answer 1

There's a lot to unpack here and I don't know about Goguen's institutions. But perhaps I can give a partial answer to your question.

Let's start with "simple interpretations" of RDF, as defined by the spec, forgetting about richer languages like RDFS or OWL. If we ignore IRIs and literals, as in the first part of your question, then an RDF model is a simple object: an edge-labeled graph, whose vertices are resources, edges are triples, and edge labels are predicates.

To view RDF models as a category of models, we can use a variation of the graph indexing category, as discussed, for example, in David Spivak's book on category theory for the sciences. Define a category $\mathbf{RDF}_0$ with three objects $T$, $R$, and $P$, representing the triples, resources, and properties, and three morphisms $subj: T \to R$, $pred: T \to P$, $obj: T \to R$, representing the subject, predicate, and object of a triple. An RDF model is a functor $M: \mathbf{RDF}_0 \to \mathbf{Set}$. There is a functor category of all such models, whose morphisms are natural transformations. Under this definition, a morphism of RDF models is just a label-preserving graph homomorphism.

IRIs and literal can be incorporated within this general approach. Define a new category $\mathbf{RDF}$ consisting of the objects and morphisms of $\mathbf{RDF}_0$, plus two additional objects $IRI$ and $L$, representing the IRIs and literals, and two additional morphisms $iri: IRI \to R + P$ and $lit: L \to R$, representing interpretations of the IRIs and literals as resources and/or properties. Here the sum of objects ($+$) is a coproduct (disjoint union). We can handle the sum in multiple ways. We can say that $\mathbf{RDF}$ is the free cocartesian category generated by the above objects and morphisms. Or we can think of $\mathbf{RDF}$ as a sketch.

On this definition, an RDF model, as defined by the "simple interpretations" of the RDF 1.0 spec, is a (coproduct-preserving) functor $M: \mathbf{RDF} \to \mathbf{Set}$. As before, morphisms of RDF models are natural transformations between such functors.

That's all I have time to say right now. If you're interested, I can describe a different way of thinking about this problem that lends itself better to richer systems like RDFS or OWL.

Answer 2

My supervisor thought the problem with the above view of the model from the IT point of view is that it forgets the interpretation part in the range of the Mod functor. Indeed the above definition of Mod takes a signature to a category of pure models. But if one thinks of things this way then one would end up with an Institution being much closer to what David Lewis called a language or indeed we call a language: that is a particular assignment of words/sentences to meanings via a grammar.

If we look at the definition of the Bare RDF Institution BRDF in the article “Semantic web languages–towards an institutional perspective” [1] we indeed find the following definition for a signature $\Sigma$ consisting just of a set $RR$ of resource references

$RR$-models I are tuples $I = (R_I, P_I, S_I, ext_I)$, where $R_I$ is a set of resources, $P_I$ is a subset of $R_I (P_I ⊆ R_I)$ - the set of properties, $S_I : RR → R_I$ is a mapping function that maps each resource reference to some resource, and $ext_I : P_I → \mathscr{P}(R_I × R_I)$ is an extension function mapping each property to a set of pairs of resources that it relates.

Clearly their use of I suggests they were also thinking in terms of an interpretation, not a model. We can rearrange that structure to $I = (S_I, (R_I, P_I, ext_I))$ or even more concisely to $I = (S_I,M_I)$ where $S_I: RR \to R_I$ is the semantic function, and $M_I ⊆ R_I \times P_I \times R_I$ is our model of triples.

If that is correct then the name Mod in institution theory is a bad name for a such a functor, as it suggests a model, and that can be used as say David Lewis would to mean a possible world for example, or sets of those, One would then expect there to many functors from a signature to a model, one for each language, whereas we actually have one mapping from a signature to a category of interpretations. Calling such a Functor $Int$ would be more intutive, but that clashes with the wide useage for integers in computing. So I thought one may want to use the ☿ symbol for Mercury the Roman version of the greek god Hermes, the god of interpretation. The discussion on that subtopic could continue on ncatlab institution entry

[1] Lucanu, Dorel, Yuan Fang Li, and Jin Song Dong. “Semantic web languages–towards an institutional perspective.” Algebra, Meaning, and Computation. Springer, Berlin, Heidelberg, 2006. 99-123.