Záznam (počítačová věda) - Record (computer science)

V informatice je záznam (nazývaný také struktura , struktura nebo složená data ) základní datovou strukturou . Záznamy v databázi nebo tabulce se obvykle nazývají " řádky ".

Záznam je sbírka polí , případně různých datových typů, obvykle v pevném počtu a pořadí. Pole záznamu lze také nazývat členy , zejména v objektově orientovaném programování ; pole mohou být také nazývána prvky , ačkoli to riskuje záměnu s prvky kolekce .

Datum může být například uloženo jako záznam obsahující číselné pole roku, pole měsíce reprezentované řetězcem a číselné pole den v měsíci . Personální záznam může obsahovat jméno , plat a hodnost . Záznam kruh může obsahovat střed a poloměr -V tomto případě samotný centrum může být reprezentován jako bod záznamu, který obsahuje x a y souřadnic.

Záznamy se od polí odlišují tím, že jejich počet polí je obvykle pevný, každé pole má název a každé pole může mít jiný typ.

Typ záznamu je datový typ , který popisuje tyto hodnoty a proměnné. Většina moderních počítačových jazyků umožňuje programátorovi definovat nové typy záznamů. Definice zahrnuje určení datového typu každého pole a identifikátor (název nebo štítek), pomocí kterého je možné k němu přistupovat. V teorii typu , typy výrobků (bez názvů polí), jsou obecně výhodné vzhledem ke své jednoduchosti, ale správné typy záznamů jsou studovány v jazycích, jako je systém F-sub . Vzhledem k tomu, že typově teoretické záznamy mohou kromě dat obsahovat také prvotřídní pole typu funkce , mohou vyjadřovat mnoho funkcí objektově orientovaného programování .

Záznamy mohou existovat na jakémkoli paměťovém médiu, včetně hlavní paměti a velkokapacitních paměťových zařízení, jako jsou magnetické pásky nebo pevné disky . Záznamy jsou základní součástí většiny datových struktur, zejména propojených datových struktur . Mnoho počítačových souborů je organizováno jako pole logických záznamů , často kvůli efektivitě seskupené do větších fyzických záznamů nebo bloků .

Parametry funkce nebo procedury lze často považovat za pole záznamové proměnné; a argumenty předané této funkci lze považovat za rekordní hodnotu, která se této proměnné přiřadí v době volání. Také v zásobníku volání, který se často používá k implementaci volání procedur, je každý záznam aktivačním záznamem nebo rámcem volání , který obsahuje parametry procedury a lokální proměnné, zpáteční adresu a další interní pole.

Objekt v objektově orientovaném jazyce je v podstatě záznam, který obsahuje postupy specializované na zpracování tohoto záznamu; a typy objektů jsou zpracováním typů záznamů. Ve většině objektově orientovaných jazyků jsou záznamy pouze speciálními případy objektů a jsou známé jako prosté staré datové struktury (PODS), což je v kontrastu s objekty, které používají funkce OO.

Záznam lze považovat za počítačový analog matematické n -tice , ačkoli n -tice může nebo nemusí být považována za záznam a naopak, v závislosti na konvencích a konkrétním programovacím jazyce. Ve stejném duchu lze na typ záznamu pohlížet jako na analogový počítačový jazyk karteziánského součinu dvou nebo více matematických množin nebo na implementaci abstraktního typu produktu v konkrétním jazyce.

Klíče

Záznam může mít nula nebo více klíčů s. Klíč je pole nebo sada polí v záznamu, která slouží jako identifikátor. Jedinečný klíč se často nazývá primární klíč nebo jednoduše klíč záznamu . Soubor zaměstnance může například obsahovat číslo zaměstnance, jméno, oddělení a plat. Číslo zaměstnance bude v organizaci jedinečné a bude primárním klíčem. V závislosti na paměťovém médiu a organizaci souboru může být indexováno číslo zaměstnance - to je také uloženo v samostatném souboru, aby bylo vyhledávání rychlejší. Kód oddělení nemusí být jedinečný; může být také indexován, v takovém případě by byl považován za sekundární klíč nebo alternativní klíč . Pokud není indexován, bude muset být naskenován celý soubor zaměstnanců, aby se vytvořil seznam všech zaměstnanců v konkrétním oddělení. Pole platů by normálně nebylo považováno za použitelné jako klíč. Indexování je jedním z faktorů zvažovaných při navrhování souboru.

Dějiny

List deníku z roku 1880 sčítání lidu Spojených států , zobrazující tabulková data s řadami dat, každý záznam odpovídající jedné osobě.

Koncept záznamu lze vysledovat k různým typům tabulek a účetních knih používaných v účetnictví od dávných dob. Moderní pojem záznamů v počítačové vědě, s obory přesně definovaného typu a velikosti, byl již implicitní v mechanických kalkulačkách 19. století, jako je Babbage 's Analytical Engine .

