Рекорд (информатика)
 | Эта статья нуждается в дополнительных цитатах для проверки . ( сентябрь 2021 г. ) |
В информатике запись , возможно , (также называемая структурой , структурой или составным типом данных ) представляет собой составную структуру данных — набор полей разных типов данных , обычно фиксированных по количеству и последовательности. [1]
Например, дата может храниться как запись, содержащая числовое поле года , поле месяца , представленное в виде строки, и числовое поле дня месяца . Запись окружности может содержать числовой радиус и центр , который представляет собой запись точки , содержащую координаты x и y .
Известные приложения включают языка программирования тип записи и для хранения на основе строк данные, организованные в виде последовательности записей, таких как таблица базы данных , электронная таблица или файл со значениями, разделенными запятыми (CSV). Как правило, значение типа записи хранится в памяти , а хранилище на основе строк — в запоминающем устройстве .
Тип записи — это тип данных , который описывает такие значения и переменные. Большинство современных языков программирования позволяют программисту определять новые типы записей. Определение включает указание типа данных каждого поля и идентификатора (имени или метки), по которому к нему можно получить доступ. В теории типов типы продуктов (без имен полей) обычно отдаются предпочтение из-за их простоты, но подходящие типы записей изучаются на таких языках, как System F-sub . Поскольку теоретико-типические записи могут содержать первоклассные поля с функциональными помимо данных типами, они могут выражать многие особенности объектно-ориентированного программирования .
Терминология
[ редактировать ]В контексте хранилища, например в базе данных или электронной таблице, запись часто называется строкой , а каждое поле — столбцом . [2] [3] [4] [5]
В объектно-ориентированном программировании объект — это запись, содержащая поля состояния и метода.
Запись похожа на математический кортеж , хотя кортеж может считаться записью, а может и не считаться, и наоборот, в зависимости от соглашений и языка программирования. В том же духе тип записи можно рассматривать как аналог декартова произведения двух или более математических наборов в компьютерном языке или реализацию абстрактного типа продукта на определенном языке.
Запись отличается от массива тем, что элементы записи (поля) определяются определением записи и могут быть гетерогенными, тогда как массив представляет собой набор элементов одного и того же типа. [6]
Параметры функции можно рассматривать вместе как поля записи, а передачу аргументов функции можно рассматривать как присвоение входных параметров полям записи. На низком уровне вызов функции включает запись активации или фрейм вызова , который содержит параметры, а также другие поля, такие как локальные переменные и адрес возврата.
История
[ редактировать ]
Понятие записи можно проследить до различных типов таблиц и регистров, используемых в бухгалтерском учете с давних времен. Современное понятие записей в информатике с полями четко определенного типа и размера уже было неявно заложено в механических калькуляторах XIX века, таких как Бэббиджа аналитическая машина . [7] [8]
Первоначальным машиночитаемым носителем данных (в отличие от контрольного) была перфокарта, использовавшаяся для записей переписи населения США 1890 года : каждая перфокарта представляла собой отдельную запись. Сравните запись в журнале 1880 года и перфокарту 1895 года. Записи были широко распространены в первой половине 20-го века, когда большая часть обработки данных выполнялась с использованием перфокарт. Обычно каждая запись файла данных записывается на одну перфокарту, причем определенным полям присваиваются определенные столбцы. Как правило, запись представляла собой наименьшую единицу, которую можно было прочитать из внешнего хранилища (например, устройства чтения карт, ленты или диска). Содержимое записей в виде перфокарт изначально называлось «единичными записями», поскольку перфокарты имели заранее определенную длину документа. [9] Когда системы хранения стали более совершенными с использованием жестких дисков и магнитной ленты , записи переменной длины стали стандартом. Запись переменной длины — это запись, у которой размер записи в байтах примерно равен сумме размеров ее полей. Это было невозможно сделать до того, как было изобретено более совершенное оборудование для хранения данных, поскольку все перфокарты должны были соответствовать заранее определенной длине документов, которые мог прочитать компьютер, поскольку в то время карты нужно было физически вводить в машину.
Большинство машинного языка реализаций и ранние языки ассемблера не имели специального синтаксиса для записей, но эта концепция была доступна (и широко использовалась) благодаря использованию индексных регистров , косвенной адресации и самомодифицирующегося кода . Некоторые ранние компьютеры, такие как IBM 1620 , имели аппаратную поддержку для разграничения записей и полей, а также специальные инструкции для копирования таких записей.
Концепция записей и полей была центральной в некоторых ранних утилитах сортировки файлов и табулирования , таких как Report Program Generator (RPG) от IBM .
COBOL был первым широко распространенным языком программирования , поддерживающим типы записей. [10] и его возможности определения записей были довольно сложными в то время. Язык позволяет определять вложенные записи с буквенно-цифровыми, целочисленными и дробными полями произвольного размера и точности, а также поля, которые автоматически форматируют любое присвоенное им значение (например, вставку знаков валюты, десятичных точек и разделителей групп цифр). Каждый файл связан с переменной записи, в которую данные считываются или записываются. COBOL также предоставляет MOVE CORRESPONDING оператор, который присваивает соответствующие поля двух записей в соответствии с их именами.
Ранние языки, разработанные для числовых вычислений, такие как FORTRAN (вплоть до FORTRAN IV ) и ALGOL 60 , не поддерживали типы записей; но более поздние версии этих языков, такие как FORTRAN 77 и ALGOL 68, добавили их. В исходном языке программирования Lisp также отсутствовали записи (за исключением встроенной cons-ячейки ), но его S-выражения представляли собой адекватный суррогат. Язык программирования Паскаль был одним из первых языков, в котором типы записей полностью интегрировались с другими базовыми типами в логически согласованную систему типов. Язык PL/I обеспечивает записи в стиле COBOL. Язык C предоставляет концепцию записи, используя structс. Большинство языков, разработанных после Паскаля (таких как Ada , Modula и Java ), также поддерживают записи.
Хотя записи больше не часто используются в их исходном контексте (т.е. используются исключительно для целей хранения данных), записи повлияли на новые объектно-ориентированные языки программирования и реляционными базами данных системы управления . Поскольку записи обеспечивают большую модульность в способах хранения и обработки данных, они лучше подходят для представления сложных, реальных концепций, чем примитивные типы данных, предусмотренные в языках по умолчанию. Это повлияло на более поздние языки, такие как C++ , Python , JavaScript и Objective-C , которые удовлетворяют те же потребности модульности программирования. [11] Объекты в этих языках по сути представляют собой записи с добавлением методов и наследования , которые позволяют программистам манипулировать поведением данных, а не только содержимым записи. Многие программисты сейчас считают записи устаревшими, поскольку объектно-ориентированные языки обладают возможностями, намного превосходящими возможности записей. С другой стороны, многие программисты утверждают, что низкие накладные расходы и возможность использования записей на языке ассемблера делают записи по-прежнему актуальными при программировании с низким уровнем абстракции . Сегодня самые популярные языки в индексе TIOBE , показателе популярности языков программирования, в той или иной степени подверглись влиянию рекордов из-за того, что они объектно-ориентированы. [12] Языки запросов, такие как SQL и язык запросов к объектам, также находились под влиянием концепции записей. Эти языки позволяют программисту хранить наборы данных, которые по сути являются записями, в таблицах. [13] Эти данные затем можно получить с помощью первичного ключа . Сами таблицы также являются записями, которые могут иметь внешний ключ : ключ, ссылающийся на данные в другой таблице.
Тип записи
[ редактировать ]Операции
[ редактировать ]Операции для типа записи включают в себя:
- Объявление типа записи, включая положение, тип и (возможно) имя каждого поля.
- Декларация рекорда; переменная, типизированная как тип записи
- Строительство рекордной стоимости; возможно, с инициализацией значения поля
- Чтение и запись значения поля записи
- Сравнение двух записей на равенство
- Вычисление стандартного хэш-значения для записи
Некоторые языки предоставляют возможности перечисления полей записи. Это средство необходимо для реализации определенных служб, таких как отладка , сборка мусора и сериализация . Это требует некоторой степени полиморфизма типов .
В контекстах, поддерживающих подтипирование записей, операции включают добавление и удаление полей записи. Определенный тип записи подразумевает наличие определенного набора полей, но значения этого типа могут содержать дополнительные поля. Таким образом, запись с полями x , y и z будет принадлежать к типу записей с полями x и y , как и запись с полями x , y и r . Смысл в том, что передача записи ( x , y , z ) функции, которая ожидает запись ( x , y ) в качестве аргумента, должна работать, поскольку эта функция найдет все необходимые поля в записи. Многие способы практической реализации записей в языках программирования могут столкнуться с трудностями при разрешении такой изменчивости, но этот вопрос является центральной характеристикой типов записей в более теоретическом контексте.
Присвоение и сравнение
[ редактировать ]Большинство языков допускают присваивание между записями, которые имеют одинаковый тип записи (включая одинаковые типы полей и имена в одном и том же порядке). Однако в зависимости от языка два типа данных записи, определенные отдельно, могут рассматриваться как разные типы, даже если они имеют одинаковые поля.
Некоторые языки также могут разрешать присваивание между записями, поля которых имеют разные имена, сопоставляя каждое значение поля с соответствующей переменной поля по их позициям в записи; так что, например, комплексное число с полями, называемыми real и imag может быть назначен переменной записи 2D-точки с полями X и Y. В этом альтернативном варианте два операнда по-прежнему должны иметь одинаковую последовательность типов полей. Некоторые языки также могут требовать, чтобы соответствующие типы имели одинаковый размер и кодировку, чтобы всю запись можно было назначить как неинтерпретируемую битовую строку . Другие языки могут быть более гибкими в этом отношении и требуют только того, чтобы каждое поле значения могло быть законно присвоено соответствующему полю переменной; так что, например, короткое целочисленное поле можно назначить длинному целочисленному полю или наоборот.
Другие языки (например, COBOL ) могут сопоставлять поля и значения по их именам, а не по позициям.
Эти же возможности применимы и к сравнению двух значений записи на равенство. Некоторые языки также могут позволять сравнивать порядок ('<' и '>'), используя лексикографический порядок, основанный на сравнении отдельных полей. [ нужна ссылка ]
PL/I допускает оба предыдущих типа присваивания, а также допускает структурные выражения , такие как a = a+1; где «a» — запись или структура в терминологии PL/I.
Выбор распределительного поля Алгола 68
[ редактировать ]В Алголе 68, если Pts представлял собой массив записей, каждая из которых имела целочисленные поля X и Y, можно было бы написать Y of Pts получить массив целых чисел, состоящий из Y поля всех элементов Pts. В результате заявления Y of Pts[3] := 7 и (Y of Pts)[3] := 7 будет иметь тот же эффект.
Утверждение «с» Паскаля
[ редактировать ]В Паскале команда with R do S выполнит последовательность команд S как будто все поля записи R были объявлены как переменные. Подобно вводу другого пространства имен в объектно-ориентированном языке, таком как C# , больше нет необходимости использовать имя записи в качестве префикса для доступа к полям. Итак, вместо того, чтобы писать Pt.X := 5; Pt.Y := Pt.X + 3 можно было бы написать with Pt do begin X := 5; Y := X + 3 end.
Представление в памяти
[ редактировать ]Представление записи в памяти варьируется в зависимости от языка программирования. Часто поля хранятся в последовательных ячейках памяти в том же порядке, в котором они объявлены в типе записи. Это может привести к тому, что два или более полей будут сохранены в одном слове памяти; действительно, эта функция часто используется в системном программировании для доступа к определенным битам слова. С другой стороны, большинство компиляторов добавляют поля заполнения, в основном невидимые для программиста, чтобы соответствовать ограничениям выравнивания, налагаемым машиной — скажем, поле с плавающей запятой должно занимать одно слово.
Некоторые языки могут реализовать запись как массив адресов, указывающих на поля (и, возможно, на их имена и/или типы). Объекты в объектно-ориентированных языках часто реализуются довольно сложными способами, особенно в языках, допускающих множественное наследование классов .
Самоопределяющиеся записи
[ редактировать ]Самоопределяющаяся запись — это тип записи, который содержит информацию для идентификации типа записи и поиска информации внутри записи. Он может содержать смещения элементов; поэтому элементы могут храниться в любом порядке или могут быть опущены. [14] Информация, хранящаяся в самоопределяющейся записи, может интерпретироваться как метаданные для записи, что аналогично тому, что можно было бы ожидать найти в UNIX метаданных о файле, содержащих такую информацию, как время создания записи и размер записи. в байтах . Альтернативно, различные элементы записи, каждый из которых включает идентификатор элемента, могут просто следовать друг за другом в любом порядке.
Ключевое поле
[ редактировать ]Запись, особенно в контексте хранения на основе строк, может включать ключевые поля, позволяющие индексировать записи коллекции. Первичный ключ уникален для всех хранимых записей; существует только один из этих ключей. [15] Другими словами, ни для одного первичного ключа не может существовать дубликат. Например, файл сотрудника может содержать номер сотрудника, имя, отдел и зарплату. Номер сотрудника будет уникальным в организации и будет первичным ключом. В зависимости от носителя и организации файлов номер сотрудника может быть проиндексирован — он также сохраняется в отдельном файле, чтобы ускорить поиск. Код отдела не обязательно уникален; он также может быть проиндексирован, и в этом случае он будет считаться вторичным ключом или альтернативным ключом . [16] Если он не проиндексирован, придется сканировать весь файл сотрудников, чтобы получить список всех сотрудников определенного отдела. Ключи обычно выбираются таким образом, чтобы свести к минимуму вероятность реального сопоставления нескольких значений с помощью одного ключа. Например, поле «Зарплата» обычно не считается пригодным для использования в качестве ключа, поскольку многие сотрудники, скорее всего, будут иметь одинаковую зарплату.
См. также
[ редактировать ]- Блок (хранилище данных) – последовательность битов или байтов максимально заданного размера.
- Составной тип данных – любой тип данных, который может быть создан в программе с использованием примитивных типов данных языка программирования и других составных типов.
- Иерархия данных – систематическая организация данных в иерархической форме, показывающая отношения между более мелкими и более крупными компонентами.
- Композиция объектов - метод компьютерного программирования формирования типов объектов более высокого уровня.
- Пассивная структура данных – еще один термин для записи
- Тип объединения — тип данных, который допускает значения, которые являются одним из нескольких различных типов данных.
Ссылки
[ редактировать ]- ^ Феллейзен, Матиас (2001). Как разрабатывать программы . С Прессой. стр. 53 , 60. ISBN. 978-0262062183 .
- ^ «Определения словаря информатики» . Студенты-компьютерщики . Проверено 22 января 2018 г.
- ^ Радвани, Тибор (2014). Системы управления базами данных . Колледж Кароя Эстерхази. п. 19. Архивировано из оригинала 23 сентября 2018 г. Проверено 23 сентября 2018 г.
- ^ Кахате, Атул (2006). Введение в системы управления базами данных . Пирсон. п. 3. ISBN 978-81-317-0078-5 . Проверено 23 сентября 2018 г.
- ^ Коннолли, Томас (2004). Решения для баз данных: пошаговое руководство по созданию баз данных (2-е изд.). Пирсон. п. 7 . ISBN 978-0-321-17350-8 .
- ^ Папе, Тобиас; Кириличев Василий; Больц, Карл Фридрих; Хиршфельд, Роберт (13 января 2017 г.). «Структуры данных записи в рэкете: анализ и оптимизация использования» . Обзор прикладных вычислений ACM SIGAPP . 16 (4): 25–37. дои : 10.1145/3040575.3040578 . ISSN 1559-6915 . S2CID 14306162 .
- ^ Бромли, Аллан (октябрь 1998 г.). «Аналитическая машина Чарльза Бэббиджа, 1838 год» . IEEE Анналы истории вычислений . 20 (4): 29–45. дои : 10.1109/85.728228 . S2CID 2285332 . Проверено 23 сентября 2018 г.
- ^ Суэйд, Дорон. «Автоматические вычисления: Чарльз Бэббидж и вычислительный метод» . Резерфордский журнал . Проверено 23 сентября 2018 г.
- ^ Эдвин Д. Рейли; Энтони Ралстон; Дэвид Хеммендингер, ред. (2003). Энциклопедия информатики (4-е изд.). Чичестер, Великобритания: Wiley. ISBN 978-1-84972-160-8 . OCLC 436846454 .
- ^ Себеста, Роберт В. (1996). Концепции языков программирования (Третье изд.). Аддисон-Уэсли Паблишинг Компани, Инк. с. 218 . ISBN 0-8053-7133-8 .
- ^ Ливенс, Гэри Т.; Вейль, Уильям Э. (1990). «Рассуждения об объектно-ориентированных программах, использующих подтипы» . Материалы Европейской конференции по объектно-ориентированному программированию по системам, языкам и приложениям объектно-ориентированного программирования - OOPSLA/ECOOP '90 . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 212–223. дои : 10.1145/97945.97970 . ISBN 0-201-52430-9 . S2CID 46526 .
- ^ «Индекс: Компания по обеспечению качества программного обеспечения» . TIOBE.com . Проверено 01 марта 2022 г.
- ^ «Что такое реляционная база данных (СУБД)?» . Оракул . Проверено 28 февраля 2022 г.
- ^ Краймер, Мартин Р. «Руководство разработчика приложений контроллера ввода-вывода (IOC) EPICS» . Аргоннская национальная лаборатория . Проверено 25 ноября 2015 г.
- ^ «Добавить или изменить первичный ключ таблицы в Access» . support.microsoft.com . Проверено 01 марта 2022 г.
- ^ «Альтернативный ключ — FAQ по Oracle» . www.orafaq.com . Проверено 01 марта 2022 г.