Связь информатики и математики в структурах данных.

[brodsky.izya]

Добрый день.
Помогите, пожалуйста, разобраться.

Преамбула.
"Отношение" является базовым понятием реляционной модели данных. Реляционную МД напрямую связывают с логикой первого порядка.
Например, в таблице

Артикул   Количество
------------------------
Носки     6
Трусы     2

Заголовок (Артикул, Количество) можно рассматривать как предикат, а пары (Носки, 6) и (Трусы, 2) - истинностные высказывания, которые соответствуют этому предикату.

А вот есть более сложная структура данных, например структура какой-нибудь накладной

Покупатель: Вася Батарейкин
Адрес:  Загород
Товары:  
   Артикул  Количество
   ------------------------
   Носки     6
   Трусы     2

ВОПРОС.
Структуру этой накладной можно изобразить следующим образом
(Покупатель, Адрес, Товары(Артикул, Количество) ).

Что это такое? Можно ли сказать, что это предикат второго порядка?

[epros]

Предикат второго порядка - это предикат, аргументами которого могут быть переменные второго порядка. А то, что у Вас написано, это непонятно что.

[Null]

Вы рассматриваете множество как предикат принадлежности этому множеству? Если вы хотите работать с логикой надо аккуратнее.

[epros]

Кстати, если говорить о множествах, то для конечных множеств можно вообще что угодно выразить без переменных, поэтому не нужна не только логика второго порядка, но и логика первого порядка, можно обойтись логикой высказываний. Какой бы уровень вложенности скобочек у Вас ни был.

Но вот если упоминаемыми объектами являются, например, числа, т.е. элементы бесконечного множества, то потребуются предикаты, т.е. такие штуки, у которых может быть переменная в аргументе.

[brodsky.izya]

epros в сообщении #1709607 писал(а):

Предикат второго порядка - это предикат, аргументами которого могут быть переменные второго порядка. А то, что у Вас написано, это непонятно что.

Спасибо, что отвечаете.
Вот я и хочу это понять и как-то назвать. Не то, что хочу, а прямо надо :).
Но у меня нет достаточного образования и/или , возможно, фантазии, что быть уверенным в своих предположениях, поэтому спрашиваю здесь.
Если у Вас найдется время мне ответить, я буду крайне благодарен.
Я понимаю, что такое "отношение" реляционной МД, и как ему соответствует предикат первого порядка - т.е. смысл этого понятия я понял исходя из конкретики. К сожалению, во всех найденных мною текстах, касаемо этой темы, конкретные примеры даются только по предикатам первого порядка - типа //"х выше у", на паре Эверест Арарат дает истину//. Или на примере моей таблички: есть предикат (Артикул, количество) и для пары (Носки, 6) он дает истину - потому что такое случилось в реальном мире.

Но ущучить, что такое предикат второго порядка - на примере тех же Эверестов и Араратов, или на примере носков, количеств, или на любом другом конкретном примере - я не могу, потому что таких примеров просто нет, сразу начинаются обозначения и формулы в которых я терюясь. А я хочу именно ущучить, въехать в смысл. Если бы Вы могли составить пару примеров с использование конкретный цифр, объектов, свойств и т.п. конкретики - это было бы замечательно.

PS Там ктсати написано, что предикат второго порядка, в т.ч. это такой предикат, где аргументом может быть другой предикат. Поэтому то я и спросил, если в общей структуре
(Покупатель, Адрес, Товары(Артикул, Количество) )
один из аргументов является отношением и имеет подструктуру (подчеркнуто), которая соответствует предикату первого порядка, то, может быть всей этой общей структуре соответствует предикат второго порядка?

[Null]

Второй порядок можно сравнить с утверждением про таблицы: Эта номенклатура(товар) не используется. Или про утверждение о любых запросах.

[epros]

brodsky.izya в сообщении #1709693 писал(а):

Я понимаю, что такое "отношение" реляционной МД, и как ему соответствует предикат первого порядка - т.е. смысл этого понятия я понял исходя из конкретики

Отношение в реляционной модели данных это просто таблица. Можно, конечно, каждому столбцу в таблице поставить в соответствие аргумент предиката и считать, что предикат истинный тогда, когда в таблице есть строка, значения всех ячеек в которой равны указанным значениям аргументов. Но это не слабо так притянуто за уши.

brodsky.izya в сообщении #1709693 писал(а):

