2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Алгебра или формальный язык для нереляционных СУБД
Сообщение31.01.2013, 09:01 


15/04/10
985
г.Москва
Сейчас в основном распостранены реляционные базы данных. Математическое описание их- реляционная алгебра была предложена Коддом в 1972 г. на основе доменов, кортежей, реляционных отношений
Но, как известно до реляционных были и т.н иерархические СУБД. Делались попытки построения сетевых СУБД. Так во ВНИСИ разрабатывалась СУБД ИНЭС.
Сейчас также есть объектные СУБД.
Означает ли это что для каждой из этих типов СУБД можно предложить алгебру или формальный язык описания операций с ними? Если да, что это в математике

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение31.01.2013, 11:16 
Заслуженный участник


09/09/10
3729
eugrita в сообщении #678183 писал(а):
Сейчас в основном распостранены реляционные базы данных.

На самом деле называть их реляционными можно лишь с большой натяжкой. Это табличные СУБД. Если вам интересна именно реляционная теория, советую книгу Дейта "Введение в системы баз данных", издания этак восьмого.

eugrita в сообщении #678183 писал(а):
Но, как известно до реляционных были и т.н иерархические СУБД. Делались попытки построения сетевых СУБД.

Да, и такие структуры проиграли. Потому что сложно и неудобно. Если вы работали с XML, то понимаете: если ваши узлыы не имеют уникальных id, то запросы становятся нереально запутанными, потому что надо бродить по всему дереву, а человек с трудом воспринимает более трех уровней вложенности.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение31.01.2013, 12:28 


10/04/12
704
Первый вопрос, который требует уточнения, это "что такое база данных"?
Цитата:
База данных — представленная в объективной форме совокупность самостоятельных материалов (статей, расчётов, нормативных актов, судебных решений и иных подобных материалов), систематизированных таким образом, чтобы эти материалы могли быть найдены и обработаны с помощью электронной вычислительной машины (ЭВМ).


А теперь СУБД:
Цитата:
Система управления базами данных (СУБД) — совокупность программных и лингвистических средств общего или специального назначения, обеспечивающих управление созданием и использованием баз данных.


Мы видим, что определения настолько общие, что даже HTML-страница может выть рассмотрена как база данных, а jQuery может быть рассмотрено как СУБД. И, соответственно, операции не выглядят настолько уж сложными:
Используется синтаксис Javascript
$("div.test").add("p.quote").addClass("blue").slideDown("slow");



Вопрос, наверное, был связан с современными распространенными СУБД а-ля MySQL, PostgeSQL, Oracle, ..? Тогда уместнее задать вопрос, в каких областях требуется транзакционность, где требуется обработка больших объемов данных? И где клиенты готовы платить деньги? Очевидно, что мы выходим в банковскую сферу, SAP и т. д. и т. п. и др. и пр., где таблицы возникли исторически задолго до этого. А потом все остальные чуть-непохожие задачи просто сводились к этому и все :)

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


А какая связь с математикой? Ну... математика это наука рассуждений. Когда рассуждения становятся очень нетривиальными, желательно иметь способ формализации и возможность решения вопросов в спорных случаях. Например, когда один человек говорит, что он доказал теорему Ферма, а второй не соглашается. Углубляясь в доказательство, мы можем дойти до формального текста, хотя на практике этого обычно не требуется. Все программирование можно легко формализовать при помощи математической нотации. В 70-х годах это казалось важным, компьютерного времени было мало, времени подумать было много. Сейчас на это просто не хватает времени, да и большой пользы во всем этом нет, потому как все вопросы практические, и каких-либо сложных доказательств (рассуждений) там или нет, или уже все сделано.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение31.01.2013, 18:34 


