Содержание Лекция Лекция 1. Модель вычислений фон Неймана и традиционные языки Лекция Лекция 2. Нетрадиционные модели вычислений Лекция Лекция 3. Ленивые. - презентация

1 Содержание Лекция Лекция 1. Модель вычислений фон Неймана и традиционные языки Лекция Лекция 2. Нетрадиционные модели вычислений Лекция Лекция 3. Ленивые вычисления и функциональная модель Лекция Лекция 4. Постулаты необходимости, их следствия. Особенности ленивых и жадных вычислений при решении различных задач ЛекцияЛекция 5. Элементы сентенциального стиля программирования Лекция 6. Лекция 7. Лекция 8. ЛекцияЛекция 9. Концепция «Model View Controller» Лекция Лекция 10. Введение в базы данных: мотивация СУБД Лекция Лекция 11. Модели баз данных Лекция Лекция 12. Проектирование баз данных

2 Лекция 1. Модель вычислений фон Неймана и традиционные языки

3 Каноническая архитектура фон Неймана 1.Три элемента вычислительной системы: –Память –Процессор –Управляющее устройство 2.Однородность памяти и адресация –Понятия ячейки, адреса и значения 3.Пассивность памяти и активность процессора 4.Роль устройства управления 5.Наличие канала связи между памятью и процессором. Работа канала осуществляется, когда –Требуется подать процессору команду для выполнения (активизируется устройством управления) –Процессору для выполнения команды требуется получить операнд (активизируется процессором) –При выполнении команды требуется изменение ячейки(активизируется процессором) Дополнение канонической архитектуры: устройства ввода и вывода

4 Схема выполнения двухадресной команды

5 Модификация канонической схемы

6 Альтернатива канонической схемы Разрешить выполнение всех команд, для которых готовы операнды Замена хранения результата передачей его в качестве операнда ранее заблокированным командам Задача динамической коммутации Data flow vs. Control flow Несоответствие стиля альтернативных программ стилю, к которому привыкли программисты Активная (ассоциативная) память Консерватизм традиционных языков

7 Особенности традиционных языков Присваивание значений (переменная аналог ячейки) Операторы (зависимость выполнения, последовательность) Структура управления (разветвления наиболее употребительные приемы) Приведения Подпрограммы

8 Присваивание значений a = процессор память Оператор Выполнение – команда Зависимость одного от другого (изменение памяти) Структура управления Последовательность выполнения Принудительная передача управления Способ указания групп операторов – типовые приемы разветвления вычислений

9 Приведения Типов выражения и переменной в присваивании Округление и отбрасывание Контролируемые (явно указываемые) и по умолчанию Приведения указателей

10 Подпрограммы Типовой прием группировки команд Повторяемые действия Модульность Современное понимание (расширено)

11 Нарушения канона: побудительные причины Повышение эффективности Повышение выразительности Фиксация типовых приемов программирования Нарушение однородности памяти –Сегментация памяти –Быстрые регистры, кэширование –… –Содержательная трактовка хранимого –Выразительность –Надежность Определение традиционных и нетрадиционных языков

12 Традиционные языки (некоторые) Fortran (IV, 76, 90, 95, 2000, 2003, …) Algol 60 Simula, Simula 67 PL/1 Algol 68 Pascal C и др. машинно-ориентированные языки Ada Объектно-ориентированные языки –Simula 67, Smalltalk, C++, Borland Pascal 5.5 – 7.0 & Object Pascal /Delphi/; CLOS – нетрадиционный! Java –Принципы «M машин x N языков» и «M машин + N языков» a)Все реализуемые языки можно вложить в промежуточный язык, т. е. их модели вычислений совместимы, не противоречат друг другу; b)Все целевые машины можно непротиворечиво представить в одной модели вычислений промежуточного языка так, чтобы трансляция программ для этой общей модели давала бы эффективный код для конкретных вычислителей

13 Лекция 2. Нетрадиционные модели вычислений

14 Повелительное и изъявительное наклонения Изъявительное наклонение и развитость языка Идеи внедрения изъявительного наклонения –Системы продукций –Системы функций –Коммутационные системы –Ассоциативные системы –Аксиоматические системы Различные стили программирования

15 Системы продукций Соотношения записываются как правила вывода: Левая Часть => Правая Часть Обрабатываемые данные сопоставляются с шаблонами (части правила для распознавания, когда правило применимо). –Соответствие шаблону –> разрешение применить правило: замена выделенного при сопоставлении фрагмента данных на что-то другое однократное выполнение замены – атомарный акт вычисления

16 Системы функций Программа – соотношение между функциями, связанных между собой аргументами, которые в свою очередь могут быть функциями. Атомарный акт вычислений это подготовка аргументов для использующей функции. Готовность аргументов – разрешение вычисления функции

17 Коммутационные системы Элемент системы – вершина графа (входные и выходные места) Дуги – каналы передачи значений Программа – граф с вершиной без входных мест (генератор перерабатываемых данных) и вершина без выходных мест (получатель результата) Вычисление – действие, связанное с вершиной или с дугой Активизация вычислений – поступление данных на входные места Возможна вложенность (структурная вершина) Если –граф без циклов, то коммутационная система – форма представления нерекурсивной системы функций –граф с циклами, то его можно проинтерпретировать как рекурсивную систему функций Но это не единственная вычислительная модель коммутационной системы (пример – сети Петри) Статическая коммутация vs. динамическая коммутация

18 Ассоциативные системы Элементы системы активные данные, представляющие собой пары: Спаривание элементов с одинаковыми ключами -> выполнение действия (в любом стиле) Результат выполнения действия – новые элементы Это иная форма коммуникационной схемы, более приспособленная к некоторым задачам (например, базы данных) тегзначение /val5 +val1 *val3 +val2 *val4 Pr3 Pr1 Pr2 Pr4 Pr5 val1 val3 val4 t: val1+ val2 t": val3+ val4 val2

19 Ассоциативные системы Элементы системы активные данные, представляющие собой пары: Спаривание элементов с одинаковыми ключами -> выполнение действия (в любом стиле) Результат выполнения действия – новые элементы Это иная форма коммуникационной схемы, более приспособленная к некоторым задачам (например, базы данных) тегзначение /val5 tval3+ val4 tval1+ val2 Pr3 Pr1 Pr2 Pr4 Pr5 Если (t = /), то val1+ val2 val5 t: val5 / (val1+ val2) …

20 Аксиоматические системы Аксиомы Описание знаний на фиксированном языке Классическая логика – соотношение между данными Вывод теорем (конструктивный!), т.е. фактов – программа (элементарный акт?) Реализуемость – ? Пример нарушения принципа обобщения без потерь: исчисление высказываний -> исчисление предикатов

21 Programming styles and structuring. Program and data structuring from three points of view Task: output ( sin (input (x)) ) b)Functional point of view Input sin Arguments Functions X c)Event-based point of view Events A: Input Events Value B: sin X Value X C : Generation of X A: Input B: sin The work is fulfilled State 1State 2 Input sin X Memory Value a)Operational point of view: a)Memory as a unique centralized warehouse is required only for of the operational programming b)Specifying arguments of functions only c)Data are transferred as messages about the events the processes are waiting for

22 Стили программирования Программирование от состояний; Структурное программирование; Сентенциальное программирование; Программирование от событий; Программирование от процессов и приоритетов; Функциональное программирование; Объектно-ориентированное программирование; Программирование от переиспользования; Программирование от шаблонов.

23 Лекция 3. Ленивые вычисления и функциональная модель

24 Ленивые и жадные вычисления Необходимость и возможность вычисления Принцип ленивости (рекурсивный ответ на вопрос): Что из того, что требуется для продуцирования результатов, может быть и, следовательно, должно быть вычислено? Принцип жадности: Что может быть и, следовательно, должно быть вычислено, используя наличествующие сейчас данные? Это управление вычислениями, берущее начало от данных Конкретное управление вычислениями, основывающееся на данных, между строгими ленивым и жадным принципами Что эффективнее? Когда как. Вырожденный случай игнорирование обоих вопросов, соответствие управляющим структурам (детерминированный процесс) Необходимость и возможность, их ограничения Функциональный язык возможность всегда точно вычислить необходимость (в императивном случае это затруднительно).

25 Необходимости при выполнении процедуры procedure P (in a, out b); … P (6*8, x); Когда появляется необходимость? in parameters Реальная и форсированная необходимость Ingermans thunks (algol 60) out parameters Только форсированная необходимость возможна в императивных языках Что препятствует? Зависимость вычислений от контекста Возможность повторного присваивания SISAL язык однократными присваиваниями. Это паллиатив! P ( in a, out b); { …a… … b = …; … } 6*8 X … r = x*5; …

