Exploration de graphiques avec un chemin le plus court

Avez-vous déjà joué six degrés de Kevin Bacon?

L’idée est que quiconque à Hollywood est lié à l’acteur en moins de six étapes. Le jeu utilise un graphique de connaissances pour représenter les connexions du film, où les acteurs sont des nœuds et les bords connectent les co-stars. La recherche de la connexion la plus courte à Kevin Bacon est rendue possible par un algorithme appelé chemin le plus court, ou recherche de largeur (BFS), pour trouver le nombre minimum d’étapes (films) reliant un acteur à Kevin Bacon.

Les algorithmes de finition PathFinding Excel pour trouver des solutions aux problèmes liés à la planification des itinéraires, à l’optimisation du réseau et à l’allocation des ressources. Les calculs de chemin les plus courts sont primordiaux dans de nombreuses applications telles que la récupération de l’information, la recherche de relations entre les documents dans les systèmes de recommandation et le moyen le plus court de passer de A à B. Ils améliorent les approches de recherche sémantique avancées qui utilisent des requêtes SPARQL pour récupérer les données du graphique en parcourant rapidement un graphique de connaissances et en identifiant des documents sémantiquement similaires.

Progrès MarkLogic Server 12 soutient maintenant nativement le Algorithme de chemin le plus court graphique pour aider à augmenter les performances de vos requêtes graphiques et à améliorer la pertinence contextuelle de votre Systèmes de chiffon sémantique. De plus, MarkLogic a longtemps pris en charge les charges de travail multimodel en utilisant des graphiques, des documents et des recherches. Les organisations génèrent des données dans de nombreux formats. Alors que d’autres solutions essaient de normaliser toutes les données en une seule structure, la plate-forme MarkLogic vous permet d’utiliser le meilleur modèle de base de données pour ces données. Il est important de comprendre que toutes les données ne sont pas créées égales et peuvent avoir différentes formes et schémas.

Dans MarkLogic Server, nous pouvons tirer parti de ces modèles pour créer un graphique de données interconnectées, des collections de documents et des vues de tablature pour les rapports. Les graphiques vous permettent de représenter des informations dans un réseau interconnecté de faits et d’informations. Certains cas d’utilisation représentatifs pour les graphiques sont des jumeaux numériques, des réseaux sociaux et des systèmes de recommandation.

Voyons comment cela fonctionne.

Algorithmes d’orientation des systèmes de recommandation

Considérons les degrés de séparation d’un lecteur et les critiques que chacune de ces personnes a soumises. Nous allons construire une requête qui va jusqu’à trois degrés de séparation de la personne actuelle et combine les revues pour chaque personne sur le chemin. Nous utiliserons l’algorithme de chemin le plus court en combinaison avec des données multimodèles pour alimenter un système de recommandation.

Les cas d’utilisation du graphique peuvent contenir de grandes quantités de données. Les explorer peut être écrasant lorsque vous avez plusieurs façons de naviguer d’un point à un autre. Le chemin le plus court est un algorithme qui peut être exploité pour déterminer le chemin le plus court et le plus efficace d’un point à un autre.

MarkLogic Server expose le Chemin le plus court à travers des extensions SPARQL.

XDMP: Shpestpath utilise ces arguments nommés:
XDMP: Démarrez – le nœud de départ dans le graphique
xdmp: fin – le nœud de fin dans le graphique
xdmp: modèle – une instruction SPARQL qui correspond aux données du graphique
XDMP: chemin – le résultat imbriqué d’un chemin le plus court
xdmp: longueur – la longueur du nœud et des bords du chemin

Marklogic a également exposé le chemin le plus court à travers l’API optique en utilisant le modificateur du plan BreftestPath.

Construire un exemple

Créons quelques exemples de données pour illustrer l’utilisation du chemin le plus court. Les commandes suivantes peuvent être exécutées dans le Console de requête Marklogic. Les exemples de données crée un graphique de personnes interconnectées. Une requête de mise à jour SPARQL peut être utilisée pour insérer des personnes dans un graphique nommé. Notez la relation FOAF: connaît. Cela créera un bord étiqueté entre deux nœuds de personnes dans le graphique.

# Simple Social Graph 

PREFIX foaf: <http://xmlns.com/foaf/0.1/>  
PREFIX dc: <http://purl.org/dc/elements/1.1/>  
PREFIX ex: <https://example.com/graph/people#>  
 
