L'information a toujours eu un intérêt dynamique adéquat. Le développement des langages de programmation, des bases de données relationnelles et des technologies de l'information a radicalement modifié le contenu et la structure des sujets d'intérêt. Un certain système d'idées strict s'est développé. La formalisation, les mathématiques exactes et les relations binaires sont devenues un domaine de connaissance et d'expérience réussi et en développement rapide.

Le monde naturel de l'information n'a pas changé sa dynamique et, en développant son contenu et sa structure, a atteint de nouveaux sommets. Il a des formes douces et il n'y a rien dans la nature "rectangulaire". L'information, bien sûr, se prête à la formalisation, mais elle a une dynamique ; non seulement les données et les algorithmes pour les traiter changent, les tâches elles-mêmes et les domaines de leur application changent.

Information > formalisation >> données

L'information se transforme en structure d'information, en base de données...) telle que la voit le programmeur. Il n'y a aucune garantie que cette vision soit correcte, mais si son programme résout le problème, alors les données ont été présentées de la manière la plus appropriée possible.

La question de savoir dans quelle mesure les informations ont été formalisées est une question de temps. Jusqu'à présent, le concept de dynamique (auto-adaptation aux conditions changeantes d'utilisation) n'est qu'un rêve de programmation.

Dépendance fonctionnelle : « solution correcte = programme (programmeur) » et condition : « respect continu de la tâche » sont valables dans la plupart des cas, mais seulement ensemble. Mais ce n’est pas la base mathématique utilisée pour créer des bases de données.

Une déclaration directe : la dynamique naturelle et continue des algorithmes d’information et de résolution de problèmes est toujours réelle. Et ce sont des relations binaires + mathématiques strictes + constructions formelles précises, +...

et bases de données

La manière dont les données sont stockées a longtemps été sans importance : qu'il s'agisse de RAM ou d'un périphérique externe. Le composant matériel a atteint un rythme de développement soutenu et offre une bonne qualité dans de gros volumes.

Les principales options de stockage, différant par les options d'utilisation des données :

• fichiers;
• bases de données.

La première est laissée au programmeur (quoi écrire, dans quel format, comment faire, comment lire...), la seconde amène immédiatement la nécessité de comprendre une simple dépendance fonctionnelle.

La vitesse de récupération et d'écriture des informations lorsque l'on travaille avec des fichiers (de taille raisonnable, pas astronomique) est très rapide, mais la vitesse d'opérations similaires avec une base de données peut parfois être sensiblement lente.

Expérience personnelle et sagesse collective

Il y a eu des tentatives tout au long de l’histoire pour dépasser ces limites, mais aujourd’hui encore, les bases de données relationnelles règnent en maître. Un grand potentiel théorique a été accumulé, la pratique des applications est étendue et les développeurs sont hautement qualifiés.

Les développeurs de bases de données imposent le concept de dépendance fonctionnelle au programmeur, même s'il n'a pas l'intention d'utiliser la riche expérience mathématique et logique de la construction de structures d'information complexes, des processus de travail avec elles, de récupération et d'enregistrement d'informations.

Même dans le cas le plus simple, le programmeur dépend de la logique de base de données avec laquelle il choisit de travailler. Il n'y a aucune envie de suivre les canons, vous pouvez utiliser des fichiers, vous obtiendrez beaucoup de fichiers et beaucoup d'expérience personnelle. Beaucoup de temps personnel sera consacré et le problème sera résolu sur une longue période.

Aussi complexes que puissent paraître les exemples de dépendance fonctionnelle, il n'est pas du tout nécessaire de plonger dans les profondeurs du sens et de la logique. Il faut souvent reconnaître que l’esprit collectif a réussi à créer d’excellentes bases de données de différentes tailles et fonctionnalités :

• Oracle solide;
• serveur MS SQL exigeant ;
• MySQL populaire.

Excellentes bases de données relationnelles avec une bonne réputation, faciles à utiliser, rapides entre de bonnes mains. Leur utilisation permet de gagner du temps et élimine le besoin d'écrire d'autres feuilles de code auxiliaire.

Fonctionnalités de programmation et de données

Pendant longtemps, la programmation a eu le mal de réécrire constamment quelque chose, de répéter le travail de ses prédécesseurs afin d'adapter d'une manière ou d'une autre quelque chose à des informations modifiées, à une tâche ou aux conditions de son utilisation.

Le problème avec la dépendance fonctionnelle est que, tout comme en programmation, une erreur peut coûter très cher. La tâche est rarement simple. Habituellement, lors de la formalisation des informations, une représentation complexe des données est obtenue. Habituellement, leurs éléments sont isolés, puis ils sont liés par des clés dans certaines relations, puis les algorithmes de formation de tableaux, de requêtes et les algorithmes de récupération d'informations sont ajustés.

La liaison avec l'encodage est souvent d'une grande importance. Toutes les bases de données n'offrent pas de solutions mobiles ; vous pouvez souvent constater comment un MySQL parfaitement configuré, sur lequel sont basées une douzaine de bases de données, fonctionnant parfaitement et de manière stable, oblige le développeur à créer la onzième base de données similaire à celles qui existent déjà.

Il arrive parfois que l'hébergement partagé limite les fonctionnalités de PHP, ce qui affecte la programmation de l'accès aux bases de données.

Dans la programmation moderne, la responsabilité de l'algorithme d'un programme équivaut à la responsabilité de créer un modèle de données. Tout devrait fonctionner, mais il ne faut pas toujours se plonger dans la jungle de la théorie.

DB : dépendance de données simple

Tout d'abord, le concept de base de données est à la fois une base de données, à la fois un système de gestion (par exemple, MySQL) et une certaine structure d'information qui reflète les données des tâches et les connexions entre elles. Une base de données MySQL « contient » autant de structures d'informations que vous le souhaitez pour différents domaines d'application. Une base de données Oracle peut prendre en charge les processus d'information d'une grande entreprise ou d'une banque, contrôler les problèmes de sécurité et d'intégrité des données au plus haut niveau, situés sur de nombreux ordinateurs situés à différentes distances, dans différents environnements instrumentaux.