26 Метод обобщения специфичного в функциональном программировании list of x = nil | cons x (list of x) Это синтаксическое представление утверждения, что список есть либо nil, либо результат применения функции cons к некоторому (абстрактному) x и уже построенному списку (list of x). Таким образом, список трех x-ов можно изобразить как cons x (cons x (cons x nil)) Список можно трактовать как запись функции, в которой первый элемент есть ее наименование, а остальные элементы ее аргументы, а точнее, как применение функции к ее аргументам (двуместная функция cons и нульместная функция nil) Обозначения: [ ] nil [1] cons 1 nil [1,2,3] cons 1 (cons 2 (cons 3 nil)) Каким способом появились значки-функции без аргументов 1, 2, и 3, не имеет значения, лишь бы для них были определены нужные для нас другие функции, например, сложение, вычитание и т.п.

27 Метод обобщения специфичного (продолжение) reduce f x nil = x reduce f x (cons a l) = f a (reduce f x l) sum nil = 0 sum (cons num list) = num + sum list reduce sum 0 ( 1, 2, 3, [ ] ) reduce multiply 1( 1, 2, 3, [ ] ) 1 * 2 * 3 * 1 (reduce f x) l sum = reduce add 0 add x y = x + y product = reduce multiply 1 (reduce cons nil) α α //copy of α reduce (:) [ ] // Haskell reduce функция с 3 аргументами, но она применяется только к 2 результат функция! append a b = reduce cons b a append [1,2] [3,4]= reduce cons [3,4] [1,2] = (reduce cons [3,4]) (cons 1 (cons 2 nil)) = cons 1 (reduce cons (cons 3 (cons 4 (cons nil)))) (cons 2 nil)) = cons 1 (cons 2 (reduce cons (cons 3 (cons 4 (cons nil))) nil)) = cons 1 (cons 2 ((cons 3 (cons 4 (cons nil)))) f x a l specific to sum

28 Gluing Functions Together: Composition and Map A function to double all the elements of a list doubleall = reduce doubleandcons nil where doubleandcons num list = cons (2*num) list Further: doubleandcons = fandcons double where double n = 2*n fandcons f el list = cons (f el) list reduce f nil gives expansion f to list specific to double An arbitrary function Function composition standard operator.: (f. g) h = f (g h) So fandcons f = cons. f Next version of doubleall: doubleall = reduce (cons. double) nil This definition is correct: fandcons f el = (cons. f) el = cons (f el) fandcons f el list= cons (f el) list specific to double Function map (for all the elements of list): map f = reduce (cons. f) nil Final version of doubleall : doubleall = map double One more example: summatrix = sum. map sum

29 Lazy Evaluation: Scheme F and G programs: ( G.F ) input G ( F input ) It is possible: F input t F ; G t F, but it is not good! The attractive approach is to make requests for computation: Using a temporary file G: Needed data produced by F F: Data are ready Hold up Resume F Resume G G: Needed data F: Hold up Resume F Resume G More precisely: … Data are ready

30 Лекция 4. Постулаты необходимости, их следствия. Особенности ленивых и жадных вычислений при решении различных задач

31 Постулаты необходимости Любое вычисление активизируется тогда и только тогда, когда оно (его результат) требуется для осуществимости одного или более других вычислений. Эта ситуация называется необходимостью вычисления. Любое вычисление перестает быть активным, т.е. приостанавливается, тогда и только тогда, когда необходимость в нем исчезает (например, требование удовлетворено). Вычисление программы в целом активизируется принудительно как запрос (необходимость) на получение результатов для внешнего использования (требование вывода продуцируемых данных). Постулаты лишь фиксируют границы, в которых должна находиться любая конкретизация понятия необходимости

32 Следствия постулатов необходимости 1.То, что ленивые вычисления задают управление программы через потоки данных, следует из постулатов необходимости 2.Поток управления вычислением динамически формируется необходимостями вычислений составляющих программных единиц Для императивных языков более слабое утверждение: 2.Если понятие необходимости определено корректно и вычисления программы в целом приводят к запланированным результатам, то можно установить соответствие между последовательностью необходимостей и потоком управления, заданным как последовательность выполняемых управляющих структур. Жадные вычисления свойством, аналогичным (2), не обладают: Для задания управления программы нужно не только определять наборы возможных действий, но и уметь их приоритезировать (из-за ресурсных ограничений)

33 Конкретизации необходимости Для императивного языка 1.Необходимость, определяется правилами, задающими поток управления в программе (декларируется необходимость выполнения следующего оператора для всех языковых конструкций) 2.Набор программных составляющих, необходимых для выполнения определяется так, чтобы было справедливо: –в него попадают все элементы (вычислительно замкнутые программные фрагменты), вычисление которых стало возможным к этому моменту, –элементы этого набора вычислительно независимы друг от друга Совместное вычисление Для функциональных языков Локальность всех вычислений Завершение вычислений или их приостановка? Возможность оперирования бесконечными структурами в функциональных языках Функции высоких порядков

34 Пример-иллюстрация F строит «очень большое» дерево (например, всех возможных последовательностей ходов) G запрашивает поддерево фиксированной глубины, т.е. обращается к F при анализе какой-то вершины. F достраивает дерево на запрошенную глубину. … … Если бы F завешалась, то требовалось бы строить уже пройденный путь дерева заново F никогда не вычисляется самостоятельно: G F /отношение запроса/

35 Метод Ньютона-Рафсона: вычисление квадратного корня Функциональная программа не эффективна. Правда ли это? Алгоритм: –Начинать с первой аппроксимации a0 –Продолжать получение более точной аппроксимации, используя правило a(n+1) = (a(n) + N/a(n)) / 2 Если аппроксимации сходятся к пределу a, то a = (a + N/a) / 2 Таким образом2a = a + N/a, a = N/a, a*a = N a = squareroot(N) Императивная программа: X = A0 Y = A0 + 2.*EPS 100 IF (ABS(X-Y).LE.EPS) GOTO 200 Y = X X = (X + N/X) / 2. GOTO CONTINUE Мы хотим показать, что вместо этого кода можно: построить простую функциональную программу получить метод ее улучшения В результате получится весьма выразительная программа!

36 Метод Ньютона-Рафсона: функциональная программа Первый вариант: next N x = (x + N/x) / 2 [a0, f a0, f(f a0), f(f(f a0)),..] repeat f a = cons a (repeat f (f a)) repeat (next N) a0 within eps (cons a (cons b rest)) = b, if abs(a-b)

37 Численное дифференцирование easydiff f x h = (f (x + h) - f (x)) / h Проблема: при малых h small (f ( x + h ) - f (x)) ошибка! differentiate h0 f x = map (easydiff f x) (repeat halve h0) halve x = x/2 within eps ( differentiate h0 f x )(1) Последовательность аппроксимаций сходится, хотя не очень быстро. elimerror n (cons a (cons b rest)) = = cons ((b*(2**n)-a)/(2**n-1)) (elimerror n (cons b rest)) при некотором n order (cons a (cons b (cons c rest))) = round(log2((a-c)/(b-c)-1)) Общая функция, вычисляющая последовательность аппроксимаций: improve s = elimerror (order s) s Более эффективно: within eps (improve (differentiate h0 f x)) (2) Используя то, что любая подпоследовательность halve обладает свойством исходной последовательности делимости пополам можно получить улучшение 4-го порядка within eps (improve (improve (improve (differentiate h0 f x)))) (3) Используя super s = map second (repeat improve s) second (cons a (cons b rest)) = b Здесь repeat improve применяется для получения все более улучшенной последовательности. Так довольно легко получен весьма сложный алгоритм within eps (super (differentiate h0 f x)) (4) Пусть A – правильный ответ, а B – терм ошибки B*h n. Тогда a(i) = A + B*2 n *h n и a(i+1) = A + B*(h**n). A = (a(i+1)*(2**n) a(i)) / 2**n – 1 Пусть A – правильный ответ, а B – терм ошибки B*h n. Тогда a(i) = A + B*2 n *h n и a(i+1) = A + B*(h**n). A = (a(i+1)*(2**n) a(i)) / 2**n – 1 n log 2 ( (a i+2 – a i ) / (a i+1 – a i ) – 1 )

38 Ленивые вычисления: императивные примеры Boolean выражения α&β&γ : (α == false) == false (α == true) & (β == false) == false if ( (precond) && (init) && (run) && (close) ) { printf (OK!); } else … Векторно-матричные выражения vector a(n), b(n), c(n); a = b + c + d; Необходимость вычислений может не появиться! The compiler does the following: Vector* _t1 = new Vector(n); for(int i=0; i < n; i++) _t1(i) = b(i) + c(i); Vector* _t2 = new Vector(n); for(int i=0; i < n; i++) _t2(i) = _t1(i) + d(i); for(int i=0; i < n; i++) a(i) = _t2; delete _t2; delete _t1; Мы вынуждены создавать и удалять временные переменные! for(int i=0; i < n; i++) a(i) = b(i) + c(i) + d(i); Для матриц аналогично Арифметические вычисления x = ( … ) * 0; x = 0; Без вычисления (…)! Ленивые и жадные вычисления при работе с файлами cat File_F | grep WWW | head -1 Subject of next slide

