WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 50 | 51 || 53 | 54 |   ...   | 82 |

Степень участия сущности в связи. Существует еще одно ограничение для типов связи – степень участия сущности в связи. Одна из возможных интерпретаций: степень участия определяет зависимость существования некоторого типа сущностей от участия в типе связи другого типа сущностей (по крайней мере, для полного участия в связи; см. далее).

Существует два вида участия типа сущности в типе связи: полное и частичное. Пусть R – тип связи, а тип сущности E – участник типа связи R (отметим, что понятие участника естественно переносится с связей на типы связей). Характеристический признак такой: если каждая сущность типа E находится по крайней мере в одной связи согласно типа связи R, то участие типа сущности E в типе связи R называется полным (total), в противном случае (то есть существует сущность типа E, которая согласно типа связи R не находится в связи ни с одной сущностью другого типа сущности) – частичным (partial).

Формализировать понятие полного и частичного участия можно посредством проекции отношения 2 (табл. 3). В предыдущих обозначениях имеем нижеследующую таблицу, где 1 (R), (R) – проекции бинарного отношения соответственно по первой и второй компонентам.

Табл. 3 – Взаимосвязь между степенью участия и проекцией отношения, а также значениями оператора min Проекция Степень участия типа сущности в связи Значение оператора min отношения участие типа сущности E в типе связи R полное 0 < min(R) 1 (R) = E участие типа сущности E в типе связи R частичное min(R) = 1 (R) E участие типа сущности F в типе связи R полное (R) = F 0 < min(R-1) 2 -участие типа сущности F в типе связи R частичное (R) F min(R ) = Структурные ограничения вида (min, max). Существует и альтернативный вариант рассмотрения ограничений на типах связи – так называемые структурные ограничения, которые предусматривают задание минимальных и максимальных значений (min, max). Как далее будет показано, эти структурные ограничения позволяют специфицировать больше информации о связи.

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

Пусть x E, полный образ одноэлементного множества {x} относительно отношения R обозначим через def R[x] ; напомним, что согласно стандартному определению R[x] = {y | y F < x,y > R } – множество всех элементов множества F, которые находятся в отношении R с элементом x.

Будем считать, что множества E, F не более чем счетные, а все полные образы одноэлементных множеств конечные; учитывая финитность всех объектов, такие ограничения являются естественными.

def Множество мощностей полных образов всех элементов множества Е обозначим как.

Im( R ) = { R[x ] x E} Очевидно, что – непустое подмножество натуральных чисел, конечное (то есть ограниченное Im(R) XII-th International Conference "Knowledge - Dialogue - Solution" сверху) или бесконечное (то есть неограниченное сверху). В любом случае это множество имеет наименьший элемент, который обозначим, как. Наибольшего же элемента множество может и min(R) Im(R) не иметь, поэтому введем следующее обозначение, в котором – некоторый элемент, не принадлежащий множеству натуральных чисел:

наибольший елемент множества Im(R), если Im(R) конечное множество, max(R) =, в противном случае.

По существу множество натуральный чисел N со стандартным порядком дополнили наибольшим def элементом, превратив его в полную решетку, где, причем n < для всех nN < N,> N = N {} (по поводу условной полноты и пополнения условно полных решеток см., например, [Биркгоф Г.,1984, гл. V, § 3, с. 153-154]). Непосредственно из определений вытекают равенства (*) min(R) = Im(R), max(R) = Im(R), где символы используются для обозначения инфимумов и супремумов соответственно (в полной, решетке N ).

Основная задача заключается в исследовании логической связи между значениями введенных операторов на исходном отношении ( R ) и на отношении, обратном к нему ( R-1). Эта задача будет решена в приведенной далее теореме, доказательство которой опирается на следующие леммы о основных свойствах операторов min,max.

Лемма 1. Для произвольного бинарного отношения R выполняются следующие утверждения:

1. min(R) max(R), более того max(R) = min(R) < max(R) ;

2. min(R) = max(R) x y (x, y E R[x] = R[y ]);

3. пусть k – такое натуральное число, что min(R) = max(R) = k ; тогда x (x E R[x] = k);

4. пусть k – такое натуральное число, что x (x E R[x] = k); тогда min(R) = max(R) = k ;

5. R = min(R) = max(R) = 0 ; более того R = min(R) = max(R) = min(R-1) = max(R-1) = (характеристическое свойство пустого бинарного отношения);

2 6. 1 (R) E min(R) = 0, 1 (R) = E min(R) > 0 ;

7. 0 < min(R) < max(R) 1 (R) 2 ;

2 8. max(R) = 1 (R) = (R) =, где – кардинал счетных множеств;

