'

Языки и методы конструирования программ

Понравилась презентация – покажи это...





Слайд 0

Языки и методы конструирования программ Программирование 2 (Без раздела про С++ и дополнение про базы данных)


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 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 языков» Все реализуемые языки можно вложить в промежуточный язык, т. е. их модели вычислений совместимы, не противоречат друг другу; Все целевые машины можно непротиворечиво представить в одной модели вычислений промежуточного языка так, чтобы трансляция программ для этой общей модели давала бы эффективный код для конкретных вычислителей


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

Ассоциативные системы Элементы системы — активные данные, представляющие собой пары: <значение, ключ> Спаривание элементов с одинаковыми ключами -> выполнение действия (в любом стиле) Результат выполнения действия – новые элементы Это иная форма коммуникационной схемы, более приспособленная к некоторым задачам (например, базы данных) 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)) ) Memory as a unique centralized warehouse is required only for of the operational programming Specifying arguments of functions only 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 Реальная и форсированная необходимость Ingerman’s thunks (algol 60) out parameters Только форсированная необходимость возможна в императивных языках Что препятствует? Зависимость вычислений от контекста Возможность повторного присваивания SISAL — язык однократными присваиваниями. Это паллиатив! … 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 , [ ] ) ? 1 + 2 + 3 + 0 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 ? результат — функция! 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 > tF; G tF, 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 Hold up Resume F Resume G G: Needed data F: Hold up Hold up Resume F Resume G More precisely: … Data are ready


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

Лекция 5. Решение численных задач в функциональном стиле


Слайд 36

Метод Ньютона-Рафсона: вычисление квадратного корня Функциональная программа не эффективна. Правда ли это? Алгоритм: Начинать с первой аппроксимации 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 100 200 CONTINUE Мы хотим показать, что вместо этого кода можно: построить простую функциональную программу получить метод ее улучшения В результате получится весьма выразительная программа!


Слайд 37

Метод Ньютона-Рафсона: функциональная программа Первый вариант: 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) <= eps = within eps (cons b rest), otherwise sqrt a0 eps N = within eps (repeat (next N) a0) Улучшение: relative eps (cons a (cons b rest)) = b, if abs(a-b) <= eps*abs(b) = relative eps (cons b rest), otherwise relativesqrt a0 eps N = relative eps (repeat (next N) a0)


Слайд 38

Численное дифференцирование 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*hn. Тогда a(i) = A + B*2n*hn и a(i+1) = A + B*(h**n). A = (a(i+1)*(2**n) — a(i)) / 2**n – 1 n ? log2( (ai+2 – ai) / (ai+1 – ai) – 1 )


Слайд 39

Лекция 6. Ленивые вычисления: императивные примеры


Слайд 40

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


Слайд 41

Анализ ленивого и жадного cat File_F | grep WWW | head -1 Жадный вариант: cat File_F grep WWW head -1 stdout stdin stdout stdin stdout One string All strings of File_F Strings with ‘WWW’ Ленивый вариант: cat File_F grep WWW head -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?


Слайд 42

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


Слайд 43

Анализ векторно-матричного примера 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 (v) appears only when a [i] is needed a[i] + = b[i] c[i] d[i] Lazy evaluation


Слайд 44

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


Слайд 45

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


Слайд 46

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 Синтаксический анализ и вычисление предложения T E E T I ( 7 + 52 + 4 * 11 ) N N N N T I T I T I E E I + 52 4 7 11 * + Дерево (конкретного) синтаксиса Дерево вычислений Грамматика


Слайд 47

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


Слайд 48

Фразовые формы, резолюция, унификация P1 ? P1 ? … ? Pn ? N1 ? N2 ? …? Nm P1 ? P1 ? … ? Pn <~N1? ~N2 ? …? ~ Nm (<заключение> < <условие>) Фраза Хорна: P <N1 ? N2 ? …? Nm (то же, что P ?~N1 ? ~N2 ? …? ~Nm) P(a) ? ~Q(b,c) & Q(b,c) ? ~R(b,c) P(a) ? R(b,c) / R(b,c)— резольвента / P(a) ? ~Q(b,c) & Q(c,c) ? R(b,c) не могут резольвироваться Унификация переменных Q(x,y) ? ~R(x,y) ??x,y (Q(x,y) ? ~R(x,y) ) Переменная унифицируется с любой константой P(a) ? ~Q(b,c) & Q(x,y) ? R(x,y) резольвируется в P(a) ? R(b,c) P(a) — фраза без условия, ~P(a) фраза без заключения Резолюция P(a) и ~P(a) — пустая фраза ? Вычисление, основанное на резолюции Доказательство того, является ли некоторая фраза следствием теории или нет Позитивные литералы Негативные литералы b и c унифицированы, поэтому P(a) ? ~Q(b,c) может быть резольвирована в