39 Анализ ленивого и жадного cat File_F | grep WWW | head -1 Жадный вариант: cat File_Fgrep WWWhead -1 stdout stdin stdout stdin stdout One string All strings of File_F Strings with WWW Ленивый вариант: cat File_Fgrep WWWhead -1 stdout stdin stdout stdin stdout One string One string with WWW For strings of File_F UNIX pipeline may be considered as optimization of lazy evaluation (in this case)! F A nice question: is this version more correct? Note: It is the same object in both cases!

40 Мемоизация Программа F (n) = F (n-1) + F (n-2) традиционный пример, когда рекурсия вредна Но не для функционального языка: –Локальность всех вычислений & независимость их от контекста повторение счета излишне. Можно «вспомнить» ранее посчитанное, если к такой возможности подготовиться – это мемоизация Прямолинейная – запоминать все Рациональная – запоминать необходимое! В императивных языках роль мемоизации – вспомогательные переменные.

41 Анализ векторно-матричного примера Consider the example more closely: a = b + c + d; t1 = b + c; t2 = t1 + d; a = t2; Order of calculations Traditional scheme Necessity of computation () appears only when a [i] is needed a[i] + = b[i] c[i] d[i] abdc t1 t2 + + I II III I II III (or I II U III) c[i] d[i] = a[i] + b[i] + abdc Lazy evaluation

42 Лекция 5. Элементы сентенциального стиля программирования

43 Что такое сентенциальное программирование? Sentence – предложение грамматика, определяющая все правильные предложения Обрабатываемые данные имеют структуру предложения Обработку удобно связывать с такой структурой Примеры: –Синтаксический анализ и вычисление предложения –Логический вывод утверждений на основе фактов Распознавание элемента структуры действие (преобразование) Возможность отложенных действий (планирование) Языковая поддержка –Lisp и другие функциональные языки: список – структура и данных, и программы. переработка данных, представленных в виде списков, как аргументов функции (дерево активизации функций) – частично –Snobol и другие языки обработки строк: сопоставление с образцами –Perl, Python и др. скриптовые языки – так называемые регулярные выражения –Prolog: данные – факты, как исходный материал для поиска –Рефал – язык, ориентированный на обработку древовидно структурированной информации и не только ее (сопоставление с образцами регулярные выражения и др.)

44 E T 1 | E + T 2 | E – T 3 T I 4 | T * I 5 | T / I 6 I ( E ) 7 | N 8 –––––––––––––––––– N D | D N N 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 Синтаксический анализ и вычисление предложения TE E T I (7+52+4*11) NNNN T I T I T I E E I * + Дерево (конкретного) синтаксиса Дерево вычислений Грамматика

45 Логический вывод утверждений на основе фактов Семья (МАША и САША) – предикат, истинность которого зависит от многих фактов. Например: –Живут вместе (МАША и САША) – другой предикат –~ Брат и сестра (МАША и САША) & Мужчина (САША) & … A, A B Правила вывода (например, ) B Цель – доказываемый предикат (конъюнктивная форма, истинность конъюнктов – доказательство) – это поле зрения, т.е. подобласть данных (фактов), которые обрабатываются в текущий момент (оно обычно имеет нетривиальную (как в фон-неймановском случае) структуру) Поле зрения – аналог регистров процессора императивной модели вычислений Факты (аксиомы, леммы, …), на которые опирается доказательство, – поле памяти программы Это идея языка Prolog.

46 Сопоставление строки T * с образцом =, где P i, – составляющие (подтермы) элементы, из которых строится образец (P i (T N V) *, N – имена элементов (подтермов) образца, V – имена переменных, которые означиваются при сопоставлении, это 1.распознавание структуры, которая соответствует описанию, представленному образцом, – исход Yes; или выяснение, что такая структура не существует, – исход No. 2.поиск такой подстроки 0 = … 032 строки, что –устанавливается соответствие между P 0, P 01, …, P 032 и указанными подстроками 0. (рекурсивно) –все вхождения каждой из переменных из получают одинаковые значения – означивание переменных, называемое конкретизацией = Сопоставление с образцом P0P0 P 01 P 03 P 011 P 012 P 013 P 014 P 02 P 031 P 032 T * 0 L = R

47 Сопоставление с образцом: примеры Пусть {a, b, …, z} * = T* = 0 – любое одиночное вхождение a в = 0 – любая подстрока, состоящая из a длины 0, 1, … = 0 – любая подстрока, состоящая из a длины 1, 2, … = 0 – любая подстрока, состоящая из a длины N N – переменная. Если она означенная, то ее значение определяет длину, если нет, то она означивается как длина 0. = 0 – любая подстрока вида a N b N c N Na, Nb, Nc, X и Y – переменные = 0 – та подстрока вида a N b N c N для которой N наибольшее Соглашения о стратегии сопоставления: первое вхождение, все вхождения, максимальное вхождение и др. Детерминатив – элемент образца, который сопоставляется (обычно наиболее простым способом) в первую очередь с целью сузить число рассматриваемых вариантов

48 Рефал: основная идея Приспособить к практическим нуждам теоретический Алгорифм Маркова: { i i }, где i, i T *, T алфавит символов Циклически повторяются в строгом порядке –поиск i (всегда с самого начала строки), –замена его на i в перерабатываемой строке. Завершение цикла предусматривается в двух случаях: –Когда ничто не может быть найдено, и –Когда выполняется продукция специального вида: i i

49 Основные символы, структурированные строки i строится как структурированная строка, из следующего: –символы T, не являющиеся скобками. Множество символов – T = T \ { (, ) } –конкретизационные скобки k и. (они могут сбалансировано появиться в строке в результате ее переработки) –выражения произвольные последовательности символов и скобок, сбалансированные по скобкам, в том числе и пустые последовательности, и отдельные символы. Множество всех выражений – E = (T {(,)} {k,.}) *, из которого удалены несбалансированные по скобкам строки –термы либо отдельные символы, либо выражения, заключенные в простые или конкретизационные скобки. Множество всех термов обозначается как W (W =(T (E))) –символы переменных, различаются по видам s-переменные: S = {s1,…,sN s } могут принимать в качестве значения только символы из перерабатываемой строки; w-переменные: W ={w1,…,wN w } могут принимать в качестве значения только термы; v- переменные: V={v1,…,vN v } могут принимать в качестве значения только непустые выражения; e-переменные: E={e1,…,eN e } могут принимать в качестве значения произвольные (в том числе и пустые) выражения

50 Рефал: продукции (операторы языка) Продукции Рефала принимают следующий вид: k i. i (левая часть правая часть) где i (T E V S W V E) *, i (T E V S W V E{k,.}) *, ( i и i сбалансированы по скобкам). Перерабатываемая строка (выражение) обрамляется конкретизационными скобками (технический прием) Поиск i = X 1...X r, строки из левой части продукции, в перерабатываемой строке заменяется процедурой проецирования i, или построения проекции i на одну из подстрок перерабатываемой строки такую, что все переменные получают значения (означиваются)

51 Проецирование строки i = X 1... X u...X r продукции k i. i на перерабатываемую строку Все следующие правила используются совместно a)Ищется подстрока вида: k i. где i (T {k,.}) * ; b)X u T: i представима как X u, X u представляет в проекции сам себя; c)X u S: i представима как t, где t T (не скобка), и тогда X u t; d)X u W: i представима как, где W ( терм), и тогда X u ; e)X u V: i представима как, где E\ { } ( непустое выражение), и тогда X u ; f)X u E: i представима как, где E ( выражение, возможно пустое), и тогда X u ; g)все X 1,...,X r должны найти свои образы в строке i в соответствии с правилами (bf), при этом значения, которые принимают одни и те же переменные в разных вхождениях, должны совпадать; h)все символы строки i должны быть сопоставлены символам и переменным X 1,...,X r в соответствии с правилами (bf).

52 Применение продукции k i. i a)построение проекции i на i (одной из возможных), b)построение i по i путем замены всех вхождений переменных их значениями, полученными при проецировании i на i ; c)замена в перерабатываемой строке ее подстроки i строкой i. Если данная продукция в данный момент неприменима, то делается попытка применить другую, текстуально следующую продукцию. Процесс применения продукций завершается, когда в перерабатываемой строке не остается конкретизационных скобок (успешное завершение), либо когда ни одна из продукций не может быть применена (неудача).

53 Разрешение неоднозначностей При неоднозначном выборе проекции i на i предпочтение отдается той проекции, удовлетворяющей одному из следующих критериев: a)в конечном итоге выбор проекции приводит к успешному завершению процесса, т.е. неявно вводится недетерминизм через механизм возвращения назад (backtracking); b)выбор проекции приводит к таким значениям переменных из списка символов X 1,...,X r, которые оказываются короче для переменных с более ранними номерами, считая номера их первых вхождений, т.е. явно вводится прагматическое детерминирование процесса; c)возможны иные критерии предпочтения.