9. R – функциональное отношение max(R) 1. Из пунктов 6, 9 этой леммы вытекает заполнение таблиц 2, 3 применительно к операторам min,max.

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

Лемма 2 (значения операторов min,max на конечном универсальном отношении). Пусть E = l > 0, def F = k > 0, а U(l,k) = EF – универсальное отношение на множествах E, F ; тогда min(R) = max(R) = l и min(R-1) = max(R-1) = k. Значения операторов min,max зависят не только от аргумента-отношения (в предыдущих обозначениях R ), но и от множества-параметра, которому принадлежат первые компоненты пар отношения (множества E ); поэтому точнее было бы писать, например, minE (R) вместо min(R). Следующая лемма уточняет зависимость от множества-параметра.

Лемма 3. Пусть отношение R и множества E, F, E, такие, что R E F и E E ; тогда minE (R) = 0 и maxE (R) = maxE (R). Следовательно, собственное расширение множества-параметра влияет только на значение оператора min, которое из возможно ненулевого становится нулевым.

228 Mathematical Foundations of AI Следующая лемма рассматривает случай, когда отношение имеет структуру объединения попарно совместных отношений (совместность в понимании [Редько В. Н., Брона Ю. Й., Буй Д. Б., Поляков С. А., def def 2 2001], т.е. U V U | X = V | X, где X = 1 U 1V – пересечение проекций отношений по первой компоненте, а U | X, V | X – ограничения отношений по множеству X ), в лемме выражаются значения операторов min,max на исходном множестве через значение тех же операторов на множествах из объединения.

Лемма 4. Пусть отношение R такое, что R =, причем все отношения R, i I попарно совместные.

R i i iI 2 Тогда maxE (R) = (R ), где множества E,Ei, такие, что 1 (R) E, 1 (Ri ) Ei для всех i I.

maxEi i iI Кроме того, обозначая проекции по первой компоненте отношений R и Ri через G и Gi соответственно, имеем равенство minG (R) = (R ).

minG i i iI Доказательство следует с равенства ImG(R) = (Ri ), равенств (*) и хорошо известного утверждения Im Gi iI о точных гранях объединения множеств (см. например, [Скорняков Л. А., 1982, § 1, теорема 9]). Все варианты значений min,max для отношений приведены в табл. 4, строки которой отвечают -исходному отношению R, а столбцы – обратному отношению R.

Следующая теорема отвечает на вопрос совместимости значений операторов min, max для отношения и обратного отношения.

Теорема. Для ячеек табл. 4, обозначенных +, существуют отношения с соответствующими значениями min, max. Для ячеек табл. 4, обозначенных –, не существуют отношения с соответствующими значениями min, max. Доказательство основывается на предыдущих леммах. Так, заполнение первой строки и первого столбца непосредственно вытекает из п. 5 леммы 1 (о характеристическом свойстве пустого отношения). Отметим только, что соответствующие отношения строятся объединением конечных универсальных отношений (лемма 2) с использованием леммы 4 для счетных объединений.

Табл. 4 – Все варианты значений min,max и их совместимость для отношения и обратного к нему отношения def def l = min(R-1), l = max(R-1) l = l = 0 l = l > 0 l = 0,l 1 l = 0,l = l 1,l l l 1,l = k = k = 0 + – – – – – k = k > 0 – + + + + + def k = min(R) k = 0,k 1 – + + + + + def k = 0,k = – + + + + + k = max(R) k 1,k k – + + + + + k 1,k = – + + + + + Отметим, что по построению табл. 4 ее заполнение симметрично (относительно главной диагонали), поскольку при смене строк на столбцы (либо наоборот) исходное отношение и обратное к нему просто меняются ролями; таким образом, доказательство требуется только для заполнения ячеек, находящихся на главной диагонали и выше неё. XII-th International Conference "Knowledge - Dialogue - Solution" Из этой теоремы следует, что, за исключением тривиального случая пустого отношения, для любого распределения значений операторов min, max существует отношение, на котором указанные значения достигаются. В этом узком смысле нет логической связи между значениями операторов min, max на исходном и обратном отношениях. Причина этого состоит в том, что полные образы одноэлементных множеств несут локальную информацию о отношении (например, функциональность выражается, а инъективность уже не выражается.) Выводы В работе были рассмотрены и уточнены в терминах теории отношений такие понятия модели „сущностьсвязь”: сущности, связи, структурные ограничения связей (показатель кардинальности, степень участия, структурные ограничения вида (min, max)).

После рассмотрения ограничений на типы связей (табл. 2-3) можно сделать вывод: структурное ограничение вида (min, max) является более выразительным, чем показатель кардинальности и степень участия сущности в связи.