Il est généralement admis que la relation est fondamentale dans le modèle relationnel. Une relation élémentaire est un ensemble de colonnes avec des noms et de lignes avec des valeurs. Classique "rectangle"(tableau) - réalisation de progrès simple et efficace. La complexité et la dépendance fonctionnelle d'une base de données commencent lorsque "rectangle" commencer à nouer des relations les uns avec les autres.

Le nom de chaque colonne de chaque table doit être unique dans le contexte de la tâche. Les mêmes données ne peuvent pas figurer dans deux tableaux. Connaître la signification des concepts :

• « définir des entités » ;
• « éliminer la redondance » ;
• « réparer les relations » ;
• "pour garantir l'authenticité."

Une nécessité élémentaire pour utiliser une base de données et construire un modèle de données pour une tâche spécifique.

La violation de l'un de ces concepts signifie une faible efficacité de l'algorithme, un échantillonnage lent des données, une perte de données et d'autres problèmes.

Dépendance fonctionnelle : logique et sens

Vous n'avez pas besoin de lire sur les tuples de relations, sur le fait qu'une fonction est une correspondance entre un ensemble d'arguments et un ensemble de valeurs, et qu'une fonction n'est pas seulement une formule ou un graphique, mais peut être spécifiée par un ensemble de valeurs - un tableau.

Ce n'est pas nécessaire, mais cela ne fait pas de mal de considérer une dépendance fonctionnelle comme :

F(x1, x2, …, xN) = (y1, y2, …, yN).

Mais il est impératif de comprendre que l'entrée est un tableau, et que la sortie est également un tableau ou une solution spécifique. Généralement, une dépendance fonctionnelle établit la logique des relations entre les tables, requêtes, privilèges, déclencheurs, procédures stockées et autres aspects (composants) de la base de données.

Généralement, les tableaux sont convertis entre eux, puis en résultat. Mais l’utilisation de la dépendance fonctionnelle ne se limite pas à cette seule idée. Le programmeur construit lui-même sa propre représentation de l'image des données, de la structure de l'information... peu importe comment vous l'appelez, mais s'il fonctionne sur une base de données spécifique, il doit être construit selon sa logique, prendre en compte sa signification et le dialecte du langage utilisé, généralement SQL.

On peut affirmer que les propriétés des dépendances fonctionnelles d'une base de données sont accessibles via le dialecte du langage SQL utilisé. Mais il est bien plus important de comprendre : après toutes les vicissitudes du développement, peu de bases de données ont survécu, mais il existe également de nombreux dialectes de cette langue et des caractéristiques des structures internes des bases de données.

À propos du bon vieux Excel

Lorsque l’ordinateur s’est montré positif, le monde a été immédiatement divisé entre programmeurs et utilisateurs. En règle générale, les premiers utilisent :

• PHP, Perl, JavaScript, C++, Delphes.
• MySQL, Oracle, Visual FoxPro.

• Mot.
• Exceller.

Certains utilisateurs parviennent à créer eux-mêmes des bases de données dans Word (sans l'aide de programmeurs) - c'est un véritable non-sens.

L'expérience utilisateur dans Excel pour créer des bases de données est pratique et intéressante. L’important est qu’Excel lui-même soit fonctionnel, coloré et pratique.

L'idée tabulaire a défini le concept de dépendance fonctionnelle de manière claire et accessible, mais chaque base de données a des nuances. Chacun a son propre « visage », mais tout le monde, d’Excel à Oracle, manipule de simples carrés, c’est-à-dire des tableaux.

Si l'on considère qu'Excel n'est pas du tout une base de données, mais que de nombreux utilisateurs (pas de programmeurs) l'utilisent de cette façon, et qu'Oracle est la réalisation la plus complexe et la plus puissante d'une grande équipe de développeurs dans le domaine des bases de données, alors il devient naturel de Admettez qu'une base de données est une représentation d'un programmeur (équipe) spécifique sur un problème spécifique et sa solution.

Qu'est-ce que la dépendance fonctionnelle, avec quoi, où, pourquoi... n'est évident que pour l'auteur ou une équipe d'entre eux.

À propos de la direction que prennent les relations relationnelles

Le progrès scientifique et technologique est un processus très douloureux, et parfois cruel. Si vous vous souvenez comment les bases de données ont commencé, ce qu'est *.dbf, comment elles ont stigmatisé la cybernétique, puis elles sont tombées amoureuses de l'informatique et ont commencé à créer des obstacles au mouvement des hautes technologies au niveau national, il devient clair pourquoi les bases de données relationnelles sont si tenace et bon. Pourquoi le style classique de programmation perdure aujourd'hui et la programmation orientée objet est simplement appréciée, mais ne règne pas encore.

Peu importe à quel point c'est beau dépendance fonctionnelle dans le contexte des mathématiques :

Il ne s’agit pas d’une relation binaire, ou plutôt d’une raison pour repenser l’idée d’​​établir des relations entre de nombreux attributs, en explorant le « un-à-plusieurs », « plusieurs-à-un », « plusieurs-à-plusieurs). -plusieurs » ou « plusieurs en général et certains en particulier ».

Vous pouvez proposer une grande variété d’options relationnelles. C'est des mathématiques avec de la logique, et c'est rigoureux ! L'information est sa propre mathématique, spéciale. On ne peut y parler que de formalité avec un très gros inconvénient.

Vous pouvez formaliser le travail du service RH, écrire un système de contrôle automatisé pour la production de pétrole ou la production de lait, de pain, faire une sélection dans l'immense base de données de Google, Yandex ou Rambler, mais le résultat sera toujours statique et le même à tout moment !

Si dépendance fonctionnelle = logique stricte et mathématiques = base des bases de données, alors de quel type de dynamique peut-on parler ? Toute solution sera formelle, tout modèle de données formel + algorithme strict = solution exacte et sans ambiguïté. Les informations et la portée de tout programme sont en constante évolution.

La sélection du moteur de recherche pour la même expression de recherche ne peut pas être la même après une heure ou deux, et certainement tous les deux jours - si l'expression de recherche appartient à un domaine d'information dans lequel le nombre de sites, de ressources, de connaissances et autres les éléments changent constamment.

Même si le programme est purement mathématique et que sa base de données ne pense même pas à la dynamique, tout est toujours des lignes. Et la chaîne a une longueur. Et cela ne peut pas être sans fin. Ce ne peut même pas être une variable, seulement une variable conditionnelle. Entre autres choses, toute base de données, avec son appareil bureaucratique mathématique et binaire, impose de nombreuses formalités, et cela signifie rapidité + qualité d'échantillonnage et de traitement de l'information.