54 Дополнение основного механизма Цель: сужение вариантов проецирования, снижение возможной недетерминированности, как следствие, повышение эффективности вычислений, повышение наглядности описания обработки Средство: пополнение словаря детерминативами. Это специальные символы, которые могут появляться в продукциях после k. Собираются в упорядоченные группы продукции, имеющие один и тот же детерминатив Процедура проецирования начинается с выбора группы продукций с детерминативом, выделенным в перерабатываемой строке Примеры: k/DETERMINATIV/ …. …………. kABCD+EF. EFGH – замена ABCD+EF на EFGH ks1XYZ. XYZs1– перенос первого символа в конец Использование детерминативов как своеобразных наименований процедур, в частности, внешних (на других языках)

55 Содержательный пример: дифференцирование (функция k/dif/) 1.ke1. k/dif/e1. 2.k/dif/v1+v2. (k/dif/v1.+k/dif/v2.) 3.k/dif/v1*v2. (k/dif/v1.*(v2)+k/dif/v2.*(v1)). 4.k/dif/(e1). k/dif/e1. 5.k/dif/w1x. w1 6.k/dif/x. 1 7.k/dif/w1. 0

56 Продолжение примерa Дифференцирование a*x+bx*(c+x)+d ka*x+bx*(c+x)+d. /1/ k/dif/a*x+bx*(c+x)+d. /2/ (k/dif/a*x.+k/dif/bx*(c+x)+d.) /2/ (k/dif/a*x.+(k/dif/bx*(c+x).+k/dif/d.)) /3/ ((k/dif/a.*(x)+k/dif/x.*(a))+(k/dif/bx*(c+x).+ k/dif/d.)) /7,6/ ((0*(x)+1*(a))+(k/dif/bx*(c+x).+k/dif/d.)) /3,7/ ((0*(x)+1*(a))+((k/dif/bx.*((c+x))+k/dif/(c+x).*(bx))+0)) /5,4/ ((0*(x)+1*(a))+((b*((c+x))+k/dif/c+x.*(bx))+0)) /2/ ((0*(x)+1*(a))+((b*((c+x))+(k/dif/c.+k/dif/x.)*(bx))+0)) /7/ ((0*(x)+1*(a))+((b*((c+x))+(0+1)*(bx))+0)) Очевидна необходимость дополнительных преобразований ke1. k/ar/k/dif/e1.. v1 = a*xиv2 = bx*(c+x)+d(продукция 2); v1 = a*x+bx*(c+x)иv2 = d(продукция 2); v1 = aиv2 = x+bx*(c+x)+ d(продукция 3); v1 = a*x+bxиv2 = (c+x)+ d (продукция 3). 1.ke1. k/dif/e1. 2.k/dif/v1+v2. (k/dif/v1.+k/dif/v2.) 3.k/dif/v1*v2. (k/dif/v1.*(v2)+k/dif/v2.*(v1)). 4.k/dif/(e1). k/dif/e1. 5.k/dif/w1x. w1 6.k/dif/x. 1 7.k/dif/w1. 0

57 Внешние вычисления в Рефале Арифметические вычисления нерациональны: k/sum/v1+v2. k/sum/ k/plus1/v1. + k/minus1/v2.. k/sum/v1+1. k/plus1/v1. k/sum/v1+0. v1 … нужны и другие правила А как проще? Обратиться к другой модели вычислений: k/sum/v1+v2 результат. sum – имя внешней функции v1 и v2 – входные параметры (для корректной работы должны быть означены как данные, соответствующие спецификациям sum) результат – выходной параметр (приводится к строковому виду) +,,. и – можно рассматривать как оформление фактических параметров функции

58 Схема вычисления Peфал программы

59 Представление строки kAB(CD)(E)F. в поле зрения Рефал-машины

60 Лекция 9. Концепция «Model View Controller» (что не удалось сделать в Delphi)

61 Система и ее декомпозиция Система – набор связанных между собой и взаимодействующих компонент. Это структура системы –Связь отражает возможность передачи информации –Взаимодействие – передача информации, в частности: Сигналы активизации компонент Запросы и отклики на них Передача данных –Взаимодействие с окружением: Передача информации от окружения – воздействие на компоненту Передача информации окружению – воздействие на окружение Функции системы – все возможные ее влияния (действия) на окружение, а также действия, осуществляемые в ответ на воздействия окружения. Нужно всегда различать функции системы и функции компонент! Состояния системы и/или ее компонент – характеристика ее поведения, т.е. осуществимости тех или иных функций в данный момент. Состояние иногда рассматривается как часть структуры При изучении, а тем более конструировании новой системы стоит задача распознавания структуры системы, обеспечивающая выполнимость всех ее функций моделирование поведения системы

62 Декомпозиция и моделирование Моделирование предполагает абстрагирование от несущественных с точки зрения рассмотрения деталей и выделение того, что рассматривается как главное Моделирование зависит от –Целей и решаемой задачи –Текущего знания о системе –Априорных установок Три подхода к изучению и конструированию системы: –Черный ящик: про систему известно, какие функции она должна выполнять, характеристики функционирования. Задача – определить структуру (вариант структуры, удовлетворяющий некоторым требованиям) –Серый ящик: помимо сведений о функциях известна информация о типе структуры, о некоторых ее элементах, возможно, о характеристиках функционирования и пр. Задача – реконструировать недостающую информацию, достроить систему –Белый ящик: структура системы известна, есть сведения о взаимодействиях компонент. Задача – определить фактическое функционирование, возможно, скорректировать поведение (пример – тестирование) Где и какая декомпозиция здесь имеется ввиду?

63 Виды декомпозиции Стихийная (Почему это плохо? Когда приемлемо?) Концептуальная – уровень соглашений о системе Проектная – какие части выделяются в проектируемой системе, как они соотносятся с планируемыми функциями Организационная – разделение труда, обязанностей, ответственности и др. Технологическая – отображение компонентов на средства программирования –модульная –структурная (структура программной системы и структура перерабатываемых данных) –объектная Специальные – связаны с соглашениями о процессе разработки, о порядке использования ресурсов и пр.

64 MVC – это: Концептуальная декомпозиция приложения, которая следует постулату разделения трех сущностей: –Понятия, объекты, действия и др., определяющие семантику вычислений, т.е. поведение системы на абстрактном уровне – Model (модель) –Понятия, объекты, компоненты интерфейса, полностью описывающие уровень взаимодействия пользователя с приложением, т.е. конкретный уровень – View (показ, представление, предъявление) –Понятия, объекты, компоненты управления поведением (изменение перерабатываемых данных и состояния системы) – Controller (контроллер, диспетчер) Шаблоны проектирования, библиотеки, языки поддерживающие концепцию Методический взгляд на разработку, соответствующий концептуальной декомпозиции и отвечающий на вопросы: –Что из того, что требуется разработать, относится к каждой из сущностей? –Что из этих сущностей для данной разработки является ключевой (самой сложной, неопределенной, определяющей остальное)? –Какие средства поддержки принятой концепции доступны в разработке? Концепция Model View Controller

65 Отвечает за взаимодействие с Model и View, обрабатывает пользовательский ввод формирует запросы к View и передает данные из Model к View Отвечает за функции системы: бизнес-логику, устройство баз данных, работу с ними и. др. Задает уровень абстракции приложения как модель уровня конструирования Usage : use-case diagrams elements of UI info for controls Запросы, команды, соответствующие внешним (пользовательским) воздействиям и обратно Diagrams: state, activity, concurrent, ER, … Dataflow & control graphs Code (API) Отвечает за UI Задает конкретные представления приложения как модель уровня анализа Model – структура системы и модель функционирования View – средства предъявления, показа Controller – средства управления поведением Model View Controller

66 Зачем нужно выделять View? Model Controller Пользователь U-Model ЗадачаЗадача U-Control Задача View Абстрактный уровень Конкретный уровень Функционирование системы

67 Информация для выбора представлений Model View + User Абстрактное представление (abstract view) Абстрактный синтаксис (abstract data tree) Параметры визуализации Model View Пользователь (разные варианты) Model View Аналитические модели: Ситуации использования (use-case) Сценарии Операционные маршруты Функции системы и ее поведение Информация для построения модели

68 Model Controller Информация для управления: Состояние системы, Данные, перерабатываемые приложением, Условия корректности изменений Model Команды управления поведением: Вводимые данные Сигналы от окружения Запросы (к обстановке, БД, др.) Controller

69 Controller View ControllerView Формы для представления информации на абстрактном уровне: Воздействия пользователей и окружения, Ввод данных Отклики на запросы Представление информации на абстрактном уровне: Воздействия на окружение Вывод данных Запросы Отображение динамики взаимодействий между абстрактным и конкретным уровнями

