Станьте совладельцем корпорации
Главная  
  • Программы  
  • Методички  
  • Рефераты  
  • Дипломы  
  • Разное  
  • Фото  
  • Контакты  
  • Карта сайта  

  • Я:
    Найти:
    Возраст:
    -

    Лекции по дисциплине Теория управления данными

    Транзитивное замыкание отношений

    Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.

    Определение 11. Пусть отношение задано на декартовом квадрате некоторого множества . Транзитивным замыканием отношения называется новое отношение , состоящее из кортежей , для которых выполняется:

    • либо кортеж ,
    • либо найдется конечная последовательность элементов , такая, что все кортежи принадлежат отношению .

    Очевидно, что .

    Пример 7. Пусть множество представляет собой следующее множество деталей и конструкций:

    = {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}

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

    Конструкция

    Где используется

    Болт

    Двигатель

    Болт

    Колесо

    Гайка

    Двигатель

    Гайка

    Колесо

    Двигатель

    Автомобиль

    Колесо

    Автомобиль

    Ось

    Колесо

    Таблица 5 Отношение R

    Транзитивное замыкание состоит из кортежей (добавленные кортежи помечены серым цветом):

    Конструкция

    Где используется

    Болт

    Двигатель

    Болт

    Колесо

    Гайка

    Двигатель

    Гайка

    Колесо

    Двигатель

    Автомобиль

    Колесо

    Автомобиль

    Ось

    Колесо

    Болт

    Автомобиль

    Гайка

    Автомобиль

    Ось

    Автомобиль

    Таблица 6 Транзитивное замыкание отношения R

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

    Выводы

    Множество- это неопределяемое понятие, представляющее некоторую совокупность данных. Элементы множества можно отличать друг от друга, а также определять, принадлежит ли данный элемент данному множеству. Над множествами можно выполнять операции объединения, пересечения, разности и дополнения.

    Новые множества можно строить при помощи понятия декартового произведения (конечно, есть и другие способы, но они нас в данный момент не интересуют). Декартово произведение нескольких множеств - это множество кортежей, построенный из элементов этих множеств.

    Отношение- это подмножество декартового произведения множеств. Отношения состоят из однотипных кортежей. Каждое отношение имеет предикат отношения и каждый n-местный предикат задает n-арное отношение.

    Отношение является математическим аналогом понятия "таблица".

    Отношения обладают степенью и мощностью. Степень отношения - это количество элементов в каждом кортеже отношения (аналог количества столбцов в таблице). Мощность отношения - это мощность множества кортежей отношения (аналог количества строк в таблице).

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






    Содержание:

    1 Множества

    2 Декартово произведение множеств

    3 Примеры отношений

    4 Транзитивное замыкание отношени

    5 Базовые понятия реляционной модели данных

    6 Типы данных

    7 Домены

    8 Отношения, атрибуты, кортежи отношения

    Выводы

    © Copyright 2006-2024. Все права защищены. Сайт бесплатно.