Written Exam

Practical Semantics: Transformations, Models, and Metadata for the Web; 27 July 2001

Harold Boley; DFKI, Univ. Kaiserslautern


Family Name     First Name      Matriculation Number     Signature


a) Are the following markups well-formed XML elements (write "yes" or "no" directly behind them)?

<alfa> 0 </alfa>
<alfa> 0 1 </beta>
<job> mechanic (skilled), repair </job>
<inequality> 4 > 3 </inequality>
<inequality> 3 < 4 </inequality>
<job> mechanic <skilled>, repair </job>
<ad> <ad> </ad> </ad>
<ad> </ad> <ad> </ad>
<ad> <who> firm </who> <whom> <job> mechanic </job> </whom> </ad>
<ad> <who> firm </whom> <whom> <job> mechanic </job> </who> </ad>

b) This is a simple DTD for the 'pre(fix)' application of unary functions:

<!ELEMENT pre       (fun, arg)>
<!ELEMENT arg       (num | var | pre)>
<!ELEMENT fun       (#PCDATA)>
<!ELEMENT num       (#PCDATA)>
<!ELEMENT var       (#PCDATA)>
Are the following XML elements valid with respect to this DTD (write "yes" or "no" behind them)?
<pre> <fun> ! </fun> <num> 4 </num> </pre>

<pre> <fun> ! </fun> <arg> </arg> </pre>

<pre>
  <fun> ! </fun>
  <arg> <num> 4 </num> </arg>
</pre>

<pre>
  <fun> ! </fun>
  <arg> <pre> <var> x </var> </pre> </arg>
</pre>

c) Consider these XML elements for 'pre(fix)' and 'post(fix)' applications that are "flat", i.e. have "no other applications inside arguments":

<pre>
  <fun> ! </fun>
  <arg> <var> x </var> </arg>
</pre>

<post>
  <arg> <var> x </var> </arg>
  <fun> ! </fun>
</post>
Inductively complete the following XML DTD (write into the "..." lines) for flat 'postfix' applications over numbers (num) and variables (var), i.e. not over other 'postfix' applications:
<!ELEMENT post      (..., ...)>
<!ELEMENT arg       (... | ...)>
<!ELEMENT ...       (.......)>
<!ELEMENT ...       (.......)>
<!ELEMENT ...       (.......)>

d) Complete the following XSLT template - by just filling in the six versions of "..." - for the (XML-to-XML) transformation of flat 'prefix' applications into flat 'postfix' applications ("flat" again meaning "no other applications inside arguments"):

  <xsl:template match="pre">
    <....>
      <...><xsl:value-of select="..."/></...>
      .   .   .
    </....>
  </xsl:template>
Could this transformation be 'inverted' - mapping flat 'postfix' applications to flat 'prefix' applications - without information loss (write in "yes" or "no" here)?

e) A binary 'do' relation can be defined for the natural numbers in 'suc' notation as follows:

do(0,0).
do(suc[M],suc[suc[N]]) :- do(M,N).
Give the first two elements of the Herbrand model of 'do' (write in here):
Express the "relation" of the second argument of 'do' to its first argument:

f) This is simplified RDF metadata about two fictitious people:

<rdf:RDF>
  <rdf:Description about="http://www.home4many/john">
    <name>John Smith</name>
    <spouse rdf:resource="http://www.home4many/mary"/>
  </rdf:Description>
  <rdf:Description about="http://www.home4many/mary">
    <name>Mary Smith</name>
    <spouse rdf:resource="http://www.home4many/john"/>
  </rdf:Description>
</rdf:RDF>
Draw the directed labeled graph (DLG) that constitutes the RDF diagram of this XML element (use space below). Hint: URLs, going into ovals, and texts, going into rectangles, may be arbitrarily shortened, as long as they remain unique (e.g.: '.../john' or just 'john'; 'John S' or just 'JS').