Et si certains champs de la base de données sont des nombres, notamment réels, alors les restrictions suivantes seront ajoutées : capacité des chiffres du nombre, présence de la lettre « e », format de représentation - bref, partout et toujours nous avons de l'importance propriétés de dépendance fonctionnelle de la base de données : des chaînes de longueur conditionnellement variable avec de nombreuses formalités binaires et des restrictions mathématiques strictes.

Si vous changez le ton et écoutez le pouls de la dynamique, alors tout peut être peint en objets. En première approximation, le nom d'une colonne dans un tableau est un objet, une liste de noms est aussi un objet, bref, un tableau est un objet d'en-tête et dans celui-ci les noms des colonnes de l'en-tête. Et il n'y a peut-être pas de chapeau du tout...

Mais il peut y avoir des lignes dans le tableau. Et la chaîne peut avoir des valeurs. Et pourquoi devrait-il y en avoir toujours le même nombre ? Table carrée complète- c'est une chose particulière, et dans la plupart des cas, privée.

Si vous représentez toutes les constructions de la base de données sous forme d'objets, vous n'aurez peut-être pas à créer des relations binaires strictes. Cela a une signification naturelle et réelle, ne serait-ce que parce que, selon une logique objective (et certainement pas mathématique), cela reflète la dynamique de l’information et l’environnement dans lequel les problèmes existent.

Une base de données relationnelle contient des informations à la fois structurelles et sémantiques. La structure d'une base de données est déterminée par le nombre et le type de relations qu'elle contient, ainsi que par les relations un-à-plusieurs qui existent entre les tuples de ces relations. La partie sémantique décrit l'ensemble des dépendances fonctionnelles qui existent entre les attributs de ces relations. Définissons la dépendance fonctionnelle.

Définition: Si deux attributs X et Y d'une relation sont donnés, alors Y est dit dépendre fonctionnellement de X si à tout moment chaque valeur de X correspond exactement à une valeur de Y. La dépendance fonctionnelle est notée X -> Y. Notez que X et Y peuvent représenter non seulement des attributs uniques, mais également des groupes constitués de plusieurs attributs d'une même relation. Nous pouvons dire que les dépendances fonctionnelles sont des relations un-à-plusieurs qui existent au sein d’une relation.

Relation de 2ème forme normale (2NF). Détermination de la dépendance fonctionnelle complète et du 2NF.

Caractéristiques des relations en 2NF. Algorithme de réduction à 2NF. Théorème de Heath. Exemples.Concept

dépendance fonctionnelle complète. Définition : attribut non clé entièrement fonctionnellement dépendant

Définition: à partir d'une clé composite si elle dépend fonctionnellement de la clé entière dans son ensemble, mais ne dépend fonctionnellement d'aucun de ses attributs constitutifs. dépendance fonctionnelle excessive

- une dépendance qui contient des informations pouvant être obtenues sur la base d'autres dépendances disponibles dans la base de données.

2NF - deuxième forme normale. 2NF, s'il est en 1NF et que chaque attribut non-clé dépend fonctionnellement entièrement de la clé.

Un schéma de base de données qui ne comporte pas de dépendances fonctionnelles redondantes est considéré comme correct. Sinon, il faut recourir à la procédure de décomposition (décomposition) de l'ensemble de relations existant. Dans ce cas, l’ensemble généré contient un plus grand nombre de relations, qui sont des projections des relations de l’ensemble d’origine. (L'opération de projection est décrite dans la section sur l'algèbre relationnelle.) Le processus réversible étape par étape consistant à remplacer un ensemble donné de relations par un autre schéma, éliminant les dépendances fonctionnelles redondantes, est appelé normalisation.

La condition de réversibilité exige que la décomposition préserve l'équivalence des circuits lors du remplacement d'un circuit par un autre, c'est-à-dire dans les relations résultantes :

1) les tuples précédemment manquants ne devraient pas apparaître ;

2) les relations du nouveau schéma doivent satisfaire l'ensemble original de dépendances fonctionnelles.

Théorème de Heath

Donnons la relation.

Si r satisfait la dépendance fonctionnelle, alors il est égal à l'union de sa projection et

Relation de 3ème forme normale (3NF).

Trouver

Dépendances fonctionnelles

La dépendance fonctionnelle décrit la relation entre les attributs et constitue l'un des concepts de base de la normalisation. Supposons que le schéma relationnel ait des attributs (A, B, C,..., Z) et que la base entière puisse être représentée comme une relation universelle R=(A, B, C,..., Z). Par conséquent, chaque attribut de la base de données possède un nom unique. Si A et B sont des attributs d'une certaine relation R, et que chaque valeur de A est associée à une et une seule valeur de B (et chacun des attributs peut être constitué d'un ou plusieurs attributs), alors l'attribut B fonctionnellement dépendant

de l'attribut A (ВАА). Une dépendance fonctionnelle valable dans toutes les conditions est appelée banal

. Les dépendances non triviales définissent des contraintes d'intégrité sur les relations. Dépendance transitive

pour les attributs A, B et C d'une certaine relation signifie ce qui suit : si AàB et BàC, alors C dépend transitivement de l'attribut A via l'attribut B (à condition que A soit fonctionnellement indépendant de B ou C).

La conception de bases de données utilisant la normalisation commence par la définition de dépendances fonctionnelles sémantiquement évidentes, c'est-à-dire réduction à la première forme normale.

Un tableau en première forme normale doit répondre aux exigences suivantes :

1) la table ne doit pas contenir d'enregistrements en double ;

2) le tableau ne doit pas contenir de groupes de champs en double ;

3) chaque champ doit être sémantiquement indivisible.

Une table sous la deuxième forme normale doit répondre à toutes les exigences de 1NF ; tout champ non clé est identifié de manière unique par un ensemble complet de champs clés, c'est-à-dire que chaque attribut de la relation dépend entièrement ou partiellement fonctionnellement d'un autre attribut.