70 Прагматическая точка зрения: При реализации систем для разных пользователей (разные view, а функционирование подобно) Стандартизация интерфейса Стремление к переиспользованию Естественно разделение сущностей и их модульной инкапсуляции Общая позиция: Никогда не игнорировать возможность концепции! Целесообразны следующие шаги: 1.В начале проекта (фаза анализа) разделить три сущности 2.Выявить, что из Model, View и Controller наиболее существенное и сложное 3.Проанализировать аспект View и откорректировать сущности. 4.Самое сложное – основа разработки! Сфера применения – разработка любого приложения! Когда применять MVC?

71 Немного истории –Delphi продукт года другие системы (C/C++ Builder, MS Visual Studio и др.) –Swing (Java) – одна из первых библиотек с осознанной поддержкой MVC Delphi: –Программирование от интерфейса (View) –Использование палитры компонентов, инспектора объектов, поддержки проектов и др. –Model – из области БД –Control – стандартизованные средства управления Почему не дошли до поддержки MVC? –Просто разработчики не успевали! –Затем – стихийный стандарт… Что не удалось сделать в Delphi?

72 Лекция 10. Введение в базы данных: мотивация СУБД

73 Структурированные файлы и базы данных Файл как последовательность записей справедливая мысль о связи понятий файла и записи модель файлов с буферной переменной: тип элементов файла = тип записей: "безликие" данные на внешних носителях обретают структуру Если при обработке естественно выделять в две фазы, разделенные во времени: –формирование структурированных данных (например, большого объема) –оперирование со сформированной совокупностью данных то использовать структурированные файлы удобно

74 Комплекс программ для поддержки работы приемной комиссии вуза Роли: абитуриент, секретарь, экзаменатор, посетитель и привилегированный посетитель, администратор, ? Функции: –Создание записи для посетителя, который становится абитуриентом; –Пополнение записи для абитуриента сведениями о сдаче экзамена; –Исключение записей абитуриентов, получивших неудовлетворительные оценки за экзамены (очевидно, что это не уничтожение информации как добиться?); –Формирование списков абитуриентов, получивших проходной средний балл; –Формирование списков абитуриентов, зачисленных в вуз Дополнительные запросы. Например: –Качество подготовки выпускников в школах города: какие школы лучше готовят учеников к поступлению в вуз, –Эффективность подготовительных курсов и др. Общие требования: Поступающая информация имеет определенную структуру; Она должна накапливаться для обработки (при первоначальном вводе, после сдачи очередного экзамена и др.); Информация обновляется (например, удаляются записи, относящиеся к сдавшим экзамен неудовлетворительно); Необходима защита данных от несанкционированного доступа (права на чтение, модификацию) Это (и другое) то, чем занимаются разработчики баз данных, когда приступают к проектированию

75 Проектирование БД и задача унификации Какое отношение проектирование имеет к файлам? –Система файлов – среда, в которой реализуется хранение информации баз данных. –Другая сторона проектирования БД: как пользовательское представление баз данных проецируется на уровень хранения информации. Решение этой задачи допускает стандартизацию системы управления базами данных (СУБД). Их назначение – обеспечивать разработчиков информационных систем всем необходимым для единообразного и эффективного представления данных и средств доступа к ним. Однако далеко не всегда универсальное решение можно считать удовлетворительным –когда требуется точный учет специфики предметной области, приходится организовывать хранение данных и доступ к ним на основе непосредственного представления базы данных структурами файловой системы (пример АСУТП).

76 Автоматизация работы приемной комиссии: структура информации об абитуриенте type TAbit = record... end; var FileAbitInf : file of TAbit; Файловое представление: не единственное, к тому же не самое удобное (что это?). Суть – файл как средство хранения данных на внешних носителях. не однозначное: можно по-разному организовывать файлы для хранения данных (в соответствии с разными моделями баз банных). С помощью типа Tabit нужно обеспечить способ задания однозначного соответствия между сведениями о конкретном абитуриенте и записями файла – это ближайшая задача

77 Требования к типу Tabit Фамилия непригодна для однозначного соответствия: –существуют однофамильцы; –поиск записи, содержащей строковое поле (такой тип, по-видимому, будет у поля фамилии), более медленный, чем поиск по числовому полю; для эффективного и однозначного соответствия между сведениями о абитуриенте и записями файла требуется числовое поле, которое мы назовем регистрационным номером (RegNum). Нужна уникальность этих номеров для каждого абитуриента если регистрацией занимается одновременно несколько членов комиссии, то необходима генерация новых номеров по запросам: программа, блокирующая одновременное обращение к ней пользователей, специальное соглашение о номерах. Последнее хуже, т.к. не исключает ошибок пользователя, но зато проще.

78 Выбор структуры для типа TAbit const lName = 10; type TAbit = record RegNum : Word; { Положительное целое } FirstName, SecondName, LastName: String[lName]; Sex : Char; Address: record Ind : Word; { Почтовый индекс } Twn, Str : String [lName]; { Город, улица } H, F: Word; { Дом, квартира } end; PreCourses : Boolean; Exam : record Ex1, Ex2, Ex3, Ex4 : 1..5; B : Real; { Средний балл } end; Student : Boolean; end { описания типа TAbit }; Задание этого типа эквивалентно описанию array [0..lName] of Char (нулевой элемент массива – фактическое число символов) Другие варианты: строки в отдельном файле, а в записи индексы; шифрованные строки (простейший случай файл перекодировок) База данных уже система файлов! Пол задается как литерное значение 'м' или 'ж', поэтому было бы правильнее ограничить количество возможных значений данного поля. В нашем случае контроль следует возложить на программу «Забыли» предусмотреть дробные номера (корпус, строение и др.), а также номера с буквенным индексированием, что для реальной программы необходимо True, если абитуриент посещал подготовительные курсы, иначе False 1 для указания, что абитуриент не сдавал данный экзамен Столько позиций резервируется для задания изображений имен. Это означает, при составлении программы надо заботиться о случаях, когда размер имени больше или меньше, чем lName. Это производное поле, оно принимает значение True, когда абитуриент становится студентом, т.е. когда Exam. B >= проходной балл. Хранить его или вычислять? Для пользователя оно всегда хранится Взаимные производные поля (нельзя сказать, что хранить, а что нет) Exam.B тоже производное поле!

79 Выбор структуры для типа TAbit const lName = 10; type TAbit = record RegNum : Word; { Положительное целое } FirstName, SecondName, LastName: String[lName]; Sex : Char; Address: record Ind : Word; { Почтовый индекс } Twn, Str : String [lName]; { Город, улица } H, F: Word; { Дом, квартира } end; PreCourses : Boolean; Exam : record Ex1, Ex2, Ex3, Ex4 : 1..5; B : Real; { Средний балл } end; Student: Boolean; end {описания типа TAbit }; var FileAbitInf : file of TAbit;

80 Анализ выбранной структуры для типа Tabit Разумна ли выбранная структура? Нет! –Для поиска абитуриентов из одного места проживания просматриваются все записи и для каждой – сравнение Address с заданным значением. –Лучше перечень населенных пунктов (возможно, с индексами), выделить в специальный файл, а в записях FileAbitInf оставлять только номер элемента нового файла Контроль пользовательского ввода или вообще: его действий Сокращение размеров, занимаемых базой данных Снова БД система файлов! Модификация: Address : record Location: Word; { Индекс записи в новом файле FileLocations } Str: String [lName]; { Улица } H, F: Word; { Дом, квартира} end; var FileLocations : file of record Ind : Word;{ Почтовый индекс } Twn : String [lName]; { Город } end; Радикальное решение для типа String [lName]: в FileAbitInf и в FileLocations использовать поля с индексами соответствующих строк, а сами строки хранить в еще одном специальном файле Это даст сокращение размеров базы данных (в частности, за счет однофамильцев, тезок, земляков и т.п.). Нужно ли это реализовывать, без обстоятельного анализа будущего применения системы сказать трудно

81 Обсуждение модернизации типа TAbit Целесообразность разбиения информационного массива БД на несколько файлов: –для повышения эффективности –для обеспечения выборочной защиты данных –для повышения эффективности поиска информации: Запросы к БД с поиском записи с заданным значением поля FirstName – вычисление функции с аргументом строкового типа, вырабатывающей номер записи с полем FirstName, равным аргументу функции, или выделенное значение (0 – нет такой записи). Такая функция реализует ключевой поиск Поле (набор полей), по которому ведется ключевой поиск, называется ключевым, Возможные значения аргумента функции ключи Ускорение ключевого поиска – индексирование записей: –Построение специального индексного файла с заранее вычисленной функцией ключевого поиска F (Key – ключ) = N – указатель на запись в файле или 0 k K ( Ind (k) = n | ¬ (n = 0) F (n) – указатель на запись в основном файле БД)