Основное задание последующей работы –формализация таких понятий модели „сущность-связь”:

атрибуты, многосторонние связи, слабые и сильные сущности.

Литература [Chen P., 1976]. The entity-relationship model – towards a unified view of data // ACM TODS. – March 1976. – v. 1, № 1.

[Batini Carlo, Ceri S., Navathe S.B. and Batini Carol, 1991]. Conceptual Database Design: an Entity/Relationship Approach, Addison-Wesley, Reading, MA, 1991.

[Thelheim B., 2000]. Fundamentals of Entity-Relationship Modeling, Springer-Verlag, Berlin, 2000.

[Гарсиа-Молина Г., Ульман Дж., Уидом Дж., 2004]. Системы баз данных. Полный курс.: пер. с англ. – Москва:

Издательский дом „Вильямс”, 2004. – 1088 с.

[Дейт Дж., 1998]. Введение в системы баз данных.: пер. с англ. – Киев: „Диалектика”, 1998.– 784 с.

[Коннолли Т., Бегг К., Страчан А., 2000]. Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд.: пер. с англ. – Москва: Издательский дом „Вильямс”, 2000.– 1120 с.

[Крёнке Д., 2003]. Теория и практика построения баз данных. 8-е изд. – Санкт-Петербург: „Питер”, 2003. – 800 с.

[Буй Д. Б., Кахута Н. Д., 2005]. Властивості теоретико-множинних конструкцій повного образу та обмеження // Вісник Київського університету. Серія: фіз.-мат. науки. – 2005. – Вип. 2. – С. 232-240.

[Биркгоф Г.,1984]. Теория решеток. – Москва: Наука, 1984. – 564 с.

[Редько В. Н., Брона Ю. Й., Буй Д. Б., Поляков С. А., 2001]. Реляційні бази даних: табличні алгебри та SQL-подібні мови. – Київ: Видавничий дім “Академперіодика”, 2001. – 198 с.

[Скорняков Л. А., 1982]. Элементы теории структур. – Москва: Наука, 1982. – 158 с.

Информация об авторах Дмитрий Буй – Киевский национальный университет имени Тараса Шевченко, факультет кибернетики: Украина, Киев, 03022, пр. Глушкова 2, корп.6; e-mail: buy@unicyb.kiev.ua Людмила Сильвейструк - Киевский национальный университет имени Тараса Шевченко, факультет кибернетики: Украина, Киев, 03022, пр. Глушкова 2, корп.6; e-mail: slm-klm@rambler.ru 230 Mathematical Foundations of AI FORMAL DEFINITION OF ARTIFICIAL INTELLIGENCE AND AN ALGORITHM WHICH SATISFIES THIS DEFINITION Dimiter Dobrev Abstract: In this paper you can find a formal definition of the notion of Artificial Intelligence. A corollary of this definition is an algorithm which satisfies it. It is suspicious that this is the first paper which gives description of the AI algorithm. Really, this is true but only from the point of view of theoretical computer science because this algorithm is useless for the practice due to the combinatory explosion. In theory, every program which terminates after finite number of steps is a terminating program but for the practice terminating programs are only those which terminate after reasonable number of steps. So, in this paper you will find an algorithm which is AI but which is not sufficiently efficient. The only thing which you have to do in order to obtain real AI is to optimise this algorithm.

Keywords: AI Definition, Artificial Intelligence.

Introduction We will start with the formal definition of Artificial Intelligence. After defining this notion the question which is the algorithm which satisfies the definition will be obvious.

A definition of Artificial Intelligence was proposed in [1] but this definition was not absolutely formal at least because the word "Human" was used. In this paper we will formalize this definition.

The definition in [1] first was published in popular form in [2, 3]. It was stated in one sentence but with many assumptions and explanations which were given before and after this sentence. Here is the definition of AI in one sentence:

AI will be such a program which in an arbitrary world will cope no worse than a human.

From this sentence you can see that we assume that AI is a program. Also, we assume that AI is a step device and that on every step it inputs from outside a portion of information (a letter from finite alphabet ) and outputs a portion of information (a letter from a finite alphabet ). The third assumption is that AI is in some environment which gives it a portion of information on every step and which receives the output of AI. Also, we assume that this environment will be influenced of the information which AI outputs. This environment can be natural or artificial and we will refer to it as "World".

The World will be: one set S, one element s of S and two functions World(s, d) and View(s). The set S contains the internal states of the world and it can be finite or infinite. The element s of S will be the world's starting state.

Pages:     | 1 |   ...   | 50 | 51 || 53 | 54 |   ...   | 82 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.