Record (informatique) - Record (computer science)

En informatique , un enregistrement (également appelé structure , struct ou données composées ) est une structure de données de base . Les enregistrements d'une base de données ou d'une feuille de calcul sont généralement appelés « lignes ».

Un enregistrement est un ensemble de champs , éventuellement de différents types de données, généralement dans un nombre et une séquence fixes. Les champs d'un enregistrement peuvent également être appelés membres , notamment en programmation orientée objet ; les champs peuvent aussi être appelés éléments , bien que cela risque de se confondre avec les éléments d' une collection .

Par exemple, une date peut être stockée sous forme d'enregistrement contenant un champ d' année numérique , un champ de mois représenté sous forme de chaîne et un champ de jour du mois numérique . Un dossier personnel peut contenir un nom , un salaire et un grade . Un enregistrement Circle peut contenir un centre et un rayon — dans ce cas, le centre lui-même peut être représenté comme un enregistrement de point contenant les coordonnées x et y .

Les enregistrements se distinguent des tableaux par le fait que leur nombre de champs est généralement fixe, que chaque champ a un nom et que chaque champ peut avoir un type différent.

Un type d'enregistrement est un type de données qui décrit de telles valeurs et variables. La plupart des langages informatiques modernes permettent au programmeur de définir de nouveaux types d'enregistrements. La définition comprend la spécification du type de données de chaque champ et d'un identifiant (nom ou étiquette) permettant d'y accéder. Dans la théorie des types , les types de produits (sans nom de champ) sont généralement préférés en raison de leur simplicité, mais les types d'enregistrement appropriés sont étudiés dans des langages tels que System F-sub . Étant donné que les enregistrements de type théorique peuvent contenir des champs de type fonction de première classe en plus des données, ils peuvent exprimer de nombreuses caractéristiques de la programmation orientée objet .

Les enregistrements peuvent exister sur n'importe quel support de stockage, y compris la mémoire principale et les périphériques de stockage de masse tels que les bandes magnétiques ou les disques durs . Les enregistrements sont un composant fondamental de la plupart des structures de données, en particulier des structures de données liées . De nombreux fichiers informatiques sont organisés sous forme de tableaux d' enregistrements logiques , souvent regroupés en enregistrements physiques ou en blocs plus importants pour plus d'efficacité.

Les paramètres d'une fonction ou d'une procédure peuvent souvent être considérés comme les champs d'une variable d'enregistrement ; et les arguments passés à cette fonction peuvent être considérés comme une valeur d'enregistrement qui est affectée à cette variable au moment de l'appel. De plus, dans la pile d'appels souvent utilisée pour implémenter des appels de procédure, chaque entrée est un enregistrement d'activation ou une trame d'appel , contenant les paramètres de procédure et les variables locales, l'adresse de retour et d'autres champs internes.

Un objet en langage orienté objet est essentiellement un enregistrement qui contient des procédures spécialisées pour gérer cet enregistrement ; et les types d'objets sont une élaboration de types d'enregistrements. En effet, dans la plupart des langages orientés objet, les enregistrements ne sont que des cas particuliers d'objets et sont connus sous le nom de structures de données anciennes (PODS), pour contraster avec les objets qui utilisent des fonctionnalités OO.

Un enregistrement peut être considéré comme l'analogue informatique d'un tuple mathématique , bien qu'un tuple puisse ou non être considéré comme un enregistrement, et vice versa, selon les conventions et le langage de programmation spécifique. Dans la même veine, un type d'enregistrement peut être considéré comme l'analogue en langage informatique du produit cartésien de deux ou plusieurs ensembles mathématiques , ou la mise en œuvre d'un type de produit abstrait dans un langage spécifique.

Clés