82 Почему нужны СУБД k1k1 k2k2 knkn F (k i : T) 1 2 n Вычисляется заранее k F (k) (когда появляется запись с полем k) Индексирование заменяет вычисление F: Ind (i : integer) Это существенно быстрее! Файл БД Требуется, чтобы значения всех ключевых полей различались Специальная организации индексных файлов В промышленных СУБД – фирменный секрет Непосредственное конструирование информационных систем, т.е. без использования СУБД, довольно трудоемко Индексирование записей – пример повышения эффективности работы с данными

83 Отношения между данными 1.Отношение «многие ко многим»: Могут существовать абитуриенты с одинаковыми фамилиями, приехавшие из одного или из разных городов, и из одного и того же города могут приехать абитуриент, имеющие одинаковые фамилии 2.Отношение «один ко многим»: RegNum определяет LastName однозначно, но для одного и того же LastName возможны разные RegNum (однофамильцы). 3.Отношение «один к одному»: RegNum определен так, чтобы он взаимно-однозначно идентифицировал каждую запись целиком Отношение 1:n – намек, что что-то может быть вынесено в отдельный файл. Отношение n:m – указание, что для запроса, связывающих эти сущности придется определять дополнительную структуру данных Отношение 1:1 – возможность склейки таблиц LastName n : m Twn RegNum n : 1 LastName RegNum 1 : 1 X : TAbit

84 Лекция 11. Модели баз данных

85 Модели баз данных.Что это? Данные : хранятся, появляются, уничтожаются, предоставляются – пассивные Сведения : формируются, сообщаются, передаются – предъявляемые Информация : извлекается (генерируется) из сведений и данных, используется в некоторой деятельности (деятельностях) – активная Данные имеют структуру. В зависимости от точки зрения на них, от использования они структурируются по-разному: одновременно имеют разные структуры. –Физическая структура данных –Логическая структура данных 1.Хранимые данные: файлы, записи в машинном представлении информации – модели уровня хранения 2.Данные, которые размещаются в БД и извлекаются для внешнего использования – модели уровня конструирования информационных систем и обработки запросов 3.Представление, воспринимаемое пользователем – модели пользовательского уровня Модель базы данных – это структуры данных, которые поддерживаются СУБД на логическом уровне (основа конструирования конкретных баз данных и информационных систем)

86 Иерархическая модель Понятия иерархий и отношений, задающих иерархии Иерархии для накопления данных, а также поиска и извлечения их (для дальнейшей обработки) Два варианта иерархической модели: –для поиска листьев, представляющих данные, атрибуты которых размещаются в нелистовых узлах, они общие для поддерева (отношение «содержит») –данные размещаются в узлах (есть содержательное отношение, задающее иерархию, по которому строится дерево поиска) Примеры, когда использовать поиск по дереву эффективно Пример с абитуриентами: Найти всех из одного города неэффективный запрос! Прошитые деревья (ссылки между узлами – для разных целей, несколько деревьев, связанных ссылками) ответ на недостаточность этой структуры и шаг к следующей модели

87 Сетевая модель Используется граф: вершины данные, дуги используются для навигации (узнали гипертекстовый html?) 1.Есть естественная (сетевая) структура данных. Например, разные отношения. 2.Такая структура строится, исходя из запросов, которые предполагаются для данной прикладной области. Для новых типов запросов надо сеть достраивать. При добавлении данных сеть увеличивается. 3.Семантическая сеть.

88 Реляционная модель: неформальное определение Дейт: –вся информация в базе данных представлена в таблицах; –поддерживается три реляционные операции: выборка, проецирование, объединение. Правила Кодда (12 критериев) их, излагаем неформально: Чтобы считаться реляционной, СУБД должна: 1.Предоставлять всю информацию в виде таблиц (как у Дейта); 2.Поддерживать логическую структуру данных, независимую от их физического представления; 3.Языки структурирования, запросов и модификации данных должны быть высокого уровня (например, SQL). Здесь про ЯОД, ЯМД и др. языки, в частности, ЯОХД; 4.Поддерживать реляционные операции (*), а также теоретико-множественные операции (,, \ как минимум); 5.Поддерживать виртуальные таблицы (термины: view, курсор); 6.Различать неизвестные, невозможные значения и пропуски в данных (что это?); 7.Обеспечивать механизмы: 1)поддержки целостности, 2) авторизации, 3) транзакций, 4) восстановления данных. Список не взаимно независимый! с помощью которых обеспечивается весь доступ к данным (физическую запись знать не надо) (*)

89 Таблицы и базы данных (1) таблица строка столбец tablerowcolumn отношениекортежатрибут relationtuple attribute файлзаписьполе filerecordfield База данных набор связанных таблиц: Строка описывает объект, или сущность (entity) Столбец описываетсвойство, или атрибут объекта Первичный ключ – свойство, которое определяет, идентифицирует запись (объект, сущность) имя таблицы + первичный ключ + столбец => значение Пользовательские таблицы данные и Системные таблицы описание базы данных (системные каталоги, мета данные и др.) К правилам Кодда: 8.Обеспечивать возможность доступа к любым таблицам, в т.ч. к системным, причем точно такую же возможность, что и к пользовательским таблицам. Пользовательские термины «Академические» термины Термины из обработки данных

90 Независимость: –на логическом уровне –на физическом уровне Независимость данных (2) Изменение взаимосвязей между таблицами не влияет на функционирование (можно разбивать таблицы по строкам, столбцам, сливать их старые запросы выполняются, как раньше) Независимость логической структуры от способа хранения (в частности, перемещения, индексирования и т.д. ничего не меняют) Почти! Это источник различий одного и того же стандарта реляционных СУБД

91 –Манипулирование данными(ЯМД); –Определение данных(ЯОД); –Определение хранимых данных (ЯОХД) –Администрирование (управление) Все это есть в SQL Языки высокого уровня (3) Запросы (query): выборка и модификация Задание структуры таблиц (мета данные) Задание таблиц, описывающих формат хранение данных Задание прав доступа к данным

92 Манипулирование данными: выборка select * from publishers вставка строки insert into publishers values (0010,Pragma,45 10th ln.,Chicago,ÍL) Определение данных create table test (id int, name char (15)) Администрирование данными grant select on test to Kate Примеры pub_idpub_nameaddresscity state New Age Books1 1st St.BostonMA 0897Binnet&Hardley12 2nd Ave.WashingtonDC 1345Algodata Info10 3rd Dr.BtrkleyCA Kate разрешена выборка из таблицы test select * from test idname Снова тот же select : pub_idpub_nameaddresscity state New Age Books1 1st St.BostonMA 0897Binnet&Hardley12 2nd Ave.WashingtonDC 1345Algodata Info10 3rd Dr.BtrkleyCA 0010Pragma45 10th ln.ChicagoÍL

93 Основа всех операций – оператор select Синтаксис (упрощенный): select from where Проецирование: задание того, какие столбцы хочется просматривать: select pub_id, pub_name from publishers Выборка: задание того, какие строки хочется просматривать select * from publishers where state = CA Объединение: дает возможность работы с несколькими таблицами как с единым целым. Все получается, когда есть совпадающие поля: select title, pub_name from titles, publishers where publishers.pub_id = titles.pub_id Результат новая таблица, состоящая из строк, в которых произошло совпадение Реляционные и теоретико-множественные операции (4) publishers: pub_idpub_nameaddresscity state New Age Books1 1st St.BostonMA 0897Binnet&Hardley12 2nd Ave.WashingtonDC 1345Algodata Info10 3rd Dr.BtrkleyCA 0010Pragma45 10th ln.ChicagoÍL pub_idpub_nameaddresscity state Algodata Info10 3rd Dr.BtrkleyCA Можно комбинировать проецирование и выборку Результат – таблица: pub_idpub_name New Age Books 0897Binnet&Hardley 1345Algodata Info 0010Pragma

94 select title, pub_name from titles, publishers where publishers.pub_id = titles.pub_id Результат: titlepub_name TTTT lll rrrNew Age Books Jjj lll rrrNew Age Books EEE yyyNew Age Books BBBBB1Binnet&Hardley BBBBB2Binnet&Hardley BBBBB3Binnet&Hardley AAA book1Algodata Info AAA book2Algodata Info PPPPPPPPPPragma titles title_id title type pub_id price advance ytd_sales contract notes pubdate publishers pub_id pub_name address pub_id city state pub_name address pub_id city state ?????? title_id title type pub_id price advance ytd_sales contract notes pubdate

95 Реляционные и теоретико-множественные операции (4 - продолжение) А почему бы не использовать объединенную таблицу? Ответ: a)дублирование данных (примере – из таблиц titles, publishers и ?????? ). Ключи дублировать можно и нужно!!! b)трудно составить согласованные со смыслом таблицы (какой сущности соответствует ?????? ? ) c)возможны противоречия (из a) Вывод: Нужно проектировать базу данных, т.е. ее таблицы !!!

96 Виртуальные таблицы(5) Альтернативный способ просмотра данных: образование виртуальной таблицы, или курсора (view), или производной таблицы create view Books_and_Pubs as select title, pub_name from titles, publishers where publishers.pub_id = titles.pub_id Трудности достичь эффективной реализации оперирования с виртуальными таблицами точно также, как с обычными таблицами (хотя это требование следует из правил Кодда) нарушение стандарта Это еще одна проблема для стандартизации (см. дополнение 8) Неизвестные, невозможные значения и пропуски в данных (6)

97 Безопасность: авторизация (7.2) Права доступа и роли авторизация механизм «знания» системой имен ее пользователей Понятие владельца данных В SQL выделены средства определения владельца (тот, кто создает таблицу, но можно делегировать права); права на чтение права на модификацию (чтение и запись) таблицы или отдельного столбца. Запрет на доступ к отдельным строкам моделируется.

98 Безопасность: целостность и ограничения на целостность (7.1, 7.3, 7.4) 1.Причины рассогласования (противоречивости, некорректности) данных: –сбой в системе (программный, аппаратный); –логические ошибки (некорректное проектирование). 2.Управление транзакциями: Транзакция выполняется с начала до конца: 3.Объектная целостность: ни один первичный ключ не может иметь нулевое значение (почему?) 4.Ссылочная целостность: непротиворечивость повторяющихся частей (почему?)

99 Безопасность: целостность и ограничения на целостность (продолжение)

100 Лекция 12. Проектирование баз данных

101 Общие положения Выбор: таблиц, столбцов таблиц, взаимосвязей между таблицами и столбцами таблиц Логическая структура не должна выбираться, исходя из хранения и предъявления данных. Хотя реляционная СУБД это обеспечивает, при проектировании БД есть возможность «забегать вперед» Тем не менее, вопросы эффективности решаются Дейт: «Создать нужную структуру базы данных зачастую проще, чем строго сформулировать, какой она должна быть» в простых случаях да, то в сложных без специальной работы с требованиями не обойтись

102 Последовательность шагов 1.Исследовать информационную среду, которую нужно моделировать: –откуда поступают данные? –как они вводятся, и кто это делает? –какие параметры будут наиболее критичными с точки зрения времени реакции и надежности? –какие виды извлечения информации нужны? 2.Создать список объектов вместе с их: –свойствами (здесь – гипотезы, которые потом корректируются: как часто объект будет использоваться, с какими другими объектами он связан, др.) –атрибутами (типы атрибутов, какие атрибуты за что отвечают и др.) 3.Можно начинать как с объектов, так и с атрибутов (не смешивать подходы!), но в обоих случаях нужно ответить на вопросы: –действительно ли выбранные атрибуты подходят для описания данного объекта? –нужны ли еще атрибуты или объекты? Все принимаемые решения записывать! В частности, на этом этапе составляется макет таблиц и связей: ER-диаграммы. Объекты – таблицы (1 объект –строка ) Атрибуты столбцы

103 Последовательность шагов 4.Убедиться, что есть атрибут (или группа атрибутов), однозначно идентифицирующая любую строку каждой таблицы, т.е., что есть первичные ключи. Если нет добавить искусственно. 5.Рассмотреть зависимости один ко многим: Есть ли возможности для объединения связанных таблиц? Для этого добавить внешние ключи: В результате появляется возможность «отобрать все из Т1, у кого внешний ключ равен первичному из Т2» 6.Проверить нормализацию, если нужно, то исправить или обосновать отклонение от нее. Проследить, как нормализация выполняется на логическом уровне. 7.Ответить на вопрос: удовлетворяет ли вас результат? Нет переделать, уточнить, дополнить и т.д. pk1 T1 pk2 T2 pk1 pk2 T1 pk2 T2

104 Хорошая и плохая структура базы данных Что такое «хорошая структура» базы данных? –максимально простое взаимодействие; –гарантии непротиворечивости; –максимальная производительность. Что такое «плохая структура» базы данных? –непонимание результатов запросов; –риск противоречивости данных; –избыточность; –сложность изменение структуры уже созданных (и заполненных) таблиц. Нужен критический анализ построенного (всегда)

105 Проект БД «Книги, авторы, издатели» (1) 1.Вопросы, которые могут задавать пользователи, самые разные: Кто из авторов проживает в Калифорнии? Какие книги стоят больше ХХ $? Кто написал самое большое число книг? Чем мы обязаны автору ХХХ?(!!!) Какова средняя стоимость книг по психологии? Как продаются книги по программированию? … 2.Что можно извлечь об информационной среде, изучая ее при опросе будущих пользователей: автор может написать несколько книг; книга может быть написана несколькими авторами; порядок фамилий авторов на первой странице книги является важным, т.к. влияет на получаемый ими гонорар; редактор может работать над несколькими книгами, и у книги может быть несколько редакторов; в заказе на покупку может быть несколько книг; … Нужно только суметь разграничить, что будет, и что не будет доступно из конструируемой базы данных Важно!

106 Проект БД «Книги, авторы, издатели» (2) 3.Объекты:Свойства:Взаимосвязи: авторыимяу книги есть один или адреси т.д. телефон … книгиназвание авторы стоимость … издательстваназвание адрес … редакторыимя адрес телефон книги 4.Макет БД и поиск первичных ключей (специальный столбец) про фамилии и др., возможность использования номера страхового полиса Пока здесь не учитывается весь круг вопросов, связанных с продажами и заказами на продажу. В последствии соответствующее дополнение будет сделано, а то, на сколько это будет легко, скажет, хороша ли была выбрана первоначальная структура базы данных Authors au_id au_lname au_fname address phone Titles title_id name price type аdvance Publishers pub_id name address Editors ed_id ed_lname ed_fname address phone

107 Проект БД «Книги, авторы, издатели» (3) 5.Отношения один ко многим Задача: связать Titles и Publishers. В результате анализа информационной среды выяснено требование, реализовать запросы, в которых название книги фигурирует совместно с издателем. Требуется обеспечить возможность объединения этих таблиц Первая попытка: Это ошибка: На все названия книг столбцов не напасешься. Трудно модифицировать данные (нереально определять для новой книги столбец) Решение обратное: Снабдить Titles внешним ключом Authors au_id au_lname au_fname address phone Titles title_id name price type аdvance Publishers pub_id name address title_id Editors ed_id ed_lname ed_fname address phone Authors au_id au_lname au_fname address phone Titles title_id name price type аdvance pub_id Publishers pub_id name Address Editors ed_id ed_lname ed_fname address phone

108 Проект БД «Книги, авторы, издатели» (4) Анализ решения (целостность): –обе таблицы содержат по одной строке на объект; –pub_id повторяется в titles, т.к. издательство издает много книг, но это не дублирование данных, а дублирование ключей! –установленную связь можно использовать для объединения таблиц: НО! Само по себе решение не обеспечивает непротиворечивости данных –удаление записи из Publishers Нужно вводить ограничения на целостность: –если меняется или удаляется запись из Publishers, то надо корректировать все записи из Titles с соответствующими pub_id. –если добавляется книга, то надо найти или добавить издателя. Кто подобные ограничения вводит и/или отслеживает? Вопрос имеет далеко не однозначный ответ. –Из правил Кодда он не следует: Ограничения хранятся в словарях, а не в приложениях, но это о хранении, а не об отслеживании. Если СУБД может поддерживать отслеживание, то это не значит, что им пользуются конструктор базы данных и запросов. –Сопоставление возможностей СУБД и приложений в части поддержки ограничений целостности см. в предыдущей лекции Пример select title, pub_name \\ Что угодно from titles, publishers where publishers.pub_id = titles.pub_id

109 Проект БД «Книги, авторы, издатели» (5) 6.Отношения многие к многим Автор может писать много книг, а книгу могут писать многие авторы Учет этого отношения нужна реализация объединения таблиц Таблица связей, или ассоциация: Authors au_id au_lname au_fname address phone Titles title_id name price type аdvance pub_id Publishers pub_id name Address Editors ed_id ed_lname ed_fname address phone TitlesAuthors title_id au_id Это пример составного первичного ключа. Можно рассматривать таблицу- ассоциацию как объект, связанный с книгами (авторами) отношением один ко многим: одна ассоциация одна книга (один автор), книга (автор) может входить в несколько ассоциаций. Нужна соответствующая пара ограничений на целостность (как выше). Связь и придуманный объект могут иметь содержательный смысл и, в частности, свои атрибуты (пример – накладная) Ассоциация – это два отношения один к многим Отношения один к многим и многие к многим и понятия главной и детализирующей таблиц