Hollerith děrná karta (1895)

Původní strojově čitelné médium používané pro data (na rozdíl od kontroly) byla děrná karta používaná pro záznamy při sčítání lidu Spojených států v roce 1890 : každá děrná karta byla jediným záznamem. Srovnejte zápis do deníku z roku 1880 a děrný štít z roku 1895. Záznamy byly dobře zavedené v první polovině 20. století, kdy byla většina zpracování dat prováděna pomocí děrných štítků. Každý záznam datového souboru by byl obvykle zaznamenán na jednu děrnou kartu, přičemž ke konkrétním polím budou přiřazeny konkrétní sloupce. Záznam byl obecně nejmenší jednotkou, kterou lze přečíst z externího úložiště (např. Čtečky karet, pásky nebo disku).

Většina implementací strojových jazyků a raných jazyků sestavování neměla speciální syntaxi pro záznamy, ale koncept byl k dispozici (a široce se používal) díky použití indexových registrů , nepřímého adresování a kódu , který se sám upravoval . Některé starší počítače, například IBM 1620 , měly hardwarovou podporu pro oddělování záznamů a polí a speciální pokyny pro kopírování takových záznamů.

Koncept záznamů a polí byl ústředním prvkem některých raných utilit pro třídění a tabulování souborů , jako je například IBM Report Program Generator (RPG) .

COBOL byl první rozšířený programovací jazyk na podporu typů záznamů a jeho zařízení pro definování záznamů byla v té době docela propracovaná. Jazyk umožňuje definici vnořených záznamů s alfanumerickými, celočíselnými a zlomkovými poli libovolné velikosti a přesnosti, jakož i pole, která automaticky formátují libovolnou hodnotu, která je jim přiřazena (např. Vkládání znaků měny, desetinných čárek a oddělovačů skupin číslic ). Každý soubor je spojen s proměnnou záznamu, do které se data načítají nebo se z nich zapisuje. COBOL také poskytujeMOVE CORRESPONDINGpříkaz, který přiřazuje odpovídající pole dvou záznamů podle jejich názvů.

Rané jazyky vyvinuté pro numerické výpočty, jako FORTRAN (až FORTRAN IV ) a Algol 60 , neměly podporu pro typy záznamů; ale pozdější verze těchto jazyků, jako FORTRAN 77 a Algol 68, je přidaly . Původní programovací jazyk Lisp také postrádal záznamy (kromě vestavěné buňky Cons ), ale jeho S-výrazy poskytovaly adekvátní náhradu. Pascal programovací jazyk byl jedním z prvních jazyků plně integrovat rekordní typy s jinými základními typy do logicky konzistentního systému typu. PL / I programovací jazyk stanovené evidence COBOL stylu. C programovací jazyk původně poskytla rekordní koncept jako jakési šablony ( struct), která by mohla být položena na horní straně paměťové oblasti, spíše než skutečný typ záznamu dat. Ty byly poskytnuty nakonec ( typedefprohlášením), ale tyto dva pojmy jsou v jazyce stále odlišné. Většina jazyků navržených po Pascalu (například Ada , Modula a Java ) také podporovala záznamy.

Operace

  • Deklarace nového typu záznamu, včetně pozice, typu a (případně) názvu každého pole;
  • Deklarace proměnných a hodnot, které mají daný typ záznamu;
  • Konstrukce rekordní hodnoty z daných hodnot polí a (někdy) s danými názvy polí;
  • Výběr pole záznamu s explicitním názvem;
  • Přiřazení hodnoty záznamu k proměnné záznamu;
  • Porovnání dvou záznamů o rovnosti;
  • Výpočet standardní hodnoty hash záznamu.

Výběr pole ze záznamové hodnoty poskytne hodnotu.

Některé jazyky mohou poskytovat zařízení, která vyjmenovávají všechna pole záznamu nebo alespoň pole, která jsou odkazy. Toto zařízení je potřeba k implementaci určitých služeb, jako jsou debuggery , garbage collectory a serializace . Vyžaduje určitý stupeň typového polymorfismu .

V systémech s podtypováním záznamů mohou operace s hodnotami typu záznamu také zahrnovat:

  • Přidání nového pole do záznamu, nastavení hodnoty nového pole.
  • Odebrání pole ze záznamu.

V takovém nastavení konkrétní typ záznamu znamená, že je k dispozici konkrétní sada polí, ale hodnoty tohoto typu mohou obsahovat další pole. Záznam s poli x , y , a z by tedy patří k typu záznamů s poli x a y , jako by záznam s poli Ix , y , a r . Důvodem je, že předání záznamu ( x , y , z ) funkci, která jako argument očekává záznam ( x , y ), by mělo fungovat, protože tato funkce najde v záznamu všechna požadovaná pole. Mnoho způsobů praktické implementace záznamů v programovacích jazycích by mělo potíže s povolením takové variability, ale věc je ústřední charakteristikou typů záznamů v teoretičtějších kontextech.

