Brevet FR3047580A1 (20170811)
REVENDICATIONS1. Un procédé de détermination de la rangée la plus spécifique dans une table de base de données maintenue par un système informatique, la table de base de données se compose d'une pluralité de rangées et d'une pluralité de colonnes, les rangées et les colonnes de la table de base de données forment des cellules, chaque cellule comprend au moins une valeur ou aucune valeur ; le système informatique maintient également un index pour la table de base de données ; chaque index comprend une structure d'index respective pour chaque colonne de la table de base de données ; chaque structure d'index comprend un ensemble respectif de tuples de pointeurs pour chaque valeur apparaissant dans la colonne respective et un bitmap dans lequel chaque tuple de pointeur comprend un premier pointeur indiquant une des valeurs qui apparaît dans la colonne et un second pointeur indiquant la rangée de la table de base de données dans laquelle la valeur apparaît, et où le bitmap indique des cellules dans la colonne respective sans valeur ; l'index indique un ordre de spécificité des rangées de la table de base de données ; le procédé comprend : - la réception par le système informatique d'une demande indiquant au moins une colonne de la table de base de données associée à une valeur d'entrée respective ; - incrémentiellement, pour chaque colonne, le système informatique : utilise le bitmap de la structure d'index pour que la colonne maintienne toutes les rangées de la table de base de données qui ne contiennent aucune valeur dans la cellule de la colonne considérée, et - utilise le tuple de pointeur de la structure d'index pour que la colonne filtre toutes les rangées de la table de base de données qui ne comprennent pas la valeur d'entrée respective, la sélection, par le système informatique, à partir des rangées restantes, de la rangée la plus en haut dans l'ordre de spécificité ; 3047580 29 - le fait de retourner, par le système informatique, la valeur d'au moins une cellule de la rangée déterminée.\n<CLM>\1\tLe procédé selon la revendication 1 comprend par ailleurs : 5 - en réponse à la réception de la requête, l'initialisation d'un bitmap résultat indiquant les rangées restantes ; dans laquelle l'utilisation des tuples de pointeur et du bitmap de la structure d'index pour chaque colonne indiquée dans la demande comprend : l'établissement d'un bitmap colonne indiquant toutes les rangées qui remplissent la valeur d'entrée respective pour la colonne respective, et la mise à jour du bitmap résultat en associant le bitmap résultat et le bitmap colonne. Le procédé selon la revendication 1 dans lequel l'ensemble respectif des tuples de pointeur est stocké de manière contiguë dans une mémoire du système informatique. Lea procédé selon l'une quelconque des revendications 1 à 3, dans leaquel l'utilisation des tuples de pointeur et du bitmap de la structure d'index pour chaque colonne indiquée dans la demande comprend par ailleurs la réalisation d'une recherche binaire sur l'ensemble respectif de tuples de pointeur. Le procédé selon l'une quelconque des revendications 2 à 4 dans lequel toutes les rangées qui remplissent la valeur d'entrée respective sont indiquées par un « 1 » dans le bitmap colonne, toutes les rangées restantes sont indiquées par « 1 » dans le bitmap résultat et l'association du bitmap résultat et du bitmap colonne comprend une opération ET bit à bit; Le procédé selon l'une quelconque des revendications 1 à 5 comprenant par ailleurs : - la génération de l'index par : - l'initialisation du bitmap indiquant toutes les cellules dans la colonne respective sans valeur, - l'ajout d'un tuple de pointeur à l'ensemble de tuples de pointeur de la structure d'index respective pour chaque valeur dans la colonne, 10\n<CLM>\1\t15\n<CLM>\1\t20\n<CLM>\1\t25\n<CLM>\1\t30 3047580 30 - la mise à jour du bitmap de la structure d'index respective pour refléter toutes les cellules sans valeur.\n<CLM>\1\t5\n<CLM>\1\t10\n<CLM>\1\t10. 20\n<CLM>\1\t25 30\n<CLM>\1\tLe procédé selon la revendication 6 dans lequel la génération d'index comprend par ailleurs : le tri des tuples de pointeur de chaque structure d'index par la valeur désignée par le premier pointeur. Le procédé selon l'une quelconque des revendications 1 à 7 dans lequel l'indication de l'ordre de spécificité des rangées de la table de base de données est réalisée en triant les rangées de la table de base de données en fonction du nombre de cellules dans chaque rangée sans valeur et/ou une spécificité des valeurs dans les cellules de la rangée. Le procédé selon la revendication 8 dans lequel l'indication de l'ordre de spécificité est donnée par un ordre de rangée unique indiquant les rangées triées. Le procédé selon l'une quelconque des revendications 1 à 7 dans lequel l'indication de la spécificité est donnée par des valeurs de pondération comprises dans l'index de la table de base de données. Le procédé d'une quelconque des revendications 1 à 10 dans lequel le système informatique est un routeur, la table de base de données est une table de routage, chaque rangée de la table de routage constitue une règle de routage pour acheminer une demande entrante vers une destination, la table de routage comprend une colonne de destination avec des valeurs de destination possibles et une colonne d'acheminement avec les valeurs correspondantes indiquant un acheminement vers la destination. Le procédé d'une quelconque des revendications 1 à 10 dans lequel le système informatique est un pare-feu, la table de base de données est une table de filtrage, la demande est un paquet de données entrant et chaque rangée de la table de filtrage constitue une règle de filtrage pour permettre ou empêcher le paquet de données entrant d'être transmis vers une destination, où la table de filtrage comprend au moins 3047580 31 une colonne de destination avec les adresses de destination possibles, au moins une colonne avec des valeurs précisant les caractéristiques du paquet de données entrant et une colonne avec des valeurs Booléennes indiquant si le paquet de données entrant doit être transmis ou rejeté. 5\n<CLM>\1\tLe procédé d'une quelconque des revendications 1 à 10 dans lequel le système informatique est un moteur de règles, la table de base de données est une table de règles, chaque rangée de la table règles constitue une règle pour répondre à la demande, les colonnes de la table de règles définissent les critères de règles. 10\n<CLM>\1\tLe procédé d'une quelconque des revendications 1 à 13 dans lequel l'index est stocké dans un cache de processeur du système informatique et reste stocké dans le cache de processeur après que la valeur d'au moins une cellule de la rangée déterminée ait été retournée pour être disponible pour d'autres demandes de traitement. 15\n<CLM>\1\tUn système informatique pour déterminer la rangée la plus spécifique dans une table de base de données maintenue par le système informatique, la table de base de données se compose d'une pluralité de rangées et une pluralité de colonnes, les rangées et les colonnes de la table de base de données 20 forment une cellule, chaque cellule comprend au moins une valeur ou aucune valeur ; le système informatique maintient également un index pour la table de base de données ; chaque index comprend une structure d'index respective pour chaque colonne de la table de base de données ; 25 chaque structure d'index comprend un tuple de pointeurs respectif pour chaque valeur apparaissant dans la colonne respective et un bitmap dans lequel chaque tuple de pointeur comprend un premier pointeur indiquant une des valeurs qui apparaît dans la colonne et un second pointeur indiquant la rangée de la table de base de données dans laquelle la valeur apparaît, et où le bitmap indique des cellules dans la 30 colonne respective sans valeur ; l'index indique un ordre de spécificité des rangées de la table de base de données ; le système informatique est configuré pour : - recevoir une demande indiquant au moins une colonne de la table de base de données associée à une valeur d'entrée respective ; 3047580 32 - incrémentiellement, pour chaque colonne indiquée dans la demande : - utiliser les tuples de pointeur de la structure d'index pour que la colonne filtre toutes les rangées de la table de base de données qui ne comprennent pas la valeur d'entrée respective, et 5 - utiliser le bitmap de la structure d'index pour que la colonne maintienne toutes les rangées de la table de base de données qui ne contiennent aucune valeur dans la cellule de la colonne considérée ; - sélectionner, à partir des rangées restantes, la rangée la plus en haut dans l'ordre de spécificité ; 10 - retourner la valeur d'au moins une cellule de la rangée déterminée.\n<CLM>\1\tLe système informatique selon la revendication 15 est agencé pour exécuter le procédé d'une quelconque des revendications 2 à\n<CLM>\1\t15\n<CLM>\1\tUn programme d'ordinateur comprenant des instructions de code de programme pour l'exécution des étapes du procédé selon les revendications 1 à 14 lorsque ledit programme est exécuté sur un ordinateur.