Слайд 49

Нисходящая (обратная) стратегия T = { P(a) ? ~Q(b,c) Q(x,y) ? ~R(x,y) S(b) R(a,b) } Является ли P(a) следствием T? Сначала Добавим к T ~P(a): T’ = { P(a) ? ~Q(b,c) [1] Q(x,y) ? ~R(x,y) [2] S(b) [3] R(a,b) [4] ~P(a) } (a): ~P(a) &[1] ?~Q(a,b) (b): ~Q(a,b)&[2] ?~R(a,b) (b): ~R(a,b) &[4]? ? Противоречие! P(a) доказано. Правила: В первой резолюции использовать добавленную фразу В каждой следующей должна участвовать резольвента предыдущей Пример Prolog программы: хакер (джон) получать_по_шее(Х) :— хакер(Х) ?— получать_по_шее(джон) ?— получать_по_шее(маша) Какие ответы мы получим? Истина Ложь Истина Недоказуемо или ?


Слайд 50

Семантика Prolog’а начальник(Фамилия, Оклад) :— служащий(Фамилия, Оклад), Оклад > 70000 Декларативная модель: Некое лицо (Фамилия) является начальником, если он или она является служащим с окладом больше 70000 (связки: если, и, или — ничего более не требуется) Процедурная модель: Один из способов обнаружить начальника — это: во-первых, отыскать служащего и, во-вторых, проверить, превышает ли его оклад 70000 (важен порядок выполнения условий) Модель абстрактного вычислителя Интерпретация действий, связанных с выполнением запроса (побочные эффекты, остановка, удаление / добавление фразы, … + прагматические соглашения) Эти три взгляда на Prolog влияют на практику программирования!


Слайд 51

