Comment puis-je représenter un graphe réseau en utilisant XML Schema?

Question

J'ai un modèle de données représentant un graphe de réseau. J'ai donc des Entités hôtes (avec leur adresse et beaucoup d'autres attributs/éléments) et j'ai besoin de modéliser l'entité Lien (représentant un lien réseau entre un nœud source et un nœud de destination, avec des attributs de latence et de débit).

La question est, je ne peux pas imaginer un moyen approprié de concevoir le réseau en utilisant XML Schema. Comment dois-je le concevoir correctement? (Après la conception XML, j'utiliserai ce schéma avec une application Java).

Je suppose que je devrais créer un élément réseau en tant qu'élément racine du schéma, mais comment puis-je gérer les liens entre les hôtes? Je ne sais pas si je dois mettre l'élément Link à l'intérieur de l'élément racine Network, donc à côté de l'élément Host, ou si je dois mettre l'élément Link dans l'élément Host.

Voici un guide exemple

<xsd:element name="network" type="NetworkType"/> 
<xsd:complexType name="NetworkType"> 
     <xsd:sequence> 
       <xsd:element name="host" type="HostType"/> 
       <!-- don't know if put Link element here or inside HostType--> 
     </xsd:sequence> 
</complexType> 

S'il vous plaît ne pas tenir compte manquer la déclaration du schéma et ainsi de suite, je juste besoin d'un conseil de modélisation et, si vous le pouvez, un exemple de la façon d'utiliser « hôte » ou de l'hôte Attribuez "hostName" (non montré dans l'exemple ci-dessus) comme clé et comment faire des éléments/attributs de "link" sourceHost et destHost pour faire référence au précédent.

EDIT: Je vais juste vous en dire plus sur le problème de modélisation, j'ai remarqué que ma question n'est pas très précise. Depuis que je modélise une infrastructure réseau, je ne me soucie même pas d'un Vertex (Host) non "connecté" à d'autres sommets (hosts). Cela dit, j'ai pensé à modéliser le graphe au moyen de liens seulement, et comme je ne me soucie pas du vertex source et du vertex de destination (pour mon cas) je pourrais modéliser en insérant seulement un lien pour chaque couple de sommets connectés. Mais le fait est que je dois modéliser une application XML (et un schéma XML) à partir d'une interface générique Java et représentant toutes les informations s'y référant. Supposons l'interface est

public interface NetworkReader { 
     public Set<Host> getHosts(); 
     public Host getHost(String hostName); 
     public Connection getConnectionPerformance(Host h1, Host h2); 
} 

Compte tenu d'une interface comme celui-ci, je choosed d'inclure également des éléments d'hôte dans mon élément racine réseau (il peut rendre les accès d'accueil plus facile requis par la première et la deuxième méthode de l'interface), qui est pourquoi la considération ci-dessus à propos d'un élément de réseau de liens seulement échoue (à mon avis).

Comme vous pouvez le constater, la troisième méthode nécessite des informations sur l'état de liaison donné par deux hôtes, c'est pourquoi j'ai aussi besoin de l'élément Link dans ma XSD.

Answer 1

Puisque vous dites que c'est le problème de modélisation qui vous intéresse, pas les détails XSD, nous allons examiner des solutions de rechange. En résumé, un graphe est une paire (V, E), où V est un ensemble arbitraire et E est une relation sur V, c'est-à-dire un ensemble de paires (v1, v2) où (a) v1 et v2 sont tous deux dans V et (b) (v2, v1) est dans E si et seulement si (v2, v1) est dans E. Les membres de V sont les sommets du graphe et les membres de E sont les arêtes. Certaines définitions de graphe font de E un sac d'arêtes, pas un ensemble, de sorte que deux sommets peuvent être reliés par zéro ou plusieurs arcs; certaines définitions autorisent et d'autres interdisent les bords avec v1 = v2.

En XML, il y a trois façons assez évidentes pour représenter un graphique:

1. Un élément pour chaque sommet et un élément pour chaque bord donnant la paire de points de terminaison dans un ordre quelconque, ni enfermés dans l'autre . Un graphique de trois nœuds a, b, c, avec des arêtes de b à lui-même et d'un être peut-être:

   <graph> 
       <vertex id="a"/> 
       <vertex id="b"/> 
       <vertex id="c"/> 
       <edge endpoints="a b"/> 
       <edge endpoints="b b"/> 
   </graph> 
   

   Certains utilisateurs (et probablement des chaînes d'outils) préféreront que les extrémités des bords soient donnés par les enfants, pas par un attribut; c'est votre schéma, vous décidez sur la base de vos propres connaissances, compétences et goûts.

2. Un élément pour chaque nœud et des éléments subordonnés indiquant les autres éléments auxquels il est adjacent. Si nous laissons le bord à enregistrer à chaque extrémité et pas nécessairement les deux, nous pourrions avoir pour le graphique décrit ci-dessus

   <graph> 
       <vertex id="a"> 
       <adjacent vertex="b"/> 
       </vertex> 
       <vertex id="b"> 
       <adjacent vertex="b"/> 
       </vertex> 
       <vertex id="c"/> 
   </graph> 
   

   En fonction de la fréquence relative des opérations telles que la mise à jour et la recherche, nous pourrions préférer exiger que tous les le bord est enregistré aux deux extrémités, donc chaque sommet a comme enfants une liste complète de tous les nœuds adjacents (au prix d'une validation plus compliquée du XML); alors nous pourrions avoir besoin:

   <graph> 
       <vertex id="a"> 
       <adjacent vertex="b"/> 
       </vertex> 
       <vertex id="b"> 
       <adjacent vertex="b"/> 
       <adjacent vertex="a"/> 
       </vertex> 
       <vertex id="c"/> 
   </graph> 
   

   Notez que dans cette représentation, l'ensemble des arêtes est représenté indirectement par la relation de contiguïté. Pour certaines raisons, c'est une bonne idée; pour d'autres, ce sera probablement une mauvaise idée. Votre choix. Tout comme il est possible de subordonner les arêtes aux sommets du XML, il est possible de subordonner les sommets aux arêtes. Comme le graphe n'est pas nécessairement connecté, nous aurons également besoin d'un autre moyen de signaler les sommets qui ne sont pas incidents à un bord quelconque. Notre graphique exemple pourrait être:

   <graph> 
       <edge endpoints="a b"/> 
       <edge endpoints="b b"/> 
       <isolated vertices="c"/> 
   </graph> 
   

   Ici, il est l'ensemble des sommets qui est implicite (il est distinct-values(for $e in $graph/edge return tokenize(@endpoints,' '), tokenize($graph/isolated/@vertices,' '))).

L'un de ces éléments est simple à définir dans XSD; faire en sorte que le XSD applique les contraintes d'intégrité référentielle nécessaires sera probablement plus facile dans certaines représentations que dans d'autres. (En particulier, dans la deuxième variante exigeant que chaque arête soit représentée aux deux extrémités sera difficile dans XSD 1.0.)

Notez que dans chaque cas il y a un certain compromis entre la franchise d'expression et la redondance. Dans la méthode 1, nous avons une représentation XML simple de l'ensemble des sommets et aussi de l'ensemble des arêtes. Mais la séparation des deux signifie que pour vérifier que les arêtes sont représentées correctement, nous devons examiner chaque valeur de point d'extrémité dans les arêtes pour nous assurer qu'il désigne un sommet connu. De plus, si nous ne sommes intéressés que par des sommets connectés à d'autres sommets - si un vertex isolé est une erreur de codage - alors dans la méthode 1, nous devons également vérifier chaque sommet pour nous assurer qu'il est nommé endpoint par au moins un bord. Dans la méthode 2, un point de terminaison est garanti pour chaque arête, car les arêtes n'apparaissent qu'en tant qu'enfants des sommets; nous devons cependant vérifier chaque identifiant pour l'autre sommet sur chaque arête. Et la méthode 2 nécessite soit des informations redondantes sur chaque lien sous chaque point de terminaison, soit elle nécessite une recherche de tous les nœuds dans le réseau afin de localiser tous les bords connectés à un bord donné.

Si vous avez des informations non triviales à stocker sur chaque noeud et chaque lien, la méthode 1 sera la moins redondante.

Answer 2

Vous pouvez modéliser en utilisant les types d'hôte dans un élément de liaison:

<?xml version="1.0"?> 
<schema targetNamespace="urn:your:domain" 
     xmlns:ud="urn:your:domain" 
     xmlns="http://www.w3.org/2001/XMLSchema" 
     elementFormDefault="qualified" 
     attributeFormDefault="unqualified" 
     blockDefault="substitution" 
     version="2.0"> 

<complexType name="hostType"> 
    <sequence> 
    <element name="…" type="string" minOccurs="0"/> 
    <element name="…" type="string" minOccurs="0"/> 
    </sequence> 
    <attribute name="…" type="string"/> 
</complexType> 

<element name="Link"> 
    <complexType> 
    <sequence> 
     <element name="Source" type="ud:hostType"/> 
     <element name="Destination" type="ud:hostType"/> 
    </sequence> 
    </complexType> 
    <attribute name="…" type="string"/> 
</element> 

</schema>