La dépendance fonctionnelle de AàB est complet dépendance fonctionnelle si la suppression d’un attribut de A entraîne la perte de cette dépendance. La dépendance fonctionnelle de AàB s’appelle partiel, si dans A il y a un certain attribut, une fois supprimé, cette dépendance demeure.

Une table qui est en troisième forme normale doit répondre à toutes les exigences de 2NF ; aucun champ non clé n'est identifié par un autre champ non clé, c'est-à-dire une relation qui est en première et deuxième forme normale et n'a aucun attribut qui ne le soit pas. dans la clé primaire des attributs , ce qui serait en dépendance fonctionnelle transitive vis-à-vis de cette clé primaire.

Boyce Code Normal Form (BCNF) est basé sur des dépendances fonctionnelles qui prennent en compte toutes les clés potentielles d'une relation, mais avec des restrictions plus strictes.

Déterminant de la dépendance fonctionnelle est un attribut (ou un groupe d'attributs) dont dépend entièrement fonctionnellement un autre attribut.

Pour vérifier si une relation appartient au BCNF, il faut retrouver tous ses déterminants et s'assurer qu'ils sont des clés potentielles.

La différence entre 3NF et BCNF est que la dépendance fonctionnelle AàB est autorisée dans une relation 3NF si l'attribut B est une clé primaire et que l'attribut A n'est pas nécessairement une clé candidate. Pour BCNF, cette dépendance n'est autorisée que lorsque l'attribut A est une clé candidate. Par conséquent, BCNF est une version plus stricte de 3NF, puisque chaque relation BCNF est 3NF, mais toutes les relations 3NF ne sont pas BCNF.

Une relation n'est en BCNF que si chacun de ses déterminants est une clé potentielle.

La quatrième forme normale (4NF) est une relation en BCNF qui ne contient pas de dépendances multivaluées non triviales.

Dépendance à valeurs multiples représente une relation entre les attributs d'une relation (par exemple, A, B et C) telle que chaque valeur de A représente un ensemble de valeurs pour B et un ensemble de valeurs pour C. Cependant, les ensembles de valeurs ​​car B et C sont indépendants l'un de l'autre.

Une dépendance à valeurs multiples peut être définie comme triviale ou non triviale. Une dépendance multivaluée AàB d'une relation R est définie comme triviale si l'attribut B est un sous-ensemble de l'attribut A ou . À l’inverse, une dépendance à valeurs multiples est définie comme non triviale si aucune des deux conditions n’est remplie. Une dépendance multivaluée triviale n’impose aucune restriction à cette relation, contrairement à une dépendance non triviale.

Lors du partitionnement d'une relation par l'opération de projection, la méthode de décomposition utilisée est déterminée avec précision. Il est nécessaire que lorsque les relations résultantes soient reconnectées, la relation originelle puisse être restaurée. Cette décomposition est appelée décomposition de la connexion sans perte(ou une jointure gagnant-gagnant ou non additive) car elle préserve toutes les données dans la relation d'origine et élimine la création de lignes factices supplémentaires.

La cinquième forme normale (5NF), également appelée forme normale connective projective, signifie qu'une relation sous cette forme n'a pas de dépendances de jointure. Une relation R avec un sous-ensemble d'attributs A,B,...,Z satisfait une dépendance de jointure si chaque valeur admissible de R est égale à la jointure de ses projections sur les sous-ensembles A,B,...,Z.

Annotation: Ce cours introduit la notion de dépendance fonctionnelle. Ce concept est à la base de la théorie mathématique des bases de données relationnelles.

Informations, données, systèmes d'information

Le concept de dépendance fonctionnelle dans les données

Laissons de côté pour l'instant la réponse à la question de savoir pourquoi les projets de bases de données relationnelles sont mauvais, c'est-à-dire Pourquoi avez-vous besoin de concevoir une base de données relationnelle ? Essayons d’abord de répondre aux questions « Qu’est-ce que conception de base de données relationnelle? et "Quelle est la base des procédures ?"

Comme on le sait, l'unité principale de représentation des données dans le modèle relationnel est une relation, qui est mathématiquement spécifiée par une liste de noms d'attributs, sinon - diagramme de relation. Au stade conception logique Dans une base de données relationnelle, le concepteur définit et construit des diagrammes de relations au sein d'un certain domaine, à savoir, représente les entités, regroupe leurs attributs et identifie les principales connexions entre les entités. Ainsi, au sens le plus général, la conception d’une base de données relationnelle implique de faire un choix éclairé de schémas relationnels spécifiques parmi une variété d’alternatives schématiques différentes.

En pratique, la construction d'un modèle logique de base de données, quel que soit le modèle de données utilisé, s'effectue en tenant compte de deux exigences principales : éliminer les redondances et maximiser la fiabilité des données. Ces exigences découlent de l’exigence d’une utilisation collective des données par un groupe d’utilisateurs. Les moyens formels de description des données nécessaires pour vérifier l'exactitude du remplissage des structures du modèle ne suffisent clairement pas. La sélection des entités, des attributs et l'enregistrement des relations entre les entités dépendent de la sémantique du domaine et sont effectués par l'analyste système de manière subjective conformément à sa compréhension personnelle des spécificités de la tâche d'application. Différentes personnes définissent et présentent les données de différentes manières.

Par conséquent, toute connaissance a priori des contraintes de domaine imposées sur les relations entre les données et leurs valeurs, ainsi que la connaissance de leurs propriétés et des relations entre elles, peuvent jouer un rôle pour répondre aux exigences ci-dessus. La formalisation d'une telle connaissance a priori sur les propriétés des données du domaine des bases de données se reflète dans le concept dépendance fonctionnelle des données, c'est-à-dire restrictions sur les relations possibles entre les données, qui peuvent être les valeurs actuelles du schéma de relation.

Les tuples de relations peuvent représenter des instances entités de domaine ou enregistrer leur relation. Mais même si ces tuples sont définis correctement, c'est-à-dire correspondent au schéma de relation et sont sélectionnés parmi des domaines valides, tous ne peuvent pas être la valeur actuelle d'une relation. Par exemple, l'âge d'une personne dépasse rarement 120 ans, ou le même pilote ne peut pas effectuer deux vols différents en même temps. De telles restrictions sur la sémantique du domaine n'ont pratiquement aucun effet sur le choix de l'un ou l'autre schéma de relations. Ils représentent des restrictions sur les types de données.

Les restrictions de domaine a priori sur la relation entre les valeurs des attributs individuels ont le plus grand impact sur le processus de conception schémas de bases de données relationnelles. Faire correspondre la valeur de certains attributs de différentes relations de base de données, c'est-à-dire la dépendance de leurs valeurs les unes par rapport aux autres détermine indicateurs de fiabilité et l'exactitude des données stockées lorsqu'elles sont utilisées collectivement et de manière cohérente.

Rappelons la définition d'une fonction comme la correspondance d'un ensemble d'arguments à certaines valeurs de l'ensemble des définitions de fonctions et des méthodes de spécification des fonctions : formule, graphique et énumération (tableau). Ce n'est pas difficile à comprendre dépendance fonctionnelle(FZ) peut être défini sur une classe d’objets assez large. La définition d'une fonction n'impose aucune restriction sur l'ensemble des arguments et l'ensemble des valeurs de la fonction, autre que leur existence et l'existence d'une correspondance entre leurs éléments. Étant donné que la loi fédérale peut être spécifiée dans un tableau et que le tableau est une forme de représentation de la relation, le lien entre la loi fédérale et la relation devient évident. Cette attitude peut être fixée par la loi fédérale. Cette affirmation est la première (1) idée constructive qui constitue la base de la théorie conception de base de données relationnelle.

Définition 1. Soit r (A 1, A 2, ..., A n) un schéma de la relation R, et X et Y des sous-ensembles de r. On dit que X détermine fonctionnellement Y si chaque valeur d'attribut relation de tupleà partir de X ne correspond pas plus d'une valeur d'attribut du même relation de tuple de Y. Une telle loi fédérale est désignée comme.

Comme le montre la définition, dépendance fonctionnelle invariant aux changements dans les états de la base de données au fil du temps.

Exemple. La notion de dépendance fonctionnelle Démontrons la notion de dépendance fonctionnelle à l'aide de l'exemple d'un programme de vol d'aéroport. FLIGHT_SCHEDULE (Pilote, Vol, Departure_Date, Departure_Time)

On sait que :

• chaque vol a une heure de départ spécifique ;
• Un seul vol est possible pour chaque pilote, date et heure de départ ;
• un pilote spécifique est affecté à un jour et à un vol spécifiques.

Ainsi:

• "Departure_time" dépend fonctionnellement de "Flight" : "Vol" -> "Heure de départ_()" ;
• "Vol" dépend fonctionnellement de ("Pilote", "Date_Départ", "Heure_Départ"): ("Pilote", "Date_depart", "Heure_depart") -> "Vol" ;
• "Pilote" dépend fonctionnellement de ("Vol", "Date_départ"): ("Vol", "Date_départ") -> "Pilote".

Une tâche importante dans l'identification dépendances fonctionnelles sur les attributs d'une relation, qui par définition est un ensemble, est de savoir lequel des attributs fait office d'argument et lequel fait office de valeur de la loi fédérale. Les candidats les plus appropriés pour les arguments FZ sont les clés possibles, puisque les tuples représentent instances d'entité, qui sont identifiés par les valeurs d'attribut de leur clé. En gros, la dépendance fonctionnelle se produit dans une relation lorsque les valeurs d'un tuple sur un ensemble d'attributs déterminent de manière unique les valeurs d'un tuple sur un autre ensemble d'attributs. Cette définition de travail d'une loi fédérale ne contient pas les éléments formels qui permettent de répondre à la question « Comment pouvons-nous vérifier la présence d'une loi fédérale entre les attributs d'une relation ? Le formalisme nécessaire pour cela nous donne l'usage opérations relationnelles. Pour obtenir une définition formelle (stricte) de la présence d'une loi fédérale en matière de opérations relationnelles.

Définition 2. Soit une relation R avec schéma r, X et Y sont deux sous-ensembles de R. FZ tient sur R si l'ensemble a au plus un tuple pour chaque valeur de x. Un tel FD est également appelé F-dépendance.

Comme le montre la définition, un contrôle formel de la présence d'une loi physique par rapport à R consiste à sélectionner (sélectionner) une relation basée sur les valeurs clé possible et établir la présence d'une absence d'ambiguïté entre sa valeur et les valeurs des autres attributs.

L'algorithme qui vérifie si une relation R satisfait à la loi fédérale consiste à trier la relation par valeurs clé possible et établir le fait de l'absence d'ambiguïté entre sa valeur et les valeurs des autres attributs. Cet algorithme est utile, mais il est de nature auxiliaire.

Il est clair que si la sémantique du domaine de la base de données est complexe, il est alors assez difficile de vérifier l'appartenance des tuples à une loi fédérale. Il est difficile d'établir de manière générale la présence de la plupart dépendance fonctionnelle correspondant à la nature des données considérées. Grâce à une telle méthode formelle, il est possible d’identifier des problèmes physiques qui ne sont pas réels et sont de nature aléatoire. Un concepteur de base de données relationnelle doit être conscient de cette méthode de vérification de la présence d'une loi fédérale, mais lors de la conception d'une nouvelle base de données, son utilisation est inefficace. Cela peut être utile lors de la réingénierie d’une base de données existante.

Dépendances fonctionnelles en fait, ils représentent des déclarations sur toutes les relations d’un domaine. Ces relations peuvent être des valeurs du schéma et, par essence, ne peuvent pas être obtenues par des méthodes formelles. La seule façon d'établir dépendances fonctionnelles car le schéma de relation r est une étude de la sémantique des attributs entités de domaine. Être des déclarations sur entités de domaine, ils ne peuvent pas être prouvés. Cette circonstance donne essentiellement lieu à une représentation non unique du domaine par des relations dans la base de données relationnelle.

C’est un bon endroit pour émettre des hypothèses sur les raisons pour lesquelles il existe de bonnes et de mauvaises conceptions de bases de données. Premièrement, en raison de la subjectivité des approches analyse de domaine les analystes peuvent manquer des lois fédérales importantes. Cela peut conduire le concepteur à travailler sur de nombreuses conceptions manifestement inéquivalentes pour créer une conception de base de données insatisfaisante. Deuxièmement, la représentation non unique d'un domaine par des relations conduit au problème du choix parmi de nombreuses alternatives. Dans ce cas, le schéma de base de données sélectionné parmi un ensemble de schémas équivalents est correct, mais peut organiser les données pour l'utilisateur d'une manière inhabituelle. Troisièmement, il est possible de définir (« couper ») des schémas de bases de données de telle sorte qu'à la suite d'opérations avec la loi fédérale, tant la loi fédérale que les données elles-mêmes soient perdues.

Les contraintes d'unicité imposées par les déclarations de clé primaire et candidate d'une relation sont un cas particulier des contraintes associées au concept dépendances fonctionnelles.

Pour expliquer le concept de dépendance fonctionnelle, considérons l'exemple suivant.

Donnons-nous une relation contenant des données sur les résultats d'une session spécifique. Le schéma de cette relation ressemble à ceci :

Session ( Carnet de notes n° , Nom, Prénom, Patronyme, Article , Grade);

Les attributs « N° du carnet de notes » et « Sujet » forment une clé primaire composite (puisque deux attributs sont déclarés comme clé) de cette relation. En effet, à partir de ces deux attributs on peut déterminer sans ambiguïté les valeurs de tous les autres attributs.

Cependant, outre la contrainte d'unicité associée à cette clé, la condition doit nécessairement être imposée à la relation selon laquelle un carnet de notes est nécessairement délivré à une personne spécifique et, par conséquent, à cet égard, les tuples avec le même numéro de carnet de notes doivent contenir les mêmes valeurs des attributs « Nom », « Nom » et « Patronyme ».

Si nous avons le fragment suivant d'une certaine base de données d'étudiants d'un établissement d'enseignement après une certaine session, alors dans les tuples avec le numéro de registre 100, les attributs « Nom », « Prénom » et « Patronyme » coïncident, et les attributs « Sujet » et « Évaluation » ne correspondent pas (ce qui est compréhensible, car ils parlent de sujets et de performances différents). Cela signifie que les attributs « Nom », « Prénom » et « Patronyme » fonctionnellement dépendant de l'attribut « Numéro du carnet de notes », et les attributs « Sujet » et « Note » sont fonctionnellement indépendants.

Ainsi, dépendance fonctionnelle est une dépendance sans ambiguïté tabulée dans les systèmes de gestion de bases de données.

Donnons maintenant une définition stricte de la dépendance fonctionnelle.

Définition: soit X, Y des sous-schémas des relations de schéma S qui définissent le schéma S diagramme de dépendance fonctionnelle X > Oui(lire « X flèche Y »). Définissons inv restrictions de dépendance fonctionnelle > Y> comme une déclaration selon laquelle, par rapport au schéma S, deux tuples quelconques qui coïncident dans la projection vers le sous-schéma X doivent également coïncider dans la projection vers le sous-schéma Y.

Écrivons la même définition sous forme formelle :

Investissement > Y> r(S) = t 1 , t 2 ? r(t 1 [X] = t 2 [X] ? t 1 [Oui] = t 2 [Oui]), X, Oui? S ;

Il est intéressant de noter que cette définition utilise le concept d’opération de projection unaire, que nous avons rencontré précédemment. En effet, comment, sans utiliser cette opération, pouvez-vous montrer que deux colonnes d'une table de relations, plutôt que des lignes, sont égales entre elles ? Par conséquent, nous avons écrit en termes de cette opération que la coïncidence de tuples dans la projection sur un ou plusieurs attributs (sous-schéma X) entraîne certainement la coïncidence des mêmes colonnes de tuples sur le sous-schéma Y dans le cas où Y dépend fonctionnellement de X .

Il est intéressant de noter que dans le cas d'une dépendance fonctionnelle de Y sur X, on dit aussi que X définit fonctionnellement O ou quoi Y fonctionnellement dépendantà partir de X. Dans un diagramme de dépendance fonctionnelle X > Y, le sous-circuit X est appelé la partie gauche et le sous-circuit Y est appelé la partie droite.

Dans la pratique de conception de bases de données, un diagramme de dépendances fonctionnelles est généralement appelé diagramme de dépendances fonctionnelles par souci de concision.

Fin de la définition.

Dans le cas particulier où le côté droit de la dépendance fonctionnelle, c'est-à-dire le sous-schéma Y, coïncide avec l'ensemble du schéma de relation, la contrainte de dépendance fonctionnelle devient une contrainte d'unicité pour la clé primaire ou candidate. Vraiment:

Investissement<K > S> r(S) = ? t 1 , t 2 ? r(t 1 [K] = t 2 [K] > t 1 (S) = t 2 (S)), K ? S;

C'est juste qu'en définissant une dépendance fonctionnelle, au lieu du sous-circuit X, vous devez prendre la désignation de clé K, et au lieu du côté droit de la dépendance fonctionnelle, le sous-circuit Y, vous devez prendre l'intégralité du diagramme de relation S, c'est-à-dire en effet, la contrainte d'unicité des clés de relation est un cas particulier de contrainte de dépendance fonctionnelle lorsque le côté droit des schémas de dépendance fonctionnelle est égal à l'ensemble du schéma relationnel.

Voici des exemples d’images de dépendance fonctionnelle :

(numéro du carnet de notes) > (Nom, Prénom, Patronyme) ;

(n° du carnet de notes, sujet) > (Note) ;

2. Règles d'inférence d'Armstrong

Si une relation de base satisfait des dépendances fonctionnelles définies par un vecteur, alors, en utilisant diverses règles d'inférence spéciales, il est possible d'obtenir d'autres dépendances fonctionnelles que cette relation de base satisfera certainement.

Un bon exemple de ces règles spéciales sont les règles d'inférence d'Armstrong.

Mais avant de commencer à analyser les règles d’inférence d’Armstrong elles-mêmes, introduisons en considération un nouveau symbole métalinguistique « + », appelé symbole d'une méta-déclaration sur la déductibilité. Lors de la formulation de règles, ce symbole est écrit entre deux expressions syntaxiques et indique que la formule à droite de celle-ci est dérivée de la formule à sa gauche.

Formulons maintenant les règles d'inférence d'Armstrong elles-mêmes sous la forme du théorème suivant.

Théorème. Les règles suivantes, appelées règles d'inférence d'Armstrong, sont valides.

Règle d'inférence 1.+ X > X ;

Règle d'inférence 2. X > Y+ X ? Z > Oui ;

Règle d'inférence 3. X > Oui, Oui ? W > Z + X ? W > Z ;

Ici, X, Y, Z, W sont des sous-schémas arbitraires du schéma de relations S. Le symbole d'une méta-énoncé sur la déductibilité sépare les listes de prémisses et les listes d'énoncés (conclusions).

1. La première règle d’inférence s’appelle « réflexivité» et se lit comme suit : « la règle est dérivée : « X implique fonctionnellement X. » Il s’agit de la plus simple des règles d’inférence d’Armstrong. Cela sort littéralement de nulle part.

Il est intéressant de noter qu’une dépendance fonctionnelle comportant à la fois des côtés gauche et droit est appelée réfléchissant. Selon la règle de réflexivité, la restriction de dépendance réflexive est automatiquement satisfaite.

2. La deuxième règle d’inférence s’appelle « réapprovisionnement» et se lit ainsi : « si X détermine fonctionnellement Y, alors la règle en découle : « l'union des sous-circuits X et Z entraîne fonctionnellement Y. » La règle de réapprovisionnement vous permet d'étendre le côté gauche de la contrainte de dépendance fonctionnelle.

3. La troisième règle d’inférence s’appelle « pseudotransitivité» et se lit comme suit : « si le sous-circuit X implique fonctionnellement le sous-circuit Y et que l'union des sous-circuits Y et W implique fonctionnellement Z, alors la règle en découle : « l'union des sous-circuits X et W détermine fonctionnellement le sous-circuit Z ».

La règle de pseudotransitivité généralise la règle de transitivité correspondant au cas particulier W : = 0. Donnons une représentation formelle de cette règle :

Il convient de noter que les prémisses et les conclusions données précédemment ont été présentées sous forme abrégée en utilisant les désignations de schémas de dépendance fonctionnelle. Sous forme développée, ils correspondent aux restrictions de dépendance fonctionnelle suivantes.

Règle d'inférence 1. inv. X>r(S);

Règle d'inférence 2. inv. Y> r(S) ? inv. Y>r(S);

Règle d'inférence 3. inv. Y> r(S) et inv Z>r(S) ? inv. Z>r(S);

Réalisons preuve ces règles d'inférence.

1. Preuve de la règle réflexivité découle directement de la définition de la restriction de dépendance fonctionnelle lors de la substitution du sous-circuit X au lieu du sous-circuit Y.

En effet, prenons la contrainte de dépendance fonctionnelle :

Investissement Y> r(S) et y substituons X au lieu de Y, nous obtenons :

Investissement X> r(S), et c'est la règle de réflexivité.

La règle de la réflexivité a été prouvée.

2. Preuve de la règle réapprovisionnement Illustrons avec des diagrammes de dépendance fonctionnelle.

Le premier diagramme est le diagramme de prémisse :

Paquet : X>Y

Deuxième schéma :

conclusion : X ? Z>Y

Que les tuples soient égaux sur X ? Z. Alors ils sont égaux sur X. D’après la prémisse, ils seront égaux sur Y.

La règle du réapprovisionnement a fait ses preuves.

3. Preuve de la règle pseudotransitivité Nous illustrerons également par des schémas, qui seront au nombre de trois dans ce cas particulier.

Le premier diagramme est la première prémisse :

prémisse 1 : X > Y

prémisse 2 : O ? W>Z

Et enfin, le troisième diagramme est le diagramme de conclusion :

conclusion : X ? W>Z

Que les tuples soient égaux sur X ? W. Alors ils sont égaux sur X et W. Selon la prémisse 1, ils seront égaux sur Y. Par conséquent, selon la prémisse 2, ils seront égaux sur Z.

La règle de pseudotransitivité a été prouvée.

Toutes les règles ont été prouvées.

3. Règles d'inférence dérivées

Un autre exemple de règles à l'aide desquelles de nouvelles règles de dépendance fonctionnelle peuvent, si nécessaire, être dérivées sont ce qu'on appelle règles d'inférence dérivées.

Quelles sont ces règles, comment sont-elles obtenues ?

On sait que si de certaines règles déjà existantes, d'autres sont dérivées par des méthodes logiques juridiques, alors ces nouvelles règles, appelées produits dérivés, peut être utilisé parallèlement aux règles originales.

Il convient de noter spécialement que ces règles très arbitraires sont « dérivées » précisément des règles d’inférence d’Armstrong que nous avons évoquées plus tôt.

Formulons les règles dérivées pour déduire des dépendances fonctionnelles sous la forme du théorème suivant.

Théorème.

Les règles suivantes sont dérivées des règles d'inférence d'Armstrong.

Règle d'inférence 1.+X ? Z > X ;

Règle d'inférence 2. X > Oui, X > Z + X ? Y>Z ;

Règle d'inférence 3. X > Oui ? Z + X > Y, X > Z ;

Ici X, Y, Z, W, comme dans le cas précédent, sont des sous-schémas arbitraires du schéma de relations S.

1. La première règle dérivée est appelée la règle de la trivialité et se lit comme suit :

« La règle est dérivée : « l'union des sous-circuits X et Z entraîne fonctionnellement X. »

Une dépendance fonctionnelle dont le côté gauche est un sous-ensemble du côté droit est appelée Une dépendance fonctionnelle valable dans toutes les conditions est appelée. Selon la règle de trivialité, les contraintes de dépendance triviales sont automatiquement satisfaites.

Il est intéressant de noter que la règle de trivialité est une généralisation de la règle de réflexivité et, comme cette dernière, pourrait être dérivée directement de la définition de la contrainte de dépendance fonctionnelle. Le fait que cette règle soit dérivée n’est pas accidentel et est associé à l’exhaustivité du système de règles d’Armstrong. Nous parlerons davantage de l'exhaustivité du système de règles d'Armstrong un peu plus tard.

2. La deuxième règle dérivée s'appelle règle d'additivité et se lit comme suit : « Si le sous-circuit X définit fonctionnellement le sous-circuit Y et que X définit simultanément fonctionnellement Z, alors de ces règles est dérivée la règle suivante : « X définit fonctionnellement l'union des sous-circuits Y et Z. »

3. La troisième règle dérivée s'appelle règle de projectivité ou la règle " inversion de l'additivité" Il se lit comme suit : « Si le sous-circuit X définit fonctionnellement l'union des sous-circuits Y et Z, alors de cette règle est dérivée la règle : « X définit fonctionnellement le sous-circuit Y et en même temps X définit fonctionnellement le sous-circuit Z » », c'est-à-dire en effet. , il s'agit d'une règle dérivée qui est l'inverse de la règle d'additivité.

Il est curieux que les règles d’additivité et de projectivité appliquées aux dépendances fonctionnelles ayant des membres gauches identiques nous permettent de combiner ou, à l’inverse, de diviser les membres droits de la dépendance.

Lors de la construction de chaînes d'inférence, après avoir formulé toutes les prémisses, la règle de transitivité est appliquée afin d'inclure une dépendance fonctionnelle dont le côté droit est situé dans la conclusion.

Réalisons preuve les règles d'inférence arbitraires répertoriées.

1. Preuve de la règle banalité.

Réalisons-la, comme toutes les preuves ultérieures, étape par étape :

1) nous avons : X > X (d’après la règle de réflexivité d’inférence d’Armstrong) ;