Un enregistrement peut avoir zéro ou plusieurs clés . Une clé est un champ ou un ensemble de champs dans l'enregistrement qui sert d'identifiant. Une clé unique est souvent appelée clé primaire ou simplement clé d'enregistrement . Par exemple, un fichier d'employé peut contenir le numéro, le nom, le service et le salaire de l'employé. Le numéro d'employé sera unique dans l'organisation et constituera la clé primaire. Selon le support de stockage et l'organisation des fichiers, le numéro d'employé peut être indexé, qui est également stocké dans un fichier séparé pour accélérer la recherche. Le code départemental peut ne pas être unique ; elle peut également être indexée, auquel cas elle serait considérée comme une clé secondaire , ou une clé alternative . S'il n'est pas indexé, l'ensemble du fichier des employés devra être numérisé pour produire une liste de tous les employés d'un service spécifique. Le champ salaire ne serait normalement pas considéré comme utilisable comme clé. L'indexation est un facteur pris en compte lors de la conception d'un fichier.

Histoire

Feuille de journal du recensement des États-Unis de 1880 , montrant des données tabulaires avec des lignes de données, chacune un enregistrement correspondant à une seule personne.

Le concept d'enregistrement peut être attribué à divers types de tables et de grands livres utilisés en comptabilité depuis des temps reculés. La notion moderne d'enregistrements en informatique, avec des champs de type et de taille bien définis, était déjà implicite dans les calculatrices mécaniques du XIXe siècle, telles que le moteur analytique de Babbage .

Carte perforée Hollerith (1895)

Le support original lisible par machine utilisé pour les données (par opposition au contrôle) était la carte perforée utilisée pour les enregistrements dans le recensement des États-Unis de 1890 : chaque carte perforée était un seul enregistrement. Comparez l'entrée de journal de 1880 et la carte perforée de 1895. Les enregistrements étaient bien établis dans la première moitié du 20e siècle, lorsque la plupart des traitements de données étaient effectués à l'aide de cartes perforées. En règle générale, chaque enregistrement d'un fichier de données serait enregistré sur une seule carte perforée, avec des colonnes spécifiques affectées à des champs spécifiques. Généralement, un enregistrement était la plus petite unité pouvant être lue à partir d'un stockage externe (par exemple, lecteur de carte, bande ou disque).

La plupart des implémentations en langage machine et les premiers langages d'assemblage n'avaient pas de syntaxe spéciale pour les enregistrements, mais le concept était disponible (et largement utilisé) grâce à l'utilisation de registres d'index , d'adressage indirect et de code auto-modifiant . Certains des premiers ordinateurs, tels que l' IBM 1620 , disposaient d'un support matériel pour délimiter les enregistrements et les champs, et d'instructions spéciales pour copier ces enregistrements.

Le concept d'enregistrements et de champs était central dans certains des premiers utilitaires de tri et de tabulation de fichiers , tels que le Report Program Generator (RPG) d'IBM .

COBOL a été le premier langage de programmation répandu à prendre en charge les types d'enregistrement, et ses fonctionnalités de définition d'enregistrement étaient assez sophistiquées à l'époque. Le langage permet la définition d'enregistrements imbriqués avec des champs alphanumériques, entiers et fractionnaires de taille et de précision arbitraires, ainsi que des champs qui formatent automatiquement toute valeur qui leur est attribuée (par exemple, l'insertion de signes monétaires, de points décimaux et de séparateurs de groupes de chiffres ). Chaque fichier est associé à une variable d'enregistrement dans laquelle les données sont lues ou écrites. COBOL fournit également uneMOVE CORRESPONDINGinstruction qui affecte les champs correspondants de deux enregistrements en fonction de leurs noms.

Les premiers langages développés pour l'informatique numérique, tels que FORTRAN (jusqu'à FORTRAN IV ) et Algol 60 , ne prenaient pas en charge les types d'enregistrement ; mais les versions ultérieures de ces langues, telles que FORTRAN 77 et Algol 68 les ont ajoutées. Le langage de programmation Lisp d' origine manquait également d'enregistrements (à l'exception de la contre-cellule intégrée ), mais ses expressions S fournissaient un substitut adéquat. Le langage de programmation Pascal a été l'un des premiers langages à intégrer pleinement les types d'enregistrement avec d'autres types de base dans un système de types logiquement cohérent. Le langage de programmation PL/I fourni pour les enregistrements de style COBOL. Le langage de programmation C a initialement fourni le concept d'enregistrement comme une sorte de modèle ( struct) qui pouvait être placé au-dessus d'une zone de mémoire, plutôt qu'un véritable type de données d'enregistrement. Ces derniers ont été fournis par la suite (par la typedefdéclaration), mais les deux concepts sont toujours distincts dans la langue. La plupart des langages conçus après Pascal (comme Ada , Modula et Java ) prenaient également en charge les enregistrements.

