Discussion :

[Contrec]

Bonjour,

J'ai un petit soucis sur une requête SQL, en effet je dois pouvoir choisir parmi plusieurs enregistrements la meilleure combinaison correspondant à une valeur donnée.

Prenons l'exemple de la table MA_TABLE(id, valeur) qui possède les valeurs suivantes :

ID	VALEUR
1	2
2	5
3	5
4	10
5	10
6	150
7	220

Je veux pouvoir sélectionner en une requête les différentes lignes qui vont pouvoir me donner la valeur la plus proche de 14 sans dépasser 14 (14 étant un exemple paramétrable).

En gros pour mon jeux d'essai, je devrais avoir soit :

ID	VALEUR
1	2
4	10

--> Donc un résultat de 2 + 10 = 12 (plus proche de 14 par la borne minimale)

Soit :

ID	VALEUR
1	2
5	10

--> Donc un résultat de 2 + 10 = 12 (peut importe quelle ligne je prends, seule la valeur est importante) donc la valeur 10 peut venir de l'ID 4 ou 5


Si je remplace la valeur 14 par 23 (par exemple) la requête devrait me retourner quelque chose comme :

ID	VALEUR
1	2
4	10
5	10

--> 2 + 10 + 10 = 22 qui est le plus proche de 23 par la borne minimale

Je n'arrive pas à trouver la requête adéquate, sachant que j'ai la contrainte de le faire en une seule requête (pas de possibilité d'algorithme ni de PL/SQL)...

J'ai essayé avec des In, Not In, Group By, Select imbriqués, Sum etc... Impossible d'avoir un résultat correct.

Si quelqu'un a un début d'idée je lui en serait reconnaissant.

Merci d'avance,
Contrec

[aieeeuuuuu]

Bonjour,

Ce type de problème est assez complexe à résoudre, et la solution passe en général par le calcul de toutes les possibilités possibles pour trouver la meilleure (des optimisations sont parfois possibles)

Quel est le volume de la table ?
Quel est votre SBGD ?


Et pour vous donner quelques pistes, faites une recherche sur le "problème du sac à dos"...

[Contrec]

Bonjour, merci pour la réponse.

Le SGDB est DB2 et le volume de cette table sera de l'ordre de plusieurs millions de lignes.

En attendant je passe par une procédure stockée (je triche sur mes contraintes) le temps de trouver si possible l'action en une requête.

De plus en attendant je teste sur Postgres SQL en espérant ne pas trop utiliser de fonctions trop spécifiques au SGBD, pour les requêtes j'essaye d'utiliser au maximum la syntaxe SQL de base.

Et merci pour l'aide, je vais voir !

[aieeeuuuuu]

Voici une piste, testée sous SQL Server mais qui devrait fonctionner tel quel sous DB2 (sous postgre, il faudra ajouter le mot clef RECURSIVE pour la CTE récursive ("Rec") )

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
WITH LaTable AS(
SELECT				1 as id  ,	2 as valeur
	union all select 2, 	5
	union all select 3, 	5
	union all select 4, 	10
	union all select 5, 	10
	union all select 6, 	150
	union all select 7, 	220
)
,
Rec AS (
	SELECT id, valeur as somme, CAST(CAST(id AS VARCHAR) + ';'  AS VARCHAR(1000)) as result
	FROM LaTable
	WHERE valeur <= 23
	AND valeur > 0
	UNION ALL
	SELECT LaTable.id, somme + valeur, CAST(result + CAST(LaTable.id AS VARCHAR) + ';' AS VARCHAR(1000)) 
	FROM Rec
	INNER JOIN LaTable 
		ON	LaTable.id > Rec.id
	WHERE somme + valeur <= 23
	AND valeur > 0
),
M AS (
	SELECT result, somme, RANK() OVER(ORDER BY somme DESC) AS RN
	FROM Rec
)
SELECT result, somme 
FROM M
WHERE RN = 1

Mais sur des millions de lignes... ça risque de prendre un bout de temps !

Il y a peut-être des améliorations a faire dans ce cas (filtrer des lignes en amont, stoper la récursion si on trouve la solution exacte,...), mais c'est difficile sans connaitre mieux le contexte. Pouvez vous le décrire ?

[Contrec]

Bonjour,

ça c'est bien une requête de compétition ! Malheureusement je ne peux pas trop expliquer le contexte global, nous avons cet algorithme à mettre en oeuvre et pas mal de données dans cette table. Je teste ça dès lundi et je vous tiens au courant.

PS : En attendant j'ai fait une procédure stockée avec une petite boucle qui fonctionne bien.

Merci pour l'aide.
Contrec

[StringBuilder]

Plutôt que dans une PS, je verrais bien votre solution passant par une vue (éventuellement matérialisée).

Ça évite de devoir recalculer les combinaisons à chaque lecture fois.

Mais le coup des "millions de lignes", ça me semble relativement compliqué à mettre en œuvre (surtout pour calculer toutes les combinaisons possibles sans exploser le serveur)