La règle de trivialité a été prouvée.

2. Effectuons une preuve étape par étape de la règle additivité:

1) nous avons : X > Y (c'est la prémisse 1) ;

2) nous avons : X > Z (c'est la prémisse 2) ;

3) on a : O ? Z > Oui ? Z (de la règle de réflexivité de l'inférence d'Armstrong) ;

4) on a : X ? Z > Oui ? Z (obtenu en appliquant la règle de pseudotransitivité de la dérivation d’Armstrong, puis en conséquence des première et troisième étapes de la preuve) ;

5) on a : X ? X > Oui ? Z (obtenu en appliquant la règle de pseudotransitivité d’Armstrong, puis découle des deuxième et quatrième étapes) ;

6) nous avons X > Y ? Z (suite à la cinquième étape).

La règle d'additivité a été prouvée.

3. Et enfin, nous construirons une preuve de la règle projectivité:

1) on a : X > Y ? Z, X > Oui ? Z (c'est une parcelle) ;

2) nous avons : Y > Y, Z > Z (dérivé en utilisant la règle de réflexivité d’inférence d’Armstrong) ;

3) on a : O ? z > y, Y ? z > Z (obtenu à partir de la règle de complétion de dérivation d'Armstrong et d'un corollaire de la deuxième étape de la preuve) ;

