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

[Mental]

«Базы данных»
3НФ, индексация, хранимые процедуры.
Все остальное от лукавого.

[rockclimber]

пианист
Я не уверен, что правильно понимаю вопрос. Вот выше я дал ссылку - это определения каких-то базовых операций, а вы спрашиваете, не построили ли с их помощью какую-то теорему, напрмер? Типа как теорема Пифагора в геометрии? Нет, такое мне неизвестно. И не думаю, что появится.

Есть немного другой пример. Идея, которая приходит в голову очень часто - сделать абстрактную структуру таблиц. То есть если обычно вы создаете таблицы "Товары", "Клиенты", "Заказы" и т. д., по одной таблице на сущность, то тут вы создаете таблицы "Объекты", "Атрибуты", "Значения" , и в них храните уже все, что угодно. И товары, и клиентов, и заказы, и так далее. Этот класс структур называется EAV (Entity-Attribute-Value), там возможны разные варианты реализации, вплоть до того, что можно обойтись вообще всего одной таблицей. Преимущество такой структуры - гибкость, чтобы добавить новый атрибут к какой-нибудь сущности, вам не нужно менять схему БД, нужно только строку вставить. Практика показала, что это преимущество - единственное, а дальше идут сплошные недостатки. Производительность хромает, а поддержка и отладка превращаются в изощренное наказание. Консенсусное мнение на данный момент заключается в том, что EAV - это антипаттерн.

[пианист]

rockclimber в сообщении #1710691 писал(а):

Вот выше я дал ссылку - это определения каких-то базовых операций, а вы спрашиваете, не построили ли с их помощью какую-то теорему, напрмер? Типа как теорема Пифагора в геометрии?

Да. Или как, скажем, ближе к топику, какой-нибудь критерий LR(k)-овости.

rockclimber в сообщении #1710691 писал(а):

Нет, такое мне неизвестно. И не думаю, что появится.

Ну вот и я так думаю. Слишком уж общее понятие. Трудно выудить что-то полезное.

[brodsky.izya]

пианист в сообщении #1710692 писал(а):

Трудно выудить что-то полезное.

А что Вы ловить хотите? Что подразумеваете под "полезным"?
Это я тому, что пока не увидишь конкретную практическую цель - не будешь знать, как и что надо "удить".

PS Плюс, я тут выше давал цитату Дейкстры. К сожалению, существующие инструменты и сформированные ими подходы, концепции и методологии утверждают, что некоторые цели недостижимы и ловить их не стоит.

[Mysterious Light]

Прошу прощения за возможный оффтоп, но почему в этой теме не обсуждается реляционное исчисление?

Кстати, бывают ли логические системы, которые можно назвать реляционными второго порядка?

[epros]

Mysterious Light в сообщении #1713558 писал(а):

можно назвать

Что это значит? Всякую вещь можно назвать трамваем...

Под "логическими системами" имеется в виду вообще что? Монадическая логика второго порядка - это "логическая система"? В каком смысле её "можно" или "нельзя" назвать "реляционной?

[Mysterious Light]

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

Всякую вещь можно назвать трамваем...
Под "логическими системами" имеется в виду вообще что?

Не надо передёргивать.

Если бы понятие «логической системы» имело формальное определение, как и «второй порядок», и «реляционный», я бы спросил о существовании реляционной логической системы второго порядка.
А поскольку я таких определений не знаю и подозреваю, что их нет (ещё или вовсе), то и вопрос таким образом я задать не могу (и не надо опять передёргивать, мол, можешь, язык не прилипнет, люди и не такую чушь говорят и не краснеют).
С другой стороны, у логиков же есть какой-то предмет изучения, они же имеют хотя бы неформальные представления о том, что можно назвать логической системой, а что — нет. Вот меня и интересует, есть ли среди формальных систем, которые логики могут назвать «логическими реляционными второго порядка» на основе своей профессиональной экспертности или в рамках установленного в научных кругах узусу этих слов.

(Оффтоп)