Или на примере моей таблички: есть предикат (Артикул, количество) и для пары (Носки, 6) он дает истину - потому что такое случилось в реальном мире.

Вопрос в том, когда этот предикат ложный: если в точности такой строки в таблице нет? А если в точности таких строк в таблице больше одной, то это означает, что предикат "более чем истинный"?

brodsky.izya в сообщении #1709693 писал(а):

Но ущучить, что такое предикат второго порядка - на примере тех же Эверестов и Араратов, или на примере носков, количеств, или на любом другом конкретном примере - я не могу, потому что таких примеров просто нет, сразу начинаются обозначения и формулы в которых я терюясь.

Я же сказал, что должна быть возможность подставить в аргумент переменную второго порядка. В логике предикатов весь смысл в переменных. Пока Вы оперируете только константами, логика предикатов Вам не нужна. Вы можете сказать "Сократ смертен" и без использования предикатов, ибо и понятие "Сократ", и понятие "смертен" уникальны, то бишь выражаются константами. Но Вы не можете выразить общее утверждение "Всякий человек смертен" без использования предикатов, ибо понятие "человек" не уникально, т.е. должно представляться не константой, а переменной.

Объекты второго порядка - это то, что имеет собственные аргументы, каковыми могут быть переменные первого порядка. Например, предикат "является человеком" - объект второго порядка, потому что в качестве его аргумента можно подставлять любые объекты первого порядка. Для человеков этот предикат истинный, а для прочих объектов - ложный. Логика первого порядка может работать с объектами второго порядка (предикатами и функциями), но только если они сами по себе - константы (а значит определены сигнатурой теории). Т.е. предикат "является человеком" - уникален, например, он не равен предикату "является птицей".

Потребность в логике второго порядка возникает только тогда, когда мы хотим говорить об объектах второго порядка обобщённо, т.е. как о переменных. Например, известная фраза "Некоторые критики восхищаются только друг другом" требует логики второго порядка только потому, что класс восхищающихся друг другом критиков - неопределённый, т.е. мы его должны выразить как переменную.

Ваш пример, когда Вы пытаетесь трактовать "товар" как объект второго порядка, конечно, интересный, но совершенно не очевидно, что нам для этого потребуется логика второго порядка, ибо "товар" может быть уникальным понятием: другой такой таблицы (со столбцами "артикул" и "количество") в базе больше нет и не будет. А значит, что нам не потребуется переменная второго порядка, значениями которой могут быть как "товар", так и какие-то иные вещи.

[Mikhail_K]

epros в сообщении #1709708 писал(а):

А если в точности таких строк в таблице больше одной

Насколько я знаю, строки в таблице реляционной базы данных не могут дублироваться.

[brodsky.izya]

Mikhail_K в сообщении #1709734 писал(а):

epros в сообщении #1709708 писал(а):

А если в точности таких строк в таблице больше одной

Насколько я знаю, строки в таблице реляционной базы данных не могут дублироваться.

категорически согласен.

Там факт, что носков было отгружено 6 штук, может встречаться во многих местах. А если эти места надо различать, то придется дополнять предикат, например (кому, артикул, кол-во) или (когда, артикул, кол-во), или (номер заказа, артикул, кол-во). Но это уже другой предикат.

[epros]

brodsky.izya в сообщении #1709736 писал(а):

Mikhail_K в сообщении #1709734 писал(а):

epros в сообщении #1709708 писал(а):

А если в точности таких строк в таблице больше одной

Насколько я знаю, строки в таблице реляционной базы данных не могут дублироваться.

категорически согласен.

Конечно нет. Строки не могут дублироваться только если в них обязательно включается уникальный номер (идентификатор, первичный ключ) строки. В общем случае такого требования нет.

brodsky.izya в сообщении #1709736 писал(а):

Там факт, что носков было отгружено 6 штук, может встречаться во многих местах.

Скажу более того, в одном месте может встречаться 6 штук носков, а в другом месте - 8 штук носков. Чтобы такого не происходило в реальной базе товаров, необходимо принимать специальные меры (если заказчику это нужно).

Общее резюме из сказанного таково: Сопоставлять реляционные таблицы логическим предикатам нужно с большой осторожностью.

-- Ср ноя 19, 2025 11:04:17 --

epros в сообщении #1709811 писал(а):

Чтобы такого не происходило в реальной базе товаров, необходимо принимать специальные меры (если заказчику это нужно).

Подсказка:

