CS 6795 Semantic Web Techniques

Assignment 3


Syllabus
Assigns
Notes
Labs
Project
Resources

1.     This is a DTD for the Datalog Markup Language (DatalogML):

 

<!ELEMENT kb                   (dl*) >

<!ELEMENT dl                    (relationship, relationship*) >

<!ELEMENT relationship    (relator, (ind | var)*) >

<!ELEMENT relator             (#PCDATA) >

<!ELEMENT ind                  (#PCDATA) >

<!ELEMENT var                  (#PCDATA) >

 

a) Complete the following RNC (write into the "..." lines) such that it is equivalent to the DTD:

 

  start = kb          

  kb = element kb { dl* }

  dl = element dl { relationship, relationship* }

  relationship = element relationship { ................................................................... }

  relator = element relator { .............................. }

  ind = element ind { .............................. }

  var = element var { .............................. }

 

b) Are the following XML elements valid with respect to this DTD/RNC (write "yes" or "no" behind them)?

 

  <kb> </kb>

 

  <kb> some facts and rules </kb>

 

  <kb> <dl> head_of_fact </dl> </kb>

 

  <kb>

    <dl>

       <relationship>

         <relator>q</relator>

         <ind>a</ind>

         <var>c</var>

       </relationship>

    </dl>

  </kb>

 

  <kb>

    <dl>

       <relationship>

         <relator>p</relator>

         <var>x</var>

         <ind>b</ind>

       </relationship>

       body_of_rule

    </dl>

  </kb>

 

  <kb>

    <dl>

       <relationship>

         <relator>p</relator>

       </relationship>

       <relationship>

         <relator>q</relator>

       </relationship>

    </dl>

  </kb>

 

c) Further consider the next XML element, for binary single-premise 'backward' [p(…,…) <= q(…,…)] DatalogML rules, and the XML element following it, for binary single-premise 'forward' [q(…,…) => p(…,…)] Datalog RuleML rules:

 

    <dl>

       <relationship>

         <relator>p</relator>

         <var>x</var>

         <ind>b</ind>

       </relationship>

       <relationship>

         <relator>q</relator>

         <ind>a</ind>

         <var>x</var>

       </relationship>

    </dl>

 

    <Implies>

       <Atom>

         <Rel>q</Rel>

         <Ind>a</Ind>

         <Var>x</Var>

       </Atom>

       <Atom>

         <Rel>p</Rel>

         <Var>x</Var>

         <Ind>b</Ind>

       </Atom>

    </Implies>

 

Inductively complete this XML DTD (write into the "..." lines) for n-ary single-premise Datalog RuleML rules:

 

  <!ELEMENT Implies          (.....................................)>

  <!ELEMENT Atom            (...............................................)>

  <!ELEMENT ........            (.....................................)>

  <!ELEMENT ........            (.....................................)>

  <!ELEMENT ........            (.....................................)>



2.     Complete the following XSLT template – by just filling in the "..." versions – for the (XML-to-XML) transformation of ground binary single-premise DatalogML into ground binary single-premise Datalog RuleML rules:

 

    <xsl:template match="dl">

      <......................>

        <xsl:apply-templates select="relationship[position()=2]"/>

        ……………………………………………………………

      </......................>

    </xsl:template>

 

    <xsl:template match="relationship">

      <....................>

        <..............><xsl:value-of select="......................."/></..............>

        .   .   .

        .   .   .

      </....................>

    </xsl:template> 

 

Could this transformation be 'inverted' – mapping ground binary single-premise Datalog RuleML into ground binary single-premise DatalogML – without information loss (write in "yes" or "no" with a very brief explanation here)?





3.     Again consider the following Datalog program in Prolog syntax:

artist(X) :- painter(X).

artist(X) :- actor(X), improvising(X).

painter(X) :- expressionist(X).

expressionist(sara).

actor(mary).


a)
Give its grounding (consistently replacing variables by constants in each rule):

___________________________________

___________________________________

________________________________________________________

________________________________________________________

_____________________________________________

_____________________________________________

__________________

__________________


b)
Construct its Least Herbrand Model by fixpoint iteration (starting with the set of ground facts, applying the rules bottom-up to add new ground facts, etc., until the set no longer changes):













4.     Using a knowledge base with the following facts and rules about fictitious people, employ a Prolog engine such as OO jDREW for (top-down) querying of their represented social network (we employ here OO jDREW's POSL syntax, where variables have a ‘?’-prefix, hence constants can be upper-case). 

knows(Mary, John).

knows(John, Peter).

knows(Peter, Cora).

may_know(?X, ?Y) :- knows(?X, ?Y).

may_know(?X, ?Y) :- knows(?X, ?Z), may_know(?Z, ?Y).


Give all results of the following (top-down) queries employing OO jDREW TD:

knows(Mary, John)

 

 

knows(Mary, ?Whom)

 

 

 

knows(?Who, ?Whom)

 

 

 

 

 

may_know(Mary, Mary)

 

 

may_know(John, Cora)

 

 

may_know(John, ?Whom)

 

 

 

 

 

Give its Least Herbrand Model, i.e. all results of the fixpoint iteration through (bottom-up) ground-fact generation, e.g. employing OO jDREW BU (via https://github.com/OOjDREW/OOjDREW/downloads):

 

 

 

 

 

 

 

 

 

 

 

 

 

Give a (top-down) query that correspond to the (bottom-up) generation.

 

 

 

Briefly explain this correspondence.

 

 

 

 

 

 

 


Maintained by Harold Boley