INSERT DATA 
{ 
     GRAPH <https://example.com/graph/people>  
     { 
        ex:1            a                 foaf:Person ; 
                        dc:identifier     1 ;              
                        foaf:firstName    "Andrey" ; 
                        foaf:lastName     "Ohlsen" ; 
                        foaf:knows        ex:2 ; 
                        foaf:knows        ex:3 . 
 
        ex:2            a                 foaf:Person ; 
                        dc:identifier     2 ;              
                        foaf:firstName    "Rodolphe" ; 
                        foaf:lastName     "Alexandersen" ;         
                        foaf:knows        ex:4 . 

        ex:3            a                 foaf:Person ; 
                        dc:identifier     3 ;              
                        foaf:firstName    "Wilow" ; 
                        foaf:lastName     "Duckels" .        

        ex:4            a                 foaf:Person ; 
                        dc:identifier     4 ;              
                        foaf:firstName    "Sheilakathryn" ; 
                        foaf:lastName     "Arkley" ;         
                        foaf:knows        ex:5 . 
 
        ex:5            a                 foaf:Person ; 
                        dc:identifier     5 ;              
                        foaf:firstName    "Frank" ; 
                        foaf:lastName     "Grayley" . 
    } 
} 

Maintenant que nous avons des exemples de données dans la base de données, nous pouvons exécuter une requête SPARQL pour voir ces personnes et leur réseau de relations. La relation FOAF: sait être élargie en utilisant Chemins de propriétés SPARQL. Les chemins de propriété vous permettent de parcourir une profondeur arbitraire d’un graphique. Dans ce cas, nous utiliserons le modificateur + pour trouver une ou plusieurs occurrences de la relation Knows.

La requête

## query 
 
PREFIX foaf: <http://xmlns.com/foaf/0.1/> 
PREFIX dc: <http://purl.org/dc/elements/1.1/>  

SELECT * FROM <https://example.com/graph/people> WHERE { 
  ?person a foaf:Person ; 
          foaf:knows+ ?knows . 
} 
ORDER BY ?person ?knows 

Le résultat

Le résultat ci-dessus montre le point de départ et les sauts possibles à la fin d’un chemin.

Dans l’exemple suivant, nous utiliserons le chemin le plus court pour voir comment nous pouvons passer de la personne numéro un à la personne numéro cinq. En utilisant les extensions SPARQL, nous définissons un début, une fin et un modèle. Le filtre garantit que nous ne recherchons que les deux personnes intéressées.

La requête

## query 
PREFIX xdmp: <http://marklogic.com/xdmp#> 
PREFIX dc: <http://purl.org/dc/elements/1.1/>  
PREFIX ex: <https://example.com/graph/people#>  
PREFIX foaf: <http://xmlns.com/foaf/0.1/> 

SELECT   ?path ?length

FROM <https://example.com/graph/people> 
WHERE {   
  ( 
    [xdmp:start ?person] 
    [xdmp:end ?knows] 
    [xdmp:pattern "?person foaf:knows ?knows"] 
  ) xdmp:shortestPath ( 
    [xdmp:path ?path]  
    [xdmp:length ?length]  
  )  
  FILTER (?person = ex:1 && ?knows = ex:5) 
} 
 

Si vous préférez rédiger votre application à l’aide de JavaScript, l’algorithme de chemin le plus court est également exposé dans le API optique marklogique.

Requête

'use strict'; 

const op = require('/MarkLogic/optic'); 

// Triple Prefixers 

const ex = op.prefixer('https://example.com/graph/people#'); 
const foaf = op.prefixer('http://xmlns.com/foaf/0.1/'); 

// Pattern Match for known people 
const person = op.col('person'); 
const knows = op.col('knows'); 

// Shortest Path Variable Setup 
const start = op.col('start'); 
const end = op.col('end'); 
const path = op.col('path'); 
const length = op.col('length'); 

op.fromTriples([op.pattern(start, foaf('knows'), end)]) 
  .shortestPath(start, end, path, length) 
  .where(op.and(op.eq(start, ex('1')), op.eq(end, ex('5')))) 
  .result(); 

Résultat