Используется синтаксис SQL

ALTER TABLE TABLE_NAME ADD PRIMARY KEY (field_name)

[brodsky.izya]

Пока не ущучил, увы.

epros в сообщении #1709708 писал(а):

"понятие человек" не уникально, т.е. должно представляться не константой, а переменной.

Согласен.
Понятие "человек" не уникально. Есть конкретные люди (Вася Батарейкин, Изя Бродский, Сократ, Epros ... и тп) Это множество, домен. Каждый элемент множества уникален среди других элементов.
Точно так же, есть множество городов (Загород, Клин, Москва, Афины.... и т.п)
Множество артикулов (Трусы, Носки, Майки...)
Есть множество чисел.

Это всё описывает нашу предметную область, и в этих множествах перечислены субъекты этой предметной области, то есть то, о чем о мы делаем утверждение.

Реляционному отношению соответствует предикат первого порядка.
Взять, например, предикат (Артикул, кол-во). Пара значений (Носки, 6) дает истину потому, что такая комбинация значений встретилась в какой-то событии, случившейся в предметной области. Причем эта пара значений могла встретится несколько раз в разных событиях. Точно так же могла встретилась пара (Трусы, 2). А пара значений (Носки, 7) не встретилась ни разу, поэтому такая пара дает ложь.

О каких событиях мы говорим? Об отгрузках. Они могут быть охарактеризованы предикатом (Покупатель, Адрес, Товары). Значения первых двух атрибутов определены на доменах "Люди" и Города", а значение третьего атрибутов представляет собой значение отношения, определенного на доменах "Артикул" и "Кол-во".

Возьмем 3 разные отгрузки

Покупатель: Вася Батарейкин
Адрес:  Загород
Товары: 
   Артикул  Количество
   ------------------------
   Носки     6
   Трусы     2

Покупатель: Изя Бродский
Адрес:  Клин
Товары: 
   Артикул  Количество
   ------------------------
   Носки     6
   Трусы     2

Покупатель: Сократ
Адрес:  Афины
Товары: 
   Артикул  Количество
   ------------------------
   Носки     6
   Трусы     4
   майки     1

У каждой отгрузки свое значение атрибута "Товары". У первых двух отгрузок это значение совершенно одинаковые, у третьей - другое. При этом, во всех трех отгрузках есть кортеж "Носки, 6".

Значения атрибута "Товары" (а это значений отношения) в каждом случае формируется одним и тем же предикатом (Артикул, Кол-во), но истинность пар значения разная для разных отгрузок. Во всех трех отгрузках пара (Носки, 6) дает истину. В первых двух отгрузок истину даст и пара (Трусы, 2) , но в третьей эта пара даст ложь. В первых двух отгрузок истину дают два разных кортежа , в третьей - три. В каждом случае, все разные кортежи, которые дают истину, формируют табличное значение атрибута "Товары".

epros писал(а):

Потребность в логике второго порядка возникает только тогда, когда мы хотим говорить об объектах второго порядка обобщённо, т.е. как о переменных.

КМК здесь именно тот случай, когда предикат (Артикул, кол-во) в каждом случае формирует разное значение атрибута "Товары", т.е. он ведет себя как переменная.

PS

epros писал(а):

Строки не могут дублироваться только если в них обязательно включается уникальный номер (идентификатор, первичный ключ) строки. В общем случае такого требования нет.

В реляционной модели данных кортежи уникальны по определению. Поэтому логика предикатов вполне точно сопоставима реляционной модели.
В этом смысле SQL с его таблицами явно нарушает реляционную модель.

[epros]

brodsky.izya в сообщении #1710056 писал(а):

Реляционному отношению соответствует предикат первого порядка.

Может соответствует, а может нет. Всё зависит от того, как определено соответствие.

Таблицу "товар", например, можно понимать как "имеющееся на складе" или как "входящее в конкретную отгрузку", или каким-то третьим образом. В первом случае, очевидно, нужно будет установить первичный ключ на поле "артикул", чтобы на складе не оказалось одновременно и 6, и 8 одних и тех же носков. Во втором случае, очевидно, в таблицу нужно добавить отдельное поле, идентифицирующее отгрузку, на которое будет установлен первичный ключ. Тогда в одной отгрузке может оказаться 2 трусов, а в другой отгрузке - 4 трусов.

brodsky.izya в сообщении #1710056 писал(а):