4) nous avons : X > Y, X > Z (ceci est obtenu en appliquant la règle de pseudotransitivité de la dérivation d’Armstrong, puis en conséquence des première et troisième étapes de la preuve).

La règle de projectivité a été prouvée.

Toutes les règles d'inférence dérivées ont été prouvées.

4. Complétude du système de règles d'Armstrong

Laisser F(S) - un ensemble donné de dépendances fonctionnelles définies sur un diagramme de relations S.

Notons par inv. <F(S)> la limitation imposée par cet ensemble de dépendances fonctionnelles. Écrivons-le :

Investissement <F(S)> r(S) = ?X > Oui ? F(S) [inv. Y> r(S)].

Ainsi, cet ensemble de restrictions imposées par les dépendances fonctionnelles se déchiffre ainsi : pour toute règle du système de dépendances fonctionnelles X > Y, appartenant à l'ensemble des dépendances fonctionnelles F(S), la restriction de dépendance fonctionnelle inv est en vigueur Y> r(S), défini sur un ensemble de relations r(S).

Laisse une certaine attitude r(S) satisfait cette contrainte.

Application des règles d'inférence d'Armstrong aux dépendances fonctionnelles définies pour un ensemble F(S), vous pouvez obtenir de nouvelles dépendances fonctionnelles, comme nous l'avons déjà dit et prouvé précédemment. Et, ce qui est significatif, les limitations de ces dépendances fonctionnelles sont liées F(S) satisfera automatiquement, comme le montre la forme étendue d'écriture des règles d'inférence d'Armstrong. Rappelons la forme générale de ces règles d'inférence étendues :

