CG.html 19.5 KB

Raw Blame History Permalink

<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta name="generator" content=
    "HTML Tidy for Mac OS X (vers 31 October 2006 - Apple Inc. build 13), see www.w3.org" />
    <title>
      Conceptual Graphs and SWeb - Reflections on Web architecture
    </title>
    <link rel="Stylesheet" href="di.css" type="text/css" />
    <meta http-equiv="Content-Type" content=
    "text/html; charset=us-ascii" />
  </head>
  <body bgcolor="#DDFFDD" text="#000000" lang="en" xml:lang="en">
    <address>
      Tim Berners-Lee<br />
      Initially created: 2001/01/06, last change: $Date: 2008/04/24
      21:23:05 $<br />
      Status: personal view only. Editing status: first draft.
    </address>
    <p>
      <a href="./">Up to Design Issues</a>
    </p>
    <h3>
      Reflections on Web Architecture
    </h3>
    <h4 id="Preface">
      Preface
    </h4>
    <p>
      A couple of times people have refereed my to the Conceptual
      Graphs work. <a href="mailto:mkeeler@u.washington.edu">Mary
      Keeler</a> came deliberately from <a href=
      "http://www.mathematik.tu-darmstadt.de/ags/ag1/iccs2000/Welcome.html">
      a CG conference</a> bearing the message of how the Semantic
      Web was really just Conceptual Graphs - or vice versa.
      However, the articles I looked over at that point didn't give
      me a good sense of what CGs were about - apart from a fervent
      desire to implement some ideas of <a href=
      "http://www.peirce.org/">Charles S. Peirce</a>. I think the
      tendency of the CG examples to relate to natural language
      rather than hard logic made it more difficult for someone of
      my own leanings toward rigid logical processing for the Sweb
      to understand what the CG folks were driving at. Anyway, on
      2001/1/5, I found a pointer John Sowa's "<a href="#[2]">the
      CG Standard</a>", and read through it. It now seems clear
      that CGs stand -- as their spec says - very much on a level
      with KIF. They are a logic, which has a tradition of being
      visualized in circles-and-arrows diagrams extended to new
      depths, but a logic all the same, which includes, as the
      Semantic Web should, higher order logic. And so -- here are a
      few comments about the comparison.
    </p>
    <hr />
    <h1>
      Conceptual Graphs and the Semantic Web
    </h1>
    <p>
      To put it in a nutshell, Conceptual Graphs (CGs) are a logic
      language used for describing closed worlds of logic. They
      have traditionally had a strong emphasis on two-dimensional
      graphical representations, but there are conventional
      serializations, one "Linear Form" much comparable with
      <a href="Notation3.html">N3</a>, and one CG Interchange
      Format (CGIF) which is more official. With various pros and
      cons, they are basically as expressive as KIF -- and so in
      way only have to be webized to a basis for the Semantic Web.
    </p>
    <p>
      Here I go over a few differences and similarities between CGs
      and Semantic Web work based on RDF.
    </p>
    <p>
      I will ignore completely "nonsemantic information" ([1], sec2
      ) in this short comparison.
    </p>
    <h2 id="Webizing">
      Webizing CGs
    </h2>
    <p>
      Let's take the principles of <a href="Webize">webizing a
      language</a> and look at how that applies to CGIF or LF, to
      imagine a semantic web based on CGIF.
    </p>
    <p>
      The first thing we clearly have to so is modify the CG
      syntaxes so that each concept and each relation can be a
      first class object, by having a URI. The syntax modification
      is just to allow the characters in a URI to be included, so
      that an arbitrary concept can be referenced, or an arbitrary
      relation used. A typical way to map URI space to CG
      identifiers would be to make URI of a CGIF identifier a
      concatenation of the URI of the CGIF document, and a hash
      sign and the local CG identifier -- making the local exsting
      identifier a fregament identifier in URI terms.
    </p>
    <p>
      Having mentally webized the language, then the question is
      how such a semantic web language maps onto say languages.
      This is simplified by the fact that the CG spec [1] gives a
      mapping to KIF.
    </p>
    <h2 id="Types">
      Types and Clases
    </h2>
    <p>
      CG and RDF share concept of type. CGs have the restriction
      that that the worlds of concepts and types, and that of
      relationships and relationship types, are disjoint.
      Therefore, you cannot use a CG to express something about a
      relation using a relation. If one wanted a true bidirectional
      mapping, then CGs would have (it seems at first reading) to
      more or less reify -- to describe at a meta level - an
      arbitrary RDF graph. However, this would not in my opinion be
      useful. The designers of CGs intended this disjunction, and
      so the natural mapping is directly from CG concept types to
      RDF Classes, and from CG relations to Properties, and from CG
      Relation Types to RDF Classes which are subclasses of
      rdf:Property.
    </p>
    <p>
      The semantic web logic language has to be universal in that
      it must allow expression of any other language; but it
      certainly does not force every language to be universal
      itself.
    </p>
    <h2 id="Centralize">
      Centralized Notions in CGs
    </h2>
    <p>
      The CG concept of a knowledge base (KB) contains a few
      centralized ideas. These are not in fact architectural
      problem with CGs - they are just engineering decisions which
      were made without the web scaling requirement. Removing does
      no damage the CG idea at all.
    </p>
    <ul>
      <li>The ideal of a closed knowledge base, especially that
      there is a single catalog of all individuals. A KB contains a
      hierarchy of types, a hierarchy of relations, and a central
      catalog of individuals. The hierarchies are no trees, but
      acyclic graphs, so they do not pose a problem above the fact
      that they are closed - A KB must
      </li>
      <li>The fact that a concept is associated wiht a single type.
      In the semantic web, though the original creator of a Thing
      may define a type, logically statements made by third parties
      can equally well make type assertions about a thing, and
      those statements may be in the form of a rdf:type statement.
      </li>
      <li>A coreference set has to have a single dominant concept.
      </li>
    </ul>
    <h2 id="Difference">
      Properties and relations
    </h2>
    <p>
      The main difference which stands out at first reading is that
      RDF properties are always dyadic, while CG relations are
      monadic.
    </p>
    <p>
      The RDF base model, and the N3 method of extending it to a
      logical framework, seem to be supported as a base structure,
      although the lack of N-ary forms shows up as a mismatch, but
      the existence of arcs explicitly in the CG model of an N-adic
      relation suggests a natural mapping back into dyadic RDF when
      n&gt;2. This just leaves a little tension as the two forms
      coexist.
    </p>
    <p>
      The CG world is a bipartite graph - one composed of two
      relations and concepts, which are disjoint. The RDF world,
      while it does consist of links which can be thought of as
      going from thing, via a property, to a thing, does not make
      properties and things disjoint. Everything is a Thing.
    </p>
    <h2 id="Similartie">
      Striking similarities
    </h2>
    <p>
      Some similarities of the CG work and the semantic web to date
      are striking. Both are inspired largely by circles and arrows
      diagrams, and in LF and N3 this even shows though in some
      syntactic forms. People have through the ages been writing
      circles and arrows on whatever material they had to hand
      [Enquire, cavewriting] and in N3 I tried to take this very
      simply into unicode with
    </p>
    <pre>