{ 
    "start": "https://example.com/graph/people#1", 
    "end": "https://example.com/graph/people#5", 
    "path": [ 
        { 
            "start": "https://example.com/graph/people#1", 
            "end": "https://example.com/graph/people#2" 
        }, 
        { 
            "start": "https://example.com/graph/people#2", 
            "end": "https://example.com/graph/people#4" 
        }, 
        { 
            "start": "https://example.com/graph/people#4", 
            "end": "https://example.com/graph/people#5" 
        } 
    ], 
    "length": 3 
} 

Combiner les données graphiques et documentées

La plate-forme MarkLogic vous permet de stocker des données de document (JSON, XML, etc.) aux côtés des données du graphique dans la même base de données. Dans ce cas, nous utiliserons JSON Records contenant de brèves métadonnées sur les critiques de livres. Ces critiques de livres seront utilisées conjointement avec le graphique pour recommander le lecteur des livres et des critiques supplémentaires.

L’extrait de code suivant insérera les enregistrements dans la même base de données.

'use strict'; 

declareUpdate(); 

const reviews = [ 
    { 
      "uuid": "ae23fdfc-06eb-4cfa-8812-b1c47a87f8d2", 
      "title": "Historical Tales", 
      "reviewer_id": 1, 
      "review_date": "2024-06-17T14:48:43.687096Z", 
      "rating": 3, 
      "genre": "non-fiction" 
    }, 
    { 
      "uuid": "f8358d6e-0ffe-42df-a3ff-a7e4cc0a5042", 
      "title": "Fictional Wonders", 
      "reviewer_id": 4, 
      "review_date": "2024-11-03T14:48:43.687169Z", 
      "rating": 5, 
      "genre": "fiction" 
    }, 
    { 
      "uuid": "661c355d-833f-4ba6-bf04-b8ffa2d6f602", 
      "title": "Non-Fiction Insights", 
      "reviewer_id": 2, 
      "review_date": "2025-02-19T14:48:43.687204Z", 
      "rating": 3, 
      "genre": "non-fiction" 
    }, 
    { 
      "uuid": "aedfc481-7aa2-495a-8628-b72f690399b9", 
      "title": "Historical Tales", 
      "reviewer_id": 1, 
      "review_date": "2025-01-16T14:48:43.687231Z", 
      "rating": 5, 
      "genre": "non-fiction" 
    }, 
    { 
      "uuid": "c09cb86b-7c16-4b5c-b161-eebed1dbda4e", 
      "title": "Love and Betrayal", 
      "reviewer_id": 1, 
      "review_date": "2024-07-01T14:48:43.687257Z", 
      "rating": 1, 
      "genre": "romance" 
    }, 
    { 
      "uuid": "44a00e0e-7626-4955-a7aa-168f746ff917", 
      "title": "Fictional Wonders", 
      "reviewer_id": 4, 
      "review_date": "2024-05-25T14:48:43.687320Z", 
      "rating": 2, 
      "genre": "fiction" 
    }, 
    { 
      "uuid": "766a9792-ba71-4969-b3cc-eb03b3714e3c", 
      "title": "Love and Betrayal", 
      "reviewer_id": 5, 
      "review_date": "2024-12-23T14:48:43.687358Z", 
      "rating": 2, 
      "genre": "romance" 
    }, 
    { 
      "uuid": "366cc1b0-6c68-4d8b-9698-91b675d543de", 
      "title": "The Hidden Truth", 
      "reviewer_id": 4, 
      "review_date": "2024-11-21T14:48:43.687383Z", 
      "rating": 1, 
      "genre": "sci-fi" 
    }, 
    { 
      "uuid": "0e34b7be-5d48-4c1c-856d-bda58eacb242", 
      "title": "The Hidden Truth", 
      "reviewer_id": 2, 
      "review_date": "2024-08-12T14:48:43.687425Z", 
      "rating": 2, 
      "genre": "sci-fi" 
    }, 
    { 
      "uuid": "f5102ffc-b53f-4791-9142-3f9454cdc1d1", 
      "title": "The Great Adventure", 
      "reviewer_id": 5, 
      "review_date": "2024-10-14T14:48:43.687444Z", 
      "rating": 1, 
      "genre": "fiction" 
    } 
  ] 
  ; 

const options = { 
        permissions : xdmp.defaultPermissions(), 
        collections : 'https://example.com/documents/reviews' 
}; 

reviews.forEach(review => xdmp.documentInsert('/data/reviews/' + review.uuid + '.json', review, options)); 

