modélisation d'un système de préferences

**matN59** · 15/03/2008, 13h00

bonjour à tous,

voila je suis confronté à un problèmes depuis quelques jours et aucune solution ne me parait efficace. je m'en remets à vous en espérant que vous pourrez me faire avancer.
mon problème est le suivant: je souhaite modéliser un système de préférences pour un catalogue et affiner les recherches par préférence des utilisateurs.
ces préférences sont des critères très variés qui sont présents ou non. la liste de ces préférences est non exhaustive.
Initialement, j'étais parti sur un système de modélisation "normal" avec une table de préférence, une table catalogue, et une table de liaison entre les deux . Relation 1/N entre la table catalogue et catalogue_preferences et relation 1/N entre la table preferences et catalogue_preferences. En fonction du nombre de jointures réussies, un score qui permet de trier les résultats. j'ai abandonné car vu le nombre de préférences (environ une dizaine pour le moment) cela à chaque fois obligeait à un nombre de jointures d'autant. Même si mes tables sont bien indexées, je pense qu'à forte volumétrie c'est ingérable.

Je travaille sous mysql (5.1).
Ma deuxième solution était l'utilisation d'un index full text. Ma table catalogue n'était liée que par une relation 1/1 à une table catalogue_preference qui contiendrais un index full text contenant les préférences
. C'était plus élégant mais il n'en reste pas moins que je pense que cela n'est pas une solution efficace car certaines des préférences peuvent se retrouver dans plus de 50 % des tuples, et donc être ignorées par l'index full text.

Au final, dans les deux cas, mes solutions sont bloquées par des problématiques techniques et aujourd'hui je ne vois pas comment faire.
Auriez vous des idées pour résoudre ce problème?
Cordialement,

**fsmrel** · 15/03/2008, 14h26

Bonjour,

Envoyé par ermelir

...En fonction du nombre de jointures réussies, un score qui permet de trier les résultats.

Comment est modélisée la relation avec l’utilisateur dans votre système ? Merci de fournir le jeu des instructions Create Table pour les tables impliquées, ainsi que les requêtes de jointure qui vous donnent du souci.

**matN59** · 15/03/2008, 16h09

bonjour,

voici le modèle que j'utilise pour la modélisation de mes préférences.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
-- 
-- Structure de la table `preferences`
-- 