w3c:Michael  &gt;- org:member -&gt; w3c:team .
</pre>
    <p>
      There was a certain feeling of recognition on seeing John
      Sowa's
    </p>
    <pre>
[Go]-
   (Agnt)-&gt;[Person: John]
   (Dest)-&gt;[City: Boston]
   (Inst)-&gt;[Bus].
</pre>
    <p>
      which in N3 would be
    </p>
    <pre>
@prefix : &lt;#&gt;.
[a :Go]
   &gt;- :agent -&gt; [a :Person; = &lt;#John&gt;];
   &gt;- :dest -&gt; [ a :City; = &lt;#Boston&gt;];
   &gt;- :inst -&gt; [ a :Bus].
</pre>
    <p>
      remarkable down to the final period. Both syntaxes also have
      backward arrows a &lt;- (p) &lt;- b in CG's LF, and
      a&lt;-p-&lt;b in N3. (See also: <a href=
      "../2000/10/swap/test/cg/bus.rdf">the same in RDF</a>)
    </p>
    <h2 id="Context">
      Contexts
    </h2>
    <p>
      The concept of "context" occurs very equivalently in CGs and
      N3, where in both cases a formula is built using quotation.
      In N3, the braces were introduced to encapsulate a set of
      information and talk about it as a set. Using an example from
      [1], loosely "Tom believes that Mary wants to marry a
      sailor":
    </p>
    <pre>
[Person: Tom]&lt;-(Expr)&lt;-[Believe]-&gt;(Thme)-
   [Proposition:  [Person: Mary *x]&lt;-(Expr)&lt;-[Want]-&gt;(Thme)-
      [Situation:  [?x]&lt;-(Agnt)&lt;-[Marry]-&gt;(Thme)-&gt;[Sailor] ]].
</pre>
    <p>
      In N3 this would be, mapping dyadic relations to RDF
      properties,
    </p>
    <pre>
&lt;#Tom&gt; a :Person; :believes [a :Proposition; = {
    &lt;#Mary&gt; a :Person; :wants [ a :Situation; = {
        &lt;#Mary&gt; :marriedTo [ a :Sailor ]
    ]}
]}.
</pre>
    <p>
      (In the above, the "=" is an statement of equivalence which
      makes up for the inability otherwise of N3 syntax to allow an
      anonymous context to be subject and object of a statement.)
      In RDF, my own style is to assume that often the type of a
      thing, when it can be deduced from the predicate's range or
      domain, should not be stated explicitly. For example, the
      object of any <em>believes</em> may be a proposition, and the
      object of any <em>wants</em> may be a situation. So an N3
      expression of the above in practice might be more like:
    </p>
    <pre>
