Основные реляционные операции над отношениями

Операция объединения (соединения) – объединение множества кортежей двух отношений в одно общее отношение. Операция определена для двух отношений одинаковой арности. Пусть R и S – отношения арности n. Объединение RÈS = { (V₁,V₂ … V_n) \ (V₁…V_n) є R Ú(V₁ … V_n) є S }

Операция разности отношений – разностью двух отношений арности n называется отношение (арности n), в которую включены кортежи первого отношения, не принадлежащие одновременно второму отношению. Пусть R и S – отношения арности n. Разность: R – S = { (V₁ … V_n) | (V₁ … V_n) є R Ù (V₁ … V_n) є S}

Операция декартового произведения – двух отношений R (арности n), и S (арности m) называется отношение арности m+n, кортежи которого составлены из кортежей R и S. Пусть R – отношение арности n, S – отношение арности m. Декартовое произведение для R= {(V₁ … V_n)} и S= {(W₁ … W_m)} это: RхS = {(V₁…V_n, W₁…W_m) \ (V₁…V_n)єRÙ(W₁…W_m)є S}

Операция проекции – это унарная операция, заключающаяся в проектировании отношения на заданную схему (отношения). Схема проектирования получается из схемы исходного отношения, удаления ряда атрибутов и (или) перестановки атрибутов исходной схемы. Пусть R – отношение арности n, обозначим π_i1,i2…im (R) – проекция R на атрибуты i₁, i₂, …i_m, где 1 ≤ i_j ≤ n, 1 ≤ j ≤ m. Проекция: π_i1,i2…im (R) = {(a₁ … a_m) | $ (b₁ … b_n) є R | a_j = b_ij " j = 1 … m }. Пример: проекция π_2,1(R) – составлена из значений второго и первого элемента схемы отношения R.

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

Пусть F (предикат на множества атрибутов) – логическая формула, в которую входят: константы; имена атрибутов; функции; операции арифметических отношений <, >, ≤, ≥≠, =; логические операции Ù,Ú,. Селекцией отношения R по формуле F – это отношение: δ_F(R)={(V₁…V_n)єR| F≡1}

Естественное соединение. Пусть отношение А имеет атрибуты{X₁, X₂…X_m, Y₁, Y₂…Y_n}, а отношение В {Y₁, Y₂…Y_n, Z₁, Z₂, …Z_k}. Атрибуты Y₁, Y₂ … Y_n, и только они являются общими для этих отношений. Пусть атрибуты с одинаковыми именами определены на одних и тех же доменах. Для простоты множества атрибутов обозначим буквами: X,Y,Z. Естественным соединением А и В (A Join B) называется отношение с атрибутами X, Y, Z, состоящими из кортежей (x, y, z), таких, для которых в отношении А атрибуты X=xÙY=y, при этом в отношении В атрибуты Y=yÙZ=z. (A Join B) JoinС = A Join (B Join C).

Задачи планирования и организации параллельных вычислений. Общие формулировки. Методы решения.

Два типа задач и их варианты распараллеливания на уровне подзадач. Оценка ресурсов ВС.

60. Понятие интерполяции. Полиномиальная интерполяция дискретных зависимостей (X_i, Y_i), полином Лагранжа.

Простейшая задача интерполирования заключается в следующем. На отрезке [a, b] заданы n+1 точек x₀, x₁, …, x_n, которые называются узлами интерполяции, и значения некоторой функции f(x) в этих точках:

f(x₀)=y₀, f(x₁)=y₁, …, f(x_n)=y_n. (1)

Требуется построить функцию F(x) (интерполирующая функция), принадлежащую известному классу и принимающую в узлах интерполяции те же значения, что и f(x), т.е. такую, что

F(x₀)=y₀, F(x₁)=y₁, …, F(x_n)=y_n. (2)

Геометрически это означает, что нужно найти кривую y=F(x) некоторого определённого типа, проходящую через заданную систему точек M_i(x_i, y_i) (i=0, 1, 2 …).

В такой общей постановке задача может иметь бесчисленное множество решений или совсем не иметь решений. Однако эта задача становится однозначной, если вместо произвольной функции F(x) искать полином P_n(x) степени не выше n, удовлетворяющий условиям (2), т.е. такой, что

P_n(x₀)=y₀, P_n(x₁)=y₁, …, P_n(x_n)=y_n.

Полученную интерполяционную формулу y=F(x) обычно используют для приближенного вычисления значений данной функции f(x) для значений аргумента х, отличных от узлов интерполирования. Такая операция называется интерполированием функции f(x). При этом различают интерполирование в узком смысле, когда x принадлежит [x₀, x_n], т.е. значение x является промежуточным между x₀ и x_n, и экстраполирование, когда x не принадлежит [x₀, x_n]. Обычно, под термином интерполирование понимают как первую, так и вторую операции.

Для произвольно заданных узлов интерполирования пользуются интерполяционной формулой Лагранжа. Пусть на отрезке [a, b] даны n+1 различных значений аргумента x₀, x₁, …, x_n и известны для функции y=f(x) соответствующие значения: f(x₀)=y₀, f(x₁)=y₁, …, f(x_n)=y_n. Полином L_n(x) степени не выше n, имеющий в заданных узлах x₀, x₁, …, x_n­ те же значения, что и функция f(x), т.е. такой, что L_n(x_i)=y_i (i=0, 1, 2, …, n) и имеющий вид

L_n(x) = ∑y_i * (x-x₀) * (x-x₁) * … * (x-x_i-1) * (x-x_i+1) * … * (x-x_n) /

(x_i-x₀) * (x_i-x₁) * … * (x_i-x_i-1) * (x_i-x_i+1) * … * (x_i-x_n).

называется полиномом Лагранжа.

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

x-x0	x0-x1	x0-x2	…	x0-xn
x1-x0	x-x1	x1-x2	…	x1-xn
x2-x0	x2-x1	x-x2	…	x2-xn
…	…	…	…	…
xn-x0	xn-x1	xn-x2	…	x-xn.

Обозначим произведение элементов первой строки через D₀, второй – через D₁ и т.д. Произведение элементов главной диагонали (в схеме эти элементы выделенным полужирным шрифтом), обозначим П_n+1(x). Тогда формула Лагранжа может быть приведена к следующему виду:

L_n(x)=П_n+1(x) * ∑ y_i/D_i (∑ по i=0, 1, …, n).