Le défi de l'allocation exacte avec des unités indivisibles remonte à la méthode Hamilton d'apportionnement utilisée pour les sièges au Congrès américain, où des représentants fractionnels sont impossibles et les restes doivent être distribués équitablement. En SQL, cela se manifeste lorsque l'on divise des montants monétaires entre des entrées de grand livre ou en distribuant des stocks où les comptes SKU doivent être des entiers. Les premières solutions s'appuyaient sur des curseurs ou des boucles procédurales, violant le paradigme basé sur les ensembles. Les fonctions de fenêtre de ANSI SQL:2003 modernes ont permis des algorithmes de report purement déclaratifs qui maintiennent la précision mathématique sans traitement ligne par ligne.
Lors de la division d'une quantité totale $T$ entre $n$ lignes avec des parts exactes fractionnaires $s_1, s_2, ..., s_n$ (où $\sum s_i = T$), un simple arrondi des lignes individuelles donne $\sum \text{round}(s_i) eq T$ en raison d'erreurs fractionnaires accumulées. L'exigence est de produire des entiers $a_1, a_2, ..., a_n$ tels que $\sum a_i = T$ exactement, tout en minimisant la déviation $|a_i - s_i|$ pour chaque ligne. L'algorithme doit respecter un ordre de priorité défini (par exemple, l'ancienneté, le timestamp de la transaction) pour décider de manière déterministe quelles lignes reçoivent la valeur plafond quand des restes fractionnaires existent.
Utilisez des fonctions de fenêtre cumulatives pour calculer l'allocation cumulée cible à chaque étape comme $\text{floor}(\sum_{j=1}^{i} s_j)$. L'allocation pour la ligne $i$ est la différence entre la cible cumulée actuelle et la cible cumulée précédente : $a_i = \text{floor}(\text{cum}i) - \text{floor}(\text{cum}{i-1})$. Cela permet d'absorber tout déficit d'arrondi des lignes précédentes dans le calcul de la ligne actuelle.
WITH allocations AS ( SELECT id, priority, exact_share, SUM(exact_share) OVER (ORDER BY priority) AS cum_exact, FLOOR(SUM(exact_share) OVER (ORDER BY priority)) AS cum_target FROM distribution_queue ) SELECT id, priority, exact_share, (cum_target - COALESCE(LAG(cum_target) OVER (ORDER BY priority), 0)) AS allocated_units FROM allocations;
Cela garantit que le $\text{cum_target}$ final est égal à $T$, et chaque étape intermédiaire absorbe les erreurs d'arrondi précédentes.
Un système de paie doit répartir un fonds de bonus annuel de 10 000,00 $ parmi 150 employés en fonction des ratios de performance. La part théorique de chaque employé se calcule à des valeurs comme 66,666... dollars, mais le système comptable nécessite des allocations en cents entiers (cents entiers) et la somme doit exactement correspondre au budget de 10 000,00 $ pour satisfaire aux contrôles d'audit.
Une approche utilise un curseur pour itérer à travers les employés, allouant la valeur FLOOR et reportant le reste fractionnaire à la ligne suivante. Cela garantit l'exactitude mais nécessite du code procédural et fonctionne mal avec de grands ensembles de données en raison du traitement ligne par ligne et du verrouillage. Cela complique également la gestion des transactions et les scénarios de rollback.
Une autre approche calcule toutes les valeurs FLOOR, puis tente d'ajouter 1 cent aux N meilleurs employés avec les plus grands restes fractionnaires en utilisant une sous-requête ROW_NUMBER(). Bien que cela soit basé sur des ensembles, cela nécessite plusieurs analyses de table et des jointures complexes pour déterminer combien de lignes ont besoin de l'extra cent (le compte des restes), et ça lutte avec les égalités lorsque de nombreux employés partagent des parties fractionnaires identiques.
La solution choisie implémente la méthode de report cumulative ANSI SQL. En calculant la somme cumulée des parts exactes et en prenant le FLOOR de cette valeur cumulée à chaque étape, le système détermine exactement combien aurait dû être distribué jusqu'à ce point. La différence entre les cibles cumulées successives donne l'allocation de la ligne actuelle. Cela absorbe naturellement les incohérences d'arrondi : si le premier employé reçoit 66 cents au lieu de 66,666, le déficit de 0,666 se reporte dans le calcul cumulatif du deuxième employé, poussant potentiellement leur cible cumulée de 133,333 à 133, leur donnant 67 cents. Cette approche traite l'ensemble de la paie en un seul passage basé sur des ensembles, maintient la conformité stricte aux ACID, et garantit que le total distribué équivaut précisément à 10 000,00 $.
Le résultat a été une réduction de 95 % du temps de traitement par rapport à la méthode du curseur et zéro erreur de réconciliation lors de l'audit financier trimestriel.
Pourquoi soustraire le plancher cumulé précédent du plancher cumulé actuel distribue-t-il correctement le reste ?
Les candidats essaient souvent de calculer les erreurs d'arrondi de chaque ligne individuellement, puis de les distribuer explicitement. L'idée est que FLOOR(cumulative_exact) représente l'allocation totale idéale jusqu'à cette ligne si nous ne pouvions allouer que des unités entières. En faisant la différence entre ces cibles cumulées, nous demandons essentiellement "combien de nouvelles unités entières cette ligne introduit-elle dans la somme cumulée ?" Si les lignes précédentes laissent un reste de 0,4, la part de 0,6 de la ligne suivante pousse la fraction cumulée au-delà de la limite entière, permettant à la ligne actuelle de revendiquer l'unité supplémentaire que la ligne précédente ne pouvait pas. Ce report implicite élimine le besoin de suivre les restes explicitement.
Comment cet algorithme se comporte-t-il avec des valeurs exact_share négatives, et pourquoi FLOOR pourrait-il poser problème dans ce cas ?
La plupart des candidats supposent des valeurs positives. Pour des parts négatives (par exemple, des débits ou des retours), FLOOR arrondit loin de zéro (par exemple, FLOOR(-1,2) = -2), ce qui exagère la magnitude de manière négative. La logique de report équilibre toujours mathématiquement, mais l'interprétation commerciale de la "priorité" change—les allocations négatives pourraient consommer le "reste" de manière inattendue. La solution nécessite d'utiliser TRUNC (vers zéro) ou CEIL pour des valeurs négatives selon que l'entreprise préfère arrondir vers zéro pour les crédits. Une mise en œuvre robuste utilise des expressions CASE pour appliquer FLOOR pour les valeurs positives et CEIL pour les valeurs négatives, garantissant que la déviation absolue est minimisée de manière cohérente.
Qu'est-ce qui garantit que l'allocation de la dernière ligne épuisera exactement la ressource totale sans vérification explicite ?
Les candidats s'inquiètent des erreurs hors par un. La garantie mathématique vient de la propriété de la série télescopique : $\sum_{i=1}^{n} (T_i - T_{i-1}) = T_n - T_0$, où $T_i = \text{FLOOR}(\sum_{j=1}^{i} s_j)$ et $T_0 = 0$. Puisque $T_n = \text{FLOOR}(\sum_{j=1}^{n} s_j) = \text{FLOOR}(T) = T$ (en supposant que $T$ est entier), la somme de toutes les différences doit être égale à $T$. Le cadre de fenêtre ANSI SQL garantit que la fonction LAG récupère correctement $T_{i-1}$, ce qui rend l'allocation finale automatiquement absorber tout reste résiduel de toutes les lignes précédentes.