&lt;#Tom&gt; :believes {
    &lt;#Mary&gt; :wants {
        &lt;#Mary&gt; :marriedTo [ a :Sailor ]
    }
}.
</pre>
    <p>
      Leaving aside the question of whether this is a good model
      for the English sentence, and a lot of philosophy and
      linguistics (which I generally avoid by not trying to express
      natural language). The CG world often uses diagrams, such as
      this one from [1] to describe the above formula:
    </p>
    <p style="text-align: center">
      <img src="Sowa/cgstand_files/tombelv.gif" alt=
      "Tom belives Mary wants to marry" />
    </p>
    <p>
      In N3, the circle-and-arrow diagram I would draw would
      include an arrow from the rectangle for the situation to the
      [circle] for the marriage to indicate that there is a
      universal quantification there.
    </p>
    <p>
      There are other mappings which once could made, none of which
      give quite such a neat result. One mapping of CGs to RDF
      would map the CG arcs to RDF properties, which for the above
      would be:
    </p>
    <pre>
[ a :Belief;
    :expr &lt;#Tom&gt;;
    :thme: [ a Proposition; = {
        [   a :Want;
            :expr &lt;#Mary&gt;;
            :thme [ a :Situation; = {
                [ a :Marriage; :agent &lt;#Mary&gt;; :thme: [a :Sailor]]
            }
        ]
    }]
].
</pre>
    <p>
      In English this would be, "There is a belief, experienced by
      Tom, that "there is a want, felt by Mary, that there should
      be a situation: ``Mary is married to a Sailor'' ".
    </p>
    <h2 id="Quantifier">
      Quantifiers and Lambda
    </h2>
    <p>
      I have not gone into the comparison in great detail in this
      area. Both N3 and CFIF have existential and universal
      quantification, though the universal quantification is
      declared an area of the spec under development called
      "defined quantifiers". Both have, like RDF, implicit
      existential quantification from anonymous nodes.
    </p>
    <p>
      A question I did not resolve in CGIF if how one can determine
      the scope of a quantifier introduced using the "?x" and "*x"
      terminology. There was a clarification in [1] that (I think)
      universal quantifiers have a higher scope than existentials
      of the same scope -- the same convention as in N3. In N3 in
      the model one has to link the quantified variable directly to
      its scope context using a log:forAll or log:forSome
      statement.
    </p>
    <p>
      N3 has no Lambda as such. Once can write out a double
      implication define the meaning of a new term (Property or
      small set of related properties) by giving a double
      implication with the equivalent formula, using universally
      quantified variables for the formal parameters.
    </p>
    <p>
      The issues faced in the two designs do a appear to have a
      high overlap. The semantic web has to work also in an open
      context, defining the meaning, if any, of a nested expression
      when referred to out of context.
    </p>
    <h2 id="Conclusion">
      Conclusion
    </h2>
    <p>
      Conceptual Graphs are easily integrated with the Semantic Web
      as it is, the mapping being apparently very straightforward.
      The export of a CG in CGIF or LF into N3 looks to be a
      suitable exercise for the reader ;-). An interesting and more
      challenging exercise would be to build a CG machine -- and a
      modified CG syntax -- which can import a graph containing
      URIs which reference external concepts. The problem that
      relation types in CGs are not concepts is not huge, as there
      are many systems - especially ontological systems -which have
      a similar restrictions and with whom interchange would be
      possible.
    </p>
    <p>
      There is an interesting subset of CGs, called "simple graph"
      which are all one context, with no negations or "defined
      quantifiers", but which can contain universal quantifiers,
      and these map directly into the RDF M&amp;S 1.0, or N3
      without braces.
    </p>
    <p>
      The RDF base model, and the N3 method of extending it to a
      logical framework, seem to be supported as a base structure,
      although the lack of N-ary forms shows up as a mismatch.
    </p>
    <p>
      All in all, there is a huge overlap, making the two
      technologies very comparable and hopefully easily
      interworkable.
    </p>
    <hr />
    <h2 id="Appendix:">
      Appendix: Comparison of terms
    </h2>
    <table border="1">
      <caption>
        Comparison of terms
      </caption>
      <tbody>
        <tr>
          <td>
            CG
          </td>
          <td>
            RDF/N3
          </td>
          <td>
            Comment
          </td>
        </tr>
        <tr>
          <td>
            concept
          </td>
          <td>
            resource/node
          </td>
          <td></td>
        </tr>
        <tr>
          <td>
            relation
          </td>
          <td>
            Property
          </td>
          <td>
            In RDF, Properties are only dyadic; inCG, relations are
            n-adic
          </td>
        </tr>
        <tr>
          <td>
            type
          </td>
          <td>
            Class
          </td>
          <td>
            In RDF, "type" is the Property stating membership of
            resource in a Class.
          </td>
        </tr>
        <tr>
          <td>
            arc
          </td>
          <td>
            Property - for N&gt;3
          </td>
          <td>
            Arcs in CG are used to model nadics in terms of
            dyadics, a la RDF. An arc is considered a pair, rather
            than a triple. It has a small integer associated with
            it (cf XLink role, or rdf:1, rdf:2 etc)
          </td>
        </tr>
        <tr>
          <td>
            context
          </td>
          <td>
            context (N3 only)
          </td>
          <td>
            Remarkable coincidence of terms
          </td>
        </tr>
        <tr>
          <td>
            coreference
          </td>
          <td>
            daml:equivalent/ =
          </td>
          <td>
            Rather complex CG architecture for a simple function?
            In CG, a coreference set (a form of equivalence class)
            has a single defining ("dominant") concept. This makes
            the equivalence not completely symmetrical. Perhaps it
            is simply useful in practice to use a dominant concept
            as a name for the coreference set.
          </td>
        </tr>
        <tr>
          <td>
            actor
          </td>
          <td>
            -
          </td>
          <td>
            Philosophical difference: in SWeb, real world is linked
            directly to things and properties, rather thn have
            another layer of represnetation. In CGs, links to
            "reality" are represented as separate from the main CG.
          </td>
        </tr>
        <tr>
          <td>
            abstract syntax
          </td>
          <td>
            model
          </td>
          <td></td>
        </tr>
        <tr>
          <td>
            identifiers
          </td>
          <td>
            URI
          </td>
          <td>
            CGIF identifiers are NOT case sensistive. URIs and XML
            IDs are. (This was a result of difficulty in specifying
            case insenistivity in a international way.)
          </td>
        </tr>
        <tr>
          <td>
            knowledge base
          </td>
          <td></td>
          <td>
            A consistent self-contained set of types,
          </td>
        </tr>
        <tr>
          <td>
            Linear Form
          </td>
          <td>
            N3
          </td>
          <td>
            Syntaxes introiduced for human readability, both driven
            by the need to serialize circles and arrows diagrams
            showing though in the syntax (&gt;- agent -&gt; bus .)
            and coincidentally similar uses of [] and . as
            delimiters
          </td>
        </tr>
        <tr>
          <td>
            signature
          </td>
          <td>
            range, domain
          </td>
          <td>
            As RDF's properties are only diadic, the signature is
            range and domain. More importantly philosophically, a
            lambda expression has a sole definitive signature,
            whereas about Properties there may exist defintive and
            third party statements about their range and domain.
          </td>
        </tr>
      </tbody>
    </table>
    <hr />
    <h2 id="References">
      References
    </h2>
    <p>
      <a name="John" id="John">[1] John F. Sowa</a>, ed. "<a href=
      "http://www.bestweb.net/~sowa/cg/cgstand.htm">Conceptual
      Graph Standard</a>", ["standard" state of which I am not
      certain. Some parts are labelled under deveopment].
    </p>
    <p>
      <a name="[2]">[2]</a> John F. Sowa, <a href=
      "http://www.bestweb.net/~sowa/cg/">Conceptual Graphs</a>, web
      page
    </p>
    <p>
      Related DesignIssues:
    </p>
    <ul>
      <li>
        <a href="Notation3.html">Notation3</a>
      </li>
      <li>
        <a href="Webize">Webizing</a>
      </li>
    </ul>
    <hr />
    <p>
      <a href="Overview.html">Up to Design Issues</a>
    </p>
    <p>
      <a href="../People/Berners-Lee">Tim BL</a>
    </p>
  </body>
</html>