Nous pouvons créer une vue en plus de ces données pour projeter les informations au format de tablature. L’extraction du modèle (TDE) est une configuration qui crée un schéma et une vue qui mappe les données JSON à un tableau des lignes et des colonnes. Cela peut être exploité dans SQL et notre API optique.

'use strict'; 
declareUpdate(); 
 
const tde = require("/MarkLogic/tde.xqy"); 
 
const template = xdmp.toJSON( 
    { 
        "template": { 
            "description": "Review Template", 
            "context": "/", 
            "collections": ["https://example.com/documents/reviews"], 
            "rows": [ 
                { 
                    "schemaName": "Review", 
                    "viewName": "Metadata", 
                    "viewLayout": "sparse", 
                    "columns": [ 
                        { 
                            "name": "source", 
                            "scalarType": "string", 
                            "val": "xdmp:node-uri(.)", 
                            "nullable": false, 
                            "invalidValues": "ignore" 
                        }, 
                        { 
                            "name": "uuid", 
                            "scalarType": "string", 
                            "val": "uuid", 
                            "nullable": false, 
                            "invalidValues": "ignore" 
                        }, 
                        { 
                            "name": "reviewer_id", 
                            "scalarType": "int", 
                            "nullable": true, 
                            "val": "reviewer_id" 
                        }, 
                        { 
                            "name": "title", 
                            "scalarType": "string", 
                            "val": "title", 
                            "nullable": false, 
                            "invalidValues": "ignore" 
                        }, 
                        { 
                            "name": "rating", 
                            "scalarType": "int", 
                            "nullable": true, 
                            "val": "rating" 
                        }, 
                        { 
                            "name": "genre", 
                            "scalarType": "string", 
                            "nullable": true, 
                            "val": "genre" 
                        }, 
                        { 
                            "name": "review_date", 
                            "scalarType": "dateTime", 
                            "nullable": true, 
                            "val": "review_date" 
                        }, 
                    ] 
                } 
            ] 
        } 
    }) 
 
var perms = [xdmp.arrayValues(xdmp.defaultPermissions(null, 'elements'))]; 
perms.push(xdmp.permission("rest-reader", "read")); 
perms.push(xdmp.permission("rest-writer", "update")); 
 
tde.templateInsert("/tde/book-review.json", template, perms); 

Nous avons maintenant deux modèles de données distincts dans le système. Un graphique représentant les personnes que nous connaissons et leurs relations les uns avec les autres. Et des documents qui suivent leurs critiques.

La requête suivante utilise l’API optique pour traverser le graphique et trouver tous les chemins les plus courts avec une longueur maximale de trois degrés. Une fois que nous avons ces chemins, nous pouvons examiner les données de vue et les fusionner avec les données de chemin. Notez que l’ordre par partie de la requête prend en compte le score d’examen et la distance dans le réseau social.

Requête (optique avec SPARQL et vues):

'use strict'; 

const op = require('/MarkLogic/optic'); 

const pathPlan = op.fromSPARQL(` 
PREFIX xdmp: <http://marklogic.com/xdmp#> 
PREFIX dc: <http://purl.org/dc/elements/1.1/>  
PREFIX ex: <https://example.com/graph/people#>  
PREFIX foaf: <http://xmlns.com/foaf/0.1/> 

SELECT *  
FROM <https://example.com/graph/people> 
WHERE {   
  ( 
    [xdmp:start ?start] 
    [xdmp:end ?end] 
    [xdmp:pattern "?start foaf:knows ?end . ?person dc:identifier ?personId . ?knows dc:identifier ?knowsId"] 
  ) xdmp:shortestPath ( 
    [xdmp:path ?path]  
    [xdmp:length ?length]  
  )  
  #FILTER (?start = ex:1 && ?length = 3) 
} 
`)  

const reviews = op.fromView('Review', 'Metadata') 

pathPlan 
 .unnestLeftOuter('path','pathUnnest','hop') 
  .bind([ 
    op.as('knowsId', op.map.get(op.col('pathUnnest'), 'knowsId')) 
  ])   
  .select(['start', 'end', 'path', 'length', 'knowsId']) 
  .joinInner(reviews, op.on(op.col('reviewer_id'), op.col('knowsId'))) 
  .orderBy([op.asc(op.col('length')), op.desc(op.col('rating'))]) 
  .offsetLimit(0, 10) 
  .result() 

