|
|
 top
|
  Subject: Design a DTD to represent the data model for DAGs
Author: John Smith
Date: 26 Feb 2012 02:40 PM
Originally Posted: 26 Feb 2012 02:39 PM
|
Dear all,
I am really stuck on this question and am really struggling as the deadline approaches. So I was wondering if any of you have any ideas that you can share with me. The question is as follows:
A Directed acyclic graph (DAG) has a unique name and consists of a set of nodes and a set of edges. Each node has a label that uniquely identifies it. A node may be a part of more than one graph. Each edge connects two distinct nodes and has an edge weight. An edge is directed from a "head" node to a "tail" node, i.e., an edge connecting head node u to tail node v is different from an edge connecting head node v to tail node u .
In a single graph, given a head node and a tail node, there is at most one edge from the head node to the tail node. A single graph may contain an edge from u to v and an edge from v to u , since these two edges are distinct. In addition, an important property of a DAG is that it does not have any cycles. A sequence of nodes forms a cycle if an edge connects each node in the sequence to the next node in the sequence and an edge also connects the last node in the sequence to the first.
(a) Design a DTD to represent the data model for the DAGs
(b) Is it possible to model the fact that a DAG does not contain a cycle? Justify your answer.
All I have managed is this so far:
<!ELEMENT dags (dag+)>
<!ELEMENT dag (node+, edge+)>
<!ELEMENT node (#PCDATA)>
<!ELEMENT edge (h_node, t_node, weight)>
<!ELEMENT h_node EMPTY>
<!ELEMENT t_node EMPTY>
<!ELEMENT weight (#PCDATA)>
<!ATTLIST dag name ID #REQUIRED>
<!ATTLIST node label ID #REQUIRED>
<!ATTLIST h_node label IDREF #REQUIRED>
<!ATTLIST t_node label IDREF #REQUIRED>
Any help will greatly appreciated. Thank you for reading.
|
|
|
|