Opérations

  • Déclaration d'un nouveau type d'enregistrement, y compris la position, le type et (éventuellement) le nom de chaque champ ;
  • Déclaration de variables et de valeurs comme ayant un type d'enregistrement donné ;
  • Construction d'une valeur d'enregistrement à partir de valeurs de champs données et (parfois) avec des noms de champs donnés ;
  • Sélection d'un champ d'un enregistrement avec un nom explicite ;
  • Affectation d'une valeur d'enregistrement à une variable d'enregistrement ;
  • Comparaison de deux enregistrements pour l'égalité ;
  • Calcul d'une valeur de hachage standard pour l'enregistrement.

La sélection d'un champ à partir d'une valeur d'enregistrement produit une valeur.

Certaines langues peuvent fournir des fonctionnalités qui énumèrent tous les champs d'un enregistrement, ou au moins les champs qui sont des références. Cette fonction est nécessaire pour implémenter certains services tels que les débogueurs , les ramasse-miettes et la sérialisation . Cela nécessite un certain degré de polymorphisme de type .

Dans les systèmes avec sous-typage d'enregistrement, les opérations sur les valeurs de type d'enregistrement peuvent également inclure :

  • Ajout d'un nouveau champ à un enregistrement, définition de la valeur du nouveau champ.
  • Supprimer un champ d'un enregistrement.

Dans de tels paramètres, un type d'enregistrement spécifique implique qu'un ensemble spécifique de champs est présent, mais les valeurs de ce type peuvent contenir des champs supplémentaires. Un enregistrement avec les champs x , y et z appartiendrait donc au type d'enregistrements avec les champs x et y , tout comme un enregistrement avec les champs x , y et r . La raison en est que passer un enregistrement ( x , y , z ) à une fonction qui attend un enregistrement ( x , y ) comme argument devrait fonctionner, car cette fonction trouvera tous les champs dont elle a besoin dans l'enregistrement. De nombreuses façons d'implémenter des enregistrements dans des langages de programmation auraient du mal à autoriser une telle variabilité, mais la question est une caractéristique centrale des types d'enregistrements dans des contextes plus théoriques.

Affectation et comparaison

La plupart des langues permettent l'affectation entre des enregistrements qui ont exactement le même type d'enregistrement (y compris les mêmes types de champs et noms, dans le même ordre). Selon la langue, cependant, deux types de données d'enregistrement définis séparément peuvent être considérés comme des types distincts même s'ils ont exactement les mêmes champs.

Certaines langues peuvent également autoriser l'affectation entre des enregistrements dont les champs ont des noms différents, en faisant correspondre chaque valeur de champ avec la variable de champ correspondante par leurs positions dans l'enregistrement ; de sorte que, par exemple, un nombre complexe avec des champs appelé realet imagpuisse être affecté à une variable d'enregistrement de point 2D avec des champs Xet Y. Dans cette alternative, les deux opérandes doivent toujours avoir la même séquence de types de champs. Certaines langues peuvent également exiger que les types correspondants aient également la même taille et le même codage, de sorte que l'ensemble de l'enregistrement puisse être affecté en tant que chaîne de bits non interprétée . D'autres langages peuvent être plus flexibles à cet égard et exigent seulement que chaque champ de valeur puisse être légalement affecté au champ variable correspondant ; de sorte que, par exemple, un champ d' entier court peut être affecté à un champ d' entier long , ou vice versa.

D'autres langages (tels que COBOL ) peuvent faire correspondre les champs et les valeurs par leur nom, plutôt que par leur position.

Ces mêmes possibilités s'appliquent à la comparaison de deux valeurs d'enregistrement pour l'égalité. Certaines langues peuvent également permettre des comparaisons d'ordre ('<'et '>'), en utilisant l' ordre lexicographique basé sur la comparaison de champs individuels.