Requête (optique avec triples et vues)

'use strict'; 

const op = require('/MarkLogic/optic'); 

// Triple Prefixers 
const ex = op.prefixer('https://example.com/graph/people#'); 
const dc = op.prefixer('http://purl.org/dc/elements/1.1/'); 
const foaf = op.prefixer('http://xmlns.com/foaf/0.1/'); 

// Pattern Match for known people 
const person = op.col('person'); 
const personId = op.col('personId'); 

const knows = op.col('knows'); 
const knowsId = op.col('knowsId'); 

 // Shortest Path Variable Setup 
const start = op.col('start'); 
const end = op.col('end'); 
const path = op.col('path'); 
const length = op.col('length'); 

 const pathPlan = op.fromTriples([ 
    op.pattern(start, foaf('knows'), end), 
    op.pattern(start, dc('identifier'), personId), 
    op.pattern(end, dc('identifier'), knowsId), 
  ]) 
  .shortestPath(start, end, path, length) 
  .where(op.and(op.eq(start, ex('1')), op.le(length, 3))); 

const pathResults = pathPlan.result(); 

const reviews = op.fromView('Review', 'Metadata') 

pathPlan 
  .unnestLeftOuter('path','pathUnnest','hop') 
  .bind([ 
    op.as('knowsId', op.map.get(op.col('pathUnnest'), 'knowsId')) 
  ])   
  .select(['start', 'end', 'path', 'length', 'knowsId']) 
  .joinInner(reviews, op.on(op.col('reviewer_id'), op.col('knowsId'))) 
  .orderBy([op.asc(op.col('length')), op.desc(op.col('rating'))]) 
  .offsetLimit(0, 10) 
  .result() 

Le résultat

{
    "start": "https://example.com/graph/people#4",
    "Review.Metadata.source": "/data/reviews/aedfc481-7aa2-495a-8628-b72f690399b9.json",
    "end": "https://example.com/graph/people#5",
    "Review.Metadata.uuid": "aedfc481-7aa2-495a-8628-b72f690399b9",
    "path": [
        {
            "start": "https://example.com/graph/people#4",
            "end": "https://example.com/graph/people#5",
            "person": "https://example.com/graph/people#5",
            "personId": 5,
            "knows": "https://example.com/graph/people#1",
            "knowsId": 1
        }
    ],
    "Review.Metadata.reviewer_id": 1,
    "length": 1,
    "Review.Metadata.title": "Historical Tales",
    "knowsId": 1,
    "Review.Metadata.rating": 5,
    "Review.Metadata.genre": "non-fiction",
    "Review.Metadata.review_date": "2025-01-16T14:48:43.687231Z"
}
{
    "start": "https://example.com/graph/people#2",
    "Review.Metadata.source": "/data/reviews/aedfc481-7aa2-495a-8628-b72f690399b9.json",
    "end": "https://example.com/graph/people#4",
    "Review.Metadata.uuid": "aedfc481-7aa2-495a-8628-b72f690399b9",
    "path": [
        {
            "start": "https://example.com/graph/people#2",
            "end": "https://example.com/graph/people#4",
            "person": "https://example.com/graph/people#5",
            "personId": 5,
            "knows": "https://example.com/graph/people#1",
            "knowsId": 1
        }
    ],
    "Review.Metadata.reviewer_id": 1,
    "length": 1,
    "Review.Metadata.title": "Historical Tales",
    "knowsId": 1,
    "Review.Metadata.rating": 5,
    "Review.Metadata.genre": "non-fiction",
    "Review.Metadata.review_date": "2025-01-16T14:48:43.687231Z"
}

Conslusion

Les capacités multimodèles de MarkLogic permettent aux organisations de pouvoir exploiter le plein potentiel de leurs données en intégrant des modèles de graphiques et de documents dans une seule plate-forme. En utilisant des graphiques de connaissances et des algorithmes puissants comme le chemin le plus court, vous pouvez découvrir des relations et des informations significatives sur des ensembles de données complexes. En combinant ces informations avec des données de documents structurées à l’aide d’outils tels que TDE et l’API optique, MarkLogic fournit une plate-forme unifiée pour l’analyse avancée et la prise de décision.

Commencez à explorer comment le Plate-forme marklogique L’intégration de graphiques et de documents peut transformer vos cas d’utilisation.