Pertinence de résultats de recherches multi-critères

Bonjour tout le monde !

Je cherche à implémenter un moteur de recherches multi-critères avec une base de données MySQL, et si possible avoir les résultats classés par pertinence. Pour faire simple, j’ai des personnages avec différentes capacités, et pour des missions il me faut composer des équipes avec des capacités définies par la mission. Les personnages peuvent avoir plusieurs capacités qui sont demandées pour la mission, et c’est là que cette histoire de pertinence intervient.

Je ne vois pas vraiment comment faire de manière simple. J’ai déjà imaginé d’avoir une série de tests selon les critères afin de déterminer la pertinence, mais ma "solution" ne me paraît pas vraiment flexible ni performante — si pour deux critères on a deux tests, pour trois critères on en a 5, pour quatre on en a 12, etc. —, sachant que je vais avoir jusqu’à sept critères.

Y a-t’il une autre manière de faire que de générer les multiples combinaisons¹ à tester pour générer une notion de pertinence ?

Merci d’avance 

Salut, j’ai pas bien compris ce que tu veux faire. De ce que je comprends, il n’y a pas de rapport avec ta base de donnée ?

Tu as des "objets" qui ont des "caractéristiques", tu dois trouver ceux qui correspondent le mieux à une contrainte. C’est ça ?

Genre chaque perso a une vitesse de course et une endurance, et tu dois composer une équipe de 3 personnes pour grimper l’everest, et une équipe de 4 personnes pour courir un 4x100m ?

Ton problème c’est un problème d’"optimisation" (enfin, recherche opérationnelle, blabla) ? Ou t’as déjà ce que tu veux et tu sais pas comment écrire une requête performante / minimiser les requêtes nécessaires ?

Oui, c’est le même genre d’idée.
Après, ce qui n’aide peut-être pas à comprendre mais qui me semble important, c’est que la contrainte porte sur plusieurs critères (un ensemble de X caractéristiques nécessaires à la réalisation de la mission), et que les objets peuvent avoir jusqu’à trois caractéristiques correspondant à celles nécessaires à l’accomplissement de la mission.

C’est une forme d’optimisation tant concrète (moins j’utilise de personnes sur une mission, plus je peux effectuer de missions en parallèle) que sur le plan algorithmique.

Imaginons qu’une mission demande d’avoir les compétences (c’est plus logique dans ce contexte que "caractéristique") de patinage et de pâtisserie. Les personnes ayant une des deux compétences devraient idéalement sortir avec une pertinence moins élevée que les personnes qui ont les deux compétences.
Techniquement, c’est relativement simple de faire comme suit :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

IF(
        competence1 IN (person.competences)
    AND competence2 IN (person.competences),
    2,
    IF(
            competence1 IN (person.competences)
        OR  competence2 IN (person.competences),
        1,
        0
    )
)

Mais quand on augmente le nombre de compétences requises, ça devient bien plus complexe, parce que justement c’est là qu’interviennent les combinaisons : ceux qui ont toutes les compétences, c’est facile de savoir et de leur attribuer la pertinence maximale. Mais avec trois compétences, j’ai déjà $C^3_2 = 3$ possibilités de paires de combinaisons pour avoir une pertinence un peu moindre, plus $C^3_1 = 3$ d’avoir une pertinence non nulle, mais encore plus faible (et là, techniquement, c’est une suite de OR plutôt que trois tests séparés, donc mon estimation n’est pas totalement correcte).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

IF (
        competence1 IN (person.competences)
    AND competence2 IN (person.competences)
    AND competence3 IN (person.competences),
    3,
    IF (
       (
                competence1 IN (person.competences)
            AND competence2 IN (person.competences)
        ) OR (
                competence1 IN (person.competences)
            AND competence3 IN (person.competences)
        ) OR (
                competence2 IN (person.competences)
            AND competence3 IN (person.competences)
        ),
        2,
        IF (
                competence1 IN (person.competences)
            OR  competence2 IN (person.competences)
            OR  competence3 IN (person.competences),
            1,
            0
        )
    )
)

