Вестник НовГУ

Вестник НовГУ > 2005 > № 34 > Дудаков С.М. Выразительная сила языков запросов первого порядка для баз данных на неупорядоченном случайном графе

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

УДК 510.67
Д у д а к о в С. М. Выразительная сила языков запросов первого порядка для баз данных на неупорядоченном случайном графе // Вестн. Новг. гос. ун-та. Сер.: Техн. науки. 2005. № 34, стр. 57-62
Изучается поставленный О.В.Белеградеком вопрос: изменяется ли выразительная сила языка логики первого порядка, если база данных рассматривается над универсумом, который является неупорядоченным случайным графом? Для упорядоченного случайного графа увеличение выразительной силы имеет место независимо от сигнатуры базы данных. Показывается, что для баз данных, сигнатура которых содержит более чем одноместные предикаты, увеличение выразительной силы тоже имеет место: можно предложить =-генерический запрос, который можно записать с использованием отношений универсума, но нельзя без их использования.
Библиогр. 8 назв.

Загрузить (517 КБ)