Пример: обращение списка % Метод 1 / с правом для присоединить обр_порядок ([C|L1], L2) :- обр_порядок (L1,Выход), присоединить (Выход,[C],L2). обр_порядок ([], []). — — — — — — — — — — — — — — — — — — — — — — — — — — — — % Метод 2 % Пример запроса: обр_порядок (L1, [], L1). % |?- обр_порядок обр_порядок (L1, [X|L2], L3) :- % ([], [a,b,c], R) обр_порядок ([X|L1,L2,L3). % R=[a,b,c] — — — — — — — — — — — — — — — — — — — — — — — — — — — — Факт (unit clause) — фраза Хорна, не имеющая условий (без правой части) Правило — фраза Хорна с одним или более условий (подцелей) (<заключение> :— <подцель>{ , <подцель>}*) Запрос (query, goal) — за счет унификации его параметры означиваются Исчисление предикатов (1-го порядка) — за счет резолюций


Слайд 52

Prolog’овские базы знаний Что такое база знаний vs. база данных? Представление знаний Вычислительные формализмы: Дескриптивный язык + Обрабатывающая структура формализма Этапы построения Анализ: поиск значимых сущностей и отношений между ними / эксперт предметной области Составление обозначений для сущностей и отношений / программист Семантическое определение: истинные и ложные реализации отношений / эксперт предметной области Аксиоматическое задание отношений фразами Prolog’а для отношений / программист Какие запросы правомерны?


Слайд 53

Задания Написать на Prolog’е программу дифференцирования Где оканчивается адекватная применимость Prolog’а? Чем означивание (в двух его формах унификации и проецирования) отличается от присваивания и в чем они сходны?


Слайд 54

Сопоставление строки ? ?T* с образцом ? = <P0, P01, …, P032>, где Pi, – составляющие (подтермы) элементы, из которых строится образец (Pi?(T ? N ? V)*, N – имена элементов (подтермов) образца, V – имена переменных, которые означиваются при сопоставлении, это распознавание структуры ?, которая соответствует описанию, представленному образцом, – исход Yes; или выяснение, что такая структура не существует, – исход No. поиск такой подстроки ??0 = ??011 ??012 ??02…??032 строки ?, что устанавливается соответствие между P0, P01, …, P032 и указанными подстроками ??0. (рекурсивно) все вхождения каждой из переменных из ? получают одинаковые значения – означивание переменных, называемое конкретизацией ? = Сопоставление с образцом P0 P01 P03 P011 P012 P013 P014 P02 P031 P032 ?T* ??0 ??L ??011 ??012= ? ??013 ??014 ??02 ??031 ??032 ??R


Слайд 55

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


Слайд 56

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


Слайд 57

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


Слайд 58

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


Слайд 59

Проецирование строки ?i = X1... Xu...Xr продукции k ?i. ? ?i на перерабатываемую строку Все следующие правила используются совместно Ищется подстрока вида: k??i. где ??i?(T?{k, .})*; Xu?T: ??i представима как ?Xu?, Xu представляет в проекции сам себя; Xu?S: ??i представима как ?t?, где t?T (не скобка), и тогда Xu < t; Xu?W: ??i представима как ???, где ??W (? — терм), и тогда Xu < ?; Xu?V: ??i представима как ???, где ??E\ {?} (? — непустое выражение), и тогда Xu < ?; Xu?E: ??i представима как ???, где ??E (? — выражение, возможно пустое), и тогда Xu < ?; все X1,...,Xr должны найти свои образы в строке ??i в соответствии с правилами (b—f), при этом значения, которые принимают одни и те же переменные в разных вхождениях, должны совпадать; все символы строки ??i должны быть сопоставлены символам и переменным X1,...,Xr в соответствии с правилами (b—f).


Слайд 60

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


Слайд 61

Разрешение неоднозначностей При неоднозначном выборе проекции ?i на ??i предпочтение отдается той проекции, удовлетворяющей одному из следующих критериев: в конечном итоге выбор проекции приводит к успешному завершению процесса, т.е. неявно вводится недетерминизм через механизм возвращения назад (backtracking); выбор проекции приводит к таким значениям переменных из списка символов X1,...,Xr, которые оказываются короче для переменных с более ранними номерами, считая номера их первых вхождений, т.е. явно вводится прагматическое детерминирование процесса; возможны иные критерии предпочтения.


Слайд 62

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


Слайд 63

Содержательный пример: дифференцирование (функция 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


Слайд 64

Продолжение пример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


Слайд 65

Внешние вычисления в Рефале Арифметические вычисления нерациональны: 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) результат – выходной параметр (приводится к строковому виду) +, ?, . и – можно рассматривать как оформление фактических параметров функции


Слайд 66

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


Слайд 67

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


Слайд 68

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


Слайд 69

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


Слайд 70

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


Слайд 71

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


Слайд 72

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


Слайд 73

Отвечает за взаимодействие с 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


Слайд 74

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


Слайд 75

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


Слайд 76

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


Слайд 77

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


Слайд 78

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


Слайд 79

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


Слайд 80

Лекция 10. Жизненный цикл программного обеспечения и его модели


Слайд 81

82 Мотивация изучения жизненного цикла и его моделей Жизненный цикл — база методологий Жизненные циклы технических и программных разработок (конструкционные материалы и окружение ПО, старение, продолжающаяся разработка (сопровождение): Причины изучения моделирования жизненного цикла: для непрофессионалов — понимание реальных возможностей; основа адекватного применения инструментов и методов разработки; общие знания — ориентиры для планирования, аргументированность решений; правильное распределение обязанностей в коллективе Соглашения, предписания, регламенты разработки и цена их игнорирования


Слайд 82

83 Жизненный цикл программного обеспечения: определение Цикл разработки, Издержки после завершения разработки Жизненный цикл — это проекция пользовательского понятия «время жизни» на понятие разработчика «технологический цикл (цикл разработки)». Происхождение термина жизненный цикл


Слайд 83

84 Задача методологии и жизненный цикл Методологии — это инструменты, с помощью которых создание программного продукта превращается в упорядоченный процесс, а работа программиста становится более прогнозируемой и эффективной? планирование процесса В материальном производстве: замысел > чертежи > проектные решения > точное воспроизводство плана Расчет времени и стоимости, определение требуемой квалификации и др. В традиционном производстве: рост технологичности & снижение креативности Перенос в программирование. Разграничение двух видов деятельности: проектирование (креативность) производство (технологичность) Задача методологии: минимизировать творческий элемент в рутинных случаях? стремление разграничить: план и конструирование программы спецификации пользовательской потребности и план, выбор инструментов работы программиста и саму работу Появление соглашений, регламентов и предписаний, следование которым уменьшает вероятность ошибочных решений Форма представления жизненных циклов в разных методологиях различна, но в основе любых представлений разработки и сопровождения программных изделий лежат общие процессы, которые ведут проекты от замыслов к удовлетворению пользовательской потребности. Любая методология предписывает организацию этих общих процессов Полностью избежать креативности не получится!


Слайд 84

85 Модели процесса и продукта Модель процесса разработки: Целенаправленное развитие объекта под воздействием разработчиков Ключевые понятия: развитие, система деятельностей, субъект ? объект, этапы деятельностей, инструменты деятельности, цели, результаты и продукты Модели продукта (различные): Как устроен (построен) продукт? Для чего нужен? Один из типов моделей продукта: проекция модели процесса, в которой игнорируется все, связанное с субъектом возможна реконструкция модели процесса, которая необязательно совпадает с исходной моделью процесса! Иллюстративность модели: явное выделение некоторых аспектов для облегчения их понимания Инструментальность модели: использование ее в качестве инструмента некоторой деятельности (т.е. способствует целенаправленному развитию). Нельзя смешивать иллюстративные и инструментальные модели Вопросы в связи с моделью: Что будет, если…? и Соответствует ли…?


Слайд 85

Лекция 11. Классические модели


Слайд 86

87 Общепринятая модель жизненного цикла программного обеспечения


Слайд 87

88 Общепринятая модель — источник базовых понятий Начало разработки — идентификация потребности Определение требований — определяются: контекст задачи, ожидаемые функции ограничения. Проекта еще нет. Спецификации системы в соответствии с требованиями — Определяется поведение системы: что она должна делать. Фактическое начало работ Проектирование (конструирование, дизайн) — определяется декомпозиция системы /архитектура & результат ее построения/: как достигается соответствие спецификациям Реализация (кодирование) — разрабатываются модули (в модели нет этапа интеграции): что обеспечивает требуемый результат Тестирование — проверка соответствия спецификациям Сопровождение — поддержка использования продукта Развитие — поддержка эволюции системы (новый проект?)


Слайд 88

89 Классическая итерационная модель Отражает потребность исправления ошибок пройденных этапов!


Слайд 89

90 Исправление ошибок или адаптивность проекта? Классическая итерационная модель — абсолютизация возможности возвратов для исправления ошибок, т.е. Идея завершенности пройденных этапов — предсказуемость Стратегия итеративного наращивания возможностей ослабляет требование завершенности ООП + CASE-системы — принципиальная возможность поддержки итеративного наращивания (не более!) Адаптивность проекта — альтернатива предсказуемости Адаптивность должна закладываться в проект на самых ранних этапах его развития Задание: Приведите примеры, когда адаптивность вредна для разработки, поддержка адаптивности не помогает справиться со сложностью разработки. Ответы обоснуйте!


Слайд 90

91 Каскадная модель Чем заканчи- ваются этапы


Слайд 91

92 Каскадная модель: новые понятия Характерные черты каскадной модели: завершение этапов проверкой полученных результатов циклическое повторение пройденных этапов Чем заканчиваются этапы? Подтверждение — разного рода документальные согласования Обзор — документ, предоставляемый для согласования Проверка полученных результатов на соответствие целям: Верификация — отвечает на вопрос, правильно ли создана (декомпозиция, программная система и др.) Аттестация — отвечает на вопрос, правильно ли работает, т.е. будет использоваться (в первую очередь — программная система) Переаттестация — аттестация, которая устанавливает насколько хорошо система соответствует пользовательским запросам


Слайд 92

93 Строгая каскадная модель Чем заканчи- ваются этапы Удалены «лишние» возвраты За счет чего это достигается?


Слайд 93

94 Строгая каскадная модель: дополнительные требования к разработке проекта Минимизация возвратов за счет ликвидации переходов через уровни ужесточение проверок (барьеров) переход вниз сопровождается передачей исходного материала для следующего этапа — задание на разработку Причины невыполнения задания: оно противоречиво, т.е. содержит несовместные или невыполнимые требования; не выработаны критерии для выбора одного из возможных вариантов решения (i и ii) — ошибка предыдущего этапа > он возобновляется: ошибка ликвидируется > переход к следующему этапу (через барьер) невозможность исправления — это ошибка более раннего этапа > он возобновляется Два существенных момента (отражающих реальности разработок проектов): точное разделение работ, заданий и ответственности разработчиков и тех, кто инициирует переход к следующему этапу — шаг к осознанию фактического разделения труда малые циклы между соседними этапами, в результате достигается компромиссное задание — совместное выполнение соседних этапов, т.е. их перекрытие Однако в каскадной модели оба момента отражаются лишь косвенно


Слайд 94

95 Каскадная модель MSF Вехи (контрольные точки) используются в качестве точек оценки и перехода от одной фазы к другой. Все задачи одной фазы должны быть завершены до того, как начнется следующая фаза. Вехи Фазы (этапы) Каскадная модель работает, когда на начальном этапе проекта можно четко определить неизменный набор требований к разрабатываемому решению. Оценка: Слабее рассмотренной ранее строгой каскадной модели, но применимость характеризуется верно


Слайд 95

96 Вопросы и задания Какие из рассмотренных моделей можно сделать инструментальными, а какие не допускают этого? Ответ обосновать. С какими видами документов, используемых в качестве барьеров вы сталкивались? Ответ поясните.


Слайд 96

Лекция 12. Развитые модели жизненного цикла: Производственные функции в моделировании жизненного цикла: модель фазы — функции Гантера Моделирование жизненного цикла объектно-ориентированных программных проектов


Слайд 97

98 Модель фазы—функции Гантера: Анализ осущест- Конструиро- вание ? Программирование ? Оценка ? Фазы (этапы)  ?5 Спецификации утверждены  ?4 Спецификации составлены ?3 Требования утверждены ?2 Требования сформулированы ?1 Ресурсы распределены ?0 Необходимость разработки признана Компоновка завершена 6? Независимые испытания начались7? Начато использование изделия 8?  Изделие передано на распространение 9?  Изделие снято с производства 10?  Конт-рольные точки (события): фазовое измерение вимости ? Использование ? Исследо- вания ? Это традиционное последовательное выполнение проекта с перекрытием этапов


Слайд 98

99 Основной тезис: На разных этапах функции имеют различное содержание, требуют различной интенсивности, при реализации проекта совмещаются. Модель фазы—функции Гантера: предпосылки функционального измерения (производственные функции — классы функций) ·        Планирование ·        Разработка ·        Обслуживание ·        Выпуск документации ·        Испытания ·        Поддержка ·        Сопровождение Классы родственных функций можно считать выполняемыми в течение всего хода развития проекта; Содержание (цели) функции на различных этапах претерпевает изменение Интенсивность функции меняется как при переходе от этапа к этапу, так и в рамках работ одного этапа В конкретных проектах это понятие доопределяется (трактуется так, как полезно, например, как потребность или расходование ресурсов).


Слайд 99

100 10 Модель фазы—функции Гантера: функциональное измерение Программирование ? Оценка ? Фазы: 0 Планирование Разработка Обслуживание Выпуск документации Испытания Поддержка Сопровождение Использование ? 1 2 3 5 6 7 8 9 4 Функции: 0 1 2 3 5 6 7 8 9 10 4 Контрольные точки Анализ осущест- Конструиро- вимости ? вание? Исследо- вания ?


Слайд 100

101 Вариативность модели Гантера В зависимости от проекта функции можно трактовать свободно, дополнять другими классами функций, игнорировать некоторые из них и т.д. Можно рассматривать не только производственные функции, но и иное, полезное для управления (например, исполнителей проекта, трактуя интенсивность как занятость определенными заданиями) Основной тезис — основа построения функционального измерения модели, которое накладывается на фазовое измерение ? Матричная модель Элементы модели можно развивать, сохраняя требуемые связи моделируемой системы Возможность превращения модели в инструментальную На разных этапах функции имеют различное содержание, требуют различной интенсивности, при реализации проекта совмещаются.


Слайд 101

102 Учет итеративности в модели фазы—функции Программирование ? Оценка ? Использование ? Фазы (этапы) Контрольные точки Конструиро- вимости ? вание? 0 1 2 3 5 6 7 8 9 10 4 Исследо- вания ? Анализ осущест- Расщепление линии развития проекта (жизненного цикла): Приостановка процесса (в любой момент, если обеспечена корректность слияния) — традиционная реакция на ошибку Действительное расщепление — появляются два (и более?) процесса. Для корректности нужно оценивать ресурсы, планировать новые контрольные точки и определять содержание существующих контрольных точек Слияние расщепленных процессов в случае 2 — должно планироваться! ? Действительное расщепление обязано быть регламентированным!


Слайд 102

103 Моделирование жизненного цикла объектно-ориентированных программных проектов


Слайд 103

104 Принципы объектно-ориентированного проектирования Итеративность развития — возможность перейти от последовательного развития к стратегии итеративного наращивания возможностей Изменение функциональности — пересмотр требований при развитии проекта Формирование системы понятий проекта — развивающийся глоссарий проекта Наращивание функциональности в соответствии со сценариями — реализация выделенных сценариев; последующие итерации реализуют другие сценарии Ничто не делается однократно — отказ от завершенности работ классических этапов, повторное прохождение их на новых итерациях (с новым набором сценариев) Оперирование на размножающихся фазах подобно — обычные этапы при выполнении любой итерации развития проекта: Определение требований, или планирование итерации; Анализ; Моделирование пользовательского интерфейса /новое/; Конструирование; Реализация (программирование); Тестирование; Оценка результатов (итерации) Вне итераций: Начальная фаза проекта: требования, ближайшая и перспективные задачи, критерии оценки результатов; Фаза завершения проекта: поставка и сопровождение + выделение переиспользуемых компонентов


Слайд 104

105 Моделирование при объектно-ориентированном проектировании Распределение реализуемых требований по итерациям: Совокупность сценариев, реализуемых на очередной итерации + набор ранее реализованных сценариев образуют законченную, хотя и неполную версию системы, предлагаемую пользователям — модели уровня анализа Особый стиль наращивания возможностей системы и ее развития: Основа декомпозиции проекта при ООП подходе — набор связанных различными отношениями классов; новая итерация расширяет этот набор. Это расширение строится на базе построения — моделей уровня конструирования Моделирование —организационно-техническая (производственная) функция всего процесса развития проекта, а не один из этапов! Следствие: Пополнение базового окружения проекта — дополнительный этап (вложенный в оценку), содержание которого — анализ возможного переиспользования накапливаемых компонентов ПО как для проекта, так и для будущего


Слайд 105

?5 Спецификации утверждены ?6 Автономная проверка завершена, комплексное тестирование началось ? Программирование ? ? Оценка ? ? Использование ? Фазы (этапы) Тестирование завершилось, начата подготовка век подготовка новой итерации 7? Конт-рольные точки (события): Итеративное зацикливание Пополнение базового окружения проекта Общие требования и общий план составлены, ближайшая и перспективная задачи, критерии оценки результатов определены Окончание работ Начало проекта Исследования Завершение проекта ? Анализ осуществимо- сти ? вание? Конструиро- Жизненный цикл при объектно-ориентированном развитии проекта (фазовое измерение) ?0 Необходимость разработки признана ?1 Ресурсы распределены ?4 Спецификации реализуемых сценариев составлены ?3 Требования к очередной итерации утверждены ?2 Требования к очередной итерации сформулированы Требования к новой итерации приняты 8? Начато использование изделия 9? Изделие или его версия передано на распространение 10? Извещение о прекращении поддержки изделия (версии) выпущено 11? Изделие (версия) снято с производства 12? 106


Слайд 106

107 Контрольные точки и вехи Контрольные точки (check points) — точки линии жизни жизненного цикла проекта, в которых возникают определенные события. Эти события рассматриваются как существенные, поскольку их необходимо отслеживать с целью управляемого развития проекта (такого, которое оставляет траекторию в рамках области допустимых операционных маршрутов) Вехи (mail stones) — это контрольные точки, прохождение которых сопровождается определенными планируемыми мероприятиями. Без успешного (результат соответствует цели) проведения таких мероприятий, прохождение вехи блокируется с целью выполнения активностей, направленных на исправление ситуации. Планирование получения результата и оценка полученного результата — основное содержание деятельности, связанной с вехами Конкретизация контрольных точек и вех — существенная задача, которую приходится решать в рамках выполнения функции планирования. Эта конкретизация делается на основе знания специфики выполняемого проекта и процесса его выполнения (т.е. приятой для проекта методологии). Специфика проекта и процесса определяет необходимость и количество вех.


Слайд 107

108 Для каждой итерации должны быть определены: Общие требования — что требуется от проекта в целом в данный момент Общий план — как предполагается достигать цели (стратегия) Ближайшая задача — набор конкретных реализуемых требований и сценариев < критерии предпочтения того, что планируется реализовывать Перспективные задачи — те, которые рассматриваются (в данный момент) как основа для планирования дальнейших итераций (в проектах жесткой отчетности) Критерии предпочтения: Актуальность для пользователя Полнота и функциональная замкнутость предлагаемых средств Функциональная полнота Реализационная полнота Интерфейсная полнота Системная значимость (внутрипроектные предпочтения) Демонстрационная значимость Скорость реализации Общие требования, общий план, ближайшая и перспективные задачи Характеристики значимости: Возможные ограничения: время, объем работ, затраты (треугольник менеджмента) Всегда лучше то, что актуально! Автоматизация деятельности в целом. Растет по мере увеличения объема уже выполненных работ Реализационные предпочтения. Конкурирует с (1). Более значим для начальных итераций Конкурирует с (1), (2) и (3) Максимально значимо для начальных итераций Лучше то, что быстрее. Если время фиксировано, то для реализации определяется пул работ. Иногда время не критерий, а ограничение Минимизация реализуемого является критерием лишь для некоторых методологий!


Слайд 108

109 Жизненный цикл при объектно-ориентированном развитии проекта (функциональное измерение) Планирование Разработка Обслуживание Выпуск документации Испытания Поддержка Сопровождение Моделирование Планирование Разработка Обслуживание Выпуск документации Испытания Поддержка Сопровождение Моделирование ? Исследова- ния? ? Программирование ? ? Оценка ? ? Использование ? Фазы (этапы) 5  4 3 2 1 0 7 9 10 12  Итеративное зацикливание Пополнение базового окружения проекта 6 8  Окончание работ 11 Контрольные точки (события) Анализ осущест- Конструиро- вимости ? вание?


Слайд 109

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


Слайд 110

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


Слайд 111

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


Слайд 112

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


Слайд 113

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


Слайд 114

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


Слайд 115

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


Слайд 116

Выбор структуры для типа 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 — тоже производное поле!


Слайд 117

Выбор структуры для типа 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;


Слайд 118

Анализ выбранной структуры для типа 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 использовать поля с индексами соответствующих строк, а сами строки хранить в еще одном специальном файле Это даст сокращение размеров базы данных (в частности, за счет однофамильцев, тезок, земляков и т.п.). Нужно ли это реализовывать, без обстоятельного анализа будущего применения системы сказать трудно


Слайд 119

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


Слайд 120

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


Слайд 121

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


Слайд 122

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


Слайд 123

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


Слайд 124

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


Слайд 125

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


Слайд 126

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


Слайд 127

Таблицы и базы данных (1) таблица строка столбец table row column отношение кортеж атрибут relation tuple attribute файл запись поле file record field База данных — набор связанных таблиц: Строка описывает объект, или сущность (entity) Столбец описывает свойство, или атрибут объекта Первичный ключ – свойство, которое определяет, идентифицирует запись (объект, сущность) имя таблицы + первичный ключ + столбец => значение Пользовательские таблицы — данные и Системные таблицы — описание базы данных (системные каталоги, мета данные и др.) К правилам Кодда: Обеспечивать возможность доступа к любым таблицам, в т.ч. к системным, причем точно такую же возможность, что и к пользовательским таблицам. Пользовательские термины «Академические» термины Термины из обработки данных


Слайд 128

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


Слайд 129

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


Слайд 130

Манипулирование данными: выборка select * from publishers вставка строки insert into publishers values (‘0010’,‘Pragma’,‘45 10th ln.’,‘Chicago’,‘IL’) Определение данных create table test (id int, name char (15)) Администрирование данными grant select on test to Kate Примеры pub_id pub_name address city state ------------------------------------------------------------- 0736 New Age Books 1 1st St. Boston MA 0897 Binnet&Hardley 12 2nd Ave. Washington DC 1345 Algodata Info 10 3rd Dr. Btrkley CA Kate разрешена выборка из таблицы test select * from test id name ------------------------------------------------------------- Снова тот же select: pub_id pub_name address city state ------------------------------------------------------------- 0736 New Age Books 1 1st St. Boston MA 0897 Binnet&Hardley 12 2nd Ave. Washington DC 1345 Algodata Info 10 3rd Dr. Btrkley CA 0010 Pragma 45 10th ln. Chicago IL


Слайд 131

Основа всех операций – оператор 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_id pub_name address city state ------------------------------------------------------------- 0736 New Age Books 1 1st St. Boston MA 0897 Binnet&Hardley 12 2nd Ave. Washington DC 1345 Algodata Info 10 3rd Dr. Btrkley CA 0010 Pragma 45 10th ln. Chicago IL pub_id pub_name address city state ------------------------------------------------------------- 1345 Algodata Info 10 3rd Dr. Btrkley CA Можно комбинировать проецирование и выборку Результат – таблица: pub_id pub_name ------------------------------------------------------------- 0736 New Age Books 0897 Binnet&Hardley 1345 Algodata Info 0010 Pragma


Слайд 132

select title, pub_name from titles, publishers where publishers.pub_id = titles.pub_id Результат: title pub_name ------------------------------------------------------------- TTTT lll rrr New Age Books Jjj lll rrr New Age Books EEE yyy New Age Books BBBBB1 Binnet&Hardley BBBBB2 Binnet&Hardley BBBBB3 Binnet&Hardley AAA book1 Algodata Info AAA book2 Algodata Info PPPPPPPPP Pragma ? ? 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 ?


Слайд 133

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


Слайд 134

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


Слайд 135

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


Слайд 136

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


Слайд 137

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


Слайд 138

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


Слайд 139

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


Слайд 140

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


Слайд 141

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


Слайд 142

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


Слайд 143

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


Слайд 144

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


Слайд 145

Проект БД «Книги, авторы, издатели» (3) Отношения один ко многим Задача: связать Titles и Publishers. В результате анализа информационной среды выяснено требование, реализовать запросы, в которых название книги фигурирует совместно с издателем. Требуется обеспечить возможность объединения этих таблиц Первая попытка: Это ошибка: На все названия книг столбцов не напасешься. Трудно модифицировать данные (нереально определять для новой книги столбец) Решение обратное: Снабдить Titles внешним ключом


Слайд 146

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


Слайд 147

Проект БД «Книги, авторы, издатели» (5) Отношения многие к многим Автор может писать много книг, а книгу могут писать многие авторы Учет этого отношения > нужна реализация объединения таблиц Таблица связей, или ассоциация: Это пример составного первичного ключа. Можно рассматривать таблицу-ассоциацию как объект, связанный с книгами (авторами) отношением один ко многим: одна ассоциация — одна книга (один автор), книга (автор) может входить в несколько ассоциаций. Нужна соответствующая пара ограничений на целостность (как выше). Связь и придуманный объект могут иметь содержательный смысл и, в частности, свои атрибуты (пример – накладная) Ассоциация – это два отношения один к многим Отношения один к многим и многие к многим и понятия главной и детализирующей таблиц


Слайд 148

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


Слайд 149

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


Слайд 150

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


Слайд 151

Проект БД «Книги, авторы, издатели» (9) Диаграммы «Сущность – связь» (ER-диаграммы) Их нужно уметь Составлять Читать


Слайд 152

Лекция C. Нормализация


Слайд 153

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


Слайд 154

Первая нормальная форма: пример Tаблица Sales не удовлетворяет пожеланию заказчика иметь в одном заказе несколько книг. Есть четыре варианта, как это преодолеть: на уровне приложения синтезировать общий заказ из нескольких «одно-книжных» — это не то: не появился объект «составной заказ», и для него не может быть никаких действий, общих для всех приложений нарушить 1НФ: атрибут title_id сделать составным (множеством, коллекцией и др.) — плохо не только формально, но и по содержанию: трудно отслеживать ссылочную целостность, искать заказы по этому атрибуту, строить объединения таблиц по связи становится невозможным; вместо одного атрибута title_id построить несколько: title_id1, title_id2, … — не решает проблему при появлении заказа с числом позиций (книг) более чем их было до того, придется добавлять в Sales новый столбец (проблемы с преобразованием таблиц) или делать ее непрямоугольной (абсурдно) Правильное решение: из первоначальной Sales сделать две таблицы: главная: Sales содержит сведения о заказе в целом и не содержит атрибута, указывающего на книги заказа (title_id), но связана отношением 1:N с дополнительной таблицей (механизм внешних ключей) детализирующая: SalesDetail описывает позиции всех заказов (составной атрибут в виде набора своих строк, каждая из которых должна давать доступ к названиям книг) доступ к книгам обеспечен через SalesDetail посредством связи с Titles


Слайд 155

Первая нормальная форма: пример (результат) Что здесь обязательно, а что относится к специфике? обязательное Связь главной Sales и детализирующей SalesDetail следствие специфики: параTitles и SalesDetail < заказы n:m книги не пришлось «придумывать» объект «позиция заказа» Из требований 1НФ, получился тот же результат, что и при объектном моделировании: таблица связи между двумя таблицами объектов, в отношении n:m 1НФ: искать столбцы с неатомарными значениями (требуется поиск тех, кто находится в одном штате > нужно выделить в address дополнительные атрибуты city и state). О «плоских» таблицах Позиция заказа содержательно подчинена заказам, но реляционная модель не может выражать этого В ООП объекты главной и подчиненной таблиц равнозначны Это отрицательно сказывается на эффективности представления ООМодели в реляционном стиле


Слайд 156

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


Слайд 157

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


Слайд 158

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


Слайд 159

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


×

HTML:





Ссылка: