Калабухов Е.В. Курс лекций по дисциплине Базы данных, знаний и экспертные системы
Подождите немного. Документ загружается.
В первом случае надо описать законы дистрибутивности:
§ 2.2ke
1
* (e
2
+e
3
) ⊥→ke
1
* e
2
⊥ +ke
1
*e
3
⊥,
§ 2.3k(e
1
+e
2
) * e
3
⊥→ke
1
* e
3
⊥ + ke
2
*e
3
⊥ ,
§ 2.4ke
1
* (e
2
+ e
3
) * e
4
⊥ → k(e
1
* е
2
+ e
1
* e
3
) * e
4
⊥.
Во втором случае по аналогии со сложением имеем
§ 2.5ke
1
* е
2
⊥ → ke
1
⊥* ke
2
⊥.
Осталось выразить возможность "снятия внешних скобок" и условие
"терминальности" символов, что определяют предложения:
§ 2.6k(e) ⊥ → ke⊥,
§ 2.7ks⊥ → s
(буквы не подлежат конкретизации).
Приведенные семь предложений § 2.1 - § 2.7 полностью решают данную
задачу.
Пример, обработки на данной программе выражения
k(A +B) * (С +D) ⊥
Последовательно получим в результате работы программы (слева указан
номер правила, которое непосредственно привело к данному выражению):
§2.2 k(A +В)*С⊥. + k(A +B)*D⊥
§2.3 kA *C⊥ +kB*C⊥ + k(A+B)*D⊥
§2.3 kA *C⊥ + kB*C⊥ + kA *D⊥ + kB*D⊥
Далее ограничимся рассмотрением первого слагаемого:
§ 2.5 kA⊥ * kC⊥ + ...
§2.7 A * kC⊥ + ...
§ 2.7 А * С + ...
После аналогичной обработки остальных слагаемых получим искомое
выражение
А*С+D*С+А*D + В*D.
281
Пример, обработки на данной программе выражения
kA + (B + С) ⊥
Последовательно получим в результате работы программы (слева указан
номер правила, которое непосредственно привело к данному выражению):
§ 2.1 kA⊥ + k(B + С) ⊥,
§ 2.7 А + k (Д + С) ⊥,
§ 2.6 А + kB + C⊥,
§2.1, 2.7 A + B + С.
Заметим, что если расположить правило § 2.5 перед правилами § 2.2 и §
2.3 в программе, то это приведет к ошибке, например, выражение А *(В+С)
будет приведено к виду: А *В + С.
282
ЛИТЕРАТУРА
1.
ANSI X3.135—1992, American National Standart for Information Systems —
Database Language — SQL, November, 1992.
2.
Astrahan M.M., System R: A Relational Approach to Data Base Management
//ACM Transactions on Data Base Systems. — 1976. — V1, 97, June.
3.
Boyce R.F., Chamberlin D.D., King W.F., Hammer M.M. Specifying Queries
as Relational Expressions: The SQUARE Data Sublanguage //Communications
ACM. — 1975. V.18, November. — P.621.
4.
Chamberlin D.D., Gray J.N., Traiger L.L. Views, Authorization and Locking
in a Relational Data Base System //Proceedings of AFIPS National Computer
Conference, Anaheim, CA, May. — 1975.
5.
Chamberlin D.D., Raymond F.B. SEQUEL: A Structured English Query
Language. //Proc. ACM—SIGMOD. — 1974. — Workshop, Ann Arbor,
Michigan, May.
6.
Codd E.F. A Data Base Sublanguage Founded On The Relational Calculus
//Proc. ACM—SIGFIDET/ — 1971. — Workshop, San Diego, Calif., Nov.
P.35—68.
7.
Codd E.F. Extending the Database Relation Model to Capture More Meaning.
//ACM Transaction on Database Systems. 1979.— V.4, №4. — P.397—434.
(Имеется перевод: Кодд Э.Ф. Расширение реляционной модели для
лучщего отражения семантики //СУБД. — 1996. — №5—6. — С.163—
192.)
8.
Codd E.F. Further Normalization of the Data base Relational Model //Data
Base Systems.— N.J.: Prentice—Hall, 1972. — P.33—64.
9.
Codd E.F. Normalized Data Base Structure: A Brief Tutorial //Proc. of 1971
ACM—SIGFIDET Workshop on Data Description, Access and Control.—
N.—Y.: ACM. — 1971. — P.1—17.
10.
Codd E.F. Recent investigations in relational data base systems //Proc. IFIP
Congress. — 1974. — North—Holland Pub. Co., Amsterdam. — P.1017—
283
1021.
11.
Codd E.F. Relation Model of Data for Large Shared Data Banks //Comm.
ACM. — 1970. — V.13, №.6. — P.377—383. (Имеется перевод: Кодд Е.Ф.
Реляционная модель данных для больших совместно используемых
банков данных //СУБД. — 1995. — №1. — С.145—160.)
12.
Eswaran K.P. Chamberlin D.D. Functional specifications of a subsystem for
data base integrity //Proc. Very Large Data Base Conf., Framingham, Mass.,
Sept. — 1975. — P.48—68.
13.
Eswaran K.P., Gray J.N., Lorie R.A., Traiger I.L. The Notions of Consistency
and Predicate Locks in a Data Base System //CACM. — 1976. — V.19, №11.
14.
Fagin R. Multivalued Dependencies and New Normal Form for Relational
Databases //ACM TODS. — 1977. — V.2, №3.
15.
Fagin R.A. Normal Form for Relational Databases That is Based on Domains
and Key //ACM Transactions on Database Systems. — 1981. — V.6, №3. —
P.387—415.
16.
Gray J., Lorie R., Putzolu G., Traiger I. Granularity of Locks and Degrees of
Consistency in a Shared Data Base //in Readings in Database Systems, Second
Edition, Chapter 3, Michael Stonebraker, Ed., Morgan Kaufmann. — 1994.
17.
Heath I.J. Unacceptable File Operations in Relational Database //Proc. 1971
ACM SIGFIDET Workshop on Data Description, Access, and Control. — San
Diego, Calif. — 1971.
18.
Held G.D., Stonebraker M.R., Wong E. INGRES: A Relational Data Base
System //Proceedings of AFIPS National Computer Conference, Anaheim, CA,
May. — 1975.
19.
Meiton J., Simon A.R. Understanding The New SQL: A Comlete Guide
//Morgan Kaufmann. — 1993.
20.
Reisner P., Boyce R.F., Chamberlin D.D. Human Factors Evaluation of Two
Data Base Query Languages: SQUARE and SEQUEL //Proceedings of AFIPS
National ComputerConference, Anaheim, CA, May. — 1975.
21.
Smith J.M., Smith D.C. Database Abstractions: Aggregation and
284
Generalization. //ACM Transactions on Database Systems. — 1977. — V.2,
№2, June.— P.105—133. (Имеется перевод: Смит Д.М., Смит Д.К.
Абстракции баз данных: Агрегация и обобщение //СУБД. — 1996. — №2.
— С.141—160.)
22.
Zloof M.M. Query By Example //Proceedings of AFIPS National Computer
Conference, Anaheim, CA, May. — 1975.
23.
Алиев Р.А., Абдикеев Н.М. и др. — Производственные системы с
искусственным интеллектом, — М.: Радио и связь, 1990.–263 с.
24.
Амамия М. Танака Ю. Архитектура ЭВМ и искусственный интеллект:
Пер. с япон. – М.: Мир, 1993. – 400 с.
25.
Атре Ш. Структурный подход к организации баз данных. — М.: Финансы
и статистика, 1983. — 320 с.
26.
Беренсон Х., Бернштейн Ф., Грэй Д., Мелтон Д., О"Нил Э., О"Нил П.
Критика уровней изолированности в стандарте ANSI SQL //СУБД. —
1996. — №2. — С.45—60.
27.
Бойко В.В., Савинков В.М. Проектирование баз данных информационных
систем. — М.: Финансы и статистика, 1989. — 351 с.
28.
Болотова Л.С., Комаров М.А., Смольянинов А.А. Системы
искусственного интеллекта. Теоретические основы СИИ и формальные
модели представления знаний: Учебное пособие/МИРЭА — М.: 1998. –
108 с.
29.
Боуман Д, Эмерсон С., Дарновски М. Практическое руководство по SQL.
— Киев: Диалектика, 1997.
30.
Буч Г. Объектно—ориентированный анализ и проектирование. 2—е изд./
Пер. с англ. — М.: Издательство Бином, СПб: "Невский диалект", 1998 г.
–560 с.
31.
Васкевич Д. Стратегии клиент/сервер. — Киев: Диалектика, 1997.
32.
Гаврилова Г.А., Хорошевский В.Ф. Базы знаний интеллектуальных
систем. – СПб., «Питер», 2000. – 384 с.
33.
Гилуа М.М. Множественная модель данных в информационных
285
системах. — М.: Наука, 1992.
34.
Голосов А.О. Аномалии в реляционных базах данных //СУБД. — 1986. —
№3. — С.23—28.
35.
Грабер М. Введение в SQL. — М.: Лори, 1996. — 379 с.
36.
Грабер М. Справочное руководство по SQL. — М.: Лори, 1997. — 291 с.
37.
Дейт К. Руководство по реляционной СУБД DB2. — М.: Финансы и
статистика, 1988. — 320 с.
38.
Дейт К.Дж. Введение в системы баз данных, 6—е издание. – К.; М.; СПб.:
ИД «Вильямс», 2000. – 848 с.
39.
Джексон Г. Проектирование реляционных баз данных для использования
с микроЭВМ. — М.: Мир, 1991. — 252 с.
40.
Диго С.М. Проектирование и использование баз данных. — М.: Финансы
и статистика, 1995. — 208 с.
41.
Злуф М.М. Query—by—Example: язык баз данных //СУБД. — 1996. —
№3. — С.149—160.
42.
Змитрович А.И. Базы данных. – Мн., Из—во «Университетское», 1991.
43.
Иванов А. Кремер Ю. Язык Smalltalk: концепция объектно-
ориентированного программирования. "Компьютер пресс", 4, 1992 г. с. 21
–31.
44.
Информатика: Энциклопедический словарь для начинающих/ под ред.
Поспелова Д.А., Борисов А.Н. и др. Обработка нечеткой информации в
системах принятия решений,— М.: Радио и связь, 1989.–303 с.
45.
Канолли Т., Бегг К., Страчан А. Базы данных: проектирование,
реализация и сопровождение. 2—е издание. — К.; М.; СПб.: ИД
«Вильямс», 2000. – 1120 с.
46.
Карпова Т.С. Базы данных: модели, разработка, реализация. – СПб.,
«Питер», 2001. – 304 с.
47.
Кириллов В.В. Структуризованный язык запросов (SQL). — СПб.:
ИТМО, 1994. — 80 с.
48.
Кондрашина Е.Ю., Литвинцева Л.В., Поспелов Д.А. Представление
286
знаний о времени и пространстве в интеллектуальных системах / Под ред.
Д.А.Поспелова. — М.: Наука. Гл.ред.физ.—мат. лит. 1989 г. — 328 с.
49.
Корнеев В.В., Гарев А.Ф. Базы данных. Интеллектуальная обработка
информации. – СПб., «Корона», 2000.
50.
Кузин Л.Т. Основы кибернетики, т. 2, — М.: Энергоатомиздат, 1994. –
350 с.
51.
Кузнецов С.Д. Введение в системы управления базами данных //СУБД. —
1995. — №1,2,3,4, 1996. — №1,2,3,4,5.
52.
Кузнецов С.Д. Дубликаты, неопределенные значения, первичные и
возможные ключи и другие экзотические прелести языка SQL //СУБД. —
1997. — №3. — С.77—80.
53.
Кузнецов С.Д. Неопределенная информация и трехзначная логика //
СУБД. — 1997. — №5. — С.65—67.
54.
Кузнецов С.Д. Операционные системы для управления базами данных //
СУБД. — 1996. — №3. — С.95—102.
55.
Кузнецов С.Д. Стандарты языка реляционных баз данных SQL: краткий
обзор // СУБД. — 1996. — №2. — С.6—36.
56.
Ладыженский Г.М. Системы управления базами данных — коротко о
главном // СУБД. — 1995. — №1,2,3,4.
57.
Левин Р., Дранг Д., Эделсон И.,/ Перевод с англ. — Практическое
введение в технологию искусственного интеллекта и экспертных систем с
иллюстрацией на Бейсике, — М.: Финансы и статистика, 1990.
58.
Логический подход к искусственному интеллекту. / Тейз А., Грибомон П.
и др. — М.: Мир. - 1990.
59.
Мартин Д. Планирование развития автоматизированных систем. — М.:
Финансы и статистика, 1984. — 196 с.
60.
Мейер М. Теория реляционных баз данных. — М.: Мир, 1987. — 608 с.
61.
Минский М. Фреймы для представления знаний. — М.:Мир, 1979.
62.
Нагао М., Катаяма Т., Уэмура С. Структуры и базы данных. — М.: Мир,
1986. — 197 с.
287
63. Нечеткие множества и теория возможностей. Последние достижения/ под
ред. Ягера Р.Р., — М.: Радио и связь, 1986. – 408 с.
64.
Нильсон Н. Искусственный интеллект. — М.: Мир,1973.
65.
Нильсон Н. Принципы искусственного интеллекта: Пер.с англ. — М.:
Радио и связь. 1985. — 376 с.
66.
Оззу М.Т., Валдуриз П. Распределенные и параллельные системы баз
данных //СУБД. — 1996. — №4. — С.4—26.
67.
Озкарахан Э. Машины баз данных и управление базами данных. — М.:
Мир, 1989.
68.
Осуга С. Обработка знаний: Пер. с япон. 1989.— 293 с.
69.
Понятие лингвистической переменной и его применение к принятию
приближенного решения/ Пер.с англ.,— М.: Мир,1976,–203 с.
70.
Попов Э.В. Экспертные системы. — М.: Наука, 1987.
71.
Поспелов Д.А. Логико-лингвистические модели в системах управления,
— М.: Энергоиздат, 1981 г.— 230 с.
72.
Поспелов Д.А. Моделирование рассуждений. Опыт анализа
мыслительных актов. — М.: Радио и связь, 1989. — 1989. — 184 с.
73.
Поспелов Д.А. Ситуационное управление. Теория и практика. — М.:
Наука, 1986 г.— 284 с.
74.
Построение экспертных систем / Под ред. Ф.Хейес—Рот, Д.Уотерман,
Д.Ленат — М.: Мир, 1987.
75.
Практическое введение в технологию искусственного интеллекта и
экспертных систем / Р.Левин, Д.Дранг, Б Эделсон: Пер. с англ. — М.:
Финансы и статистика. 1991.— 239 с.
76.
Представление и использование знаний: Пер. с япон./ Под ред. Х. Уэно,
М. Исудзука. – М.: Мир, 1989. – 220 с.
77.
Пржиялковский В. В. Абстракции в проектировании БД // СУБД. — 1998.
— №1. — С.90—97.
78.
Приобретение знаний: Пер. с япон. / Под ред. С.Осуги, Ю.Саэки. – М.:
Мир, 1990. – 304 с.
288
79. Прохоров А, Определение оптимальной структуры базы данных //
Informix magazine. Русское издание. — 1998. — Апрель.
80.
Тиори Т., Фрай Д. Проектирование структур баз данных. В 2 кн., — М.:
Мир, 1985. Кн. 1. — 287 с.: Кн. 2. — 320 с.
81.
Ульман Д. Базы данных на Паскале. — М.: Машиностроение, 1990. —
386 с.
82.
Ульман Д. Основы систем баз данных. — М.: Финансы и статистика,
1983. — 334 с.
83.
Ульман Дж.Д., Уидом Дж. Введение в системы баз данных. – М., «Лори»,
2000.
84.
Форсайт Р. Экспертные системы. – М., ФиС, 1987.
85.
Хаббард Д. Автоматизированное проектирование баз данных. — М.:
Мир, 1984. — 294 с.
86.
Хансен Г., Хансен Дж. Базы данных. Разработка и управление. – М.,
Издательство «Бином», 1999. – 704 с.
87.
Харрингтон Дж. Л. Проектирование реляционных баз данных. Просто и
доступно. – М., «Лори», 2000. – 231 с.
88.
Хомоненко А.Д., Цыганков В.М. Базы данных. Учебник для высших
учебных заведений. – СПб., «Корона», 2000.
89.
Цаленко М.Ш. Моделирование семантики в базах данных. — М.: Наука,
1988.
90.
Цикритизис Д., Лоховски Ф. Модели данных. — М.: Финансы и
статистика, 1985. — 344 с.
91.
Чамберлин Д.Д., Астрахан М.М., Эсваран К.П., Грифитс П.П., Лори Р.А.,
Мел Д.В., Райшер П., Вейд Б.В. SEQUEL 2: унифицированный подход к
определению, манипулированию и контролю данных //СУБД. — 1996. —
№1. — С.144—159.
92.
Чаудхари С. Методы оптимизации запросов в реляционных системах
//СУБД. — 1998. — №3. — С.22—36.
93.
Чен П. Модель "сущность-связь" — шаг к единому представлению о
289
данных //СУБД. — 1995. — №3. — С.137—158.
290