Problem 1; 14-Apr-2000

XML: Foundations, Techniques, Applications; Summer 2000

Harold Boley; DFKI, Univ. Kaiserslautern

Using only a pencil and the left half of a paper, construct a random, non-trivial well-formed XML element with tag names x, y, z and sub(...sub)elements as follows: Write an x/y/z start-tag such as <x>, pronouncing it "angle, x, angle"; leave plenty of space and write, vertically below, the matching end-tag </x>, pronouncing it "angle, slash, x, angle" (with practice, you can also pronounce the 'x-colored brackets' <x> as "start-x" and </x> as "end-x"). Then fill in, indented by two blanks, another x/y/z start-tag such as <y>, pronouncing it "angle, y, angle" ("start-y"); leave some space and write, again vertically below, the matching end-tag </y>, pronouncing it "angle, slash, y, angle" ("end-y"). If there is more space left below the current subelement, proceed with the next subelement vertically below it; otherwise, proceed by filling in the space between two other pairs of matching tags, indented by two further blanks. Continue in this way to fill in the space between matching pairs of tags, repeatingly using tag names from the set {x, y, z}. However, instead of adding more tag pairs, you may also fill in natural-language phrases between matching pairs of tags.

a) Count the number of subelements of your generated XML element, including the main element in the sum. For each tag name x, y, z give the number of subelements using it.

b) Write a Prolog term on the right half of the A4 paper such that an XML tag pair like <x> ... </x> becomes a Prolog structure x( ... ). Align each constructor and its opening parenthesis such as x( with the corresponding start-tag <x>; align each matching closing parenthesis ) with the corresponding end-tag </x>. Put an XML natural-language phrase into double quotes (") before its use in a Prolog structure.

c) Draw the node-labeled, (left-to-right-)ordered tree for which the XML element and equivalent Prolog structure are just two linearized representations. Hint: The vertical subelement/substructure extension corresponds to subtree breadth; the horizontal subelement/substructure indention corresponds to subtree depth.

d) List the notational (dis)advantages of the XML and Prolog representations.

e) Can anything be logically wrong with the legal Prolog structures corresponding to arbitrary XML elements that use repeated tags from {x, y, z}? Hint: Consider ways in which not only XML but also Prolog is "less formal" than logic (types, modes, arities, ...).