Какое-то время назад я попытался найти внятное определение понятию система типов.
Оказалось, что есть огромное количество разных систем, которые называются системами типов, и все попытки дать общее определение были очень ограниченными и покрывали очень малый класс из всего разнообразия системы, которые называются «системами типов».
Причём относительно почти всех таких систем у меня нет возражений, и лишь в единице случаев мне хочется сказать «вот эту систему, по моему субъективному взгляду, называть системой типов неоправданно».

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

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

Монадическая логика второго порядка - это "логическая система"? В каком смысле её "можно" или "нельзя" назвать "реляционной?

Я не знаю, потому что не логик.
Могу лишь предположить, что монадическая логика второго порядка является логической системой, причём второго порядка. На это указывает возможность квантификации по предикатам, пусть и с ограничением на тип предиката. Реляционная ли она? Вот вообще не знаю. В первую очередь потому, что не понимаю критерии «реляционности».
Ввиду того, что реляционное исчисление требует явного указания области, по которой пробегает переменная, а (E)MSO, судя по всему, подобных ограничений не накладывает, я бы предположил отрицательный ответ.

Ждём эксперта в логике, который сможет дать ответы на наши вопросы.

[epros]

Mysterious Light в сообщении #1713861 писал(а):

Не надо передёргивать.

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

Mysterious Light в сообщении #1713861 писал(а):

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

Конечно есть. Там должны быть как минимум правила синтаксиса, аксиоматика, правила вывода. А ещё семантика. И в этом смысле монадическая логика второго порядка - это несомненно "логическая система". И ещё вполне внятно можно объяснить, почему она "второго порядка", т.е. к первому порядку не сводится.

Mysterious Light в сообщении #1713861 писал(а):

Реляционная ли она? Вот вообще не знаю. В первую очередь потому, что не понимаю критерии «реляционности».

Я тоже не знаю, потому что тоже не понимаю критерия "реляционности". Во всяком случае, если у нас в синтаксисе появилась возможность употребить выражение с двумя уровнями вложения скобочек, это ещё не говорит о том, что нам необходимо употреблять логику второго порядка. Об этом и была эта тема. Это немножко конкретнее вопроса о том, что как "можно называть".

[Mysterious Light]

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

Там должны быть как минимум правила синтаксиса, аксиоматика, правила вывода. А ещё семантика.

То есть логическая система — это формальная система (с синтаксисом и семантикой), которая содержит аксиоматику и правила вывода, так?

(Пример логической системы)

Получается, что $\lambda$-исчисление может быть представлено в виде логической системы, потому что имеется схема аксиом

$$(\lambda x. M)N \to M[N / x]$$

и схемы правил вывода

$$\frac{M \to M'}{MN \to M'N} \qquad \frac{M \to M'}{NM \to NM'} \qquad \frac{M \to M' \quad M' \to M''}{M \to M''}$$

Правда, для этого потребуется $M\to N$ рассматривать как синтаксическую конструкцию $\lambda$-исчисления, а не метатеории, но это не большая проблема — так делают.

Верно?

(Зачем отдельно задавать семантику)

Вопрос не по теме: зачем нам отдельно задавать семантику языка, если уже есть аксиомы и правила вывода, которые её уже задают аксиоматически?

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

Mysterious Light в сообщении #1713861 писал(а):

Реляционная ли она? Вот вообще не знаю. В первую очередь потому, что не понимаю критерии «реляционности».

Я тоже не знаю, потому что тоже не понимаю критерия "реляционности".

Привет, родственная душа!

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

Об этом и была эта тема.

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

[epros]

Mysterious Light в сообщении #1713894 писал(а):

То есть логическая система — это формальная система (с синтаксисом и семантикой), которая содержит аксиоматику и правила вывода, так?

Ну, можно сказать, что это формальная подсистема. Добавляем сигнатуру теории и прикладную аксиоматику и получаем формальную систему. Логика - это ведь общая часть для некоторого класса теорий.

Mysterious Light в сообщении #1713894 писал(а):

зачем нам отдельно задавать семантику языка, если уже есть аксиомы и правила вывода, которые её уже задают аксиоматически?

Семантика - не про аксиомы и правила вывода, а про интерпретации.

Mysterious Light в сообщении #1713894 писал(а):

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

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