15/04/10
985
г.Москва
[quote=" Если вам интересна именно реляционная теория, советую книгу Дейта "Введение в системы баз данных"./quote]
Да мне интересна реляционная теория но и немного боязна как и вся чистая математика. А для чего она практически используется разработчиками БД или ПО?
А то прослеживается аналогия с обычной алгеброй - для школьников -плотно а в взрослой жизни исчезла, разве что в кодировании или шифровании связанными с полиномами. Т.е. я хочу задачки по реляционной теории но не совсем абстрактные а чтоб была какая-то связь с практикой

-- Чт янв 31, 2013 19:52:15 --

[quote
Но, например, для шахматных баз партий и типичных запросов использование всей этой кухни дает настолько злобный оверхед, что не используется практически нигде. [/quote]
Интересно, интересно. 1 раз слышу о базе шахматных партий . Это что, есть?
Мне интересны задачи на анализ деревьев. Но у шахмат дерево столь развесистое что трудно анализировать. Т.е партии хранятся в БД а потом не спеша анализируются как читателями в библиотеке?

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение31.01.2013, 20:55 
Заслуженный участник


09/09/10
3729
В реляционной теории нет ничего сложного, к тому же, как я уже сказал, современные т.н. "реляционные" СУБД ею не пользуются :wink:

Совсем кратенько: мы описываем нашу область знаний набором предикатов. Например, $S(sid,city,status)=$"Поставщик $sid$ находится в городе $city$ и имеет статус $status$", $P(pid,name,colour)=$"Деталь $pid$ называется $name$ и цвета $colour$", $SP(sid,pid,qty)=$"Поставщик $sid$ поставляет деталь $pid$ в количестве $qty$ штук". Соответственно, когда мы подставляем в предикат кортеж, мы получаем высказывание — истинное или ложное. С каждым предикатом естественно связывается множество (множество истинности), состоящее из всех кортежей, которые при подстановке в предикат дают истинные высказывания, и только из них. Это множество является отношением, в математическом смысле (в реляционной теории, правда, принято определять отношения и кортежи чуть иначе, чем в математике: компоненты не нумеруются, а именуются). Ну вот, и мы храним в БД эти отношения.

Теперь фокус. Рассмотрим предикат $F(sid,city,status,pid,qty)=S(sid,city,status)\wedge SP(sid,pid,qty)=$"Поставщик $sid$ находится в городе $city$, имеет статус $status$ и поставляет деталь $pid$ в количестве $qty$ штук". Как найти его множество истинности? Возьмем множества истинности предикатов $S$ и $SP$ и сделаем операцию $\mathrm{JOIN}$. И все остальные реляционные операции соответствуют каким-то логическим операциям с предикатами. Если нам нужно что-то узнать, мы формулируем запрос в терминах предикатов, соответствующих хранящимся в БД отношениям, автоматически переводим его в выражение реляционной алгебры — и высчитываем по имеющимся отношениям множество истинности интересующего нас запроса.

Все просто. Булева алгебра да логика предикатов — железобетонны.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение01.02.2013, 09:56 


10/04/12
704
eugrita в сообщении #678433 писал(а):
Интересно, интересно. 1 раз слышу о базе шахматных партий . Это что, есть?
Мне интересны задачи на анализ деревьев. Но у шахмат дерево столь развесистое что трудно анализировать. Т.е партии хранятся в БД а потом не спеша анализируются как читателями в библиотеке?


Все просто, есть 5-10 миллионов шахматных партий. По которым выполняется (1) поиск конкретной позиции + статистика по ней (выигрыши, ничьи, поражения, максимальный рейтинг где встречалась, ...) (2) нечеткий поиск по пешечной структуре, материалу; (3) поиск по мотивам, например все партии, где был осуществлен удар Bxh7+ (Bxh2+); (4) хранение анализов. Плюс постоянные обновления.

Тут пример на web такой базы.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение01.02.2013, 15:35 
Заслуженный участник


15/05/05
3445
USA
eugrita в сообщении #678433 писал(а):
Да мне интересна реляционная теория но и немного боязна как и вся чистая математика.
Цаленко М.Ш. "Моделирование семантики в базах данных". 1989
Ничего "математичнее", чем Цаленко, я не встречал. И это не удивительно - он еще написал книгу по теории категорий...

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение05.02.2013, 17:10 


22/01/11
309
Joker_vD в сообщении #678209 писал(а):
На самом деле называть их реляционными можно лишь с большой натяжкой. Это табличные СУБД


:mrgreen: :mrgreen:
Не надо тут народ вводить в заблуждение.

Цитата:
Но, как известно до реляционных были и т.н иерархические СУБД.


Ага, а потом куда-то они внезапно подевались.
Иерархические СУБД - это как раз ad-hoc, они не только существуют по сей день, но и активно используются.
Кроме того, многие известные СУБД являются именно иерархическими в общем виде.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение05.02.2013, 20:25 
Заслуженный участник


09/09/10
3729
Esp_ в сообщении #680324 писал(а):
Ага, а потом куда-то они внезапно подевались.

Угу. У Дейта, кажется, был обзор по истории СУБД. А ныне эту идею снова возрождают (XML, anyone?).

Esp_ в сообщении #680324 писал(а):
Не надо тут народ вводить в заблуждение.

Извините, но это факт. Современные "реляционные" СУБД оперируют таблицами и запросами (да, еще представления, триггеры, хранимые процедуры и пр., но это довески), которые по своим свойствам радикально отличаются от отношений и формул реляционной алгебры/реляционного исчисления. В стандарте SQL вообще ни разу не упоминается реляционность.

Отношение в реляционной теории имеет вполне четкое определение. "Таблицы" в него никак не вписываются: в них упорядочены строки, в них упорядочены столбцы, в них разрешены дублирующиеся строки, в них разрешены столбцы с одинаковыми именами, в них разрешены NULL-метки, в них запрещены столбцы, содержащие отношения. В SQL отсутствует важнейшее свойство реляционной алгебы и реляционного исчисления — замкнутость. Не все запросы можно вкладывать друг в друга, а результаты некоторых невозможно сохранить в таблицу.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение05.02.2013, 22:01 


15/04/10
985
г.Москва
Joker_vD
Я хотел бы преподавать курс Базы Данных.
При анализе программ известных мне курсов по этой дисциплине и связанной с ней "ИС в Экономике" я обратил внимание, что редко доходит до вопросов о cтруктурах реляционных данных, подобно обсуждаемым здесь.
Например, Табличные задания отношений или через n-местный предикат.
Если где и говорится о нормализации таблиц, то без задач для студентов..
Конечно, вопросы настолько обширны что укладываясь в заданное кол-во часов
можно очень по-разному составить программы. Я тем не менее-сторонник теоретического осмысления. Элементы математич.логики начинают изучать еще в школе (хорошей). И именно там ,кажется, надо это проталкивать на уровне информатики.
Вы значит считаете таблицы, как я понял, понятием не тождественным кортежу отношений?
Интересно бы понять и рассказать понятие "транзитивное замыкание" в терминах SQL а не теории отношений и множеств.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение05.02.2013, 23:54 


15/04/10
985
г.Москва
Есть немного разные термины реляционной алгебры. Проследим их
---------------------------------
кортеж=экземпляр сущностей
набор кортеженй -отношение-сущность (табл)
Атрибут-столбец отношений
Связь (Relationship)–ассоциация 2 или более сущностей
---------------------------------------------------------------
Но ведь есть еще в логической(семантической)модели данных понятия
идентифицирующая и неидентифицирубщая связи.
А также типизирующие отношения (включающие и исключающие)
и даже рекурсивная связь.
Они в частности имеют свои нотации в ErWin
Что все это означает на языке алгебры отношений или логики предикатов?

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение06.02.2013, 20:36 


22/01/11
309
Joker_vD в сообщении #680411 писал(а):
которые по своим свойствам радикально отличаются от отношений и формул реляционной алгебры/реляционного исчисления.


Уважаемый Joker_vD, вы согласны с тем, что мощность СУБД больше либо равна мощности реляционной алгебры?

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение06.02.2013, 22:21 
Заслуженный участник


09/09/10
3729
Esp_ в сообщении #680795 писал(а):
что мощность СУБД больше либо равна мощности реляционной алгебры?

Это, конечно, зависит от того, что вы называете "мощностью". Реляционное исчисление полно по Гёделю, но, разумеется, не полно по Тьюрингу — потому что Кодд с самого начала хотел, чтобы оно было алгоритмически разрешимо.

Впрочем, SQL тоже не является Тьюринг-полным языком, потому-то мы и имеем хранимые процедуры.

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение06.02.2013, 22:42 


22/01/11
309
Joker_vD

Я просто хотел сказать вам следующее: от того, что на практике у нас в таблицах лежат дубликаты, и используются триггеры и прочие объекты СУБД - это не есть большая натяжка, как вы говорите.
Реляционная база данных (или субд, как вам угодно) подразумевает, что информация хранится в таблицах. Таким образом, каждой таблице соответствует некоторое отношение.

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

 Профиль  
                  
 
 Re: Алгебра или формальный язык для нереляционных СУБД
Сообщение07.02.2013, 04:38 


15/04/10
985
г.Москва
1)Цаленко активно использует в своей книге понятие ТИП.
С точки зрения, характерной для теории категорий это нормально.
в частности он пишет о типах ПРОСТРАНСТВО и ВРЕМЯ, вводит траектории пространства состояний
Что же это ? Можно ли сказать, что соотношение типа объекта объекту аналогично соотношению главной и подчиненной сущности?
В частности, динамику ИС задавать таблицей ВРЕМЯ или ввести время как часть ключа во все таблицы?

2)По поводу связей - он рассматривает отношения
IS-A, INSTANСE OF, СOMPONENT OF
Отношение СOMPONENT OF не то же что понятие контейнеры в ООП ?
Или класс с набором ссылок или экземпляров объектов других более простых классов?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group