Règle d'inférence 1. inv. < X >X> r(S);

Règle d'inférence 2. inv. Y> r(S) ? inv. ? Z>Y> r(S);

Règle d'inférence 3. inv. Y> r(S) & inv. ? W>Z> r(S) ? inv. ? W>Z> ;

Revenant à notre raisonnement, complétons l'ensemble F(S) de nouvelles dépendances qui en dérivent en utilisant les règles d'Armstrong. Nous appliquerons cette procédure de réapprovisionnement jusqu'à ce que nous n'obtenions plus de nouvelles dépendances fonctionnelles. Grâce à cette construction, nous obtenons un nouvel ensemble de dépendances fonctionnelles, appelé court-circuit ensembles F(S) et noté F+(S).

En effet, ce nom est tout à fait logique, car nous-mêmes, à travers une longue construction, avons « fermé » de nombreuses dépendances fonctionnelles existantes sur nous-mêmes, ajoutant (d'où le « + ») toutes les nouvelles dépendances fonctionnelles résultant de celles existantes.

Il convient de noter que ce processus de construction d’une clôture est fini, car le schéma relationnel lui-même, sur lequel s’effectuent toutes ces constructions, est fini.

Il va sans dire que la fermeture est un sur-ensemble de l'ensemble fermé (en effet, il est plus grand !) et ne change pas du tout lorsqu'il est refermé.

Si nous écrivons formellement ce qui vient d’être dit, nous obtenons :

F(S) ? F + (S), [F + (S)] + =F + (S);

De plus, de la vérité prouvée (c'est-à-dire la légalité, la légalité) des règles d'inférence d'Armstrong et de la définition de la fermeture, il s'ensuit que toute relation qui satisfait aux contraintes d'un ensemble donné de dépendances fonctionnelles satisfera à la contrainte de dépendance appartenant à la fermeture. .

X > Oui ? F + (S) ? ?r(S) [inv. <F(S)> r(S) ? inv. Y> r(S)];

Ainsi, le théorème d'exhaustivité d'Armstrong pour le système de règles d'inférence stipule que l'implication externe peut être remplacée de manière tout à fait légitime et justifiée par l'équivalence.

(Nous ne considérerons pas la preuve de ce théorème, puisque le processus de preuve lui-même n'est pas si important dans notre cours magistral spécifique.)