PL/I autorise les deux types d'affectation précédents, ainsi que les expressions de structure , telles que a = a+1;"a" étant un enregistrement, ou une structure dans la terminologie PL/I.

Sélection du champ distributif d'Algol 68

Dans Algol 68, if Ptsétait un tableau d'enregistrements, chacun avec des champs d'entiers Xet Y, on pouvait écrire pour obtenir un tableau d'entiers, composé des champs de tous les éléments de . En conséquence, les déclarations et auraient le même effet. Y of PtsYPtsY of Pts[3] := 7(Y of Pts)[3] := 7

La déclaration "avec" de Pascal

Dans le langage de programmation Pascal , la commande with R do Sexécuterait la séquence de commandes Scomme si tous les champs d'enregistrement Ravaient été déclarés en tant que variables. Ainsi, au lieu d'écrire, Pt.X := 5; Pt.Y := Pt.X + 3on pourrait écrire with Pt do begin X := 5; Y := X + 3 end.

Représentation en mémoire

La représentation des enregistrements en mémoire varie selon les langages de programmation. Habituellement, les champs sont stockés dans des positions consécutives en mémoire, dans le même ordre qu'ils sont déclarés dans le type d'enregistrement. Cela peut entraîner le stockage de deux champs ou plus dans le même mot de mémoire ; en effet, cette fonctionnalité est souvent utilisée dans la programmation système pour accéder à des bits spécifiques d'un mot. D'un autre côté, la plupart des compilateurs ajouteront des champs de remplissage, pour la plupart invisibles pour le programmeur, afin de se conformer aux contraintes d'alignement imposées par la machine, par exemple, qu'un champ à virgule flottante doit occuper un seul mot.

Certains langages peuvent implémenter un enregistrement sous la forme d'un tableau d'adresses pointant vers les champs (et, éventuellement, vers leurs noms et/ou types). Les objets dans les langages orientés objet sont souvent implémentés de manière assez compliquée, en particulier dans les langages qui autorisent l' héritage de plusieurs classes .

Enregistrements auto-définis

Un enregistrement auto-défini est un type d'enregistrement qui contient des informations permettant d'identifier le type d'enregistrement et de localiser les informations dans l'enregistrement. Il peut contenir les décalages d'éléments ; les éléments peuvent donc être stockés dans n'importe quel ordre ou peuvent être omis. Alternativement, divers éléments de l'enregistrement, comprenant chacun un identifiant d'élément, peuvent simplement se succéder dans n'importe quel ordre.

Exemples

Voici des exemples de définitions d'enregistrement :

  • PL/I :
      declare 1 date,
                2 year  fixed binary,
                2 month fixed binary,
                2 day   fixed binary;
    
  • Algol 68 :
  mode date = struct (int year, int month, int day);
  • C :
    struct date {
       int year;
       int month;
       int day;
    };
    
  • Fortran :
    type :: date
       integer :: year, month, day
    end type date
    
  • Allez :
    type Date struct {
            year  int
            month time.Month
            day   int
    }
    
  • Pascale :
    type TDate = record
       Year: Integer;
       Month: 1..12;
       Day: 1..31;
    end;
    
  • Rouille :
    struct Date {
        year: u32,
        month: u32,
        day: u32,
    }
    
  • Rapide :
    struct Date {
        year: Int,
        month: Int,
        day: Int,
    }
    
  • Haskell :
    data Date = Date { year :: Integer
                     , month :: Integer
                     , day :: Integer
                     }
    
  • Julia :
    struct Date
        year::Int
        month::Int
        day::Int
    end
    
  • ML standard :
    type date = {year:int, month:int, day:int}
    
  • COBOL :
           01 WS-DATE.
              02 WS-YEAR  PIC 9999.
              02 WS-MONTH PIC 99.
              02 WS-DAY   PIC 99.
    
  • Java 15 :
    record Date(int year, int month, int day) {
        // this is the minimum required    
    }
    
  • Lisp commun :
    (defstruct Date
      (year  0 :type integer)
      (month 1 :type (integer 1 12))
      (day   1 :type (integer 1 31)))
    

Voir également

Les références