110 Проект БД «Книги, авторы, издатели» (6) Анализ может указать явно на то, что требуется реализация запросов, которые требуют объединение таблиц Но он не может показать, что такого сорта запросы не появятся при развитии конструируемой информационной системы в будущем Потребность расширения запросов преобразование структуры существующих таблиц потеря эффективности нужно постараться ликвидировать причины возможных потерь производительности. (примеры: незамеченные отношения многие ко многим и один ко многим) Важно угадать и постараться ликвидировать причины, из-за которых возможны потери производительности (эффективности системы и работников при реализации новых возможностей)

111 Проект БД «Книги, авторы, издатели» (7) 7.Отношения один к одному свободны от необходимости угадывать будущие незапланированные запросы: Обнаружив такое отношение, можно –слить две таблицы в одну или –ничего не менять Рекомендация: выделять в отдельную таблицу то, что реже используется это сократит время реакции для частых запросов

112 Проект БД «Книги, авторы, издатели» (8) 8.Первый итог: a)независимые объекты строки таблиц; b)свойства столбцы; c)у всех таблиц есть первичные ключи; d)надо проверить, есть ли еще отношения 1:N, и, если да то: –добавить внешние ключи к «многим», –определить ограничения на целостность, связанные с отношениями. e)надо проверить, есть ли еще отношения N:M, и, если да то: –построить таблицы связи, –определить ограничения на целостность. f)что еще не учли? Если надо учесть, то доделать.

113 Проект БД «Книги, авторы, издатели» (9) Диаграммы «Сущность – связь» (ER-диаграммы) Их нужно уметь –Составлять –Читать Authors au_id au_lname au_fname address phone Titles title_id name price type аdvance pub_id Publishers pub_id name Address Editors ed_id ed_lname ed_fname address phone TitlesAuthors title_id au_id Sales sonum stor_id date qty_ordered qty_shipped data_shipper title_id TitlesEditors title_id ed_id

114 Лекция 13. Проектирование баз данных: нормализация

115 Понятие нормализации и первая нормальная форма Нормализация набор стандартов проектирования БД, называемых нормальными формами, которые гарантирует качество с точки зрения выполнения различных критериев Существует пять (иногда говорят о семи!) нормальных форм НФ i НФ i+1, (именно столько критериев качества) –уменьшение избыточности данных (за счет дробления таблиц и дублирования ключей) –формальная непротиворечивость (для содержательной гарантий быть не может) 1.Первая нормальная форма 1НФ требует, чтобы на пересечении любых столбца и строки находилось единственное атомарное значение. Содержательно: атрибут неделим (строковое поле для СУБД неделимо тоже) Что это дает? –Разграничение возможностей СУБД и приложений + –Корректное оперирование с атрибутами, которые изначально, казалось бы, требованиям 1НФ не удовлетворяют + –Технологичное решение: главная (master) и детализирующая (detail) таблицы.

116 Первая нормальная форма: пример Tаблица Sales не удовлетворяет пожеланию заказчика иметь в одном заказе несколько книг. Есть четыре варианта, как это преодолеть: на уровне приложения синтезировать общий заказ из нескольких «одно-книжных» это не то: не появился объект «составной заказ», и для него не может быть никаких действий, общих для всех приложений нарушить 1НФ: атрибут title_id сделать составным (множеством, коллекцией и др.) плохо не только формально, но и по содержанию: трудно отслеживать ссылочную целостность, искать заказы по этому атрибуту, строить объединения таблиц по связи становится невозможным; вместо одного атрибута title_id построить несколько: title_id1, title_id2, … не решает проблему при появлении заказа с числом позиций (книг) более чем их было до того, придется добавлять в Sales новый столбец (проблемы с преобразованием таблиц) или делать ее непрямоугольной (абсурдно) Sales sonum stor_id date qty_ordered qty_shipped data_shipper Правильное решение: из первоначальной Sales сделать две таблицы: главная: Sales содержит сведения о заказе в целом и не содержит атрибута, указывающего на книги заказа (title_id), но связана отношением 1:N с дополнительной таблицей (механизм внешних ключей) детализирующая: SalesDetail описывает позиции всех заказов (составной атрибут в виде набора своих строк, каждая из которых должна давать доступ к названиям книг) доступ к книгам обеспечен через SalesDetail посредством связи с Titles Salesdetail sonum title_id Titles title_id name price type аdvance pub_id

117 Первая нормальная форма: пример (результат) Authors au_id au_lname au_fname address phone Titles title_id name price type аdvance pub_id Publishers pub_id name Address Editors ed_id ed_lname ed_fname address phone TitlesAuthors title_id au_id Sales sonum stor_id date qty_ordered qty_shipped data_shipper title_id TitlesEditors title_id ed_id Salesdetail sonum title_id Что здесь обязательно, а что относится к специфике? обязательное –Связь главной Sales и детализирующей SalesDetail следствие специфики: –параTitles и SalesDetail заказы n:m книги –не пришлось «придумывать» объект «позиция заказа» Из требований 1НФ, получился тот же результат, что и при объектном моделировании: таблица связи между двумя таблицами объектов, в отношении n:m 1НФ: искать столбцы с неатомарными значениями (требуется поиск тех, кто находится в одном штате нужно выделить в address дополнительные атрибуты city и state). О «плоских» таблицах Позиция заказа содержательно подчинена заказам, но реляционная модель не может выражать этого В ООП объекты главной и подчиненной таблиц равнозначны Это отрицательно сказывается на эффективности представления ООМодели в реляционном стиле

118 Вторая нормальная форма 2НФ в добавление к 1НФ требует: любой неключевой столбец должен зависеть (= определяться функционально) от всего первичного ключа (требование для таблиц с составными первичными ключами). Пример с полем contract a)автор заключает индивидуальный контракт с заказчиком, не дожидаясь соавторов: contract есть функция от title_id и au_id. Поле contract должно быть добавлено к таблице b)авторы заключает контракт все вмести: contract – функция только от title_id, (не зависит от au_id). Это атрибут книги, а не пары «автор, книга». Поле contract должно быть добавлено к таблице Что будет, если 2НФ нарушается? возможны странные запросы к БД (см. b); избыточность данных: в случае (b) надо хранить значение (общего) атрибута contract в разных строках таблицы TitlesAuthors Ситуация зависимости решения от предметной области! Titles title_id name price type аdvance pub_id TitlesAuthors title_id au_id

119 Третья нормальная форма 3НФ в добавление к к 1НФ и 2НФ требует: ни один неключевой столбец не должен зависеть от каких бы то ни было других неключевых столбцов. Он зависит только от всех столбцов первичного ключа и ни от чего больше Выплата гонорара зависит от номера в списке авторов. Попробуем вставить au_royalper и au_ord в Authors Это ошибка! au_royalper и au_ord зависят не только от au_id! То же про Titles. Это атрибуты связи авторов и книг: Где должен быть атрибут data_shipper? Это зависит от того, выполняется ли весь заказ сразу (наше решение), или он по позициям (тогда data_shipper надо перенести в таблицу связи). Здесь зависимость решения от информационной среды. Поддержка в СУБД выполнения требований 3НФ невозможна. Причина для введения 3НФ та же, что и у 2НФ: ликвидация дублей и логическая точность. Authors au_id au_lname au_fname address phone au_royalper au_ord Sales sonum stor_id date qty_ordered qty_shipped data_shipper title_id TitlesAuthors title_id au_id au_royalper au_ord

120 Другие нормальные формы Четвертая нормальная форма формализует требования, выполнение которых гарантирует от появления «дырявых» таблиц, т.е. от таких ситуаций, когда в таблицах возможны столбцы-атрибуты, которые не для всех объектов осмыслены Пятая нормальная форма требует, чтобы все таблицы были бы разбиты на минимально возможные части, тем самым полностью ликвидируется избыточность данных за счет дублирования ключей –Проблема управления целостностью упрощается до предела: изменение неключевых столбцов ничего не затрагивает –Однако изменение ключей становится довольно сложным: нужно проследить все вхождения ключей в другие таблицы. Но это более редкое действие, прослеживание изменений достаточно хорошо формализовано и не зависит от содержания базы данных, а потому обычно поддерживается на уровне СУБД.

121 Общие соображения о нормализации и реляционном подходе Правила нормализации удобны для того, чтобы проверять корректность конструируемых баз данных. В большинстве случаев они формализуют требования, которые понятны на уровне здравого смысла –Можно не знать их, но проектировать вполне приличные информационные системы –знание и даже применение этих правил не гарантирует от того, что конструируемая информационная система окажется хорошей с точки зрения области применения. Один из главных недостатков реляционного подхода, как уже упоминалось не раз, принципиально равная значимость всех объектов с точки зрения манипулирования и хранения данных. –Это противоречит фактическому положению дел, когда объекты связаны, к примеру, иерархическими отношениями: наследование, вложенность и др. Возможность построения сопряжения между объектной и реляционной моделями –Эта задача не имеет однозначного решения