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) Are the following XML elements valid with respect to this DTD (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>

 

b) Further consider these XML elements for binary single-premise 'backward' [p(…,…) <= q(…,…)] DatalogML rules and 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 OO jDREW to query their represented social network (OO jDREW employs 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 all results of the (bottom-up) generation employing OO jDREW BU:

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

Briefly explain this correspondence.

 

 

 

 

 

5.     Assume w, wi, x, xi, y, yi (i=1,2) are individuals.

For
two classes A and B, you are given the unary ABox assertions A(w1), A(y1), B(x1), and B(y1) extensionally as sets thus:

 

          A :  {  w1,  y1 }
          B :  {  x1,  y1  }

 

For a predicate R, you are given the binary ABox assertions R(w, w1), R(x, x1), R(x, x2), R(y, y1), and R(y, y2) extensionally as a set of pairs thus:

 

          R :  {  (w, w1),

                    (x, x1),

                    (x, x2),

                    (y, y1),

                    (y, y2)  }

 

Compute the extensional sets of the following intensional class descriptions (Forall and Exists denote Description Logic’s intensional class-property-restricting quantifiers; Intersect and Union denote Description Logic’s corresponding intensional class operators):

 

          Forall R.A :

 

          Exists R.B :

 

 

          Forall R.(A Intersect B) :

 

 

          Exists R.(A Intersect B) :

 

 

          Forall R.(A Union B) :

 

 

          Exists R.(A Union B) :

 

 

 


Maintained by Harold Boley