Je me demandais s’il y avait un moyen différent que de construire les $n$ membres de $1 + C^n_{n-1} + C^n_{n-2} + C^n_{n-3} + … + C^n_2 + 1$, sachant que $n$ représente notamment le nombre de compétences nécessaires, mais aussi les $n$ niveaux de pertinence et donc les $n$ niveaux de IF imbriqués, pour reprendre la structure des codes proposés.

Si, dans la mesure ou je pense qu’il est logique de faire calculer la pertinence par le SGBDR, donc d’avoir ce qu’il faut soit dans le moteur de bases de données (auquel cas je ne sais pas comment le faire avec MySQL), soit dans la requête (et c’est là que je vois comment faire, mais ça me paraît lourd).

Ne t’en fais pas, je me rends compte avec ton commentaire que j’ai fait un mélange de SQL et de DQL dans mes exemples 
Je n’ai pas un champ contenant toutes mes compétences de la personne dans celle-ci.

J’avais vaguement pensé à une somme (ce qui me semblerait effectivement bien plus simple et léger), mais c’était tard hier soir et avoir dormi dessus n’as pas aidé, j’ai même oublié la chose 

En fait, quelque chose comme ce qui suit pourrait peut-être faire l’affaire aussi…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

SELECT
        p.*,
        count(DISTINCT s.id) AS relevance
    FROM
            person p
        INNER JOIN
                skill_person sp
            ON  p.id = sp.person_id
        INNER JOIN
                skill s
            ON      s.id = sp.skill_id
    WHERE
            s.id IN (:s_id1, :s_id2, etc.)
    GROUP BY
        p.id
    ORDER BY
        relevance DESC

Tout cet étalement de logique pour en arriver à ça… 

Edit

Allez, des missions, des compétences, et ce sujet, quelques indices supplémentaires bien placés, d’aucuns devraient switcher sur ce que je manigance 

Tu dois forcément faire ça avec MySQL ? Elasticsearch me semble bien plus optimisé pour faire ce que tu souhaites.

Je m’en doute, mais j’ai la flemme d’installer un autre serveur, d’apprendre à l’utiliser, d’adapter mon application pour ça juste parce qu’Elasticsearch calcule le score automatiquement. 

Et il me semble que les solutions NoSQL sont justement moins récentes que le SQL, donc j’étais aussi curieux de savoir comment on faisait avant…

Sans parler du fait que la solution est d’une simplicité déconcertante par rapport à ce sur quoi j’étais parti.

Oui et non, franchement. Elasticsearch, pour moi, c’est plutôt pour stocker des documents et leurs métadonnées, analyser le tout, indexer le tout, puis faire des recherches textuelles et multi-critères. Là oui.

Dans le cas présent ça me semble largement overkill vu qu’il n’y a pas du tout d’aspect document ou textuel.

Il a une liste de critères tout à fait définie et il veut juste faire une recherche dedans. Le faire dans une base de donnée relationnelle ou récupérer les données et leur attribuer une pertinence dans le backend, ces 2 solutions me semblent meilleures dans son cas que de sortir ES pour ça.

Oui et non. On est d’accord qu’ES est prévu pour des choses plus "complexes" que ça. D’un autre côté, il est aussi fait pour faire du requêtage rapide, avec de multiples critères, et de ressortir les données triées par pertinence. Ce de manière "plus ou moins" automatique ("plus ou moins" parce que derrière il y a un peu de conf quand même).

Après je ne connais pas l’appli d’Ymox. Mais c’est toujours bien de se poser la question de l’évolutivité. Et si dans 6 mois un critère est rajouté, il faut potentiellement modifier l’algo PHP, ce qui serait (normalement) moins le cas avec une base ES.

Après si le besoin est simple et n’est pas amené à évoluer, du SQL fera en effet très bien l’affaire.