О каких событиях мы говорим? Об отгрузках. Они могут быть охарактеризованы предикатом (Покупатель, Адрес, Товары). Значения первых двух атрибутов определены на доменах "Люди" и Города", а значение третьего атрибутов представляет собой значение отношения, определенного на доменах "Артикул" и "Кол-во".

Вообще-то это довольно корявенько. Я бы определил:
1) Таблицу "отгруженные товарные позиции" полями: идентификатор позиции (первичный ключ), отгрузка (внешний ключ), артикул товара (внешний ключ), количество товара.
2) Таблицу "отгрузка" полями: идентификатор отгрузки (первичный ключ), покупатель (внешний ключ), дата и время.
3) Таблицу "покупатель" полями: ФИО, адрес, иные необходимые идентифицирующие данные (первичный ключ на все поля).
4) Таблицу "товар" полями: артикул (первичный ключ), дополнительное описание.
Чтобы увидеть содержание конкретной отгрузки, нужно выполнить select, указав в условии идентификатор отгрузки, а в списке полей: ФИО (из таблицы "покупатель"), адрес (из таблицы "покупатель"), дата и время (из таблицы "отгрузка"), артикул (из таблицы "товар"), количество (из таблицы "отгруженные товарные позиции"). Будет сформирована таблица, в которой для каждого артикула товара и его количества в данной отгрузке будет предусмотрена отдельная строка.

Так что количество товаров в отгрузке, например, вообще не принадлежит таблице "товар", но через идентификатор конкретной отгрузки привязывается к артикулу.

brodsky.izya в сообщении #1710056 писал(а):

КМК здесь именно тот случай, когда предикат (Артикул, кол-во) в каждом случае формирует разное значение атрибута "Товары", т.е. он ведет себя как переменная.

Я вообще не понимаю, что такое "предикат (Артикул, кол-во)".

brodsky.izya в сообщении #1710056 писал(а):

В реляционной модели данных кортежи уникальны по определению. Поэтому логика предикатов вполне точно сопоставима реляционной модели.
В этом смысле SQL с его таблицами явно нарушает реляционную модель.

Вообще не понимаю, откуда Вы это взяли. Реляционная модель данных достаточно гибкая для того, чтобы допускать таблицы с любой структурой, включая дублирование строк. И это отражено именно в языке SQL.

Если Вы придумали это требование именно для того, чтобы таблицы однозначно определяли логические предикаты, то пожалуйста. Однако очень странно утверждать, например, что отсутствие в таблице "товар" строчки с артикулом "носки" означает объективное отсутствие носков "в реальном мире": сегодня строчки нет в таблице, а завтра она появится, а послезавтра опять исчезнет.

[epros]

brodsky.izya, если Вас интересует логика второго порядка, то вот Вам задача на неё. Рассмотрим то самое утверждение Гича-Каплана. Пусть у нас есть таблицы:
1) "критики" с единственным полем: ФИО (первичный ключ).
2) "восхищается" с двумя полями: кто (внешний ключ), кем (внешний ключ) (на оба поля ставим первичный ключ, так что строки не дублируются).

В Вашей логике первая таблица определяет унарный предикат "являться критиком", а вторая - бинарный предикат "восхищается" (определяет, кто из критиков кем восхищается)

Выберите все сообщества критиков, в которых каждый из членов восхищается всеми теми и только теми критиками, которые принадлежат к этому сообществу. Сможете сформировать выборку запросом на языке SQL?

Замечу, что предикат "является сообществом критиков" как раз и является предикатом второго порядка.

[brodsky.izya]

epros в сообщении #1710071 писал(а):

Вообще-то это довольно корявенько. Я бы определил:

Это тоже довольно корявенько. Я не спрашиваю, как создаать схему конкретной БД, как нормализовать данные, какие функциональные зависимотси и т.п. вещи, относящиеся к теории реляционных баз данных. Я спрашиваю о предикатах, а именно, можно ли соотнести ненормализованную схему (пример я дал) с предикатом второго порядка.

epros в сообщении #1710071 писал(а):

Вообще не понимаю, откуда Вы это взяли. Реляционная модель данных достаточно гибкая для того, чтобы допускать таблицы с любой структурой, включая дублирование строк. И это отражено именно в языке SQL.

