CS 6999 Semantic Web Techniques
Assignment 3
Syllabus Assigns Notes Labs Project Resources	All questions are to be answered. This assignment is due Oct 24, to be handed in at the beginning of class. 1. This is a DTD for simple (almost natural-language) 'forward' rules and facts: <!ELEMENT forward ((rule | fact)*)> <!ELEMENT rule (if, then)> <!ELEMENT fact (#PCDATA)> <!ELEMENT if (#PCDATA)> <!ELEMENT then (#PCDATA)> Are the following XML elements valid with respect to this DTD (write "yes" or "no" behind them)? <forward> </forward> <forward> the weather </forward> <forward> <fact> it snows </fact> </forward> <forward> <rule> if it rains then the road gets wet </rule> </forward> <forward> <rule> <if> it rains </if> <then> the road gets wet </then> </rule> </forward> <forward> <fact> it rains </fact> <rule> <if> it rains </if> <then> the road gets wet </then> </rule> </forward> 2. Consider these XML elements for 'forward' (p => c) and 'backward' (c <= p) rules: <forward> <rule> <if> p </if> <then> c </then> </rule> </forward> <backward> <rule> <conc> c </conc> <prem> p </prem> </rule> </backward> Inductively complete this XML DTD (write into the "..." lines) for 'backward' rules and facts: <!ELEMENT backward (................)> <!ELEMENT rule (................)> <!ELEMENT ........ (................)> <!ELEMENT ........ (................)> <!ELEMENT ........ (................)> 3. Complete the following XSLT template – by just filling in the "..." versions – for the (XML-to-XML) transformation of 'forward' rules and facts into 'backward' rules and facts: <xsl:template match="forward"> <........> <xsl:apply-templates/> </........> </xsl:template> <xsl:template match="rule"> <....> <....><xsl:value-of select="...."/></....> . . . </....> </xsl:template> <xsl:template match="fact"> <....> . . . </....> </xsl:template> Could this transformation be 'inverted' – mapping 'backward' rules and facts into 'forward' rules and facts – without information loss (write in "yes" or "no" here)? 4. Using the following rules for “connected_to”, use j-DREW-BU to build all of the facts about what is connected to what. connected_to_via_Acadian_Lines('Sydney', 'Truro'). connected_to_via_Acadian_Lines('Truro', 'Amherst'). connected_to_via_SMT('Amherst', 'Sussex'). connected_to_via_SMT('Sussex', 'Fredericton'). connected_to(X, Y) :- connected_to_via_Acadian_Lines(X, Y). connected_to(X, Y) :- connected_to_via_SMT(X, Y). %Symmetry connected_to(X, Y) :- connected_to(Y, X). %Transitivity connected_to(X, Y) :- connected_to(X, Z), connected_to(Z, Y). Now, add the following rules for creating the route from place to place. For the moment, comment out the symmetry and transitivity rules (above). connected_to(X, nil, X). connected_to(X, r(X, R), Y) :- connected_to(X, Z), connected_to(Z, R, Y). Up to here we suppose that you have been able to calculate the tables of what is connected to what, and via what route. Are all of your routes there? If not, which ones are missing? Suppose that you had not removed the symmetry rule. Try running the full set of rules and facts. What occurs? What could you do to control the j-DREW-BU rule engine to run in this case? Here is a domain-independent way of forcing j-DREW to not investigate all of an infinite space of possibilities, but to give the user a limited amount of output: Do not allow a newFact to be selected if its length is more than, say, some maximum. Implement this solution with facts allowed to be up to some given length. (Hint: look at newFact.symbols.length.) 5. We discussed the definition of subsumption and the method of computing it, which were quite different. In this question we suppose that C and D are both atoms and they do not have any variables in common. For each of the following conditions, give an example C and D such that the condition holds, or state why no such example exists: 1. C does not subsume D, yet C unifies with D 2. C does not subsume D, yet after grounding D, C unifies with the grounded D.

Maintained by Bruce Spencer