Přiřazení a srovnání

Většina jazyků umožňuje přiřazení mezi záznamy, které mají přesně stejný typ záznamu (včetně stejných typů polí a jmen, ve stejném pořadí). V závislosti na jazyce však lze dva samostatné typy záznamů definované samostatně považovat za odlišné typy, i když mají přesně stejná pole.

Některé jazyky mohou také povolit přiřazení mezi záznamy, jejichž pole mají různá jména, odpovídající každé hodnotě pole s odpovídající proměnnou pole podle jejich pozic v záznamu; takže například komplexní číslo s poli s názvem reala imagmohou být přiřazeny k 2D bodového záznamu proměnné s poli Xa Y. V této alternativě musí oba operandy mít stále stejnou posloupnost typů polí. Některé jazyky mohou také vyžadovat, aby odpovídající typy měly stejnou velikost a kódování, takže celý záznam lze přiřadit jako neinterpretovaný bitový řetězec . Jiné jazyky mohou být v tomto ohledu flexibilnější a vyžadují pouze to, aby každé pole hodnoty bylo možné legálně přiřadit k odpovídajícímu poli proměnných; tak, že například krátké celočíselné pole lze přiřadit dlouhému celočíselnému poli nebo naopak.

Jiné jazyky (například COBOL ) se mohou shodovat s poli a hodnotami podle jejich názvů, nikoli s pozicemi.

Tyto stejné možnosti platí pro srovnání dvou rekordních hodnot pro rovnost. Některé jazyky mohou také povolit porovnávání objednávek ('<' a '>') pomocí lexikografického pořadí založeného na srovnání jednotlivých polí.

PL/I umožňuje oba předchozí typy přiřazení a také umožňuje výrazy struktury , například a = a+1;kde „a“ je záznam, nebo strukturu v terminologii PL/I.

Algol 68's distributive field selection

V Algolu 68, pokud Ptsbylo pole záznamů, každý s celočíselnými poli, Xa Ydalo by se zapsat, aby se získalo pole celých čísel, skládající se z polí všech prvků . V důsledku toho prohlášení a bude mít stejný účinek. Y of PtsYPtsY of Pts[3] := 7(Y of Pts)[3] := 7

Pascalovo prohlášení „s“

V programovacím jazyce Pascalwith R do S by příkaz provedl sekvenci příkazů, Sjako by všechna pole záznamu Rbyla deklarována jako proměnné. Místo psaní se tedy Pt.X := 5; Pt.Y := Pt.X + 3dalo psát with Pt do begin X := 5; Y := X + 3 end.

Reprezentace v paměti

Reprezentace záznamů v paměti se liší v závislosti na programovacích jazycích. Pole jsou obvykle uložena v po sobě jdoucích pozicích v paměti, ve stejném pořadí, v jakém jsou deklarována v typu záznamu. To může mít za následek uložení dvou nebo více polí do stejného slova paměti; ve skutečnosti je tato funkce často používána v programování systémů pro přístup ke konkrétním bitům slova. Na druhou stranu většina kompilátorů přidá výplňová pole, která jsou pro programátora většinou neviditelná, aby vyhověla omezením zarovnání uloženým strojem - řekněme, že pole s plovoucí desetinnou čárkou musí zabírat jediné slovo.

Některé jazyky mohou implementovat záznam jako pole adres směřujících na pole (a případně na jejich jména a/nebo typy). Objekty v objektově orientovaných jazycích jsou často implementovány poměrně komplikovanými způsoby, zejména v jazycích, které umožňují dědění ve více třídách .

Vlastní definující záznamy

Self-definovat záznam je druh záznamu, který obsahuje informace potřebné k určení typu záznamu a vyhledávat informace v rámci záznamu. Může obsahovat odsazení prvků; prvky proto mohou být uloženy v libovolném pořadí nebo mohou být vynechány. Alternativně mohou různé prvky záznamu, každý včetně identifikátoru prvku, jednoduše na sebe navazovat v libovolném pořadí.

Příklady

Následující příklady ukázek definic záznamů:

  • 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
  • Jít :
    type Date struct {
        year  int
        month time.Month
        day   int
}
  • Pascal :
    type TDate = record
   Year: Integer;
   Month: 1..12;
   Day: 1..31;
end;
  • Rez :
    struct Date {
    year: u32,
    month: u32,
    day: u32,
}
  • Swift :
    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
  • Standardní ML :
    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 :
    (defstruct Date
  (year  0 :type integer)
  (month 1 :type (integer 1 12))
  (day   1 :type (integer 1 31)))

Viz také

Reference