Я это взял из статей Кодда, из книг Дейта и монографии Давида Мейера. Если угодно, я это взял из определения понятия "множество" в том смысле, что каждый элемент множества отличается от другого. В отношении не может быть повторяющихся кортежей по умолчанию. Например тот же Мейер определяет отношение приблизительно как типа "множество отображения из множества атрибутов на множество доменов". В практических реализациях реляционной модели, типа SQL-таблиц - может, поэтому для реализация обычно пишут "обязателен первичный и др ключи", а в SQL даже это не обязательно, поэтому там допускается дублирование.
Писать про реляционную модель "допускает дублирование строк", это такая же фигня, как написать про арифметику, что в ней не может быть цифр больше 2^16 основываясь на опыте общения с примитивным калькулятором.

epros в сообщении #1710080 писал(а):

Пусть у нас есть таблицы:

Да не хочу я говорить про таблицы. Я в них давно ковырюсь, есть статейки на эту тему в "Открытых системах", на Citforum, в Scitepress, Academia.org и тп. Судя по всему, вряд ли Вы сможете открыть мне что то новое.
Я просто не могу ущучить, что такое предикат второго порядка. И у меня есть опасения... если Вы в предикатах 2-го порядка такой же специалист, как в реляционной модели, то лучше не надо. В любом случае, Спасибо Вам за попытку. Всего Вам хорошего.

-- 21.11.2025, 15:04 --

epros в сообщении #1710071 писал(а):

Я вообще не понимаю, что такое "предикат (Артикул, кол-во)".

Есть какой то массив данных, определенный на доменах, которые описаны выше. Все равно, нормализованной структуры или нет. В любом случае, когда мы будем смотреть, какие пары значений (Артикул, кол-во) дают истину, то, для моего последнего примера где три отгрузки, это будет

   Артикул  Количество
   ------------------------е
   Носки     6
   Трусы     2
   Трусы     4
   майки     1

некоторые кортежи встречались во всех трех отгрузках, некоторые - в 2х, некоторые - только в 1-й. Эта информация здесь (в этом результате) уже потеряна, остался просто факт, что например носков отгружалось 6 штук и никак иначе.
Но это - если рассматривать его как предикат первого порядка, то есть как предикат, накладываемый на весь массив данных. Но если этот предикат использовать как ....мммм..... характеристику атрибуты "Товары" в отдельных отгрузках, то он там в каждой отгрузке даст что-то свое.

[epros]

brodsky.izya в сообщении #1710089 писал(а):

Я спрашиваю о предикатах, а именно, можно ли соотнести ненормализованную схему (пример я дал) с предикатом второго порядка.

Я уже Вам сказал, что с предикатами соотнести можно, только вопрос в смысле этого соотнесения. Вы этот смысл не сформулировали, а хотите чтобы Вам ответили, второго ли порядка предикат.

brodsky.izya в сообщении #1710089 писал(а):

Я это взял из статей Кодда, из книг Дейта и монографии Давида Мейера.

brodsky.izya в сообщении #1710089 писал(а):

Писать про реляционную модель "допускает дублирование строк", это такая же фигня, как написать про арифметику, что в ней не может быть цифр больше 2^16 основываясь на опыте общения с примитивным калькулятором.

Я не знаю, кто там как ухитряется определить "реляционную модель данных" таким образом, что строки не могут дублироваться, но если у нас в этой "модели" есть "отношение":
Артикул, Количество
(носки, 6)
(трусы, 6)
(строки не дублируются), а потом мы вдруг делаем из него выборку:
SELECT Количество FROM Товар WHERE Количество = 6,
то в этом новом "отношении" строки внезапно начинают дублироваться.
И как Вы с этим собираетесь иметь дело в рамках Вашего определения "реляционной модели данных"?

brodsky.izya в сообщении #1710089 писал(а):

Я просто не могу ущучить, что такое предикат второго порядка.

Решите задачку из моего предыдущего сообщения и ущучите. Я же Вам сказал, что предикат "является сообществом критиков" - это типичный пример предиката второго порядка.

brodsky.izya в сообщении #1710089 писал(а):

И у меня есть опасения... если Вы в предикатах 2-го порядка такой же специалист, как в реляционной модели, то лучше не надо.

А у меня такое опасение, что Вы не пытаетесь разобраться, а начинаете троллить. Вам уже сказали, что Вы не сформулировали чётко вопрос. Если Вы действительно хотите понять, что такое предикат второго порядка, то не нужно начинать с того, что "вот здесь у меня выражение с двумя уровнями вложения скобочек, могу ли я считать, что это - предикат второго порядка?".