Brevet FR3024914A1 — publié le 20160219

PROCÉDÉ ET SIMLIPME DE GÉNÉRATION DE CONCEPTIONS DE SCHÉMAS DE BASES DE DONNÉES DOMAINE DE L'INVENTION La présente invention concerne un système et procédé destiné à générer trhe conception de schémas de bases de données relationnelles pour des applications qui nécessitent des données incertaines. 10 CONTEXTE DE L'INVENTION Des bases de données relationnelles ont été développées pour les applications dans lesquelles des données sont produites avec une certitude totale, telles -que les applications de comptabilité, d'inventaire et de traitement de salaires. Les applications 15 modernes, par exemple les applications d'extraction d'informations, de données massives (Big Data), d'intégration et de nettoyage de données, nécessitent des techniques en mesure de traiter les données incertaines. Si la recherche sur les données incertaines a été prolifique, deux tendances peuvent pourtant être observées : Le traitement des requêtes est le principal point de focalisation, et l'incertitude est essentiellement 20 modélisée quantitativement en termes de données probabilistes. Dans la présente spécification, où il a été fait référence à des spécifications de brevet, à d'autres documents externes, ou à d'autres sources d'information, ceci est généralement réalisé dans le but de fournir un contexte permettant l'examen des caractéristiques de l'invention. Sauf indication contraire, toute référence à de tels 25 documents externes ne doit pas être interprétée comme une admission que de tels documents, ou de telles sources d'information, dans une quelconque juridiction, relèvent de l'art antérieur, ou font partie des connaissances générales communes dans l'art. RÉSUMÉ DE L'INVENTION 30 La présente invention cherche à fournir un système et/ou un procédé de génération d'une conception de schémas de bases de données relationnelles pour des applications qui font appel à des données incertaines. Dans un premier aspect, l'invention consiste principalement en un procédé de 35 génération de conceptions de schémas de bases de données relationnelles pour des 3024914 2 applications de bases de données qui comportent des données incertaines, comprenant les étapes ci-dessous consistant à : recevoir des données de conception d'entrée indicatives du schéma de relations et des dépendances fonctionnelles présentant un degré de certitude associé ou affecté à partir d'une échelle de degrés de certitude ; appliquer un algorithme de normalisation au schéma de relations, ainsi qu'un ensemble de dépendances fonctionnelles qui est défini par une entrée de commande ; et générer des données de conception de sortie comprenant des données indicatives des schémas de relations générés par l'algorithme de normalisation appliqué. Dans un mode de réalisation, les données de conception de sortie comportent des données indicatives des schémas de relations et des données indicatives des dépendances fonctionnelles qui sont valables pour les ou chacun des schémas de relations générés par l'algorithme de normalisation. Dans un exemple, les données indicatives des schémas de relations comportent le nombre de schémas et les attributs de chaque schéma de relations. Dans une forme, les données de conception de sortie comportent des données indicatives de quelconques dépendances fonctionnelles qui n'étaient pas conservées dans les schémas de relations générés par l'algorithme de normalisation. Dans un mode de réalisation, la réception des données de conception d'éntrée comporte en outre la réception de données indicatives de l'échelle de degrés de certitude. Dans un autre mode de réalisation, le procédé comprend en outre la détermination de l'échelle de degrés de certitude à partir des degrés de certitude associés aux dépendances fonctionnelles. Dans un mode de réalisation, l'entrée de commande définit le niveau de normalisation appliqué au schéma de relations. Dans un exemple, l'entrée de commande détermine l'ensemble de dépendances fonctionnelles pour lequel l'algorithme de normalisation est appliqué. Dans cet exemple, l'entrée de commande peut être donnée par la valeur de cohérence. Dans un mode de réalisation, l'entrée de commande correspond ou se rapporte aux degrés de certitude ou à l'échelle de degrés de certitude associés aux dépendances fonctionnelles. Dans une forme, l'entrée de commande correspond à une variable d'index qui est sélectionnable à partir d'une échelle d'index correspondant à l'échelle de degrés de certitude. Dans un exemple, l'ensemble de dépendances fonctionnelles appliqué dans l'algorithme de normalisation comporte toutes les dépendances fonctionnelles présentant un degré de certitude associé qui correspond ou se situe à un niveau de certitude plus élevé que la variable d'index sélectionnée. 3024914 3 Dans un mode de réalisation, l'algorithme de normalisation est un algorithme de décomposition de forme normale de Boyce-Codd (BCNF). Dans un autre mode de réalisation, l'algorithme de normalisation est un algorithme de synthèse de troisième forme normale (3NF). Dans un mode de réalisation, les données de conception d'entrée comportent des données indicatives des attributs ou des noms de champs du schéma de relations. Dans un mode de réalisation, chaque degré de certitude dans l'échelle de degrés de certitude est mis en concordance avec un degré de possibilité correspondant à partir 10 d'une échelle de possibilités, les degrés de possibilité étant affectés ou associés à des uplets de données sur le schéma de relations. Dans un mode de réalisation, le procédé comprend en outre l'étape consistant à affecter ou à associer un degré de certitude à chacune des dépendances fonctionnelles, l'étape comprenant l'affectation du degré de certitude à chaque dépendance fonctionnelle qui correspond à la possibilité du plus petit 15 monde possible dans lequel la dépendance fonctionnelle est enfreinte pour les uplets de données. Dans un exemple, l'algorithme de décomposition de forme BCNF est appliqué à un ensemble de dépendances fonctionnelles présentant un degré de certitude supérieur au degré de certitude utilisé en qualité d'entrée de commande. Dans cet exemple, l'algorithme de décomposition de forme BCNF réalise toujours une conception de sortie 20 qui garantit qu'aucune redondance de données ne sera produite dans des quelconques uplets associés aux degrés de possibilité correspondants. Dans un exemple, l'algorithme de synthèse 3NF est appliqué à un ensemble de dépendances fonctionnelles présentant un degré de certitude supérieur au degré de certitude utilisé en qualité d'entrée de commande. Dans cet exemple, l'algorithme de synthèse 3NF réalise toujours une 25 conception de sortie qui garantit que la quantité de redondance de données qui se produira dans des quelconques uplets associés aux degrés de possibilité correspondants est minimale parmi toutes les conceptions de sortie qui conservent toutes les dépendances fonctionnelles dans l'ensemble. Dans un mode de réalisation, le procédé comporte en outre les étapes consistant 30 à modifier ou à faire varier l'entrée de commande, et à ré-appliquer l'algorithme de normalisation pour la ou chaque nouvelle entrée de commande modifiée, jusqu'à ce que les données de conception de sortie correspondent à des critères prédéterminés. Dans un exemple, les critères prédéterminés peuvent être l'un ou plusieurs des critères ci-après : des données définissant le nombre de schémas de relations souhaités, des données 35 indicatives d'une certaine efficacité de mise à jour souhaitée ; et des données indicatives d'une certaine efficacité de requête souhaitée. 3024914 4 Dans une configuration, le procédé peut en outre comporter la génération d'une représentation graphique des données de conception de sortie pour un nombre d'entrées de commande distinctes. Par exemple, le procédé peut comporter la génération d'un graphique traçant le nombre de schémas dans les données de conception de sortie par rapport à l'entrée de commande ayant généré ces données de conception de sortie. Dans une configuration, le procédé est mis en oeuvre par un processeur qui est configuré de manière à exécuter les étapes de procédé. Dans un exemple, le procédé est mis en oeuvre par ordinateur. Dans un deuxième aspect, l'invention consiste principalement en un système de 10 conception de bases de données destiné à générer des conceptions de schémas de bases de données relationnelles pour des applications de bases de données qui comportent des données incertaines, comprenant : une interface d'entrée configurée de manière à recevoir ou récupérer des données de conception d'entrée indicatives du schéma de relations et des dépendances 15 fonctionnelles présentant un degré de certitude associé ou affecté à partir d'une échelle de degrés de certitude ; un processeur de normalisation mise à l'échelle qui est configuré de manière à appliquer un algorithme de normalisation au schéma de relations ainsi qu'un ensemble de dépendances fonctionnelles qui sont définis par une entrée de commande ; et 20 une interface de sortie qui est configurée de manière à générer des données de conception de sortie comprenant des données indicatives des schémas de relations générés par l'algorithme de normalisation appliqué. Dans un mode de réalisation, l'interface de sortie est configurée de manière à générer des données de conception de sortie comportant des données indicatives des 25 schémas de relations et des données indicatives des dépendances fonctionnelles qui sont valables pour les ou chacun des schémas de relations générés par l'algorithme de normalisation. Dans un exemple, les données indicatives des schémas de relations comportent le nombre de schémas et les attributs de chaque schéma. Dans une forme, les données de conception de sortie comportent des données 30 indicatives de quelconques dépendances fonctionnelles qui n'étaient pas conservées dans les schémas de relations générés par l'algorithme de normalisation. Dans un mode de réalisation, l'interface d'entrée est configurée de manière à recevoir ou récupérer des données de conception d'entrée comportant des données indicatives de l'échelle de degrés de certitude. Dans un autre mode de réalisation, le 35 système est en outre configuré de manière à déterminer l'échelle de degrés de certitude à partir des degrés de certitude associés aux dépendances fonctionnelles. 3024914 5 Dans un mode de réalisation, l'entrée de commande définit le niveau de normalisation appliqué au schéma de relations par le processeur de normalisation mise à l'échelle. Dans un exemple, l'entrée de commande détermine l'ensemble de dépendances fonctionnelles auquel le processeur de normalisation mise à l'échelle est appliqué. Dans cet exemple, l'entrée de commande peut être donnée par la valeur de cohérence. Dans un mode de réalisation, l'entrée de commande correspond ou se rapporte aux degrés de certitude ou à l'échelle de degrés de certitude associés aux dépendances fonctionnelles. Dans une forme, l'entrée de commande correspond à une valeur ou 10 variable d'index qui est sélectionnable à partir d'une échelle d'index correspondant à l'échelle de degrés de certitude. Dans un exemple, l'ensemble de dépendances fonctionnelles appliqué par le processeur de normalisation mise à l'échelle comporte toutes les dépendances fonctionnelles présentant un degré de certitude associé qui correspond ou se situe à un niveau de certitude plus élevé que la valeur ou variable 15 d'index sélectionnée. Dans un mode de réalisation, le processeur de normalisation mise à l'échelle est configuré de manière à appliquer un algorithme de normalisation comprenant un algorithme de décomposition de forme normale de Boyce-Codd (BCNF). Dans un autre mode de réalisation, le processeur de normalisation mise à l'échelle 20 est configuré de manière à appliquer un algorithme de normalisation comprenant un algorithme de synthèse de troisième forme normale (3NF). Dans un mode de réalisation, l'interface d'entrée est configurée de manière à recevoir ou à récupérer des données de conception d'entrée comportant des données indicatives des attributs ou des noms de champs du schéma de relations. 25 Dans un mode de réalisation, chaque degré de certitude dans l'échelle de degrés de certitude est mis en concordance avec un degré de possibilité correspondant à partir d'une échelle de possibilités, les degrés de possibilité étant affectés ou associés à des uplets de données sur le schéma de relations. Dans un mode de réalisation, le système est en outre configuré de manière à affecter ou à associer un degré de certitude à 30 chacune des dépendances fonctionnelles, en affectant le degré de certitude à chaque dépendance fonctionnelle qui correspond à la possibilité du plus petit monde possible dans lequel la dépendance fonctionnelle est enfreinte pour les uplets de données. Dans un exemple, le système applique l'algorithme de décomposition de forme BCNF à un ensemble de dépendances fonctionnelles présentant un degré de certitude supérieur au 35 degré de certitude utilisé en qualité d'entrée de commande. Dans cet exemple, le système produit toujours une conception de sortie qui garantit qu'aucune redondance de données 3024914 6 ne sera produite dans des quelconques uplets associés aux degrés de possibilité correspondants. Dans un autre exemple, le système applique l'algorithme de synthèse 3NF à un ensemble de dépendances fonctionnelles présentant un degré de certitude supérieur au degré de certitude utilisé en qualité d'entrée de commande. Dans cet 5 exemple, le système réalise toujours une conception de sortie qui garantit que la quantité de redondance de données qui se produira dans des quelconques uplets associés aux degrés de possibilité correspondants est minimale parmi toutes les conceptions de sortie qui conservent toutes les dépendances fonctionnelles dans l'ensemble. Dans un mode de réalisation, le système est en outre configuré de manière à 10 modifier ou à faire varier l'entrée de commande, et à ré-appliquer l'algorithme de normalisation pour la ou chaque nouvelle entrée de commande modifiée, jusqu'à ce que les données de conception de sortie correspondent à des critères prédéterminés. Dans un exemple, les critères prédéterminés peuvent être l'un ou plusieurs des critères ci-après : des données définissant le nombre de schémas de relations souhaités, des données 15 indicatives d'une certaine efficacité de mise à jour souhaitée ; et des données indicatives d'une certaine efficacité de requête souhaitée. Dans une configuration, l'interface de sortie comporte un écran et le système est en outre configuré de manière à générer une représentation graphique des données de conception de sortie pour un nombre d'entrées de commande distinctes. Dans un 20 exemple, le système est configuré de manière à générer un graphique traçant le nombre de schémas dans les données de conception de sortie par rapport à l'entrée de commande ayant généré ces données de conception de sortie. Dans un troisième aspect, l'invention consiste principalement en un procédé de génération d'une conception de schéma de bases de données relationnelles pour des 25 applications qui comportent des données incertaines, comprenant l'application d'une normalisation mise à l'échelle à un schéma de relations d'entrée sur la base d'un ensemble de dépendances fonctionnelles dans lequel chacune des dépendances fonctionnelles de l'ensemble présente un degré de certitude associé ou affecté qui satisfait une entrée de commande configurable ou sélectionnable. 30 Dans une configuration, le procédé est mis en oeuvre par un processeur qui est configuré de manière à exécuter les étapes de procédé. Dans un exemple, le procédé est mis en oeuvre par ordinateur. Dans un quatrième aspect, l'invention consiste principalement en un système de conception de bases de données destiné à générer une conception de schéma de bases 35 de données relationnelles pour des applications qui comportent des données incertaines, comprenant un _processeur qui est exploitable de manière à appliquer une normalisation 3024914 7 mise à l'échelle à un schéma de relations d'entrée sur la base d'un ensemble de dépendances fonctionnelles dans lequel chacune des dépendances fonctionnelles de l'ensemble présente un degré de certitude associé ou affecté qui satisfait une entrée de commande configurable ou sélectionnable. 5 Dans un cinquième aspect, l'invention consiste principalement en un procédé de génération d'une conception de schéma de bases de données relationnelles pour des applications qui comportent des données incertaines, comprenant l'application d'une normalisation mise à l'échelle à un schéma de relations d'entrée sur la base d'un sous-ensemble d'un ensemble complet de dépendances fonctionnelles associées au schéma 10 de relations d'entrée. Dans un exemple, le procédé comprend la génération d'un nombre de sous-ensembles ou de groupes de dépendances fonctionnelles à partir de l'ensemble complet de dépendances fonctionnelles, et l'application de la normalisation mise à l'échelle au schéma de relations d'entrée pour un sous-ensemble sélectionné ou un groupe 15 sélectionné de dépendances fonctionnelles. Les dépendances fonctionnelles de chaque sous-ensemble ou groupe peuvent présenter une relation mutuelle ou être sélectionnées pour leur sous-ensemble ou groupe sur la base d'un degré de certitude associé ou d'un autre critère, ou peuvent alternativement être sélectionnées ou affectées arbitrairement à leur sous-ensemble ou groupe. 20 Dans une configuration, le procédé est mis en oeuvre par un processeur qui est configuré de manière à exécuter les étapes de procédé. Dans un exemple, le procédé est mis en oeuvre par ordinateur. Dans un sixième aspect, l'invention consiste principalement en un système de conception de bases de données destiné à générer une conception de schéma de bases 25 de données relationnelles pour des applications qui comportent des données incertaines, comprenant un processeur qui est exploitable de manière à appliquer une normalisation mise à l'échelle à un schéma de relations d'entrée sur la base d'un sous-ensemble d'un ensemble complet de dépendances fonctionnelles associées au schéma de relations d'entrée. 30 Dans un exemple, il existe un nombre de sous-ensembles ou de groupes de dépendances fonctionnelles provenant de l'ensemble complet de dépendances fonctionnelles, et le système est configuré de manière à appliquer la normalisation mise à l'échelle au schéma de relations d'entrée pour un sous-ensemble sélectionné ou un groupe sélectionné de dépendances fonctionnelles. Les dépendances fonctionnelles de 35 chaque sous-ensemble ou groupe peuvent présenter une relation mutuelle ou être sélectionnées pour leur sous-ensemble ou groupe sur la base d'un degré de certitude 3024914 8 associé ou d'un autre critère, ou peuvent alternativement être sélectionnées ou affectées arbitrairement à leur sous-ensemble ou groupe. Dans un autre aspect, l'invention consiste principalement en un support lisible par ordinateur sur lequel sont enregistrées des instructions exécutables par ordinateur qui, 5 lorsqu'elles sont exécutées sur un ou des dispositifs de traitement, amènent le ou les dispositifs de traitement à mettre en oeuvre un procédé selon l'un quelconque des aspects précédents de l'invention. Le terme « comportant/comprenant », tel qu'il est utilisé dans la présente 10 description, ainsi que dans les revendications, signifie « constitué au moins partiellement de ». Dans le cadre de l'interprétation de chaque énoncé de la présente description et des revendications qui comporte le terme «comportant/comprenant », des caractéristiques ou fonctionnalités distinctes de celle ou celles qui sont précédées dudit terme peuvent également être présentes. Des termes connexes tels que « 15 comportent/comprennent » et « comporte/comprend » doivent être interprétés de la même manière. Plages de numéros Il est entendu que toute référence à une plage de numéros/nombres divulguée 20 dans le présent document (par exemple, de 1 à 10) inclut également la référence à tous les nombres rationnels dans cette plage (par exemple, 1, 1.1, 2, 3, 3.9, 4, 5, 6, 6.5, 7, 8, 9 et 10) et également toute plage de nombres rationnels dans cette plage (par exemple, 2 à 8, 1.5 à 5.5 et 3.1 à 4.7) et, par conséquent, toutes les sous-plages de toutes les plages expressément divulguées dans le présent document sont ainsi expressément divulguées. 25 Ce ne sont là que des exemples de ce qui est expressément entendu, et toutes les combinaisons possibles des valeurs numériques entre la valeur la plus basse et la valeur la plus élevée énumérées doivent être considérées comme expressément indiquées de façon similaire dans la présente demande. Tel qu'il est utilisé dans le présent document, le terme « et/ou » signifie « et » ou 30 « ou», ou les deux. La présente invention peut également être considérée globalement comme étant constituée des parties, éléments et caractéristiques visés ou indiqués dans la description de la demande, individuellement ou collectivement, et de tout ou partie des combinaisons de deux ou plus desdites parties, desdits éléments ou desdites fonctionnalités, et lorsque 35 des nonibres entiers epécifiques sont mentionnés dans le présent document, lesquels présentent des équivalents connus dans l'art auquel la présente invention se rapporte, de 3024914 9 tels équivalents connus sont réputés être intégrés ici comme s'ils étaient énoncés individuellement. La présente invention est constituée de ce qui précède et envisage également des constructions dont la suite de la présente description donne des exemples uniquement. 5 BRÈVE DESCRIPTION DES DESSINS Des modes de réalisation de la présente invention seront décrits à titre d'exemple uniquement et en référence aux dessins, dans lesquels : 10 La figure 1 est un diagramme illustrant les mondes possibles de la relation possibiliste pour un scénario exemplaire ; La figure 2 est un diagramme illustrant la mise en concordance d'une échelle de degrés de possibilité sur une échelle de degrés de certitude pour le scénario exemplaire ; 15 La figure 3 est un diagramme illustrant le concept de redondance de données mises à l'échelle pour le scénario exemplaire ; La figure 4 est un schéma de principe de la configuration matérielle du système de conception de bases de données selon un mode de réalisation ; La figure 5 est un organigramme d'un processus de conception de bases de 20 données selon un mode de réalisation ; La figure 6 est un organigramme de l'application d'algorithmes de normalisation mise à l'échelle selon un mode de réalisation du processus de conception de bases de données. La figure 7A est une représentation graphique de la sortie de l'organigramme de la 25 figure 6 illustrant le nombre de schémas générés pour chaque conception tracée par rapport au degré de certitude de l'ensemble de dépendances fonctionnelles pour lequel le schéma d'entrée est normalisé ; La figure 7B est une représentation graphique démontrant les diverses sorties de décomposition d'une normalisation mise à l'échelle appliquée à un schéma de relations 30 d'entrée dans lequel une entrée de commande est utilisée pour faire varier ou commander le niveau de normalisation appliqué ; La figure 8 est une capture d'écran de l'écran principal d'unpjaterface utilisateur graphique, GUI, du système de conception de bases de données selon un mode de réalisation ; 3024914 10 La figure 9 est une capture d'écran de l'interface utilisateur d'un écran d'entrée de données de normalisation mise à l'échelle du système de conception de bases de données selon un mode de réalisation ; La figure 10 est une capture d'écran des données d'entrée et des données de sortie d'interface utilisateur pour une décomposition de type « f12-BCNF » d'un scénario exemplaire ; La figure 11 est une capture d'écran des données d'entrée et des données de sortie d'interface utilisateur pour une décomposition de type « /33-BCNF » d'un scénario exemplaire ; 10 La figure 12 est une capture d'écran des données d'entrée et de sortie d'interface utilisateur pour une décomposition de type «134-BCNF » d'un scénario exemplaire ; La figure 13 est une capture d'écran des données d'entrée et de sortie d'interface utilisateur pour une synthèse de type «f34-3NF » d'un scénario exemplaire ; La figure 14 illustre des tracés graphiques pour des expériences avec le système 15 de conception de bases de données, selon un mode de réalisation, illustrant la taille moyenne de décompositions, prises chacune sur 5 000 exécutions, où les schémas de relations d'entrée présentent 10 attributs dans la rangée supérieure et 15 attributs dans la rangée inférieure, et où la taille d'ensemble de dépendances PFD maximale est n dans la colonne de gauche et 5n dans la colonne de droite. 20 La figure 15 illustre des tracés graphiques pour des expériences avec le système de conception de bases de données, selon un mode de réalisation, illustrant les temps moyens de génération de décompositions, prises chacune sur 5 000 exécutions, où les schémas de relations d'entrée présentent 10 attributs dans la rangée supérieure et 15 attributs dans la rangée inférieure, et où la taille d'ensemble de dépendances PFD 25 maximale est n dans la colonne de gauche et 5n dans la colonne de droite. La figure 16 illustre des tracés graphiques pour des expériences avec le système de conception de bases de données, selon un mode de réalisation, illustrant les pourcentages de sorties 3NF dans la forme BCNF par rapport à des sorties BCNF qui conservent les dépendances, prises chacune sur 5 000 exécutions, où les schémas de 30 relations d'entrée présentent 10 attributs dans la rangée supérieure et 15 attributs dans la rangée inférieure, et où la taille d'ensemble de dépendances PFD maximale est n dans la colonne de gauche et 5n dans la colonne de droite. La figure 17 illustre des tracés graphiques pour des expériences avec le système de conception de bases de données, selon un mode de réalisation, illustrant les temps de 35 vérification pour la forme BCNF-dans des sorties 3NF par rapport à une conservation de dépendances dans les sorties BCNF, prises chacune sur 5 000 exécutions, où les 3024914 11 schémas de relations d'entrée présentent 10 attributs dans la rangée supérieure et 15 attributs dans la rangée inférieure, et où la taille d'ensemble de dépendances PFD maximale est n dans la colonne de gauche et 5n dans la colonne de droite. La figure 18 illustre des tracés graphiques pour des expériences avec le système 5 de conception de bases de données, selon un mode de réalisation, illustrant les résultats et temps moyens pour déterminer des problèmes d'implication pour des ensembles de dépendances PFD et les ensembles de dépendances FD suite à la suppression des degrés de certitude, pris chacun sur 1 000 exécutions, où les schémas de relations d'entrée présentent entre 3 et 20 attributs et où il existe 15 degrés de certitude ; 10 La figure 19 illustre des tracés graphiques pour des expériences avec le système de conception de bases de données, selon un mode de réalisation, illustrant la moyenne de degrés de certitude et des temps de calcul de degré de certitude pour des ensembles de dépendances PFD, pris chacun sur 1 000 exécutions, où les schémas de relations d'entrée présentent entre 3 et 20 attributs et où il existe 15 degrés de certitude ; et 15 La figure 20 illustre des tracés graphiques pour des expériences avec le système de conception de bases de données, selon un mode de réalisation, illustrant les tailles moyennes de couvertures et des temps pour leur calcul, prises chacune sur 1 000 exécutions, où les schémas de relations d'entrée présentent entre 3 et 20 attributs et où il existe 15 degrés de certitude. 20 DESCRIPTION DÉTAILLÉE DES MODES DE RÉALISATION PRÉFÉRÉS Dans la description ci-après, des détails spécifiques sont donnés pour fournir une compréhension approfondie des modes de réalisation. Toutefois, l'homme du métier 25 comprendra que les modes de réalisation peuvent être mis en pratique sans ces détails spécifiques. Par exemple, des modules logiciels, des fonctions, des circuits, etc., peuvent être illustrés dans des schémas de principe afin de ne pas obscurcir les modes de réalisation par des détails inutiles. Dans d'autres cas, des modules, structures et techniques bien connus peuvent ne pas être illustrés en détail afin de ne pas obscurcir les 30 modes de réalisation. En outre, il convient de remarquer que les modes de réalisation peuvent être décrits sous la forme d'un processus qui est représenté sous la forme d'un schéma de procédé, d'un organigramme, d'un diagramme de structure, ou d'un schéma de principe. Bien qu'un schéma de procédé puisse décrire les opérations sous la forme d'un 35 processus séquentiel, bon nombre des opérations peuvent être mises en oeuvre en parallèle ou simultanément. En outre, l'ordre des opérations peut être réorganisé. Un 3024914 12 processus est achevé lorsque ses opérations sont terminées. Un processus peut correspondre à un procédé, à une fonction, à une procédure, à une sous-routine, à un sous-programme, etc., dans un programme informatique. Lorsqu'un processus correspond à une fonction, son achèvement correspond à un retour de la fonction à la 5 fonction d'appel ou à une fonction principale. Des aspects des systèmes et procédés décrits ci-dessous peuvent être exploitables sur tout type de dispositif informatique ou système d'ordinateur à usage général, y compris, mais sans s'y limiter, un ordinateur de bureau, un ordinateur portable, une tablette ou un dispositif mobile. Le terme « dispositif mobile » inclut, mais sans s'y 10 limiter, un dispositif sans fil, un téléphone mobile, un dispositif de communication mobile, un dispositif de communication d'utilisateur, un assistant numérique personnel, un ordinateur de poche mobile et un ordinateur portable. 1. Présentation générale 15 Une conception de schéma de bases de données relationnelles classique est régie par des règles commerciales que les données dans toutes les instances de bases de données futures sont censées satisfaire. Dans la pratique, ces règles commerciales sont généralement et exclusivement constituées de ce que l'on appelle les « 20 dépendances fonctionnelles ». La technologie de normalisation existante suppose que ces dépendances fonctionnelles s'appliquent à toutes les données uniformément. Le procédé et système de conception de bases de données utilise l'impact de l'incertitude sur une conception de schéma de bases de données relationnelles. L'incertitude est modélisée qualitativement en affectant, à des uplets, un degré de 25 possibilité avec lequel ils se produisent dans une relation, et en affectant, à des dépendances fonctionnelles, un degré de certitude qui indique à quels uplets elles s'appliquent. Dans certains modes de réalisation, le système et procédé met en oeuvre une théorie de conception basée sur des dépendances fonctionnelles possibilistes, notamment des caractérisations axiomatiques et algorithmiques efficaces de leur 30 problème d'implication. Les degrés de possibilité des uplets se traduisent par une échelle de différents degrés de redondance de données, occasionnés par des dépendances fonctionnelles qui sont valables, autrement dit qui se maintiennent, avec les degrés de certitude correspondants. Des versions mises à l'échelle de la forme normale de BoyceCodd et de la troisième forme normale syntaxiques classiques sont établies et justifiées 35 sémantiquement en termes d'évitement d'une redondance des données de différents degrés. Les techniques de décomposition et de synthèse classiques sont également 3024914 13 mises à l'échelle. L'utilisation des dépendances fonctionnelles possibilistes permet aux concepteurs de commander, ou contrôler, le niveau d'intégrité de données ciblé, mais également d'équilibrer ou de pondérer le compromis classique entre l'efficacité des mises à jour et l'efficacité des requêtes. Dans un mode de réalisation, le système est mis en 5 oeuvre dans une interface utilisateur graphique (GUI) basée sur le Web qui peut être commandée par l'utilisateur en vue de générer des conceptions de schémas de bases de données basées sur des paramètres d'entrée indicatifs de la base de données requise. Le procédé et système de conception de bases de données est basé sur une théorie qui étudie l'impact de l'incertitude sur la conception de schéma de bases de données, 10 qualitativement, en ciblant le traitement efficace des requêtes et mises à jour fréquentes. Dans une conception de schéma classique, les inefficacités de mises à jour sont évitées en supprimant la redondance des données potentielle occasionnée par les dépendances fonctionnelles. Si les données sont incertaines, il en est de même pour toute redondance qui résulte de ces données. Plus il est possible qu'une redondance de 15 données se produise, plus les dépendances fonctionnelles peuvent occasionner cette redondance, et plus l'effort de normalisation sera important pour supprimer cette redondance. En d'autres termes, la suppression de la redondance des données les moins possibles nécessite uniquement une normalisation par rapport à un nombre inférieur de dépendances fonctionnelles. Cependant, ceci est un point positif étant donné que les 20 données qui sont moins possibles sont soumises à plus de mises à jour. Par conséquent, la plupart des mises à jour fréquentes peuvent être prises en charge de manière efficace avec un effort de normalisation moindre. À son tour, une normalisation moindre se traduit par une meilleure efficacité des requêtes. Le procédé et système de conception de bases de données permet aux concepteurs de tirer pleinement parti de cet impact de 25 l'incertitude. Dans le système et procédé, l'incertitude est modélisée en affectant, à chaque uplet, un degré de possibilité par lequel il semble se produire. Le degré de possibilité provient d'une quelconque échelle finie donnée de valeurs ordonnées linéairement. La structure répond bien à l'intuition et à la capacité des personnes à raisonner 30 qualitativement et non pas quantitativement. En effet, les humains aiment classer les éléments dans un nombre faible de catégories, et ils ne sont pas à l'aise dès lors qu'il s'agit d'affecter des valeurs exactes telles que les probabilités. La structure se traduit par une chaîne imbriquée de mondes possibles, dont chacun correspond à une relation classique. La plus petite relation ne contient que des uplets qui sont tout à fait possibles, 35 alors que la plus grande relation contient tous les uplets, hormis ceux qui ne peuvent pas se produire. La certitude selon laquelle une dépendance fonctionnelle classique est 3024914 14 valable est dérivée du degré de possibilité de la plus petite relation dans laquelle la dépendance fonctionnelle est enfreinte. Aux extrémités, il existe des dépendances fonctionnelles qui sont pleinement certaines, étant donné qu'elles sont valables, autrement dit se maintiennent, même sur la plus grande relation, et il existe des dépendances fonctionnelles qui ne sont pas du tout certaines, étant donné qu'elles ne se maintiennent pas même dans la plus petite relation. Les résultats du procédé et système de conception de bases de données, dans au moins certains modes de réalisation, sont les suivants : 1. L'incertitude est formalisée par l'affectation de degrés de possibilité à des uplets 10 dans une base de données. Il en résulte une distribution de possibilités sur des mondes possibles qui forment une chaîne linéaire de relations. 2. Des dépendances fonctionnelles possibilistes (PFD) sont définies en tant que des dépendances fonctionnelles classiques (FD) avec un degré de certitude, dérivé du degré de possibilité du monde le plus petit possible dans lequel il est enfreint. 15 3. Le système et procédé est basé sur une théorie de conception complète pour les dépendances PFD, notamment des caractérisations axiomatiques et algorithmiques de leur problème d'implication associé, ainsi que des algorithmes pour calculer des couvertures et les degrés de certitude maximale moyennant quoi les dépendances PFD sont impliquées. Cette structure possibiliste permet au système d'établir des liens 20 robustes entre les dépendances PFD et les dépendances FD classiques, et d'indiquer par conséquent l'efficacité des caractérisations. 4. Le système et procédé utilise la théorie de conception en vue d'établir une nouvelle structure de normalisation, notamment des versions mises à l'échelle de la forme normale de Boyce-Codd (BCNF) et de la troisième forme normale (3NF), leur justification 25 sémantique en termes de conservation des dépendances et la suppression de la redondance de données, ainsi que des algorithmes de normalisation. Le système et procédé fournit, aux concepteurs de bases de données, une échelle complète de schémas normalisés, à partir de laquelle des sélections plus éclairées du schéma final peuvent être faites. Dans certaines configurations, le système et procédé peut présenter 30 deux principaux scénarios de cas d'utilisation : i) Une organisation qui est principalement axée sur l'intégrité des données peut choisir les dépendances FD qui s'appliquent au degré de certitude cible (intégrité des données). Dans ce cas, les algorithmes s'exécutant dans le système calculent les formes normales qui satisfont exactement cette cible. 35 ii) Une organisation qui est principalement axée sur le traitement efficace de sa charge de travail en termes de requêtes et de mises à jour. Dans ce cas, un concepteur de 3024914 15 bases de données peut utiliser le système pour dériver les formes normales qui correspondent le mieux à la charge de travail. Le système fournit également une sortie ou une rétroaction, ou retour d'information, sur le niveau d'intégrité des données qui est atteint. 5 Le système utilise les degrés de certitude des dépendances FD en vue de fournir un mécanisme efficace pour commander, ou contrôler, le degré d'intégrité des données ciblé, et également pour dériver des conceptions qui correspondent à la charge de travail de la base de données cible, en pondérant le compromis entre l'efficacité des requêtes et l'efficacité des mises à jour. Dans un exemple, le système peut être utilisé pour justifier un 10 schéma classique dé-normalisé en termes de permission d'une redondance de données qui est occasionnée par des dépendances FD dont le degré de certitude est inférieur à celui ciblé. 5. Dans un mode de réalisation, le système fournit une interface utilisateur graphique (GUI) dans laquelle les mises en oeuvre des algorithmes peuvent être consultées et 15 exécutées par un concepteur de bases de données. 6. Des expériences approfondies avec les algorithmes exécutés dans le système confirment leur efficacité dans la pratique, et offrent un nouvel éclairage dans le cadre des compromis de normalisation classiques. Par exemple, le système fournit une preuve empirique qu'il existe presque toujours une bonne chance que la synthèse 3NF se 20 traduise par une décomposition optimale, définie comme une décomposition de forme BCNF à conservation de dépendances et sans perte, alors qu'il n'existe presque jamais de chance raisonnable que l'algorithme de décomposition de forme BCNF se traduise par une décomposition avec conservation des dépendances. Un mode de réalisation du procédé et système de conception de bases de 25 données sera décrit ci-après en référence à une application du système à un scénario exemplaire, expliqué plus en détail dans la section 2. La structure possibiliste pour modéliser l'incertitude au niveau des uplets est décrite dans la section 3. la sémantique des dépendances PFD est définie dans la section 4, et la théorie de conception des dépendances PFD est établie dans la section 5. Des versions mises à l'échelle de la 30 forme BCNF et de la troisième forme normale, 3NF, sont définies dans la section 6, et leurs justifications sémantiques sont dérivées. Les algorithmes de normalisation sont établis dans la section 7. Un exemple de système de conception de bases de données avec une interface GUI offrant un accès aux algorithmes est expliqué dans la section 8, et les résultats des expériences du système sont examinés dans la section 9. 35 3024914 16 1. Scénario exemplaire Un scénario exemplaire simple est fourni en vue de faire la démonstration du système. L'exemple implique une application dans laquelle un employé extrait des informations de sites web au sujet d'éventuelles réunions hebdomadaires autour de 5 projets au sein de son entreprise. Les attributs d'intérêt sont les suivants : « Projet », à savoir l'enregistrement des projets avec des noms uniques, « Horaire », à savoir l'enregistrement du jour de la semaine et de l'heure ou horaire de début de la réunion, « Responsable », à savoir l'enregistrement des responsables du projet qui assistent à la réunion, et « Salle », à savoir l'enregistrement du nom unique d'une salle. 10 L'employé classe la possibilité avec laquelle des uplets se produisent dans la relation selon le site web d'où proviennent les informations. Les uplets recueillis auprès du site web de la réunion de projet officielle se voient affecter le degré de possibilité al, indiquant qu'ils sont tout à fait possible, les uplets provenant du site web d'un responsable de projet se voient affecter le degré a2, les uplets provenant du site web d'un membre du 15 projet se voient affecter le degré a3, et les uplets qui proviennent de rumeurs se voient affecter le degré a4. Les autres uplets se voient affecter le degré as, indiquant qu'il est impossible qu'ils se produisent. La classification aurait également pu être le résultat d'une interprétation différente. Admettons que des réunions déjà tenues sont classées comme al, les 20 réunions confirmées sont classées comme a2, les réunions demandées sont classées comme a3, les réunions prévues sont classées comme a4, et toutes les autres réunions sont classées comme as. Le fait est que l'employé a choisi 5 différents degrés de possibilité al > a2 > a3 > a4 > as pour affecter qualitativement différents niveaux d'incertitude à des uplets, où al désigne le degré supérieur et as désigne le degré 25 inférieur, respectivement. Certes, les degrés peuvent également être interprétés numériquement, par exemple 1 > 0.75 > 0.5 > 0.25> 0. Le tableau 1 illustre une relation possibiliste, autrement dit une relation classique où un degré de possibilité est affecté à chaque uplet. 30 35 3024914 17 Tableau 1: Relation possibiliste Projet Horaire Responsable Salle Degré de possibilité Eagle Lundi, 9h Ann Aqua ai Hippo Lundi, 13h Ann Aqua , al Kiwi Lundi, 13h Pete Buff ai Kiwi Mardi, 14h Pete Buff al Lion Mardi, 16h Gill Buff ai Lion Mercredi, 9h Gill Cyan al Lion Mercredi, 11h Bob Cyan a2 Lion Mercredi, 11h Jack Cyan a3 Lion Mercredi, 11h Pam Lava a3 Tiger Mercredi, 11h Pam Lava cr4 5 L'affectation de degrés de possibilité se traduit par une chaîne ordonnée linéairement de mondes possibles : Pour i = 1, ...,4, la relation ri se compose d'uplets avec un degré de possibilité ai ou supérieur, c'est-à-dire ai avec j i. Le degré de possibilité du monde ri est ai. En particulier, des uplets totalement possibles se 10 produisent dans chaque monde possible, et ils ont donc également une certitude totale de se produire. Les mondes possibles de la relation possibiliste dans le tableau 1 sont illustrés dans la figure 1. Une dépendance FD arbitraire est soit satisfaite par le plus grand monde possible soit il existe un monde le plus petit possible dans lequel elle est enfreinte. Par exemple, la 15 dépendance FD Responsable, Horaire Salle est satisfaite par le monde r4, et est par conséquent valable dans chaque monde possible. Par conséquent, elle se voit affecter le degré de certitude le plus élevé, noté je,. La plus petite relation qui enfreint Salle, Horaire Projet est ri, autrement dit, la dépendance FD se voit affecter le deuxième degré de certitude le plus élevé, 132. La plus petite relation qui enfreint Projet Responsable est r2, 20 ce qui signifie que la dépendance FD vaut pour un degré de certitude /34. La dépendance FD Responsable, Salle -> Horaire est enfreinte y compris par le plus petit monde possible r1, et elle se voit par conséquent affecter le degré de certitude le plus faible fis= )3k+1. Par conséquent, le degré de possibilité ai du plus petit monde possible ri dans lequel la dépendance FD est enfreinte détermine le degré de certitude iek+2_i moyennant 25 quoi la dépendance FD se maintient. Plus la possibilité d'un monde possible est élevée, plus le nombre d'uplets qu'il contient est faible et plus le-nombre de dépendances FD pouvant se maintenir sur celui-ci est important, et, par conséquent, plus les occurrences de données peuvent être redondantes. Par conséquent, dès lors que l'on désire éliminer les occurrences de 3024914 18 données redondantes dans le plus de données possible, l'effort de normalisation augmentera. La redondance dans le monde le plus petit possible ri, par exemple, pourrait être occasionnée par des dépendances FD qui se maintiennent avec un quelconque degré de certitude, hormis le degré le plus faible, tandis que la redondance dans le plus 5 grand monde possible r4 ne peut être causée que par des dépendances FD présentant le degré de certitude le plus élevé. Dans le scénario exemplaire, la deuxième occurrence de Gill est redondante par rapport à la dépendance FD Projet -> Responsable qui se maintient avec un degré 134. En effet, tout remplacement de cette occurrence de données par une valeur différente se traduira par un degré de certitude de la dépendance Projet 10 Responsable qui est plus petit que Al, avec lequel elle est supposée se maintenir. De même, l'occurrence de Lava dans le dernier uplet est redondante par rapport à la dépendance FD Responsable, Horaire -> Salle qui se maintient avec un degré f3i. Il est naturel de penser que les données moins possibles sont plus susceptibles d'être mises à jour que les données plus possibles, étant donné que le,s données moins 15 possibles ont en effet une possibilité inférieure d'être vraies. Par conséquent, pour le dire de façon positive, la redondance dans les données moins possibles peut être éliminée avec un effort de normalisation moindre. En effet, pour éliminer toute la redondance dans des uplets avec un degré de possibilité a4 il suffit de normaliser par rapport à des dépendances FD qui se maintiennent avec un degré de certitude lei. Toutefois, pour 20 éliminer toute la redondance dans des uplets avec un degré de possibilité al il est nécessaire de normaliser par rapport à des dépendances FD qui se maintiennent avec un quelconque degré de certitude fla,,62,ig3 et fl4. Par conséquent, l'impact de l'incertitude sur la conception de schéma se traduit par le fait que les mises à jour plus fréquentes sont susceptibles d'être traitées efficacement avec moins d'effort de normalisation. Cela 25 signifie également que plus de requêtes peuvent être traitées de manière efficace, étant donné que moins de jointures sont requises. Par conséquent, l'incertitude se traduit par une plus grande variété de conceptions de schémas normalisées à partir desquelles les concepteurs de bases de données peuvent choisir la meilleure correspondance pour la charge de travail cible en termes de mises à jour et de requêtes. En d'autres termes, 30 l'incertitude peut être comprise comme un mécanisme efficace pour mieux contrôler le compromis classique entre efficacité des mises à jour et des requêtes. 2. Bases de données incertaines 35 La présente section examine le modèle de données possibiliste pour l'incertitude des uplets, sur lequel la structure de conception de schémas pour le système de conception de base de données est constituée. Un schéma de relations, 3024914 19 généralement désigné par R, est un ensemble fini non vide d'attributs. Chaque attribut A e R présente un domaine dom(A) de valeurs. A uplet t sur R est un élément du produit cartésien {LER dom(A) des domaines des attributs. Pour X g. R nous désignons par t(X) la projection de t sur X. Une relation sur R est un ensemble fini r d'uplets sur R. À titre d'exemple, le modèle de données sera expliqué en référence au scénario exemplaire dans lequel le schéma de relations est Réunion avec les attributs Projet, Horaire, Responsable, Salle de la section 2. Dans les relations classiques, les uplets appartiennent ou n'appartiennent pas à une relation, il n'y a pas place pour l'incertitude. Par exemple, nous ne pouvons pas 10 exprimer que nous avons moins confiance dans le fait que Bob assiste à une réunion du projet Lion mercredi à 11 heures dans la salle Cyan que dans le fait que Gill assiste à une réunion du projet Lion mercredi à 11 heures dans la salle Cyan. Toutefois, une prise en charge efficace des bases de données pour de nouvelles applications, notamment d'échange, d'extraction et d'intégration de données, exige de la part des concepteurs de 15 prendre en compte l'incertitude dans les bases de données, mais aussi de tirer le meilleur parti de ces informations supplémentaires. Les relations incertaines sont définies comme des relations où chaque uplet est associé à un niveau de confiance. Le niveau de confiance d'un uplet indique jusqu'à quel degré de possibilité un uplet se produit dans une relation. Formellement, nous 20 modélisons la confiance sous la forme d'une échelle de possibilité, c'est-à-dire un ordre linéaire strict fini S = (S, - -oe > ak > ak+1, et dont nous appelons degrés de possibilité les éléments ai E S. Le degré de possibilité le plus élevé al est réservé aux uplets dont il est « totalement possible » qu'ils se produisent dans une relation, tandis que le degré de 25 possibilité le plus faible ak+i est réservé aux uplets dont il n'est « pas possible du tout », autrement « impossible », qu'ils se produisent dans une relation. Les humains aiment utiliser des échelles simples dans la vie quotidienne, par exemple pour communiquer, comparer, ou classer. La notion « simple » renvoie généralement à un classement qualitatif des éléments, plutôt qu'à un classement quantitatif avec une valeur précise 30 annexée à ces éléments. Remarquons que les relations classiques utilisent une échelle avec deux éléments, à savoir où k = 1. Dans le scénario exemplaire, une échelle de cinq degrés de possibilité est utilisée à titre d'exemple, allant de totalement possible (a1), à plutôt possible (a2), moyennement possible (a3), peu possible (a4), et enfin à pas du tout possible (a5). 35 Un schéma de relations possibilistes (R, S) est constitué d'un schéma de relations R et d'une échelle de possibilité S. Une relation possibiliste sur (R,S) est 3024914 20 constituée d'une relation r sur R, conjointement avec une fonction Poss, qui met en concordance chaque uplet t E r sur un degré de possibilité Possr(t) dans l'échelle de possibilité S. Par exemple, le tableau 1 illustre une relation possibiliste sur (Réunion,S = ---,a5D- 5 Les relations possibilistes tirent parti d'une sémantique bien fondée en termes de mondes possibles. En effet, une relation possibiliste donne lieu à une distribution de possibilités sur des mondes possibles de relations. Pour i = 1, k, admettons que ri désigne la relation qui est constituée de tous les uplets dans r qui présentent un degré de possibilité d'au moins ai, c'est-à-dire, ri = {t E riPossr(t) ad. L'ordre linéaire des 10 degrés de possibilité se traduit par un ordre linéaire (inversé) des mondes possibles de relations. En effet, nous avons r1 r2 g --- rk. La distribution de possibilités Zr pour cette chaîne linéaire de mondes possibles est définie par Ir(r1) = ai. Remarquons que rk-Fi n'est pas considéré comme étant un monde possible, étant donné que sa possibilité 7r(rk+i) = ak+i signifie « pas du tout possible ». Inversement, la possibilité Possr(t) d'un 15 uplet t c r est la possibilité du plus petit monde possible dans lequel t se produit, c'est-à- dire, la possibilité maximale maxtailt E ri) d'un monde auquel t appartient. Si t e rk, alors Possr(t)= ak+i. Le degré de possibilité le plus élevé a1 endosse un rôle essentiel : chaque uplet qui est « totalement possible » se produit dans chaque monde possible - et est par conséquent - « totalement certain ». Cela confirme formellement que les relations 20 incertaines subsument, autrement dit incluent dans une classification, des relations (d'uplets totalement certains) en qualité de cas particulier. La figure 1 illustre les mondes possibles r1 r2 r3 ni qui résultent de la relation possibiliste du tableau 1. 3. Dépendances FD possibilistes 25 Sur la base de la structure des sections précédentes, des dépendances FD possibilistes (PFD) seront définies et décrites comme des dépendances FD classiques conjointement avec un degré de certitude. De la même manière que les dépendances FD classiques sont fondamentales pour la conception de bases de données classiques, les 30 dépendances PFD jouent un rôle fondamental dans la conception de schémas pour les données incertaines. Rappelons qu'une dépendance fonctionnelle X Y sur un schéma de relations R est satisfaite par une relation r sur R si et seulement si chaque paire d'uplets dans r qui présentent des valeurs correspondantes sur tous les attributs dans X 35 présentent également des valeurs correspondantes Sur tous les attributs dans Y. Par exemple, la dépendance FD Responsable, Salle Horaire n'est pas satisfaite par une quelconque relation ri, ...,r4. La dépendance FD Projet -> Responsable est satisfaite par 3024914 21 la relation r1, mais pas par la relation r2 et par conséquent pas par les relations r3 et r4. La dépendance FD Projet, Horaire -÷ Responsable est satisfaite par les relations r1 et r2, mais pas par la relation r3 et par conséquent pas par la relation 7-4. La dépendance FD Horaire, Salle -> Projet est satisfaite par les relations r1, r2, et r3, mais pas par la relation 5 r4. Finalement, la dépendance FD Responsable, Horaire Salle est satisfaite par toutes les relations r1,...,r4. Les degrés de possibilité d'uplets qui définissent une relation incertaine définissent également des degrés de certitude avec lesquels les dépendances FD se maintiennent dans une relation incertaine. Étant donné que la dépendance Responsable, 10 Horaire Salle est satisfaite dans chaque monde possible, elle est totalement certaine de se maintenir dans r. Étant donné que la dépendance Horaire, Salle Projet n'est enfreinte que dans un monde peu possible r4, elle est assez certaine de se maintenir dans r. Étant donné que la dépendance Projet, Horaire -> Responsable est enfreinte dans un monde moyennement possible r3 (mais pas dans un monde assez possible), elle 15 est moyennement certaine de se maintenir dans r. Étant donné que la dépendance Projet Responsable est enfreinte dans un monde assez possible r2 (mais pas dans un monde totalement possible), elle est peu certaine de se maintenir dans r. Finalement, .ètant donné que la dépendance Responsable, Salle Horaire est enfreinte dans un monde totalement possible r1, elle n'est pas du tout certaine de se maintenir dans r. 20 En résumé, la certitude avec laquelle une dépendance FD se maintient dans une relation incertaine correspond à la possibilité du monde le plus petit possible dans lequel la dépendance FD est enfreinte. Par conséquent, de manière similaire à une échelle S de degrés de possibilité pour les uplets, une échelle ST de degrés de certitude pour des dépendances FD est utilisée. Dans cet exemple, des versions indicées de la 25 lettre grecque fi sont utilisées pour désigner des degrés de certitude associés à des dépendances FD. Formellement, la correspondance entre les degrés de possibilité dans S et les degrés de certitude dans ST peut être définie par la mise en concordance ai 1--> 13k+2_i pour i = 1, k +1. La figure 2 étend l'échelle de degrés de possibilité du scénario exemplaire par une échelle de degrés de certitude, selon la mise en 30 concordance ai i-> i3k+2-i. Formellement, ensuite, la certitude Cr(X --> Y) avec laquelle la dépendance FD X -+ Y se maintient dans une relation incertaine r correspond au degré le plus élevé dès lors que X -> Y est satisfaite par rk, ou sinon le minimum parmi les degrés de certitude qui correspondent à des mondes possibles ri dans lesquels la dépendance X -> Y esteereinte, c'est-à-dire, 35 Cr (X Y) = mintflk+2-i lIrj X --> , si rk satisfait X --> Y , sinon 3024914 22 En d'autres termes : une dépendance FD est soit totalement certaine dès lors qu'elle se maintient sur le monde le plus grand possible rk, soit son degré de certitude flk+2-i correspond au monde le plus petit possible ri dans lequel elle est enfreinte. La syntaxe et la sémantique des dépendances PFD sont définies ci-après : 5 Définition 1 : Une dépendance fonctionnelle possibiliste sur un schéma de relations possibiliste (R, S) est une expression (X -> y, /3) où X,Y R et )3 E ST. Une relation possibiliste (r, Possr) sur (R, S) est considérée comme satisfaisant la dépendance fonctionnel possibiliste (X -> Y, /3) si et uniquement si Cr(X -> Y) 10 Par exemple, la relation possibiliste (r, Possr) du scénario exemplaire satisfait les dépendances fonctionnelles possibilistes ci-dessous : - Responsable, Horaire -> Salle, )31 - Salle, Horaire -> Projet, 132 15 - Projet, Horaire -> Responsable, /33 - Projet -> Responsable, P4 - Responsable, Salle -> Horaire, /35 Pour un autre exemple, elle enfreint la dépendance PFD : Projet, Horaire -> 20 Responsable, P2, étant donné que C,-(Projet, Horaire -> Responsable) = f33 Y, f3) sépare les relations possibilistes sémantiquement significatives des relations possibilistes sémantiquement non significatives en autorisant les infractions, ou violations, de la dépendance FD X -> Y 25 uniquement par des uplets avec un degré de possibilité ai où j k + 1 - i. Pour i = 1, k, le degré de certitude fi i de (X -> Y, Pi) signifie que la dépendance FD classique X -> Y doit se maintenir dans le monde possible rk+i_i. Ceci constitue un mécanisme flexible pratique pour appliquer le niveau ciblé d'intégrité des données de manière efficace. 30 Comme motivation pour les sections futures, il convient de souligner l'impact des dépendances PFD sur la redondance de données. Étant donné que les dépendances PFD avec différents degrés de certitude ne s'appliquent pas aux mêmes mondes, elles peuvent également occasionner différents degrés de redondance de données. En effet, la redondance de données ne peut se produire que dans des mondes auxquels une 35 dépendance PFD donnée s'applique. Cette observation permettra d'alléger l'effort de normalisation lors de l'élimination de la redondance de données des mondes moins 3024914 23 possibles, sur lesquels seules des dépendances FD plus certaines se maintiennent. 4. Théorie de conception mise à l'échelle 5 Les algorithmes de normalisation classiques comme la décomposition BCNF et la synthèse 3NF sont fondés sur la théorie des dépendances FD classiques. Par conséquent, le système et procédé de conception de bases de données repose sur l'établissement d'une théorie de conception de dépendances PFD. En partant d'une correspondance robuste entre le problème d'implication des dépendances PFD et celui 10 des dépendences FD classiques, une axiomatisation pour des dépendances PFD est identifiée laquelle constitue une réminiscence des axiomes d'Armstrong pour les dépendances FD, et cela montre que le problème d'implication associé peut être déterminé linéairement dans le temps dans l'entrée. Comme les applications, dans ce qui suit, un algorithme est examiné qui déduit le degré de certitude le plus élevé avec lequel 15 une dépendance FD donnée est impliquée par un ensemble donné de dépendances PFD, ainsi que le calcul de couvertures non redondantes et canoniques. 5.1 L'utilisation de fractions-fi 20 Tout d'abord, une correspondance robuste entre l'implication des dépendances PFD et FD est examinée. Admettons que E u (yo} désigne un ensemble de dépendances PFD sur un schéma de relations possibilistes (R, S). E suppose y o , désigné par E ço, si chaque relation possibiliste (r, Possr) sur (R, S) qui satisfait chaque dépendance PFD dans E satisfait également yo. E* = [(PIE (p) est utilisé pour désigner la clôture 25 sémantique de E. Exemple 1 Admettons que I se compose des quatre dépendances PFD suivantes (Responsable, Horaire Salle, pl), (Salle, Horaire Projet, 02), (Projet, Horaire Responsable, P3), (Projet --+ Responsable, 134 sur (Réunion (a1,...,a5)). En outre, 30 admettons que cp désigne la dépendance PFD (Salle, Horaire --+ Projet, p2). Alors I ne suppose pas cp en tant que les témoins de relations possibilistes suivantes : Projet Horaire Responsable Salle Degré de possibilité Lion Mercredi, 15h Gill Cyan ai Lion Mercredi, 15h Robert Cyan a3 3024914 24 Pour un ensemble E de dépendances PFD sur un certain schéma de relations possibiliste (R, S) et un certain degré de certitude 13 e ST où 13 > flk+i, admettons que = [X -> Y I(X -> Y, f3') E E and [and = et] soit la fraction f3 de E. Le principal atout de la structure de conception de bases de données est gravé dans le résultat suivant. Théorème 1 : Admettons que X u ((X -> Y, i3)) soit un ensemble de dépendances PFD sur un schéma de relations possibilistes (R, S) où 13 > )31,1_1. Alors I (X --> Y,13) si et 10 seulement si Efl X -> Y. Preuve : Supposons que (r,Possr) représente une certaine relation possibiliste sur (R,S) qui satisfait E, mais qui enfreint (X -> Y , fl). En particulier, Cr(X -> Y) Y et où 15 Mc+2-1 V E Efl, où (U --> V, e) E E. Étant donné que r satisfait (U -> V ,13') e E nous avons Cr(U V) (2) Si ri enfreint U -> V, alors 13 > f3+ by (1) 20 Cr(U -> V) by Dffinition of Cr by (2) est une contradiction. Par conséquent, la relation ri satisfait E13 et enfreint X -> Y. [by = par ; by definition of = par définition de] Admettons que r' désigne une certaine relation qui satisfait Eu et enfreint X -> Y. Il est supposé que r' = ft, t') ne se compose que de deux uplets. Si tel n'es pas le cas, alors on 25 sait qu'il y a une sous-relation de r' avec deux uplets qui satisfait Efl et enfreint X -> Y. Admettons que r soit la relation possibiliste sur (R, S) qui se compose de la relation r' et où Possr,(t) = al et Possr,(e) = ai, de sorte que fi'k±i_i = fi. Alors r enfreint (X Y, )3) étant donné que Cr(X --> Y)R = puisque ri = r' est la plus petite relation qui enfreint X -> Y, et f?k+2-i V, f3') E E, deux cas peuvent être distingués. Si 30 ri satisfait U -> V, alors Cr(U -> V) = ie. Si ri enfreint U -> V, alors U -> V e autrement dit, V. Nous concluons que Cr(U -> V) > fl'. Par conséquent, (r,Possr) est une relation possibiliste qui satisfait E et enfreint (X -4 3024914 25 Exemple 2: Admettons que E et yo soient comme dans l'exemple 1, en particulier I n'implique pas cp. Le théorème 1 indique que E2 n'implique pas Salle, Horaire 5 Responsable. En effet, la relation Projet Horaire Responsable Salle Lion Mercredi, 15h Gill Cyan Lion Mercredi, 15h Robert Cyan satisfait les deux dépendances FD classiques Responsable, Horaire -+ Salle et Salle, Horaire -> Projet qui forment If32, et enfreint la dépendance FD Salle, Horaire 10 Responsable. Remarquons en quoi cette relation est le monde possible r3 de la relation possibiliste de l'exemple I. 5.2 Axiomes d'Armstrong mis à l'échelle 15 Afin de déterminer la clôture sémantique, il est possible d'utiliser une approche syntaxique en appliquant des règles d'inférence de la forme prémisse condition, conclusion où les règles sans prémisse sont appelées des axiomes. Pour un ensemble 9t de règles d'inférence, admettons que E ep désigne l'inférence de cp à partir de E par R. Par 20 conséquent, il existe une certaine séquence a ---, de sorte que un = ço et chaque ui est un élément de E ou est la conclusion qui résulte d'une application d'une règle d'inférence dans 9i à certaines prémisses dans {oà, Admettons que E,'"î - (q. I E cp) désigne la clôture syntaxique de E en vertu d'inférences par R. 9I est sûr (complet) si pour chaque relation possibiliste (R,S) et pour chaque ensemble E nous 25 avons 4-i E* (E* 4). L'ensemble (fini) 9t est considéré comme étant une axiomatisation (finie) si 9î est à la fois sûr et complet. Un des premiers résultats bien connus de la théorie des bases de données relationnelles concerne les axiomes d'Armstrong dont Armstrong a montré qu'ils étaient sûrs, autrement dit robustes ou solides, et complets pour l'implication des dépendances 30 FD. Les axiomes sont illustrés dans le tableau 2. 3024914 26 Tableau 2 : Axionns d'Armstrong 91 = , , T'} des dépendances FD Les dépendances FD possibilistes tirent parti d'une axiomatisation similaire, résumée dans le tableau 3, tel que cela sera illustré par la suite. Dans ces règles, il est implicitement supposé que tous les ensembles d'attributs X, Y, Z sont des sous-ensembles du schéma de relations donné arbitrairement R et que les degrés de certitude ie et Je' sont des éléments de l'échelle de certitude donnée arbitrairement ST. En particulier, /3k+1 désigne le degré de certitude le plus faible. Remarquons que le système 13 est équivalent 10 aux axiomes d'Armstrong pour les dépendances FD, si l'échelle ST n'est composée que de deux degrés de certitude. Tableau 3 : Axiomatisation 13 = {R, E, T, W} de dépendances PFD 15 Théorème 2: L'ensemble 13 = [R, £,T,73,112) de règles d'inférence forme une axiomatisation finie pour l'implication de dépendances fonctionnelles possibilistes. -> Y XY -> Y X --> XY (réflEkivité, R') (Ektffision, E') X -* Y Y -> Z X Z (transitivité, T') (X -> Y, je) (XY -> Y, /3) (X -> XY , fi) (réfl Decivité, R) (Bannsion, E) (X -> Y , fl) (Y Z , fl) (X Z , jq) (transitivité, T) (X --> Y, f3) Je' Y, e) (affaiblissnnEht,W) (X -* (fond, D) Preuve : Les preuves de solidité sont basées sur le fait de garder à l'esprit la solidité des 3024914 27 axiomes d'Armstrong pour les dépendances FD et le théorème 1. Pour la preuve d'exhaustivité, le meilleur parti est tiré du théorème 1 et du fait que les axiomes d'Armstrong sont sûrs et complets pour l'implication des dépendances FD. Admettons que (R, S) soit un schéma de relations possibilistes arbitraire avec S = k + 1, et E u [(X -4 5 Y, f3)} un ensemble arbitraire de dépendances PFD sur le schéma, de sorte que Ei= (X -> Y, fi') se maintient. Il doit être montré que E 1-13 (X -4 Y, fi) se maintient également. Deux cas peuvent être distingués. Si = k+1, alors E (X -> Y,13) signifie que E 13(X -> Y, ,e) se maintient par une unique application de la règle de fond B. Pour le reste de la preuve, il peut donc être supposé que iq Y par le théorème 1. Étant donné que les axiomes d'Armstrong 91 sont complets pour l'implication des dépendances FD, il peut être conclu que Ep 2IX -> Y se maintient. À présent, pour l'ensemble de dépendances FD Efi, nous définissons 4 = ((X Y, 16)IX -> Y EEO. Par conséquent, l'inférence de X -> Y à partir de Efi. en utilisant les axiomes d'Armstrong peut être transformée en une inférence de 15 (X -> Y, je) à partir de 4par 13, en ajoutant le degré de certitude fi à chaque dépendance FD qui se produit dans l'inférence. Par conséquent, dès lors qu'un axiome d'Armstrong E' ou est appliqué, la règle correspondante R, E, ou T, peut être appliquée, respectivement. Il s'ensuit que Ee _> Y , fi') se maintient. Finalement, la définition de EP garantit que chaque dépendance PFD dans re peut être déduite d'une dépendance 20 PFD dans E par une unique application de la règle d'affaiblissement W. Par conséquent, Efl 1-13 (X -> Y, fi) signifie, en particulier, E 13(X -> Y , 13). Ceci complète la preuve. Alternativement, la définition des dépendances PFD aurait pu être limitée à des degrés de certitude qui sont différents du degré le plus faible. Dans ce cas, l'axiome inférieur 23 n'est pas nécessaire. Ici, il a été décidé d'inclure le degré le plus faible pour 25 affecter à chaque dépendance FD un certain degré de certitude. Exemple 3 Admettons que X et (p soient comme dans l'exemple 1, et (p' = (Salle, Horaire -> Responsable, p3). Une inférence de (p' à partir de X par ¶3 peut être montrée. Les noms d'attributs sont abrégés par leurs premières lettres. (RT --> P, )32) W: (RT 30 E: (RT -> RT P, fl3) 1?: (RT P -> PT , fl3) T: (RT -> PT , )63) (PT -> M , ,G3) T: (RT -> M , 133) 3024914 28 Certes, (p ne peut pas être déduit à partir de E par 13, comme l'exemple 1 et la solidité de 13 le montrent. 5 5.3 Algorithme de décision mis à l'échelle En pratique, il n'est souvent pas nécessaire de calculer l'ensemble complet E* de contraintes d'intégrité impliqué par un ensemble donné E. En revanche, le problème selon lequel pour un ensemble donné E u [(p) de contraintes d'intégrité, E suppose (p est 10 assez fréquent. Une option consiste à calculer E* et à vérifier si (p E E*, mais ceci n'est guère efficace et ne fait pas un usage effiCace de l'entrée (p. Dans le cas de dépendances PFD, 15 le théorème 1 peut à nouveau être exploité pour dériver un algorithme qui détermine le problème d'implication linéairement dans le temps dans l'entrée. Étant donné un ensemble de dépendances PFD E u [(X -> Y,13)}, vrai est renvoyé siiecalculantino nil suffit de vérifier si Eft X --> Y. Ce dernier test peut être fait en temps linéaire sinon la clôture d'ensemble d'attributs X4,= fil E RIE 1-21X -> A) de X par rapport à E. 20 L'algorithme 1 calcule la clôture d'ensemble d'attributs dans le temps 0(11Ef311 +1)(1). ilEil désigne le nombre total d'occurrences d'attributs dans E, et 1X1 désigne la cardinalité de X, que E soit un ensemble de dépendances PFD ou de dépendances FD. PROBLÈME: IMPLICATION ENTRÉE: Schéma de relations R, SORTIE: Échelle S avec k + 1 degrés de possibilité, Ensemble E u [(p) de dépendances PFD sur (R,S) Oui, si E yo, et non autrement Algorithme 1 Calcul de clôture proceduce Closure(R, X, Ep) Closure Y e Efl; repeat OldClosure Closure; Remove Closure from LHS of FDs in FDList; for all 0 --> Yin FDList do Closure 4- Closure u Y; FDList FDList - (0 -) Y); end for until Closure=01dClosure or FDList-[] return(Closure); end procedure 1 : 2: 3: 4: 5: 6: 7: 8: 9: 10: 11 : 12: 13: 3024914 29 [Closure = Clôture ; old = ancienne] Par conséquent, la caractérisation algorithmique suivante du problème d'implication pour les dépendances PFD est obtenue. Théorème 3 : Le problème d'implication E yo de dépendances FD possibilistes peut être déterminé dans le temps (2(11£ U t(p)IF). Exemple 4 : Admettons que I et q) soient comme dans l'exemple 1, et 9' = (Salle, Horaire 10 Responsable, p3) s'ensuit que Cp n'est pas impliquée par I étant donné que Clôture(Réunion, RT,I2)= RTP. En outre, (p' est impliquée parE étant donné que Clôture(Réunion, RT, L;q3)= RTPM. 5.4 Inférence de certitude 15 Du point de vue de l'incertitude, le problème suivant est intéressant : Étant donné un ensemble E de dépendances PFD sur le schéma (R,S) et une dépendance FD X -> Y sur R, quel est le degré de certitude maximum je e ST de sorte que Ei= (X -4 Y, f3) se maintient ? 20 25 Une approche pour résoudre le problème d'inférence consiste à calculer des clôtures d'ensembles d'attributs de X progressivement en ajoutant des dépendances FD à 30 partir de Efli, , - Efli, jusqu'à ce que Y Ç XiEpi pour le plus petit i, ou Y g . Dans le premier cas, nous retournons f3i, dans le dernier cas fik.".. L'algorithme pk devrait uniquement être appliqué à des indices i pour lesquels une dépendance PFD -> V, f3) E E existe. PROBLÈME: INFÉRENCE ENTRÉE: Schéma de relations R, SORTIE: Échelle S avec k + 1 degrés de possibilité, Ensemble E de dépendances PFD sur (R,S), Dépendance FD X -4 Y sur R max[f3 E ST IE (X -> Y , fl)) 35 Théorème 4: Le problème d'inférence pour les dépendances PFD avec l'entrée E u {X --> 3024914 30 Y} peut être calculé dans le temps 0(11X1] + IX u YI). Exemple 5 : Admettons que I soit comme dans l'exemple 1. Alors le degré de certitude maximum je pour lequel la dépendance FD (RT -> M, fi) est impliquée par .1' est fl3. 5 6.5 Calcul de couvertures Du point de vue des contraintes d'intégrité, la notion d'une couverture intègre une quantité minimale de ressources nécessaire pour faire appliquer les règles 10 commerciales qui ont été identifiées afin qu'elles soient sémantiquement significatives pour un domaine d'application. Les notions standards de couvertures s'appliquent aux dépendances PFD également. Un ensemble 0 de dépendances PFD est une couverture d'un ensemble E dépendances PFD si 0-'. = E-'.. Une couverture 0 est dite non redondante, si pour chaque dépendance PFD a e 0, u e (0 - fcr});. 0 est dite réduite par 15 L, si pour chaque (X -> e E et pour tous Z c X, (Z -> Y,fi) e0. Une couverture 0 est dite canonique, si 0 est non-redondante, réduite par L, et s'il n'existe pas deux différents (X --> Y, fi), (X -> Z, fi) e O. En exploitant l'algorithme 1, les deux algorithmes suivants calculent des couvertures non redondantes et canoniques, respectivement. Sans perte de généralité, il est supposé que l'entrée E au niveau des deux algorithmes est 20 exclusivement constituée de dépendances PFD (X -> Y, fi) où Y = A désigne un attribut à ensemble unitaire, ou singleton, du schéma de relations sous-jacent. Algorithme 2 Couverture non-redondante 1: procedure NR-Cover(R,E) 2: for all = (X --> A, fl) E E do 3: if A E ClosureER, X, (E - (0-Dp) then 4: 5: end if 6: end for 7: return(E); 8: end procedure [Closure = Clôture] 25 Bien que les couvertures non redondantes éliminent les dépendances PFD redondantes, les couvertures canoniques éliminent également les attributs redondants. Dans l'algorithme ci-dessous, il est important d'éliminer tout d'abord les attributs redondants, avant d'éliminer les dépendances PFD redondantes. Cette séquence d'étapes est déjà établie dans le cas classique. 30 3024914 31 [Cover = Couverture] Théorème 5: Sur l'entrée (R, E), l'algorithme 2 calcule une couverture non-redondante de I dans le temps 0(111112), et l'algorithme 3 calcule une couverture canonique de E dans le 5 temps 0(IRI x 111112). Exemple 6 : Examinons le schéma de relations Réunion avec l'ensemble suivant I de dépendances PFD xi1 = (Responsable, Horaire Salle, pi), a2 = (Responsable, Horaire, Salle -> Projet, Pl), et o-3 = (Responsable, Horaire Projet, 02). Une couverture non- 10 redondante de I correspond à l'ensemble 0 = (0-1,021 tandis qu'une couverture canonique de E correspond à l'ensemble e' = «Responsable, Horaire -> Salle, Projet, /3/». 155. Formes normales mises à l'échelle Dans les bases de données relationnelles classiques, la forme normale de Boyce-Codd (BCNF) caractérise syntaxiquement les schémas de relations qui sont garantis comme étant libres ou exempts de toute redondance de données dans des 20 relations quelconques sur le schéma, en termes de dépendances fonctionnelles. La troisième forme normale (3NF) caractérise syntaxiquement des schémas de relations qui sont garantis comme ayant la quantité la plus faible de redondance des données dans leurs relations parmi tous les schémas sur lesquels toutes les dépendances fonctionnelles peuvent être appliquées localement. Dans les bases de données relationnelles Algorithme 3 Couverture canonique procedure Can-Cover(R,E) for all 0- = (X -> A, 16) E E do Z A, fi)); end for E NR - Cover(R, while (X -> Y, (X -> Z, 13) E E do E E - [(X -> Y , j3), (X -> Z , ie)); E E [(X -> YZ, je)); end while return(E); end procedure 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:- 14: 15: 16: 17: 3024914 32 classiques, tous les uplets sont totalement certains et toutes les dépendances fonctionnelles sémantiquement significatives s'appliquent à toutes les données. Ainsi, dans les bases de données relationnelles classiques, la redondance des données est traitée uniformément pour toutes les données, et l'élimination de la totalité de la 5 redondance de données requiert une normalisation à l'égard de toutes les dépendances fonctionnelles. Dans les relations possibilistes utilisées dans ce procédé et système de conception de bases de données, différentes données peuvent se produire avec différents degrés de possibilité, et différentes dépendances FD possibilistes peuvent s'appliquer à 10 différentes données. Par conséquent, une redondance de données peut se produire avec différents degrés de possibilité. Plus le degré de possibilité pour lequel la redondance de données doit être éliminée est faible, plus l'effort de normalisation sera allégé. Dans la présente section seront examinées des notions de redondance de données qui sont adaptées au degré de possibilité d'uplets dans lesquels elles se produisent. Cela se 15 traduit par une plage complète de formes normales sémantiques moyennant quoi les redondances de données de degrés de possibilité croissants sont éliminées. Nous caractérisons ensuite chacune de ces formes normales sémantiques par une forme normale syntaxique correspondante, et nous établissons une correspondance robuste avec la forme BCNF dans des bases de données relationnelles. En outre, nous adaptons 20 la troisième forme normale, 3NF, à des bases de données possibilistes. 6.1 Redondance de données mise à l'échelle Le concept de notions de redondance de données mise à l'échelle sera décrit 25 à l'égard du scénario exemplaire. Supposons que nous est donné le schéma de relations possibilistes Réunion avec l'ensemble E de dépendances PFD provenant de l'exemple 1. Supposons que nous savons que la relation possibiliste (r,Possr) dans la figure 3 satisfait E, mais que nous ne pouvons pas voir toutes ses occurrences de valeurs de données. Étant donné que r satisfait E, le point d'interrogation dans r4 ne saurait représenter toute 30 valeur de données différente de Lava - étant donné que toute autre valeur de données enfreindrait la dépendance PFD (Horaire, Responsable Salle, pi). Par conséquent, l'occurrence de valeur de données de Lava dans le dernier uplet est redondante dans le sens qu'elle peut être déduite des autres occurrences de valeurs de données et des dépendances PFD données. Plus précisément, la valeur de données est redondante 35 relativement à a4 étant donné qu'elle se produit dans le monde possible r4 et ne peut donc être occasionnée que par des dépendances PFD qui se maintiennent avec le degré 3024914 33 de certitude fil. Le point d'interrogation dans r3 ne peut être remplacé que par la valeur de données redondante Lion, occasionnée par la dépendance PFD (Horaire, Salle -> Projet, f32). La valeur de données est redondante relativement à a3, et pourrait être occasionnée par toute dépendance PFD dans E avec le degré de certitude f3 ou /32. Enfin, le point 5 d'interrogation dans r1 représente l'occurrence de valeur de données redondante de Gill, occasionnée par la dépendance PFD (Projet -> Responsable, f34). Cette occurrence est redondante relativement à al, et pourrait être occasionnée par toute dépendance PFD dans E - dont toutes s'appliquent aux uplets avec le degré de possibilité ai.. Le concept des différentes notions de redondance de données qui sont 10 adaptées à l'incertitude des uplets sera à présent examiné. Pour cela, une proposition classique est exploitée. Admettons que R désigne un schéma de relations, A désigne un attribut de R, t désigne un uplet sur R, et E désigne un ensemble de dépendances FD sur R. Un remplacement de t(A) correspond à un uplet E sur R qui satisfait aux conditions suivantes : i) pour tous les À E R - [A} nous avons i(À) = t(À), et ii) i(A) t(A). Pour 15 une relation r sur R qui satisfait E et t e r, l'occurrence de valeur de données t(A) dans r est redondante relativement à E si et seulement si pour chaque remplacement E de t(A), f:= (r - {t}) u ti) enfreint certaines dépendances FD dans E. Un schéma de relations R est dans une forme normale sans redondance (RFNF) à l'égard d'un ensemble E de dépendances FD si et seulement si il n'existe pas de relation r sur R qui satisfait E, l'uplet 20 t e r, et l'attribut A e R, de sorte que l'occurrence de valeur de données t(A) est redondante relativement à E. Définition 2: Admettons que (R, S) désigne un schéma de relations possibilistes, désigne un ensemble de dépendances PFD sur (R, S), A e R désigne un attribut, 25 (r,Possr) désigne une relation possibiliste sur (R, S) qui satisfait E, et t désigne un uplet dans ri. L'occurrence de valeur de données t(A) est redondante relativement à ai si et seulement si t(A) est redondante relativement à Eqi = [X -> YI(X -> Y, fl) E E et ig Jek+1-i) .*. Cette définition répond à l'intuition selon laquelle une redondance de données 30 a été dérivée du scénario exemplaire. En particulier, les occurrences de Lava, Lion, et Gill sont redondantes relativement à azi, a3 et al, respectivement. Plus important encore, les occurrences de valeurs de données redondantes relativement à ai ne peuvent être occasionnées que par des dépendances PFD (X -> Y,fl) qui s'appliquent au monde de l'occurrence, c'est-à-dire lorsque /3 Par conséquent, la redondance relativement 35 à ai peut être occasionnée par des dépendances -PFD avec un quelconque degré de 3024914 34 certitude dans /31, ...,flk, tandis que la redondance relativement à ak ne peut être occasionnée que par des dépendances PFD avec le degré de certitude fil. Nous en venons à présent à la définition des formes normales sémantiques suivantes. 5 Définition 3: Un schéma de relations possibilistes (R,S) est dans une forme normale sans redondance relativement à ai en ce qui concerne un ensemble I de dépendances PFD sur (R,S) si et seulement si il n'existe pas de relation possibiliste (r,Possr) sur (R,S) qui satisfait I, un attribut A E R, et un uplet t E ri de sorte que t(A) est redondante relativement à ai. 10 (Réunion, Ô) n'est pas dans la forme de type « a4-RFNF », « a3-RFNF », ni « al-RFNF », mais est dans la forme « a2-RFNF » relativement à E. Les résultats négatifs découlent immédiatement de la figure 2 ci-dessus, mais la satisfaction de la condition de type « a2- RFNF » n'est pas évidente. Le résultat suivant montre que « ai-RFNF » caractérise des 15 schémas possibilistes qui permettent précisément ces relations possibilistes dont le monde possible ri est garanti comme étant exempt de redondance de données occasionnée par les dépendances FD classiques qui s'y appliquent. Théorème 6: (R,S) est dans la forme de type « ai-RFNF » relativement à L' si et 20 seulement si R est dans la forme RFNF relativement à xai. Preuve : Nous illustrons tout d'abord le point suivant : si (R,S) n'est pas dans la forme de type « ai-RFNF » relativement à E, alors R n'est pas dans la forme RFNF relativement à E. Selon notre hypothèse, il existe une certaine relation possibiliste (r,Possr) sur (R,S) 25 qui satisfait E, un attribut A e R, et un uplet t e ri de sorte que t(A) est redondante à l'égard de E. En particulier, il s'ensuit que ri satisfait Eat étant donné que r satisfait E. Par conséquent, R n'est pas dans la forme RFNF en ce qui concerne Eau Nous illustrons à présent le point suivant : si R n'est pas dans la forme RFNF 30 relativement à Eai, alors (R,S) n'est pas dans la forme « ai-RFNF » relativement à E. Selon notre hypothèse, il existe une certaine relation ri sur R qui satisfait Zay et certains t e ri et A e R de sorte que t(A) est redondante à l'égard de Eai. En particulier, ri doit contenir un uplet t1 # t. Nous étendons à présent la relation ri à une relation possibiliste (r,Possr) en définissant Possr(ti) = al et Possr(e) = ai pour la totalité des t' c r1 - {ta 35 Nous montrons que r satisfait E. Si (U -> e E est dans Eai, alors Cr(U -> V) = )611 3024914 35 Si (U -> V, f3) e sa' alors fi V, alors Cr(U --> V) /3. Si ri enfreint U -> V, alors Cr(U --> V)R = ,k+2-i 13. Étant donné que t(A) est redondante relativement à ai nous avons montré que (R,S) n'est pas dans la forme ai-RFNF en ce qui concerne E. 5 6.2 Forme BCNF mise à l'échelle Nous caractérisons à présent la forme normale sans redondance a, laquelle est une forme normale sémantique, d'un point de vue purement syntaxique. Ceci est 10 réalisé par une mise à l'échelle de la condition BCNF classique. Rappelons qu'un schéma de relations R est dans la forme normale de Boyce-Codd (BCNF) à l'égard d'un ensemble E de dépendances FD sur R si et seulement si pour tous les X --* Y eEit' où y e x, nous avons X -> R e 4. Nous allons également montrer que la définition de la forme BCNF mise à l'échelle est indépendante de la représentation des dépendances PFD et peut être 15 contrôlée efficacement. Alors que la forme a-RFNF est définie en termes de sémantique dans le monde possible avec le degré de possibilité a, la forme BCNF mise à l'échelle est définie en termes de syntaxe des dépendances PFD données avec leurs degrés de certitude. 20 Définition 4: Un schéma de relations possibilistes (R,S) est dans la forme normale de Boyce-Codd ,61 à l'égard d'un ensemble L' de dépendances PFD sur (R,S) si et seulement si pour chaque dépendance PFD (X -> Y, 13) E E-1+3- où Y e X, nous avons (X -> RJ3) e E. Remarquons que la propriété en ce qui concerne le fait d'être du type «/3BCNF » relativement à E est indépendante de la représentation de E. En effet, pour toute 25 couverture E' de E, (R,S) est du type « fi-BCNF » relativement à E si et seulement si (R,S) est du type « 13-BCNF » relativement à E'. De la même façon le type « a-RFNF » à l'égard d'un ensemble de dépendances PFD E pourrait être caractérisé par la forme RFNF à l'égard de l'ensemble de dépendances FD Ea, le type « /3-BCNF » à l'égard d'un ensemble de dépendances PFD E peut être caractérisé par la forme BCNF à l'égard de 30 l'ensemble de dépendances FD E. Théorème 7: (R,S) est dans la forme de type « /3-BCNF » relativement à un ensemble I si et seulement si R est dans la forme BCNF relativement à E. 35 Preuve : Par définition, (R,S) est dans la forme de type « f3-BCNF » relativement à un 3024914 36 ensemble E si et seulement si pour chaque dépendance PFD (X -> Y, je) e Er1+3' et Y ex nous avons (X -> R,,e) E E. Sous l'effet du théorème 2, cette dernière condition revient à dire que pour chaque dépendance PFD (X -> Y, fi) qui est impliquée par E et Y e X, la dépendance PFD (X -> R, fl) est impliquée par E également. Selon le théorème 1, cette 5 énoncé revient à dire que pour chaque dépendance FD X -> Y qui est impliquée par Eft et ye X, la dépendance FDX -> R est impliquée par Ep également. En raison de l'exhaustivité des axiomes d'Armstrong pour l'implication des dépendances FD, cet + , énoncé revient à dire que pour chaque dépendance FD X -> Y e (E19)21 ou Y e X, nous avons X -> R E (Efi,),I+ également. Le dernier énoncé, toutefois, revient à dire que R est 10 dans la forme BCNF à l'égard de Ep.. Nous pouvons à présent caractériser la forme RFNF-ai sémantique par la forme f3ki_i_i-BCNF syntaxique. Théorème 8: Pour tous les i = 1, k, (R,S) avec 'SI = k + 1 est dans la forme ai-15 RFNF relativement à I si et seulement si (R,S) est dans la forme igki_l_i-BCNF relativement à X. Preuve : Selon le théorème 6, (R,S) est dans la forme ai-RFNF relativement à E si et seulement si R est dans la forme RFNF relativement à Eau Étant donné que Eal 20 et étant donné que les formes RFNF et BCNF coïncident dans les bases de données relationnelles, le dernier énoncé revient à dire que R est dans la forme BCNF_ relativement à Toutefois, ce dernier énoncé revient à dire que (R,S) est dans la forme de type « iek+1_i-BCNF » relativement à E, selon le théorème 7. 25 Le tableau 4 illustre les correspondances entre les formes normales syntaxiques et sémantiques, et leurs relations aux formes normales classiques. Tableau 4: Relations entre les formes normales E194 - BCNF /34-BCNF a1-RFNF .=> - RFNF Eft, - BCNF a3 - RFNF .=> Ea3 - RF1VF E191- BCNF .=> f3i - BCNF a4 - RFNF E24 - RFNF 30 En raison de l'insensibilité aux couvertures de la condition /3-BCNF, il peut être souhaitable d'examiner l'efficacité s'agissant de contrôler si un schéma de relations 3024914 37 possibilistes donné (R,S) est dans la forme [3-BCNF relativement à un ensemble E. En effet, comme dans le cas classique, il suffit de contrôler certaines dépendances PFD dans E au lieu de contrôler toutes les dépendances PFD dans E. 5 Théorème 9: Un schéma de relations possibilistes (R,S) est dans la forme iq-BCNF à l'égard d'un ensemble X de dépendances PFD sur (R,S) si et seulement si pour chaque dépendance PFD (X --> Y, je') E I où e [3 et Y e X, nous avons (X -> R, e X. Preuve : Selon le théorème 7, (R,S) est dans la forme 13-BCNF relativement à E si et 10 seulement si R est dans la forme BCNF relativement à Efi . Toutefois, cette dernière condition est bien connue en ce qu'elle revient à contrôler pour chaque dépendance FD ,+ X -> Y E Eig où Y e X que X --*R ,6.)21. La condition que X --+ Y e E,e revient à dire que ,+ (X -4 Y,e) e E pour fl' ie. Enfin, la condition X -> R E (Ep) revient à dire que (X -> R, e) e Ei3' pour ,6' fl, selon le théorème 2 et le théorème 1. 15 Exemple 7 : Admettons que (Réunion, 6) et X soient comme dans l'exemple 1. En faisant appel au théorème 9, nous pouvons observer que le schéma n'est ni dans la forme de type « ,81-BCNF », ni dans la forme de type « f2 -BCNF », ni dans la forme de type « f3BCNF » relativement à I, mais il est dans la forme de type « [33-BCNF » en ce qui 20 concerne X. Selon le théorème 8, nous concluons que le schéma n'est ni dans la forme de type « a4-RFNF », ni dans la forme de type « a3-RFNF », ni dans la forme de type « al-RFNF » à l'égard de X, mais il est dans la forme de type « a2-RFNF » relativement à X. Selon le théorème 7, il s'ensuit que Réunion n'est ni dans la forme BCNF relativement à X, ni dans la forme Is2, ni dans la forme Xp4, mais est dans la forme BCNF relativement 25 à %. Enfin, selon le théorème 6, il s'ensuit que Réunion n'est ni dans la forme RFNF relativement à 44, ni dans la forme X',, ni dans la forme L'ai, mais est dans la forme RFNF relativement à 4,2. 6.3 Troisième forme normale mise à l'échelle 30 De manière similaire à la forme BCNF 6', nous présentons à présent la troisième forme normale fl (3NF). L'objectif de cette forme normale est similaire à celui de son homologue classique : 3NF garantit que toutes les dépendances fonctionnelles peuvent être appliquées localement, sans qu'il soit nécessaire de relier les relations en 35 vue de vérifier la cohérence des mises à jour. _Ce point sera examiné plus en détail dans 3024914 38 la section suivante. Rappelons la condition 3NF à partir de bases de données relationnelles : un schéma de relations R est dans la forme 3NF à l'égard d'un ensemble donné E de dépendances FD si et seulement si pour chaque dépendance FD X --> A e Lj où Ae X, 5 nous avons X --> R E Ej ou si A est un attribut premier. Un attribut A est premier si et seulement si il se produit dans une certaine clé minimale en ce qui concerne E. Un sous-ensemble d'attributs X de R est une clé de R à l'égard de E si et seulement si X -> R e Ei/E. La clé X de R est minimale en ce qui concerne E si et seulement si chaque sous-ensemble d'attributs propre Y de X n'est pas une clé de R en ce qui concerne E. 10 Nous présentons à présent des concepts analogues pour les bases de données possibilistes. Étant donné un schéma de relations possibilistes (R, S), un degré de certitude f? e ST, et un ensemble E de dépendances PFD sur (R, S), un sous-ensemble d'attributs X de R est considéré comme étant une clé fi de R à l'égard de E si et seulement si (X R, j3) e E. Une clé f3 X de R relativement à E est une clé minimale 13 si et 15 seulement si chaque sous-ensemble d'attributs propre Y de X n'est pas une clé ,51 de R relativement à E. Un attribut A e R est considéré comme étant premier je si et seulement si il est contenu dans une certaine clé minimale fl X de R relativement à E. Définition 5 : Un schéma de relations possibilistes (R,S) est dans la troisième forme 20 normale (3NF) fi relativement à un ensemble I de dépendances PFD sur (R,S) si et seulement si pour chaque dépendance PFD (X -4 A, fl) e /'3- où A e X, nous avons (X -> R,ig) E Ei3F ou si A est un attribut premier Le théorème 7 a caractérisé la forme BCNF ,G à l'égard de l'ensemble de *dépendances PFD E en termes de forme BCNF classique relativement à la fraction-,e E. 25 Un résultat analogue est valable pour 3NF. Théorème 10 : (R,S) est dans la forme 13-3NF relativement à un ensemble I si et seulement si R est dans la forme 3NF relativement à E. 30 Preuve : Le théorème 1 garantit que (X -> Y , ie) E EiF3. si et seulement si X -> Y e (E02/. En particulier, X est une clé (minimale) je de R à l'égard de E si et seulement si X est une clé (minimale) de R relativement à E. . De même, en raison de l'insensibilité aux couvertures de la condition 3NF je, il peut être souhaitable d'examiner « l'efficacité » s'agissant de contrôler si un schéma de 35 relations possibilistes donné (R,S) est dans la forme ,6-3NF relativement à un ensemble 3024914 39 E. En effet, comme dans le cas classique, il suffit de contrôler certaines dépendances PFD dans E au lieu de contrôler toutes les dépendances PFD dans E-113". 5 Théorème 11 : Un schéma de relations possibilistes (R, S) est dans la forme 3NF relativement à un ensemble I de dépendances PFD sur (R, S) Si et seulement si pour chaque dépendance PFD (X -> Y, je') E I où e ig et Y X, nous avons (X -> R,13) E L'i3E ou si chaque attribut A E Y-X est un attribut premier 10 Preuve Un schéma de relations R est dans la forme 3NF à l'égard d'un ensemble de dépendances FD Efl si et seulement si pour chaque dépendance FD X --> Y E Efl où ye X, nous avons X -> R E (E,g)i ou si chaque attribut A e Y-X est premier. Le théorème découle à présent du théorème 1. 15 Exemple 8 : Admettons que (Réunion, ô) et I soient comme dans l'exemple 1. En faisant appel au théorème 11 nous pouvons observer que le schéma n'est ni dans la forme « ,g1- 3NF », ni dans la forme « f32-3NF » relativement à E, mais il est dans la forme « f33-3NF » et dans la forme « ,84-3NF » relativement à I. Enfin, selon le théorème 10, il s'ensuit que Réunion n'est ni dans la forme 3NF en ce qui concerne lui ni en ce qui concerne 20 mais est dans la forme 3NF à l'égard de Ef3 et dans la forme 3NF à l'égard de I. 6. Normalisation mise à l'échelle 25 Dans cette section, les moyens algorithmiques qui sous-tendent le système et procédé de conception de bases de données pour la conception de schémas de bases de données relationnelles pour des applications avec des données incertaines sont décrits. À titre d'exemple, la normalisation d'un schéma de relations possibilistes donné (R,S) à l'égard de l'ensemble donné E de dépendances PFD sera décrite. Le système et procédé 30 de conception de bases de données est exploitable de manière à définir un degré de certitude 13 E ST qui détermine quels mondes possibles sont normalisés à l'égard de quelles dépendances FD. Dans une configuration exemplaire, les décompositions BCtIF sont employées en vue d'obtenir des décompositions sans perte, exemptes de toute redondance des données, mais où certaines dépendances FD peuvent nécessiter une 35 validation par la jonction de certaines relations. Dans une autre configuration exemplaire, la synthèse 3NF est employée en vue d'obtenir des décompositions sans perte sur 3024914 lesquelles toutes les dépendances FD peuvent être validées sans joindre de relations (c'est-à-dire une décomposition avec conservation des dépendances), et où le niveau de redondance des données est minimal en ce qui concerne des quelconques décompositions qui conservent les dépendances. La capacité du système de conception 5 des bases de données à appliquer les algorithmes à différents degrés de certitude offre aux concepteurs de bases de données et aux organisations une échelle complète de schémas de bases de données normalisées, chacun ciblé sur différents degrés d'intégrité des données, sur l'efficacité des différentes mises à jour, et sur l'efficacité des différentes requêtes. 10 7.1 Décomposition de forme BCNF mise à l'échelle Nous rappelons la terminologie de base des bases de données relationnelles. Une décomposition de schéma de relations R correspond à un ensemble D = [R1, ..., Rn} 15 de schémas de relations de sorte que R1 u ..- u R = R. Pour Ri g R et l'ensemble de dépendances FD E sur R, E[Ri] = (X -> YIX -> Y E EiFi and X,Y Ri) désigne la projection de E sur R. Une décomposition D d'un schéma de relations R avec un ensemble de dépendances FD est appelée E sans perte si et seulement si chaque relation r sur R qui satisfait E est la jointure de ses projections sur les éléments de D, 20 c'est-à-dire r =Exl R .ED r[Ri]. Ici, r[R1] = ft(Ri)It e r). Une décomposition de forme BCNF d'un schéma de relations R avec un ensemble de dépendances FD E correspond à une décomposition D de R où chaque Ri E D est dans la forme BCNF en ce qui concerne E[Ri]. Le théorème 7 motive la définition 6. 25 Définition 6: Une décomposition de forme BCNF sans perte d'un schéma de relations possibilistes (R, S) relativement à l'ensemble de dépendances PFD X est une décomposition de forme BCNF sans perte de R relativement à Le théorème de décomposition ci-après contribue à la définition 6. 11 généralise le théorème de décomposition classique pour les dépendances FD, qui est 30 couvert par le théorème 12 comme le cas spécial où seul un monde possible est disponible. Théorème 12 : Admettons que (X -> YA) soit une dépendance PFD qui satisfait la relation possibiliste (r, Possr) sur le schéma de relations possibilistes (R, S). Alors 35 rk+l-i rk-Fi-1[XY1 N rk+l-i[X (R n], 3024914 41 à savoir, le monde possible rk+i_i de r est la jointure sans perte de sa projection sur XY et X (R - Y). Par conséquent, une décomposition de forme BCNF sans perte f3 à l'égard d'un ensemble de dépendances PFD E peut être obtenue en mettant en oeuvre une 5 décomposition de forme BCNF sans perte classique à l'égard de la fraction fi Ep de E. Cela suggère une stratégie de décomposition de forme BCNF sans perte. Le processus de décomposition est décrit plus en détail ci-dessous en 10 référence au scénario exemplaire. Exemple 9: Admettons que (Réunion, Ô) et soient comme dans l'exemple 1. Étant donné que (Réunion, Ô) n'est pas dans la forme ,62-BCNF relativement à I, nous mettons en oeuvre une décomposition de forme BCNF sans perte '32. Le résultat se compose de 15 R1= {Projet, Salle, Horaire} avec un ensemble de dépendances FD projeté Ep2[R1]= {Salle, Horaire -> Projet}, et R2= {Responsable, Salle, Horaire} avec l'ensemble de dépendances FD projeté L2[R2] = {Responsable, Horaire -> Salle} Remarquons que chaque dépendance FD Eiq, est impliquée par Ep2 [R1] U Efl2 [RA. 20 La situation dans le dernier exemple et assez particulière. En effet, on ne peut pas espérer conserver toutes les dépendances FD dans le processus de décomposition de forme BCNF. Ceci est illustré par un autre cas sur le scénario exemplaire. 25 Exemple 10: Admettons que (Réunion, ô) et I soient comme dans l'exemple 1. Étant donné que (Réunion, Ô) n'est pas dans la forme ,64-BCNF relativement à I, nous mettons en oeuvre une décomposition de forme BCNF sans perte ,6'4. Le résultat est R1 Décomposition de forme BCNF mise à l'échelle PROBLÈME ENTRÉE: Schéma de relations possibilistes (R, S) Ensemble E de dépendances PFD sur (R, S) Degré de certitude ie E ST SORTIE: fi- décomposition de forme BCNF sans perte de (R, S) relativement à E PROCÉDÉ Mettre en oeuvre une décomposition de forme BCNF sans perte de R relativement à Ep 3024914 42 {Responsable, Projet} avec un ensemble de dépendances FD projeté Eim[R1]= {Projet -> Responsable} et R2= {Projet, Salle, Horaire} avec l'ensemble de dépendances FD projeté E,34[R2] = {Salle, Horaire -+ Projet ; Projet, Horaire -> Salle} Remarquons que la dépendance FD Responsable, Horaire Salle n'est pas impliquée par E,q4[R1] u Ep4[R2]. Une décomposition D de schéma de relations R avec un ensemble de dépendances FD E offre une conservation de dépendances si et seulement si EI 10 (uR.ev Définition 7 : Une décomposition avec conservation de dépendances d'un schéma de relations possibilistes (R, S) relativement à l'ensemble de dépendances PFD X est une décomposition avec conservation de dépendances de R relativement à E. 15 La décomposition de forme 132-BCNF sans perte issue de l'exemple 9 offre une conservation des dépendances 162, mais la décomposition de forme J34-BCNF sans perte issue de l'exemple 9 n'offre pas de conservation des dépendances En effet, pour (Réunion, ô) et E comme dans l'exemple 1, il n'y a pas de décomposition de forme BCNF sans perte avec conservation des dépendances )614 de E. Dans la pratique, les 20 dépendances perdues ne peuvent être validées qu'en joignant les relations après des insertions ou modifications. Par exemple, pour valider la dépendance FD Responsable, Horaire Salle après une mise à jour, il conviendrait de joindre R1 et R2 de l'exemple 10. 7.2 Synthèse 3NF mise à l'échelle 25 La synthèse 3NF garantit la conservation des dépendances, mais ne peut pas garantir l'élimination de la totalité de la redondance des données en termes de dépendances FD. Récemment, une structure théorique d'information a été élaborée pour fournir une justification formelle pour la troisième forme normale en montrant qu'elle paie 30 le plus petit prix possible, en termes de redondance des données, pour atteindre une conservation des dépendances. Pour ces raisons, le système de conception de bases de données est configuré avec une stratégie de synthèse 3NF exploitable. Une décomposition 3NF d'un schéma de relations R relativement à un ensemble de dépendances FD E correspond à une décomposition D de R où chaque 35 Rj E D est dans la forme 3NF en ce qui concerne E[Ri]. Le théorème 10 motive la 3024914 43 définition ci-dessous. Définition 8: Une décomposition 3NF avec conservation des dépendances fl sans perte ,61 d'un schéma de relations possibilistes (R, S) relativement à l'ensemble de dépendances PFD X est une décomposition 3NF sans perte avec conservation des dépendances de R relativement à E. Sous l'effet du théorème 12, une synthèse 3NF avec conservation des dépendances fl, sans perte relativement à un ensemble de dépendances E, peut être obtenue en mettant en oeuvre une synthèse 3NF sans perte avec conservation des 10 dépendances classique relativement à la fraction fi Efl de E. PROBLÈME: Synthèse 3NF mise à l'échelle ENTRÉE: Schéma de relations possibilistes (R, S) Ensemble E de dépendances PFD sur (R, S) Degré-de certitude je E ST SORTIE: fiDécomposition 3NF sans perte fl avec conservation des dépendances de (R, S) relativement à E PROCÉDÉ: Mettre en oeuvre une synthèse 3NF sans perte avec conservation des dépendances de R à l'égard de Ep Le processus de synthèse est décrit plus en détail ci-dessous en référence au scénario exemplaire. 15 Exemple 11 : Admettons que (Réunion, ô) et X soient comme dans l'exemple 1. Étant donné que (Réunion, Ô) n'est pas dans la forme ,e2-3NF relativement à X, nous mettons en oeuvre une synthèse 3NF avec conservation des dépendances ig2, sans perte fl2. Le résultat se compose de R1= {Projet, Salle, Horaire] avec un ensemble de dépendances 20 FD projeté E/32[Ri] = {Salle, Horaire Projet} et Ri= {Responsable, Salle, Horaire] avec l'ensemble de dépendances FD projeté Ep2[R2] = {Responsable, Horaire Remarquons que R1 est dans la forme BCNF relativement à E192 [R1], et R2 est dans la 25 forme BCNF relativement à E192 [R2], comme nous l'avons déjà vu dans l'exemple 9. Généralement, le summum qu'un concepteur de bases de données peut espérer est une décomposition de forme BCNF sans perte avec conservation des dépendances. En général, il existe deux approches consistant à : mettre en oeuvre une décomposition de forme BCNF sans perte en espérant qu'elle offre une conservation des 3024914 44 dépendances, ou mettre en oeuvre une synthèse 3NF avec conservation des dépendances en espérant que tous les schémas sont réellement dans la forme BCNF. La question de savoir quelle approche offre la meilleure chance de réussite sera abordée ultérieurement dans la section 9 avec des preuves empiriques générées à partir de 5 diverses expériences. 7. Exemple de système de conception de bases de données avec une interface utilisateur graphique (GUI) 10 Un mode de réalisation exemplaire du système de conception de bases de données sera à présent décrit. Système et procédé de conception de bases de données - algorithme de 15 normalisation mise à l'échelle Le processus général 50 pour un utilisateur, par exemple un concepteur de bases de données et/ou une organisation, utilisant la structure de conception de bases de données du système et procédé de conception de bases de données sera à présent 20 décrit plus en détail en référence à l'organigramme de la figure 5. Premièrement, la structure de conception de bases de données comprend des degrés de possibilité qui modélisent l'incertitude avec laquelle des uplets se produisent dans la base de données, tel que cela est illustré à l'étape 52. Une organisation choisit une échelle de possibilité qui contient un nombre de degrés de possibilité différents qu'elle 25 peut associer à des uplets dans la base de données. Les degrés sont totalement ordonnés, du degré le plus élevé, désigné par al, au degré le plus faible, désigné par ak+1 , où k 1. Les degrés peuvent être associés à la signification qualitative, par exemple al pourrait se voir affecter l'étiquette qualitative « totalement possible » et 0k.,1 pourrait se voir affecter l'étiquette qualitative « impossible ». L'organisation peut choisir un nombre fini 30 arbitraire de degrés intermédiaires : cil> az > > Ce choix dépend du nombre de degrés différents que l'organisation souhaite affecter aux uplets. L'échelle de possibilité permet à l'organisation de modéliser des données dans différentes couches : pour i=1,...,k, la lème couche contient des uplets avec le degré de possibilité a, où j 5 j. Deuxièmement, la structure de conception de bases de données comprend 35 des degrés de certitude qui modélisent la Certitude avec laquelle les dépendances fonctionnelles sont satisfaites. Une organisation peut utiliser les degrés de possibilité pour affecter à chaque dépendance fonctionnelle un degré de certitude f3, moyennant quoi la dépendance fonctionnelle est satisfaite par les données tel que cela est illustré à l'étape 3024914 54. Ici, i désigne un nombre entier compris entre 1 et k+/ à nouveau. Une dépendance fonctionnelle se voit affecter le degré de certitude [3; lorsqu'elle se maintient sur la (k+1- i)1' couche tel que cela est illustré à l'étape 56. Par exemple, une dépendance fonctionnelle avec le degré de certitude le plus élevep, se maintient sur la kième couche, à 5 savoir la couche la plus élevée. Il est par conséquent possible d'associer une étiquette qualitative à pl, par exemple « totalement certain ». Une dépendance fonctionnelle avec le degré de certitude le plus faible pk.,, ne se maintient même pas sur le ler niveau, le niveau le plus bas. Cela suggère une étiquette qualitative telle que « pas du tout certain ». 10 Troisièmement, la structure de conception de bases de données comprend des algorithmes pour normaliser les schémas de bases de données par rapport à un ensemble de dépendances fonctionnelles avec des degrés de certitude. Pour chaque i=1,..., k, un ensemble I; est défini lequel se compose de ces dépendances fonctionnelles qui présentent le degré de certitude p, où j i tel que cela est représenté à l'étape 58. Le 15 processus comprend ensuite l'application d'un ou plusieurs algorithmes de normalisation classiques quelconques à l'ensemble d'attributs donné (par exemple, des noms de champs) et tout ensemble I, pour i=1,...,k tel que cela est représenté à l'étape 60. Par exemple, des algorithmes tels que la décomposition de forme normale de Boyce-Codd classique ou la synthèse de troisième forme normale et leurs variantes peuvent être 20 appliqués. Le résultat de l'application de ces algorithmes est une gamme de conceptions de schémas de base de données à choisir, chaque conception différente étant générée sur la base d'un ensemble distinct de dépendances fonctionnelles 2, appliquées aux algorithmes. Le choix sera influencé par plusieurs facteurs, par exemple, la performance des requêtes cibles et des mises à jour cibles sur le schéma tel que cela est représenté à 25 l'étape 62. Chacun des schémas générés est doté de certaines garanties de qualité. Par exemple, un schéma de forme normale de Boyce-Codd généré pour I, caractérise ces schémas qui sont exempts d'occurrences de redondance des données dans des uplets avec un degré de possibilité cri où j k+1-i. Un schéma de troisième forme normale généré pour Z conserve toujours toutes les dépendances fonctionnelles avec un degré de 30 certitude où j 5 i. Exemple - entrées et sorties d'algorithme de normalisation mise à l'échelle À titre d'exemple, une application des algorithmes de normalisation mise à 35 l'échelle sous-tendant la structure de conception de bases de données sera décrite ultérieurement en référence aux figures 6, 7A, et 7B. Dans cette application exemplaire 3024914 46 70 représentée dans la figure 6, le processus est configuré de manière à générer une plage de conceptions de schémas de base de données pour un schéma de relations pour une plage de différents ensembles de dépendances fonctionnelles 2,, en appliquant chaque ensemble, respectivement, à une décomposition de forme BCNF en vue de 5 générer un ensemble de conceptions et à une décomposition 3NF en vue de générer un autre ensemble de conceptions. Après l'initiation 72, des données d'entrée 74 indicatives de ce qui suit sont reçues ou récupérées : - Schéma de relations R 10 - Échelle S - ...,flk,14+1) de degrés de certitude où ,31 > ig2 > --- >13k > [4+1 - Ensemble E de dépendances fonctionnelles possibilistes (X -) Y, f3) sur (R,S) - Ensemble d'index I g_(1, ..., k) L'algorithme met ensuite en oeuvre ce qui suit : Pour chaque i e I: 15 1. Calculer la fraction j3i Ei: = (X -> YI(X -> Y, jej)eEnlji} de l'ensemble donné E de dépendances fonctionnelles possibilistes tel que cela est représenté à l'étape 76, 2. Mettre en oeuvre une décomposition de forme normale de Boyce-Codd classique avec l'entrée R et Ei et désigner la sortie BCNF(R,Ei) tel que cela est représenté à l'étape 20 78, et 3. Mettre en oeuvre une décomposition de troisième forme normale classique avec l'entrée R et Ei et désigner la sortie 3NF(R,Ei) tel que cela est représenté à l'étape. Les étapes 1-3 de cycles ou boucles d'algorithme ci-dessus incrémentent le compteur j de un à chaque cycle tel que cela est représenté à l'étape 82, jusqu'à ce que 25 j=k tel que cela est représenté à l'étape 84, après quoi le traitement d'algorithme se termine à l'étape 86. A la fin du traitement, l'algorithme génère en sortie des données indicatives de : - Pour chaque i e I, une décomposition de forme normale de Boyce-Codd sans perte BCNF(R,Ei) de R par rapport à la fraction-f3 i Ei de E 30 Pour chaque i e I, une décomposition de troisième forme normale sans perte avec conservation des dépendances 3NF(R,Ei) de R par rapport à la fraction-f3 i Ei de E Dans ce processus, les garanties de qualité suivantes sont fournies : BCNF(R,Ei) se traduit toujours par des conceptions de schémas qui permettent des instances de bases de données qui sont garanties comme étant exemptes 35 de toute redondance des données dans des uplets avec un degré de possibilité cri où j 3024914 47 3NF(R,Ei) se traduit toujours par des conceptions de schémas qui sont garanties de présenter la plus petite quantité de redondance de données dans des uplets avec un degré de possibilité apj k + 1 - i parmi toutes les conceptions de schémas qui conservent toutes les dépendances fonctionnelles dans Ei En référence à la figure 7A, un exemple du nombre de schémas (tableaux) générés pour chaque conception est tracé en fonction du degré de certitude de l'ensemble de dépendances fonctionnelles Ei appliquées pour générer cette conception, comparant les sorties de conception de forme BCNF aux sorties 3NF. Dans cet exemple, K = 15. Ici : plus la taille (à savoir le nombre de schémas) est élevée, plus il y aura de 10 mises à jour prises en charge de manière efficace et moins il y aura de requêtes, et inversement ; et plus le degré de certitude est élevé, plus l'intégrité des données sera optimale. En référence à la figure 7B, un autre exemple des sorties qui peuvent être générées par le système de conception de base de données en utilisant une 15 normalisation mise à l'échelle est illustré en utilisant la décomposition 3NF appliquée à une entrée de schéma de relations exemplaire théorique et un ensemble de dépendances fonctionnelles. La taille de la décomposition 120 sur l'axe Y est tracée en fonction du degré de certitude de l'ensemble de dépendances fonctionnelles Ei sur l'axe X, en fonction de quoi le schéma de relations d'entrée est normalisé. En particulier, l'axe X 20 représente, pour chaque i=1,...,k, un ensemble Z qui se compose de ces dépendances fonctionnelles qui présentent un degré de certitude pi où j i. L'entrée de commande 124 démontre que le niveau de normalisation mise à l'échelle peut être contrôlé par le concepteur de bases de données selon ses paramètres de conception. Dans cet exemple, l'entrée de commande 124 se présente sous la forme d'un cadran fonctionnel, 25 mais il est entendu que tout autre moyen d'interface utilisateur, d'échelle, d'entrée ou de commande peut être utilisé pour contrôler ou sélectionner le niveau de normalisation mise à l'échelle appliqué à un schéma de relations d'entrée. Dans cet exemple, l'entrée de commande spécifie le degré de certitude associé à l'ensemble de dépendances fonctionnelles Ei sur lequel le schéma de relations d'entrée est normalisé. Au niveau 30 d'une extrémité de l'échelle sur l'axe X, le schéma de relations d'entrée est normalisé par rapport à un ensemble de dépendances fonctionnelles Ei qui comprend toutes les dépendances fonctionnelles présentant le degré de certitude le plus élevé, c'est-à-dire « totalement certain », pi. Lorsque cela est sélectionné, la taille de la décomposition, c'est-à-dire le nombre de tableaux dans les schémas de relations est indiqué(e) à l'étape 126. 35 En revanche, à l'autre extrémité de l'échelle de l'axe X, où le schéma de relations d'entrée est normalisé par rapport à toutes les dépendances fonctionnelles Ek ce qui inclut toutes 3024914 48 les dépendances fonctionnelles présentant un quelconque degré de certitude, du plus élevé au plus faible, la taille de la décomposition est tracée à l'étape 128. Dans cet exemple, lorsque l'entrée de commande El est sélectionnée par la base de données conçue, la normalisation mise à l'échelle génère une décomposition plus petite 126 5 (autrement dit moins de tableaux) qui se matérialise par une efficacité plus élevée en termes de traitement des requêtes, mais aussi par une efficacité moindre en termes de traitement des mises à jour, et également un niveau plus faible d'intégrité des données, par rapport à la sélection de l'entrée de commande Ek. Lorsque l'entrée de commande Ek est sélectionnée, la décomposition 128 se traduit par une décomposition plus grande 10 (c'est-à-dire plus de tableaux), qui se matérialise par une efficacité plus élevée en termes de mises à jour, mais également par un efficacité moins élevée en termes de requêtes, et en outre par un niveau plus élevé d'intégrité des données. Les tracés intermédiaires 130 représentent la sortie de normalisation mise à l'échelle pour des entrées de commande sélectionnées entre les deux extrêmes Ei et Ek. L'entrée de commande 124, dans ce cas, 15 peut être considérée comme représentant une valeur ou métrique de cohérence qui détermine à quel ensemble de dépendances fonctionnelles la normalisation mise à l'échelle sera appliquée, et par conséquent les schémas de relations de sortie générés ne chercheront qu'à éviter la redondance des données par rapport à, ou en accord avec, cet ensemble de dépendances fonctionnelles. Dans ce cas, où la valeur de cohérence est la 20 plus faible, par exemple si elle se situe à l'extrémité Ei de l'échelle, la redondance des données associée aux schémas de relations de sortie générés est compatible uniquement avec l'ensemble de dépendances fonctionnelles El. . Alors que, dans le cas d'une valeur de cohérence supérieure au niveau de l'autre extrémité, par exemple Ek, les schémas de relations de sortie générés présentent une redondance de données qui est compatible 25 avec toutes les dépendances fonctionnelles. Tel que cela a été illustré, le concepteur de bases de données peut utiliser l'entrée de commande pour sélectionner une conception de schémas de bases de données de sortie qui corresponde à ses besoins spécifiques en termes d'efficacité des requêtes, d'efficacité des mises à jour et d'intégrité des données, et il peut comparer les avantages et bénéfices des conceptions contrastantes. 30 Configuration matérielle Dans un mode de réalisation, à titre d'exemple uniquement, le système de conception de base de données peut être fourni sous la forme d'instructions programmables ou de logiciels qui sont exécutés par un dispositif programmable, tel qu'un 35 ordinateur ou un autre matériel programmable, et il peut être exploité par un concepteur de bases de données ou un autre utilisateur par l'intermédiaire d'une interface utilisateur 3024914 49 graphique (GUI). La figure 4 illustre un exemple de la configuration matérielle ou du système 10, tel qu'un ordinateur personnel, sur laquelle/lequel le système de conception de bases de données 10 peut fonctionner. Le système 10 comprend un processeur 12 ou des processeurs, par exemple une unité centrale de traitement, un microprocesseur, un 5 microcontrôleur ou un élément similaire, pour exécuter des instructions programmables et une mémoire associée 14. Une interface utilisateur 16 est fournie, laquelle peut être de la forme d'un ou plusieurs des composants parmi une souris, un clavier, une surface tactile, un écran tactile ou tout autre dispositif d'interface utilisateur approprié. Un écran d'affichage 18 est également fourni sur lequel l'interface GUI interactive peut être 10 présentée à l'utilisateur. Un ou plusieurs modules de communication 20 et une ou plusieurs interfaces de dispositifs externes 22 peuvent également être fournis pour permettre la communication de données avec des réseaux ou des dispositifs externes. Dans d'autres modes de réalisation, le système de conception de bases de données peut être exécuté par un serveur ou un serveur « cloud » qui est accessible sur un réseau de 15 données, par exemple Internet ou une autre liaison de communication de données. Dans ces modes de réalisation, l'utilisateur peut accéder et exploiter le système sur le serveur par l'intermédiaire d'un navigateur Internet qui fournit une interface GUI de site web ou d'un autre programme d'application qui fournit l'interface GUI. 20 Interface GUI de site web À titre d'exemple uniquement, le fonctionnement du système de conception de bases de données, dans ce mode de réalisation, sera décrit en référence à une interface GUI de site web. En référence à la figure 8, l'écran principal 90 de l'interface GUI est illustré, lequel présente trois options ou fonctions principales pouvant être sélectionnées 25 par l'utilisateur, nommément : Une normalisation classique 92, une normalisation mise à l'échelle 94 et des expérimentations mises à l'échelle 96, dont chacune est expliquée plus en détail ci-dessous. Normalisation classique 30 Dans le cadre de la normalisation classique 94, un utilisateur peut entrer un schéma de relations et un ensemble de dépendances FD. Plusieurs algorithmes peuvent être appliqués à cette entrée et à une entrée supplémentaire. En ce qui concerne les décompositions de forme BCNF, l'utilisateur peut choisir parmi l'algorithme standard, l'algorithme en temps polynomial, et une variation de ce dernier qui calcule la projection 35 d'ensembles de dépendances FD d'origine sur les schémas de sortie finaux uniquement. Pour la synthèse 3NF, un utilisateur peut décider si l'algorithme doit être appliqué par 3024914 rapport à une couverture canonique comme précédemment (option : LHS unique), ou à l'égard de couvertures non redondantes, réduites par L, dans lesquelles chaque dépendance FD présente un seul attribut sur le côté droit (option : Expansé). Un utilisateur peut également choisir de calculer simplement l'une de ces couvertures pour un 5 ensemble de dépendances FD donné, de calculer l'ensemble de toutes les clés minimales, de calculer la projection de l'ensemble de dépendances FD donné ou la clôture d'ensembles d'attributs d'un autre sous-ensemble d'attributs à préciser du schéma donné. En outre, un utilisateur peut également générer des données d'entrée randomisées pour lesquelles il peut spécifier la taille souhaitée. 10 Normalisation mise à l'échelle Dans le cadre de la normalisation mise à l'échelle 94, des versions mises à l'échelle de tous les algorithmes ci-dessus peuvent être appliquées à un ensemble de dépendances PFD sur un schéma de relations possibilistes et un sous-ensemble 15 d'attributs facultatif, tel que spécifié par un utilisateur ou généré de manière aléatoire par l'interface GUI. En particulier, l'utilisateur peut spécifier une échelle de degrés de certitude sous la forme d'entiers positifs, et ceux-ci peut être affectés à des dépendances FD pour obtenir des dépendances PFD. Dès lors que l'utilisateur spécifie un degré de certitude (sous Index d'échelle), l'interface GUI applique la version mise à l'échelle d'un algorithme 20 avec ce degré de certitude. Si l'utilisateur ne spécifie pas de degré de certitude, la même sortie est retournée tel que dans le cas des algorithmes classiques. En outre, les utilisateurs peuvent également appliquer les algorithmes suivants : couvertures canoniques possibilistes, inférence de certitude, clôture de dépendances FD, et décisions d'implications. 25 À titre d'illustration, la figure 9 illustre une partie de l'interface utilisateur 100 disponible sous Normalisation mise à l'échelle 94. L'utilisateur entre des données indicatives du schéma de relations R à l'étape 102, l'échelle de degrés de certitude S = ftk, fik+1.) à l'étape 104, et l'ensemble E de dépendances fonctionnelles possibilistes (X --> Y,M) sur (R,S) à l'étape 106. L'utilisateur sélectionne ensuite 30 l'algorithme de décomposition souhaité à l'étape 108 à partir d'une liste d'algorithmes, et une entrée d'index d'échelle souhaitée à l'étape 110. L'index d'échelle détermine la fraction- f3i Ei de E, c'est-à-dire l'ensemble de dépendances fonctionnelles à l'égard duquel le schéma de relations sera normalisé tel que décrit précédemment. Divers exemples d'entrée de données et de sortie de données à partir de 35 l'interface de Normalisation mise à l'échelle 100 seront à présent décrits à titre d'exemple en référence aux figures 10-13. 3024914 51 La figure 10 illustre les données d'entrée pour la décomposition de forme ,g2- BCNF tirée de l'exemple 9, entrées par l'utilisateur dans l'interface GUI à l'étape 100a, et les données de sortie résultantes 110a indicatives du schéma de relations de sortie à l'égard de la fraction-f31 Ei de E. Dans cet exemple, le schéma de relations de sortie normalisé comprenant deux tableaux R1 et R2 est illustré à l'étape 112a, ainsi que les dépendances fonctionnelles à l'égard desquelles le schéma de relations a été normalisé. Des données 114a indiquant qu'aucune dépendance n'a été perdue sont également présentées. La figure 11 est similaire à la figure 10, mais illustre l'entrée 100b et la sortie 10 110b pour une décomposition de forme f33-BCNF, y compris le schéma de relations de sortie normalisé comprenant le tableau R à l'étape 112b. Des données 114b indiquant qu'aucune dépendance n'a été perdue sont également présentées. La figure 12 est similaire à la figure 10, mais illustre l'entrée 100c et la sortie 110c pour une décomposition de forme « f34-BCNF » tirée de l'exemple 10, y compris le 15 schéma de relations de sortie normalisé comprenant deux tableaux RI et R2 tel que représenté à l'étape 112c. Des données 114c indiquant qu'une dépendance a été perdue sont également présentées. La figure 13 est similaire à la figure 10, mais illustre l'entrée 110d et la sortie 100d pour une synthèse de type « /34-3NF », y compris le schéma de relations de sortie 20 normalisé comprenant un tableau R, comparé aux deux tableaux générés par la décomposition de forme BCNF avec la même entrée dans la figure 12. Expérimentations mises à l'échelle Dans le cadre des Expérimentations mises à l'échelle 96, l'interface GUI offre 25 la possibilité de lancer des expérimentations avec les algorithmes du système de conception de base de données. Dans une configuration, les paramètres doivent être spécifiés avant que les expérimentations puissent être exécutées. Ils incluent le paramètre m, qui spécifie le nombre d'exécutions à mettre en oeuvre, le paramètre n, qui spécifie la taille du schéma à générer et peut être une plage de valeurs min: max, le 30 paramètre I, qui spécifie la cardinalité de l'échelle à utiliser et peut être une plage min: max de valeurs, et un accélérateur d'ensembles de dépendances FD, un nombre a qui détermine la taille maximale a - n d'un ensemble de dépendances FD à générer. Les expérimentations disponibles incluent : les décompositions, les clôtures d'ensembles de dépendances FD, les décisions d'implications, les inférences, et les couvertures. Des 35 exemples d'expérimentations seront examinés ci-après. 3024914 52 8. Expérimentations Dans la présente section, l'analyse des résultats d'expérimentations en ce qui 5 concerne les versions mises à l'échelle de décompositions de forme BCNF et synthèses 3NF, les problèmes d'implications et d'inférences de dépendances PFD, ainsi que le calcul de couvertures, est examinée, en référence aux figures 14-20. 9.1 Normalisation 10 L'analyse de base concerne les compromis entre l'élimination de la redondance des données obtenue par les décompositions de forme BCNF et la conservation de dépendances FD obtenue par les synthèses 3NF, ainsi qu'entre l'efficacité des requêtes et des mises à jour. La mesure générale la plus simple pour 15 l'efficacité des requêtes et des mises à jour d'une décomposition est le nombre de ses schémas - dont il est ici fait référence en tant que taille de la décomposition. Plus une décomposition contient de schémas, plus elle peut prendre en charge efficacement les mises à jour et moins elle peut prendre en charge efficacement les requêtes. En particulier, moins il y a de schémas et moins les jointures sont nécessaires, ce qui 20 constitue la principale source de complexité dans l'évaluation des requêtes. La structure du système de conception de base de données permet d'analyser les résultats sous différents angles : L'effort de normalisation peut être mesuré soit d'un point de vue classique, dans la taille de l'ensemble de dépendances FD d'entrée, soit d'un point de vue mis à l'échelle, dans le degré de certitude donné. L'analyse ci-dessous peut être lue avec 25 les deux points de vue à l'esprit. Dans le cadre de l'analyse, cinq algorithmes de normalisation sont comparés : BCNF(1) représente l'algorithme de décomposition de forme BCNF classique qui fait appel à l'espace et au temps exponentiels, BCNF(2) représente l'algorithme en temps polynomial de Tsou et Fischer, BCNF(3) représente la variante de l'algorithme BCNF(2), 30 où la projection d'ensembles de dépendances FD d'origine est déterminée uniquement pour les schémas de sortie, 3NF(1) représente l'algorithme de synthèse 3NF qui calcule tout d'abord une couverture non-redondante réduite par L dans laquelle tous les dépendances FD ont un attribut singleton sur le côté droit, et 3NF(2) représente l'algorithme de synthèse 3NF qui calcule tout d'abord une couverture canonique, tel que 35 défini précédemment. La figure 14 illustre les graphiques de quatre expérimentations. Pour chacun parmi 15 degrés de certitude )31, ... As, 5 000 ensembles de tout au plus ci-n 3024914 53 dépendances PFD sur un schéma de relations avec n attributs ont été créés, et des décompositions de forme /3-BCNF et des synthèses f3.-3NF ont été créées, en utilisant nos 5 algorithmes. La rangée supérieure montre les graphiques où n = 10 avec a = 1 sur la gauche et a = 5 sur la droite. La rangée inférieure montre les graphiques où n = 15 5 avec a = 1 sur la gauche et a = 5 sur la droite. Les quatre expérimentations distinctes montrent des résultats presque uniformes : La décomposition dont la taille est la plus faible est BCNF(1), suivie des BCNF(2, 3), qui concordent, suivie de 3NF(2), et ensuite de 3NF(1). Les résultats montrent que la synthèse 3NF produit plus de schémas afin de contenir ou loger la 10 conservation de toutes les dépendances fonctionnelles, sacrifiant ainsi l'élimination d'une certaine redondance des données. Les graphiques montrent le prix pour la production d'une décomposition de forme BCNF en temps polynomial, qui résulte du fait de ne pas avoir à vérifier la condition BCNF de résultats intermédiaires, et produisant par conséquent des schémas superflus non requis par BCNF(1). Il est intéressant que ce prix 15 soit encore principalement inférieur à celui à payer pour inclure ou loger une conservation des dépendances. Cependant, il sera plus tard observé que les schèmes superflus dans BCNF(2, 3) sont peu susceptibles d'aider à une conservation des dépendances. Enfin, 3NF(2) génère moins de schémas que 3NF(1) étant donné qu'une couverture canonique contient moins de dépendances FD que l'autre couverture considérée. La différence entre 20 BCNF(1) et 3NF(2) nous indique combien d'autres schémas sont nécessaires en vue de garantir la conservation des dépendances. Les résultats suggèrent de privilégier la décomposition de forme BCNF en termes d'efficacité des requêtes et en termes d'élimination de la redondance des données. Ils ne veulent cependant certainement pas dire qu'il convient de privilégier la décomposition de forme BCNF en ce qui concerne 25 l'efficacité des mises à jour. En effet, les décompositions de forme BCNF sont uniquement plus efficaces pour les mises à jour d'occurrences de valeurs de données redondantes occasionnées par les dépendances FD conservées lors de la décomposition, tandis que les inefficacités de mises à jour résultent du fait qu'il est nécessaire de réaliser des jointures de schémas pour valider les dépendances FD qui n'ont pas été conservées. 30 Les quatre graphiques montrent en outre que plus la taille du schéma de relations d'entrée est élevée, plus la taille de la décomposition le sera également - si l'on observe la colonne des graphiques sur la gauche et celle sur la droite. Cependant, il en est autrement en ce qui concerne la croissance de la taille des dépendances FD - si l'on observe chaque rangée de gauche à droite. Lorsqu'il y a à peu près autant de 35 dépendances FD données que d'attributs sous-jacents, la taille moyenne des décompositions augmente linéairement. Lorsqu'il y a beaucoup plus de dépendances FD 3024914 54 données que d'attributs sous-jacents, un maximum global est observable en ce qui concerne la taille moyenne des décompositions. Ceci s'explique par le fait qu'à un moment il y aura suffisamment de dépendances FD qui transforment les ensembles d'attributs en clés, auquel cas des décompositions supplémentaires deviendront inutiles. Ce point de saturation intervient plus tôt pour BCNF(1) que pour tous les autres algorithmes considérés. Pour les ensembles de dépendances FD plus grands, des niveaux supérieurs d'intégrité des données atteignent les mêmes niveaux d'efficacité des requêtes que des niveaux d'intégrité des données significativement inférieurs. La figure 15 montre les durées ou temps moyens pour générer les 10 décompositions pour les quatre expérimentations. Tel que cela est observé à l'égard de la taille moyenne des décompositions, les quatre expérimentations différentes donnent des résultats à peu près uniformes en ce qui concerne les temps moyens : L'algorithme BCNF(2) nécessite le moins de temps, suivi de BCNF(3), suivi de BCNF(1), et enfin de 3NF (1, 2). L'algorithme BCNF(2) montre son principal atout par rapport aux autres 15 algorithmes, avec un temps moyen maximum de 8 ms pour a = 1 et de 13 ms pour a = 5. L'algorithme BCNF(3) nécessite un peu plus de temps, avec un temps moyen maximum de 12 ms pour a = 1 et de 35 ms pour a = 5, résultant des projections des ensembles de dépendances FD d'origine sur les schémas de sortie finaux à la fin. L'algorithme BCNF(1) nécessite plus de temps, avec un temps moyen maximum de 630 ms pour a = 1 et de 20 627 ms pour a = 5, résultant des projections des ensembles de dépendances FD d'origine sur tous les schémas intermédiaires et finaux. Enfin, l'algorithme 3NF (1, 2) nécessite beaucoup plus de temps, avec un temps moyen maximum de 64 s pour a = 1 et de 530 s pour a = 5. Deux observations principales illustrent les compromis inhérents. Pour les 25 décompositions de forme BCNF tout d'abord, les décompositions de plus petite taille sont obtenues au prix d'un temps plus important requis pour leur génération. En d'autres termes, les décompositions de forme BCNF en temps polynomial résultent du fait de ne pas avoir à consacrer du temps à la validation de la condition BCNF, générant ainsi des schémas supplémentaires qui sont superflus en termes d'efficacité des mises à jour, mais 30 elles peuvent rajouter de manière significative à l'inefficacité de l'évaluation des requêtes. Pour les décompositions 3NF, d'autre part, le prix à payer pour la conservation des dépendances est une plus grande complexité en termes de taille des décompositions, ainsi que le temps nécessaire à leur génération. La décision finale d'utiliser ou non une décomposition 3NF qui n'est pas une 35 décomposition de forme BCNF ou une décomposition de forme BCNF qui n'offre pas de conservation des dépendances est susceptible de nécessiter une analyse détaillée qui 3024914 diffère d'un cas à l'autre. Lorsqu'est considérée l'efficacité des mises à jour, il convient d'examiner si des mises à jour fréquentes sont davantage ralenties par des redondances de données inhérentes dans la décomposition 3NF donnée qui n'est pas une décomposition de forme BCNF, ou par la validation de dépendances FD qui ne sont pas conservées dans la décomposition de forme BCNF donnée. Cela devrait être pondéré avec une analyse indiquant lequel des schémas fournit une meilleure efficacité en termes d'évaluation des requêtes fréquentes. Une question pratique importante consiste à trouver laquelle des deux stratégies de normalisation est plus susceptible de se traduire par une meilleure 10 décomposition, définie comme une décomposition de forme BCNF sans perte, avec conservation des dépendances. Par conséquent, nous avons créé de manière aléatoire les pourcentages de ces décompositions de forme BCNF sans perte qui offrent une conservation des dépendances et de ces décompositions 3NF sans perte qui sont dans la forme BCNF. Les résultats sont présentés dans la figure 16. La figure indique que la 15 stratégie 3NF est beaucoup plus susceptible d'aboutir à une meilleure décomposition que la stratégie BCNF. La probabilité de générer un certain motif 3NF qui enfreint la condition BCNF est inférieure à la probabilité de ne pas préserver certaines dépendances FD. Néanmoins, la différence est assez substantielle. En effet, pour le cas où a = 1, le pourcentage moyen pour 3NF(1, 2) est de 73, pour BCNF(1) il est de 22,5, et pour 20 BCNF(3) il est de 20. Pour le cas où a = 5, le pourcentage moyen pour 3NF(1, 2) est de 53, pour BCNF(1) il est de 18,5, et pour BCNF(3) il est de 12. Ces observations fournissent des explications empiriques indiquant pourquoi la stratégie 3NF est la stratégie de normalisation préférée dans la pratique classique. Enfin, la figure 17 montre que le temps moyen pour valider la condition BCNF 25 pour une décomposition 3NF donnée est inférieur au temps moyen pour valider la conservation des dépendances pour une décomposition de forme BCNF donnée. Cependant, le cas le plus chronophage nécessite moins de 2 ms. En résumé, la segmentation d'un ensemble de dépendances FD en des dépendances PFD au moyen de degrés de certitude permet des approches de 30 normalisation standard pour dériver une variété de schémas de bases de données relationnelles dont la sélection finale peut être basée sur le niveau ciblé d'intégrité des données ou la charge de travail attendue des requêtes et mises à jour. Plus les degrés de certitude peuvent être modélisés de manière efficace, plus il y a de contrôle acquis par rapport à des compromis classiques entre efficacité des mises à jour et efficacité des 35 requêtes, étant donné que de meilleures concordances avec la charge de travail attendue peuvent être trouvées et qu'il est possible d'éviter l'application non souhaitée de l'intégrité. 3024914 56 En effet, l'exclusion des dépendances FD dont le degré de certitude est inférieur à celui ciblé se traduira par des schémas de bases de données qui sont normalisés par rapport au degré cible, mais dé-normalisés au sens classique. Ceci explique en quoi la structure du système de conception de ,base de données peut être considérée comme unifiant la normalisation et la dé-normalisation. Ainsi, les schémas dé-normalisés de manière classique peuvent être justifiés en termes de niveau ciblé d'intégrité des données. 9.2 Problème d'implication La présente section étudie expérimentalement l'efficacité s'agissant de 10 déterminer le problème d'implication pour des dépendances FD possibilistes, fournissant une confirmation de la limite théorique et un aperçu du temps réel requis pour parvenir à des décisions. Pour les expérimentations, nous avons créé de manière aléatoire 1 000 instances différentes du problème d'implication pour les dépendances PFD pour chacun 15 des schémas de relations sous-jacents avec n = 3, ...,20 attributs. Pour chacune de ces instances, nous avons alors simplement supprimé les degrés de certitude associés et déterminé les instances correspondantes du problème d'implication pour les dépendances FD. Pour chaque n, nous avons ensuite calculé le pourcentage de résultats positifs et pris le temps moyen pour la détermination de chacune des 1 000 instances sur n. 20 La figure 18 matérialise les résultats pour des ensembles de dépendances PFD, sous la forme de la ligne noire, et les résultats pour les ensembles de dépendances FD correspondants, sous la forme de la ligne bleue. En moyenne, le taux de réussite de la décision d'implication sur les ensembles de dépendances FD correspondants double par rapport aux ensembles de dépendances PFD à partir desquels ils ont été dérivés. En 25 chiffres réels, il s'agit d'une augmentation de 30 %, depuis une moyenne de 29 % pour les ensembles de dépendances PFD jusqu'à une moyenne de 59,5 % pour les ensembles de dépendances FD. En moyenne, nous déterminons si la même dépendance FD est impliquée par deux fois plus de dépendances FD données. En moyenne, le temps nécessaire à la décision d'implication pour les ensembles de dépendances FD 30 correspondants double par rapport aux ensembles de dépendances PFD à partir desquels ils ont été dérivés. En chiffres réels, il s'agit d'une augmentation depuis une moyenne de 0,08 ms pour les ensembles de dépendances PFD jusqu'à une moyenne de 0,17 ms pour les ensembles de dépendances FD. Dans les deux cas, les graphiques confirment la complexité en temps linéaire. Dans la pratique, les problèmes peuvent tous 35 deux être déterminés de manière très efficace. 3024914 57 9.3 Problème d'inférence La présente section étudie expérimentalement l'efficacité s'agissant d'inférer le degré de certitude maximum pour une dépendance FD donnée qui est impliquée par un 5 ensemble donné de dépendances PFD, fournissant une confirmation de la limite théorique et un aperçu du temps réel requis pour parvenir au degré de certitude. Pour les expérimentations, nous avons créé de manière aléatoire 1 000 instances différentes du problème d'inférence pour les dépendances PFD pour chacun des schémas de relations sous-jacents avec n = 3, ...,20 attributs. Pour chaque n, nous 10 avons ensuite calculé la moyenne de degrés de certitude et pris le temps moyen pour le calcul du degré pour chacune des 1 000 instances sur n. La figure 19 illustre les résultats des expérimentations pour le problème d'inférence. Le degré de certitude maximum moyen par lequel une dépendance FD donnée est impliquée par un ensemble donné de dépendances PFD est 6,8025, pris sur 15 les moyennes de la totalité des n = 3, ...,20. Le temps moyen pour calculer ces degrés est de 38,64 ms, pris sur les temps moyens de la totalité des n = 3, ...,20. Le graphique concernant les temps moyens confirme la complexité en temps linéaire du problème d'inférence. En pratique, le problème peut être résolu de manière très efficace. 20 9.4 Calcul des couvertures La présente section étudie expérimentalement l'efficacité du calcul des couvertures canoniques et non redondantes pour des ensembles de dépendances PFD. Nous comparons également les résultats à des couvertures canoniques et non 25 redondantes pour des ensembles de dépendances FD correspondants, obtenus à partir des ensembles de dépendances PFD en supprimant leurs degrés de certitude. Dans le cadre des expérimentations, nous avons créé de manière aléatoire 1 000 instances distinctes d'ensembles comportant jusqu'à 5n dépendances PFD pour chacun des schémas de relations sous-jacents avec n = 3, ... ,20 attributs et 15 degrés de 30 certitude différents. Pour chaque n, nous avons ensuite calculé le pourcentage moyen de la taille des couvertures canoniques et non redondante par rapport à leur ensemble de dépendances PFD d'entrée. La taille d'un ensemble de dépendances FD ou d'un ensemble de dépendances PFD correspond au nombre total d'attributs qu'il contient. Le temps moyen pour calculer les -couvertures est également calculé pour chaque n. 35 La figure 20 illustre les résultats des expérimentations pour le calcul de couvertures. En cohérence avec nos résultats pour le problème d'implication, les couvertures pour des ensembles de dépendances PFD sont d'une plus grande taille que 3024914 58 les couvertures pour les ensembles de dépendances FD correspondants. Comme auparavant, la raison fondamentale est que nous augmentons indirectement la taille d'entrée en supprimant des degrés de certitude, ce qui augmente la redondance parmi les dépendances FD données. Tant dans le cas PFD que dans le cas FD, les couvertures 5 canoniques se traduisent par des économies supplémentaires importantes en termes de taille. Les économies supplémentaires en termes de taille nécessitent un temps de calcul supplémentaire. En moyenne, les couvertures non redondantes des ensembles de dépendances PFD aboutissent à 66,64 % de la taille d'origine, calculée sur un temps moyen de 6,77 ms ; et les couvertures canoniques des ensembles de dépendances PFD 10 aboutissent à 62,85 % de la taille d'origine, calculée sur un temps moyen de 9,63 ms. De même, les couvertures non redondantes des ensembles de dépendances FD correspondants aboutissent à 43,73 % de la taille d'origine, calculée sur un temps moyen de 12,31 ms ; et les couvertures canoniques des ensembles de dépendances FD correspondants aboutissent à 34,74 % de la taille d'origine, calculée sur un temps moyen 15 de 15,76 ms. Les résultats confirment l'efficacité des différentes couvertures et le temps requis pour les calculer. En pratique, le calcul des couvertures canoniques et non redondantes est très efficace, ce qui se traduit par des économies considérables en termes de taille. Par conséquent, la validation des couvertures des ensembles de dépendances (P)FD peut se traduire par d'importantes économies de temps dès lors que 20 les mises à jour sont traitées. 9. Synthèse des avantages du système et procédé de conception de bases de données 25 La présente divulgation fournit une structure pour concevoir des schémas de bases de données relationnelles pour des applications nécessitant des données incertaines. Chaque uplet se voit affecter un degré de possibilité, et chaque dépendance fonctionnelle se voit affecter un degré de certitude qui modélise les uplets auxquels la dépendance fonctionnelle s'applique. La structure se traduit par une segmentation 30 personnalisée de la forme normale de Boyce-Codd et de la troisième forme normale, toutes deux bien connues, étendant la totalité de leurs propriétés à chaque segment. Les organisations ou les concepteurs de bases de données peuvent sélectionner la conception qui correspond le mieux à leur charge de travail attendue et au niveau ciblé d'intégrité des données. Les degrés de possibilité et les degrés de certitude autorisent les 35 concepteurs à concentrer l'effort de normalisation sur l'amélioration du traitement efficace des mises à jour les plus fréquentes, ce qui permet également le traitement efficace de 3024914 59 plus de requêtes. La structure unifie en outre la dé-normalisation et la normalisation relationnelle traditionnelle, étant donné que les schémas dé-normalisés de manière classique sont entièrement normalisés par rapport aux dépendances fonctionnelles qui satisfont le degré de certitude ciblé. Les expérimentations examinées confirment l'efficacité et l'efficience de la structure de conception de bases de données. En outre, elles donnent un aperçu initial de la conception de schémas de bases de données traditionnels. Par exemple, nous établissons une justification empirique robuste pour l'utilisation de la synthèse 3NF dans la pratique, montrant qu'elle offre une bien meilleure chance d'obtenir un schéma de base 10 de données optimal par rapport à ce qu'offrent les décompositions de forme BCNF. 11 Généralités Les modes de réalisation peuvent être mis en oeuvre par du matériel, des logiciels, des micrologiciels, des logiciels médiateurs, des microcodes, ou leurs 15 combinaisons. Dans le cas d'une mise en oeuvre dans un logiciel, un micrologiciel, un logiciel médiateur, ou un microcode, le code de programme ou les segments de code pour mettre en oeuvre les tâches nécessaires peuvent être stockés dans un support lisible par machine, par exemple un support de stockage ou d'autres types de stockage. Un processeur peut exécuter les tâches nécessaires. Un segment de code peut représenter 20 une procédure, une fonction, un sous-programme, un programme, une routine, une sous- routine, un module, un progiciel, une classe, ou une combinaison quelconque d'instructions, de structures de données, ou d'énoncés de programme. Un segment de code peut être couplé à un autre segment de code ou à un circuit matériel en transmettant et/ou en recevant des informations, des données, des arguments, des paramètres ou des 25 contenus de mémoire. Des informations, des arguments, des paramètres, des données, etc., peuvent être transmis, acheminés, ou envoyés par tout moyen approprié, y compris un partage de mémoire, une transmission de messages, une transmission de jetons, une transmission de réseau, etc. Dans ce qui précède, un support de stockage peut représenter un ou 30 plusieurs dispositifs de stockage de données, notamment une mémoire morte (ROM), une mémoire vive, ou à accès aléatoire, (RAM), des supports de stockage sur disque magnétique, des supports de stockage optique, des dispositifs de mémoire flash et/ou d'autres supports lisibles par machine permettant le stockage d'informations. Les expressions « support lisible par machine » et « support lisible par ordinateur » incluent, 35 mais sans toutefois s'y limiter, des dispositifs de stockage portables ou fixes, des 3024914 dispositifs de stockage optique, et/ou divers autres supports en mesure de stocker, de contenir ou de transporter une ou des instructions et/ou des données. Les différents blocs logiques, modules, circuits, éléments et/ou composants ilrustratifs décrits en relation avec les exemples décrits dans le présent document peuvent 5 être implémentés ou mis en oeuvre avec un processeur à usage générique, un processeur de signal numérique (DSP), un circuit intégré à application spécifique (ASIC), un réseau prédiffusé programmable par l'utilisateur (FPGA) ou un autre composant logique programmable, une logique de porte ou de transistor discrète, des composants matériels discrets, ou toute combinaison de ceux-ci conçue pour mettre en oeuvre les fonctions 10 décrites dans le présent document. Un processeur à usage général peut être un microprocesseur, mais en variante, le processeur peut être tout processeur, contrôleur, microcontrôleur, circuit, et/ou machine à états de type conventionnel. Un processeur peut également être mis en oeuvre sous la forme d'une combinaison de composants informatiques, par exemple, une combinaison d'un processeur DSP et d'un 15 microprocesseur, d'un nombre de microprocesseurs, d'un ou plusieurs microprocesseurs conjointement avec un coeur de processeurs DSP, ou toute autre configuration de ce type. Les procédés ou les algorithmes décrits en relation avec les exemples divulgués dans le présent document peuvent être incorporés ou intégrés directement dans le 20 matériel, dans un module logiciel exécutable par un processeur, ou dans une combinaison des deux, sous la forme d'une unité de traitement, d'instructions de programmation ou d'autres indications, et peuvent être contenus dans un unique dispositif ou répartis sur plusieurs dispositifs. Un module logiciel peut résider dans une mémoire RAM, une mémoire flash, une mémoire ROM, une mémoire EPROM, une mémoire 25 EEPROM, des registres, un disque dur, un disque amovible, un CD-ROM, ou dans toute autre forme de support de stockage connue dans l'art. Un support de stockage peut être couplé au processeur, de sorte que le processeur peut lire des informations à partir du support de stockage, et écrire des informations sur celui-ci. En variante, le support de stockage peut être intégré au processeur. 30 Un ou plusieurs des composants et une ou plusieurs des fonctions illustrés dans les figures peuvent être ré-agencés et/ou combinés en un seul composant ou intégrés à plusieurs composants sans s'écarter de l'invention. Des éléments ou des composants supplémentaires peuvent également être ajoutés sans s'écarter de l'invention. En outre, les caractéristiques décrites dans le présent document peuvent être 35 mises en oeuvre dans des logiciels, du matériel, sous la forme d'un procédé commercial, et/ou une combinaison de ces éléments. 3024914 61 Dans ses divers aspects, l'invention peut être intégrée dans un processus mis en oeuvre par ordinateur, une machine (par exemple un dispositif électronique ou un ordinateur à usage général, ou un âutre dispositif qui fournit une plateforme sur laquelle des programmes informatiques peuvent être exécutés), des processus exécutés par ces 5 machines, ou un article de fabrication. De tels articles peuvent inclure un produit- programme informatique ou un produit d'information numérique dans lequel est présent un support de stockage lisible par ordinateur contenant des instructions de programme informatique ou des données lisibles par ordinateur stockées sur celui-ci, et des processus et machines qui créent et utilisent ces articles de fabrication. 10 La description précédente de l'invention inclut les formes préférées de celle-ci. Des modifications peuvent y être apportées sans sortir du champ d'application de la présente invention. REVENDICATIONS1. Procédé de génération des conceptions de schémas de bases de données relationnelles pour des applications de bases de données qui comportent des données incertaines, comprenant les étapes ci-dessous consistant à: recevoir des données de conception d'entrée indicatives du schéma de relations et des dépendances fonctionnelles présentant un degré de certitude associé ou affecté à partir d'une échelle de degrés de certitude ; appliquer un algorithme de normalisation au schéma de relations, ainsi qu'un ensemble de dépendances fonctionnelles qui est défini par une entrée de commande ; et générer des données de conception de sortie comprenant des données indicatives des schémas de relations générés par l'algorithme de normalisation appliqué. 2. Procédé selon la revendication 1, dans lequel les données de conception de sortie comportent des données indicatives des schémas de relations et des données indicatives des dépendances fonctionnelles qui sont valables pour les ou chacun des schémas de relations générés par l'algorithme de normalisation, et dans lequel les données indicatives des schémas de relations comportent le nombre de schémas et les attributs de chaque schéma de relations. 3. Procédé selon la revendication 2, dans lequel les données de conception de sortie comportent des données indicatives de quelconques dépendances fonctionnelles qui n'étaient pas conservées dans les schémas de relations générés par l'algorithme de normalisation. 4. Procédé selon l'une quelconque des revendications précédentes, dans lequel la réception des données de conception d'entrée comporte en outre la réception de données indicatives de l'échelle de degrés de certitude. 5. Procédé selon l'une quelconque des revendications précédentes, dans lequel le procédé comprend en outre la détermination de l'échelle de degrés de certitude à partir des degrés de certitude associés aux dépendances fonctionnelles. 6. Procédé selon l'une quelconque des revendications précédentes, dans lequel l'entrée de commande définit le niveau de normalisation appliqué au schéma de relations. 7. Procédé selon la revendication 6, dans lequel l'entrée de commande détermine l'ensemble de dépendances fonctionnelles pour lequel l'algorithme de normalisation est appliqué. 3024914 63 8. Procédé selon la revendication 7, dans lequel l'entrée de commande représente une valeur de cohérence. 9. Procédé selon l'une quelconque des revendications 6 à 8, dans lequel 5 l'entrée de commande correspond ou se rapporte aux degrés de certitude ou à l'échelle de degrés de certitude associés aux dépendances fonctionnelles. 10. Procédé selon la revendication 9, dans lequel l'entrée de commande correspond à une variable d'index qui est sélectionnable à partir d'une échelle d'index correspondant à l'échelle de degrés de certitude, et dans lequel l'ensemble de 10 dépendances fonctionnelles appliqué dans l'algorithme de normalisation comporte toutes les dépendances fonctionnelles présentant un degré de certitude associé qui correspond ou se situe à un niveau de certitude plus élevé que la variable d'index sélectionnée. 11. Procédé selon l'une quelconque des revendications précédentes, dans lequel l'algorithme de normalisation est un algorithme de décomposition de forme normale 15 de Boyce-Codd (BCNF) ou un algorithme de synthèse de troisième forme normale (3NF). 12. Procédé selon l'une quelconque des revendications précédentes, dans lequel les données de conception d'entrée comportent des données indicatives des attributs ou des noms de champs du schéma de relations. 13. Procédé selon l'une quelconque des revendications précédentes, dans 20 lequel chaque degré de certitude dans l'échelle de degrés de certitude est mis en concordance avec un degré de possibilité correspondant à partir d'une échelle de possibilités, les degrés de possibilité étant affectés ou associés à des uplets de données sur le schéma de relations, et dans lequel le procédé comprend en outre l'étape consistant à affecter ou à associer un degré de certitude à chacune des dépendances 25 fonctionnelles, l'étape comprenant l'affectation du degré de certitude à chaque dépendance fonctionnelle qui correspond à la possibilité du plus petit monde possible dans lequel la dépendance fonctionnelle est enfreinte pour les uplets de données. 14. Procédé selon la revendication 13, dans lequel l'algorithme de normalisation est l'algorithme de décomposition de forme BCNF et celui-ci est appliqué à 30 un ensemble de dépendances fonctionnelles présentant un degré de certitude supérieur au degré de certitude utilisé en qualité d'entrée de commande de tel sorte que l'algorithme de décomposition de forme BCNF réalise toujours une conception de sortie qui garantit qu'aucune redondance de données ne sera produite dans des quelconques uplets associés aux degrés de possibilité correspondants. 35 15. Procédé selon la revendication 13, dans lequel l'algorithme de normalisation est l'algorithme de synthèse de forme 3NF et celui-ci est appliqué à un 3024914 64 ensemble de dépendances fonctionnelles présentant un degré de certitude supérieur au degré de certitude utilisé en qualité d'entrée de commande de tel sorte que l'algorithme de synthèse 3NF réalise toujours une conception de sortie qui garantit que la quantité de redondance de données qui se produira dans des quelconques uplets associés aux 5 degrés de possibilité correspondants est minimale parmi toutes les conceptions de sortie qui conservent toutes les dépendances fonctionnelles dans l'ensemble. 16. Procédé selon l'une quelconque des revendications précédentes, dans lequel le procédé comporte en outre les étapes consistant à modifier ou à faire varier l'entrée de commande, et à ré-appliquer l'algorithme de normalisation pour la ou chaque 10 nouvelle entrée de commande modifiée, jusqu'à ce que les données de conception de sortie correspondent à des critères prédéterminés. 17. Procédé selon la revendication 16, dans lequel les critères prédéterminés comprennent l'un ou plusieurs des critères ci-après : des données définissant le nombre de schémas de relations souhaités, des données indicatives d'une certaine efficacité de 15 mise à jour souhaitée ; et des données indicatives d'une certaine efficacité de requête souhaitée. 18. Procédé selon l'une quelconque des revendications précédentes, comprenant en outre la génération d'une représentation graphique des données de conception de sortie pour un nombre d'entrées de commande distinctes. 20 19. Procédé selon la revendication 18, dans lequel le procédé comporte la génération d'un graphique traçant le nombre de schémas dans les données de conception de sortie par rapport à l'entrée de commande ayant généré ces données de conception de sortie. 20. Procédé selon l'une quelconque des revendications précédentes, dans 25 lequel le procédé est mis en oeuvre par un processeur qui est configuré de manière à exécuter les étapes de procédé. Dans un exemple, le procédé est mis en oeuvre par ordinateur. 21. Système de conception de bases de données destiné à générer des conceptions de schémas de bases de données relationnelles pour des applications de 30 bases de données qui comportent des données incertaines, comprenant : une interface d'entrée configurée de manière à recevoir ou récupérer des données de conception d'entrée indicatives du schéma de relations et des dépendances fonctionnelles présentant un degré de certitude associé ou affecté à partir d'une échelle de degrés de certitude ; 3024914 65 un processeur de normalisation mise à l'échelle qui est configuré de manière à appliquer un algorithme de normalisation au schéma de relations ainsi qu'un ensemble de dépendances fonctionnelles qui sont définis par une entrée de commande ; et une interface de sortie qui est configurée de manière à générer des données de 5 conception de sortie comprenant des données indicatives des schémas de relations générés par l'algorithme de normalisation appliqué.