CREATE TABLE `preferences` (
  `id` tinyint(3) unsigned NOT NULL auto_increment COMMENT 'l''identifiant préference',
  `preference` varchar(50) NOT NULL COMMENT 'le nom de la preference',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `preference` (`preference`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='table des preferences' AUTO_INCREMENT=5 ;

-- 
-- Contenu de la table `preferences`
-- 

INSERT INTO `preferences` (`id`, `preference`) VALUES 
(1, 'preference 1'),
(2, 'preference 2'),
(3, 'preference 3'),
(4, 'preference 4');

-- --------------------------------------------------------

-- 
-- Structure de la table `products`
-- 

CREATE TABLE `products` (
  `id` smallint(5) unsigned NOT NULL auto_increment COMMENT 'li''dentifiant catalogue',
  `product` varchar(50) NOT NULL COMMENT 'le produit',
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='table des produits' AUTO_INCREMENT=5 ;

-- 
-- Contenu de la table `products`
-- 

INSERT INTO `products` (`id`, `product`) VALUES 
(1, 'produit 1'),
(2, 'produit 2'),
(3, 'produit 3'),
(4, 'produit 4');

-- --------------------------------------------------------

-- 
-- Structure de la table `products_preferences`
-- 

CREATE TABLE `products_preferences` (
  `product_id` smallint(5) unsigned NOT NULL COMMENT 'l''identifiant produit',
  `preference_id` tinyint(3) unsigned NOT NULL COMMENT 'l''identifiant preference',
  UNIQUE KEY `catalog_id` (`product_id`,`preference_id`),
  KEY `preference_id` (`preference_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='table d''association des préférences produits';

-- 
-- RELATIONS POUR LA TABLE `products_preferences`:
--   `preference_id`
--       `preferences` -> `id`
--   `product_id`
--       `products` -> `id`
-- 

-- 
-- Contenu de la table `products_preferences`
-- 

INSERT INTO `products_preferences` (`product_id`, `preference_id`) VALUES 
(2, 1),
(3, 2),
(1, 3),
(1, 4);

-- --------------------------------------------------------

-- 
-- Structure de la table `users`
-- 

CREATE TABLE `users` (
  `id` tinyint(3) unsigned NOT NULL auto_increment,
  `username` varchar(20) NOT NULL COMMENT 'Le compte de l''utilisateur',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `username` (`username`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='table des utilisateurs' AUTO_INCREMENT=3 ;

-- 
-- Contenu de la table `users`
-- 

INSERT INTO `users` (`id`, `username`) VALUES 
(1, 'utilisateur 1'),
(2, 'utilisateur 2');

-- --------------------------------------------------------

-- 
-- Structure de la table `users_preferences`
-- 

CREATE TABLE `users_preferences` (
  `user_id` tinyint(3) unsigned NOT NULL COMMENT 'l''identifiant de l''utilisateur',
  `preference_id` tinyint(3) unsigned NOT NULL COMMENT 'l''identifiant de la préference',
  UNIQUE KEY `user_id` (`user_id`,`preference_id`),
  KEY `preference_id` (`preference_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='table d''association des préférences utilisateurs';

-- 
-- RELATIONS POUR LA TABLE `users_preferences`:
--   `preference_id`
--       `preferences` -> `id`
--   `user_id`
--       `users` -> `id`
-- 

-- 
-- Contenu de la table `users_preferences`
-- 

INSERT INTO `users_preferences` (`user_id`, `preference_id`) VALUES 
(1, 2),
(1, 3),
(1, 4),
(2, 4);

-- 
-- Contraintes pour les tables exportées
-- 

-- 
-- Contraintes pour la table `products_preferences`
-- 
ALTER TABLE `products_preferences`
  ADD CONSTRAINT `products_preferences_ibfk_3` FOREIGN KEY (`preference_id`) REFERENCES `preferences` (`id`) ON DELETE CASCADE,
  ADD CONSTRAINT `products_preferences_ibfk_2` FOREIGN KEY (`product_id`) REFERENCES `products` (`id`) ON DELETE CASCADE;

-- 
-- Contraintes pour la table `users_preferences`
-- 
ALTER TABLE `users_preferences`
  ADD CONSTRAINT `users_preferences_ibfk_2` FOREIGN KEY (`preference_id`) REFERENCES `preferences` (`id`) ON DELETE CASCADE,
  ADD CONSTRAINT `users_preferences_ibfk_1` FOREIGN KEY (`user_id`) REFERENCES `users` (`id`) ON DELETE CASCADE;

Je vais rechercher ce que j'utilisais comme requete à l'époque pour faire la sélection, je l'ai un peu égaré devant sa complexité

Cordialement,

**matN59** · 15/03/2008, 16h59

rebonjour,

voila en repensant ma requete, j'arrive à autre chose:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
SELECT p.id, p.product, COUNT(up.preference_id) AS `nombre de preference matchant le produit` ,  u.username AS utilisateur
FROM products AS p
LEFT JOIN products_preferences AS pp ON (p.id = pp.product_id)
LEFT JOIN users_preferences AS up ON (up.preference_id = pp.preference_id)
LEFT JOIN users AS u ON (up.user_id = u.id)
WHERE u.id IS NULL OR u.id = 1
GROUP BY p.id
ORDER BY COUNT(up.preference_id) DESC, COUNT(up.preference_id) DESC

mais j'ai un doute: dans le cas de l'utilisateur 1, j'obtiens bien le résultat attendu.
Par contre, dans le cas de l'utilisateur 2, un des produits ne sorts pas dans la requête.
Suis je sur la bonne voie, je commence à avoir le cerveau embrumé par toutes ces requêtes SQL

**fsmrel** · 15/03/2008, 17h39

J’ai exécuté avec SQL Server (je n’ai pas MySQL).

Celui-ci annonce 2 erreurs :

1) La clause Select Comporte des noms de colonnes ne faisant pas partie du GROUP BY : p.product et u.username

2) COUNT(up.preference_id) figure 2 fois dans la clause Order by

Si la 2e erreur est facile à corriger, pour la 1re, c’est plus délicat : que cherche-t-on exactement comme résultat d’un point de vue fonctionnel ?

**matN59** · 15/03/2008, 18h37

bonjour,

Envoyé par fsmrel

1) La clause Select Comporte des noms de colonnes ne faisant pas partie du GROUP BY : p.product et u.username

Sous Mysql 5.1, je n'ai aucun problème moi de ce coté la.

Envoyé par fsmrel

2) COUNT(up.preference_id) figure 2 fois dans la clause Order by

Si la 2e erreur est facile à corriger, pour la 1re, c’est plus délicat : que cherche-t-on exactement comme résultat d’un point de vue fonctionnel ?

Effectivement, la seconde clause de tri est COUNT(pp.preference_id)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 SELECT p.id, p.product, COUNT( up.preference_id ) AS `nombre de preference matchant le produit` , u.username AS utilisateur
FROM products AS p
LEFT JOIN products_preferences AS pp ON ( p.id = pp.product_id )
LEFT JOIN users_preferences AS up ON ( up.preference_id = pp.preference_id )
LEFT JOIN users AS u ON ( up.user_id = u.id )
WHERE u.id IS NULL
OR u.id =2
GROUP BY p.id
ORDER BY COUNT( up.preference_id ) DESC , COUNT( pp.preference_id ) DESC

Alors, au niveau fonctionnel, ce que je souhaite faire, c'est faire ressortir tous les produits de la table catalogue, mais trié en fonction des preferences des utilisateur:
avec l'utilisateur 1 par exemple, nous obtiendrons:

"id";"product";"nombre de preference matchant le produit";"utilisateur"
"1";"produit 1";"2";"utilisateur 1"
"3";"produit 3";"1";"utilisateur 1"
"4";"produit 4";"0";NULL
"2";"produit 2";"0";NULL

ce qui correspond à ce que j'attends.

Par contre, j'ai un soucis avec l'utilisateur 2. J'obtiens :
"id";"product";"nombre de preference matchant le produit";"utilisateur"
"1";"produit 1";"1";"utilisateur 2"
"2";"produit 2";"0";NULL
"4";"produit 4";"0";NULL

Or le produit 3 n'apparaît pas.

Est ce que vous pensez que passer par une table temporaire contenant un produit cartésien entre ma table products et ma table preferences peut être viable? J'ai peur de la volumétrie.
Cordialement,

**fsmrel** · 16/03/2008, 02h14

Envoyé par ermelir

Or le produit 3 n'apparaît pas.

J'ai pensé à une union de ce qui apparaît et de ce que qui n'apparaît pas. Ensuite, pour faire absorber les scories (dues aux préferences matchant le produit) à zéro, je somme (x + 0 = x).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
Select ProdName
     , Sum(CountUserPref) As Sum1
     , Utilisateur
     , Sum(CountProdPref) As Sum2 
From
  (
     SELECT  p.product As ProdName
             , COUNT(up.preference_id) AS CountUserPref
             , u.username AS Utilisateur
             , COUNT(pp.preference_id) As CountProdPref
     FROM products AS p
     LEFT JOIN products_preferences AS pp ON (p.id = pp.product_id)
     LEFT JOIN users_preferences AS up ON (up.preference_id = pp.preference_id)
     LEFT JOIN users AS u ON (up.user_id = u.id)
     where  u.id IS not NULL
     GROUP BY p.id, p.product, u.Id, u.username
    UNION
     Select   a.Product, 0, b.username, 0 
     From     products a
            , users b
     Where not exists
     (Select  *
      From
        (
          SELECT p.id As ProdId
                  , p.product As ProdName
                  , COUNT(up.preference_id) AS CountUserPref 
                  , u.Id as UserId
                  , u.username AS Utilisateur
                  , COUNT(pp.preference_id) As CountProdPref
          FROM products AS p
          LEFT JOIN products_preferences AS pp ON (p.id = pp.product_id)
          LEFT JOIN users_preferences AS up ON (up.preference_id = pp.preference_id)
          LEFT JOIN users AS u ON (up.user_id = u.id)
          WHERE u.id IS NULL OR u.id = 1
          GROUP BY p.id, p.product, u.Id, u.username
        ) As x 
     Where (a.id = x.ProdId
       And b.id = x.userId)
    )
  )  As y 
Group by ProdName, Utilisateur
Order by Sum1 Desc, Sum2 Desc, ProdName, Utilisateur

Cette requête est vraisemblablement améliorable, mais normalement le produit cartésien est transformé en somme.

Je tombe de sommeil. A vous de vérifier tout cela. Si marche, tant mieux, sinon on remettra les compteurs à zéro...

**matN59** · 16/03/2008, 21h15

Bonsoir,

tout d'abord merci pour votre réponse.
j'ai testé la requete et elle me retourne le résultat suivant:

"ProdName";"Sum1";"Utilisateur";"Sum2"
"produit 1";"2";"utilisateur 1";"2"
"produit 1";"1";"utilisateur 2";"1"
"produit 3";"1";"utilisateur 1";"1"
"produit 2";"0";"utilisateur 1";"0"
"produit 2";"0";"utilisateur 2";"0"
"produit 3";"0";"utilisateur 2";"0"
"produit 4";"0";"utilisateur 1";"0"
"produit 4";"0";"utilisateur 2";"0"

Alors en ce qui concerne le tri des données effectivement cela semble bien, merci.
Par contre, je n'ai pas été capable de filtrer les données pour que seules celles d'un utilisateur donné sorte.
D'autre part, l'explain m'indique de nombreuses recherches sans utilisation d'index. Est ce que l'utilisation d'une table temporaire serait plus a même d'améliorer cette requête?
Mon modèle semble correcte pourtant.
Cordialement,

**fsmrel** · 17/03/2008, 00h06

Bonsoir,

Tout d’abord, voici une requête moins copieuse. J’ai ajouté le test pour un utilisateur donné, car j’ignorais que vous aviez besoin de la fonctionnalité.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
27
28
29
30
31
32
  Select   c.Id As IdProduit, c.Product As NomProduit
         , Count(*) As CountProdUser 
         , d.userName As Utilisateur
         , Count(a.Preference_Id) As CountPreference 
  From     products_preferences a
         , users_preferences b
         , Products c
         , Users d
  Where    a.preference_id = b.preference_id
    And    a.Product_Id = c.Id
    And    b.User_Id = d.Id
    And    d.Id = 1
  Group by c.Id, c.Product, b.user_Id, d.userName
Union all
  Select    a.Id As IdProduit, a.Product As NomProduit
          , 0 As CountProdUser
          , b.userName As Utilisateur
          , 0  As CountPreference
  From       products a
           , users b
  Where   b.Id = 1             
    And Not Exists
         (  
          Select   *
          From     products_preferences c  
                 , users_preferences d
          Where    c.preference_id = d.preference_id 
            And    a.Id = c.Product_Id
            And    b.Id = d.User_Id
         )               
Order by Utilisateur, CountProdUser Desc, CountPreference Desc, NomProduit

D'autre part, l'explain m'indique de nombreuses recherches sans utilisation d'index. Est ce que l'utilisation d'une table temporaire serait plus a même d'améliorer cette requête?

Je ne connais pas MySQL. Mais, par exemple, dans le cas un SGBD comme DB2 for z/OS, si les tables du catalogue indiquent une faible volumétrie des tables en jeu, les index ne sont pas utilisés. Avez-vous la possibilité de "suggérer" à MySQL d’utiliser tel ou tel index ? Sinon, avant Explain, avez-vous réorganisé vos tables ?

En tout état de cause, si produit cartésien il y a entre Products et Users (cf. le 2e bloc de l’union de la requête ci-dessus), dans le cas général il est normalement réduit par le Where Not Exists (mais c’est SGBD dépendant...) Maintenant, dans le cas où l’on s’intéresse à un seul utilisateur, le cardinal du produit cartésien est égal à 1 X N (où N représente le nombre de lignes de la table Products) et là, il n’y a pas de risque (sauf si votre SGBD n’effectue la restriction qu’après le produit : explain à surveiller...)

Avant de vous lancer dans la mise en œuvre d’une table temporaire — ce à quoi je ne crois pas trop —, faites un test de montée en charge, afin de savoir quel sera le comportement de la requête en production.

Questions :
A la louche, combien de produits ? De préférences ? d’utilisateurs ? de couples {user, préférence} ? de couples {produit, préférence} ?

Mon modèle semble correcte pourtant.

Il l'est.

**matN59** · 17/03/2008, 21h04

Bonjour,

tout d'abord merci pour votre aide.
Alors en ce qui concerne MySQL, effectivement nous pouvons forcer l'utilisation d'index. Mais il semblerait que le problème n'existe plus avec cette version simplifiée de la première requete puisque mis à part sur l'union, j'ai bien au moins à chaque fois un index d'utilisé.
En ce qui concerne la volumétrie, le projet n'est qu'en phase de conception.
Je pense que nous pouvons attendre plusieurs milliers d'utilisateurs, plusieurs centaines de milliers de produits. Chaque utilisateur aurait au maximum une dizaine de préférences, les produits au grands maximum une 20 aine.
Je vais faire des tests de charge en créant des données aléatoirement, je vous dirais ce qu'il en est.
Cordialement,

**fsmrel** · 18/03/2008, 01h05

Bonsoir,

Merci effectivement de me tenir au courant, le cas est intéressant.

Ad augusta per angusta...

modélisation d'un système de préferences

Schéma

Discussions similaires

Partager

Partager