튜플 관계 미적분학

Tuple relational calculus

투플 미적분은 에드가 F에 의해 만들어지고 소개된 미적분이다. 관계형 모델의 일부로, 이 데이터 모델에서 데이터 조작을 위한 선언적 데이터베이스 쿼리 언어를 제공하기 위해 Codd.그것은 데이터베이스 쿼리 언어 QUEL과 SQL에 대한 영감을 형성했으며, 그 중 후자는 원래의 관계 모델과 미적분학에 훨씬 덜 충실하지만, 현재는 사실상의 표준 데이터베이스 쿼리 언어가 되었다; SQL의 방언은 거의 모든 관계 데이터베이스 관리 시스템에 의해 사용된다.미셸 라크로스와 알랭 피로테가 제안한 도메인 미적분학은 1차적 논리에 가깝고 Codd와 함께 이러한 미적분학(관계 대수학뿐만 아니라)이 모두 표현력에서 동등하다는 것을 보여주었다.이후 관계형 모델에 대한 쿼리 언어는 적어도 이러한 쿼리를 모두 표현할 수 있다면 관계형 완전 언어라고 불렸다.null

미적분학의 정의

관계형 데이터베이스

미적분학은 관계형 데이터베이스의 질의어이기 때문에 우리는 먼저 관계형 데이터베이스를 정의해야 한다.기본적인 관계형 빌딩 블록은 도메인이다(일부는 비슷하지만 동일하지는 않은 데이터 유형).튜플(tuple)은 순서가 정해진 도메인과 값의 쌍으로 정렬된 속성의 유한 순서다.관계는 (호환성) 튜플의 집합이다.이러한 관계적 개념은 수학적으로 정의되지만, 그러한 정의는 전통적인 데이터베이스 개념에 느슨하게 매핑된다.표는 관계에서 허용되는 시각적 표현이다. 튜플은 행의 개념과 유사하다.null

우리는 먼저 "이름", "작성자", "주소" 등이 그 예인 열 이름의 집합 C의 존재를 가정한다.우리는 헤더를 C의 유한 부분 집합으로 정의한다.관계형 데이터베이스 스키마는 tuple S = (D, R, h)로 정의된다. 여기서 D는 원자 값의 영역이다(영역과 원자 값의 개념에 대한 자세한 내용은 관계 모델 참조), R은 관계 이름의 유한 집합이다.

h : R → 2C

R의 각 관계 이름과 헤더를 연결하는 함수(이것은 둘 이상의 도메인이 있고 헤더가 열 이름 집합이 아니라 이 열 이름을 도메인에 매핑하는 전체 관계 모델에서 단순화한 것이라는 점에 유의한다.)도메인 D에 주어진 우리는 일부 열 이름을 D의 원자 값에 매핑하는 부분 함수로 D에 대한 튜플을 정의한다.예로는 (이름 : "해리", 나이 : 25)가 있다.null

t : C ⇸ D

D에 대한 모든 튜플 집합은 T로D 표시된다.튜플 t가 정의되는 C의 부분집합을 t의 도메인(스키마의 도메인과 혼동해서는 안 됨)이라고 하며 돔(t)으로 표시한다.null

마지막으로 스키마 S = (D, R, h)가 주어진 관계형 데이터베이스를 함수로 정의한다.

db : R → 2TD

R의 관계 이름을 T의D 유한 부분 집합에 매핑하여 db(r)의 모든 관계 이름 r과 tuple t에 대해 다음을 보유한다.

돔(t) = h(r)

후자의 요건은 단순히 관계 내의 모든 튜플이 동일한 열 이름, 즉 스키마에 정의된 열 이름을 포함해야 한다고 말한다.null

원자

공식의 구성을 위해 우리는 튜플 변수의 무한 세트 V를 가정할 것이다.수식은 데이터베이스 스키마 S = (D, R, h)와 일부 기능 유형: V ⇸ 2C(유형 할당 시 호출되며 일부 튜플 변수에 헤더를 할당한다.그런 다음 다음과 같은 규칙으로 원자 공식 A[S, type] 집합을 정의한다.

  1. v와 w가 V, a 유형(v)과 b 유형(w)인 경우 v.a = w.b 공식은 A[S, type],
  2. V에서 v in type(v) 및 k가 D의 값을 나타내는 경우 v.a = k 공식은 A[S, type] 및
  3. V in V, r in R 및 type(v) = h(r)인 경우 공식 r(v)은 A[S, type]이다.

원자의 예는 다음과 같다.

  • (t.age = s.age) — t는 연령 속성을 가지며 s는 동일한 값을 갖는 연령 속성을 가진다.
  • (t.name = "Codd") — tuple t는 이름 속성을 가지고 있으며 값은 "Codd"이다.
  • Book(t) — tuple t는 관계 Book에 있다.

그러한 원자의 공식 의미론에는 S에 대한 데이터베이스 db와 S:의 도메인 위에 튜플 변수를 매핑하는 튜플 변수 결합 val : V → T가D 정의된다.

  1. v.a = w.b는 val(v)(a) = val(w)(b)인 경우에만 참이다.
  2. v.a = k는 val(v)(a) = k인 경우에만 참임
  3. r(v)은 val(v)이 db(r)에 있는 경우에만 참임

공식

원자는 1차 논리학에서 흔히 그렇듯이 논리 연산자 ∧(및), ∨(또는) 및 ((not)로 공식으로 결합될 수 있으며, 우리는 실존적 정량자 ∃(∃)와 만능정량자 ((∀)를 사용하여 변수를 결합시킬 수 있다.다음 규칙을 사용하여 F[S, type] 공식 집합을 귀납적으로 정의한다.

  1. A[S, type]의 모든 원자도 F[S, type]에 있다.
  2. f와1 f가2 F[S, type]에 있으면 f1 ∧ f2 공식도 F[S, type]에 있다.
  3. f와1 f가2 F[S, type]에 있으면 f1 ∨ f2 공식도 F[S, type]에 있다.
  4. f가 F[S, type]인 경우, formula f 공식도 F[S, type]에 있다.
  5. V에서 헤더와 f가 F[S, type[v->H]]의 공식인 경우, ∃ v : H ( f ) 공식도 F[S, type]에 있고, 여기서 type은[v->H] v를 H에 매핑한다는 점을 제외하고 유형과 동일한 함수를 나타낸다.
  6. V에서 H가 헤더와 f가 F[S, type[v->H]]에서 공식인 경우, v v : H ( f ) 공식도 F[S, type]에 있다.

수식의 예:

  • t.name = "C. J. Date" t.name = "H. Darwen"
  • 북(t) ∨ 매거진(t)
  • ∀ t : {저자, 제목, 주제} (¬ (Book(t) ∧ t.author = "C. J. Date" ∧ (t.subject = "관계 모델")))

마지막 공식에 따르면 C. J. Date에 의해 쓰여진 모든 책들은 그들의 주제로서 관계 모델을 가지고 있다.평소와 같이, 만약 이것이 공식의 의미론에 대해 모호함을 야기하지 않는다면 우리는 괄호를 생략한다.null

우리는 정량자가 스키마의 도메인 위에 있는 모든 튜플의 우주를 수량화한다고 가정할 것이다.이는 S에 대한 데이터베이스 db와 튜플 변수 바인딩 val : V -> T에D 대해 주어진 공식에 대해 다음과 같은 공식적 의미론들로 이어진다.

  1. f1 ∧ f는2 f가1 참이고 f가2 참이면 참이다.
  2. f1 ∨ f는2 f가1 참이거나 f가2 참이거나 둘 다 참일 경우에만 참이다.
  3. ¬ f는 만약 f가 사실이 아니라면 그리고 만약 f가 사실이 아니라면,
  4. ∃ v : H ( f )는 D 위에 돔(t) = H와 같은 튜플 t가 있고 f 공식은 발에[v->t] 대해 참인 경우에만 참이다.
  5. ∀ v : H ( f )는 D를 초과하는 모든 튜플 t에 대해 dom(t) = H 공식 f가 val에[v->t] 대해 참인 경우에만 참이다.

쿼리

마지막으로 주어진 스키마 S = (D, R, h):

{ v : H f(v) }

여기서 v는 튜플 변수, H 헤더 및 f(v) 형식(F[S, type], 여기서 type = { (v, H) }이고 v를 유일한 자유 변수로 사용함.S에 대한 주어진 데이터베이스 db에 대한 그러한 질의의 결과는 db에 대해 f가 참이고 val = { (v, t) }인 D에 대한 모든 tuplle t의 집합이다.

쿼리 표현식의 예는 다음과 같다.

  • { t : {name} ∃ s : {name, 삯} (사원 ∧ s.임금 = 50.000 ∧ t.name = s.name ) }
  • { t : {supplier, article} ∃ s : {s#, sname} ( Supplier(s) ∧ s.sname = t.supplier ∧ ∃ p : {p#, pname} ( Product(p) ∧ p.pname = t.article ∧ ∃ a : {s#, p#} ( Supplies(a) ∧ s.s# = a.s# ∧ a.p# = p.p# ))) }

미적분의 의미적 및 통사적 제한

도메인 독립 쿼리

정량자의 의미론은 스키마의 도메인 전체에 걸쳐 튜플을 정량화하는 것이기 때문에, 다른 스키마가 추정될 경우 쿼리가 특정 데이터베이스에 대해 다른 결과를 반환할 수 있다.예를 들어 도메인 D1 = { 1 }, D2 = { 1, 2 }, 관계 이름 R = {r1" }, 헤더 h = {"a1"}이(가) 있는 두 스키마 S1 = (D1, R, h )와 S2 = (D2, R, h )를 고려하십시오. 두 스키마는 공통적인 예가 있다.

db = { ( "r1", {("a", 1) } ) }

다음 쿼리 식을 고려하는 경우

{ t : {a} t.a = t.a }

그 다음 db에 대한 결과는 S에1 따라 { (a : 1) } 또는 S에2 따라 { (a : 1) }이다.도메인을 무한 집합으로 가져가면 질의의 결과도 무한이 된다는 것도 분명할 것이다.이러한 문제를 해결하기 위해 도메인 독립 쿼리, 즉 모든 스키마에서 데이터베이스에 대해 동일한 결과를 반환하는 쿼리에 대한 주의를 제한한다.null

이러한 쿼리의 흥미로운 속성은 데이터베이스 또는 쿼리 표현식에서 적어도 하나의 튜플에서 발생하는 도메인의 하위 집합인 데이터베이스의 소위 활성 도메인에서 튜플을 초과한다고 가정할 경우 쿼리 표현식의 의미론이 변경되지 않는다는 것이다.실제로 튜플 미적분학의 많은 정의에서 정량자의 의미론적 정의는 이렇게 정의되는데, 이것은 정의 영역별 모든 질의를 독립적으로 만든다.null

안전 쿼리

도메인 독립적인 쿼리만 표현하도록 쿼리 표현을 제한하기 위해 안전 쿼리의 구문적 개념이 일반적으로 도입된다.질의 표현식이 안전한지 결정하기 위해 우리는 질의에서 두 가지 유형의 정보를 도출할 것이다.첫째는 변수-열 쌍 t.a가 관계 또는 상수의 열에 바인딩되어 있는지 여부, 둘째는 두 변수-열 쌍이 직간접적으로 동일시되는지 여부(표시 t.v == s.w)이다.null

한정성을 도출하기 위해 다음과 같은 추론 규칙을 도입한다.

  1. v.a = w.b "에서 변수 열 쌍은 바인딩되지 않는다.
  2. v.a = k "에서 변수 열 쌍 v.a는 바인딩되어 있다.
  3. " r(v)"에서 모든 쌍 v.a는 in(v) 형식에 바인딩되어 있다.
  4. " f1 ∧ f2 "에서 모든 쌍은 f 또는1 f로2 구속된다.
  5. " f1 ∨ f2 "에서 모든 쌍은 f와1 f2 둘 다로 묶여 있다.
  6. " ¬ f "에서 쌍은 묶이지 않는다.
  7. " ∃ v : H ( f ) "에서 w.a 한 쌍은 f와 w <> v로 묶이면 바인딩된다.
  8. " ∀ v : H ( f ) "에서 w.a 한 쌍은 f와 w <> v로 묶이면 바인딩된다.

동일성을 도출하기 위해 우리는 다음과 같은 추론 규칙을 도입한다(동일성 관계에 대한 일반적인 추론 규칙 옆: 반사성, 대칭성 및 전이성).null

  1. " v.a = w.b "에서 v.a == w.b를 보유한다.
  2. " v.a = k "에서 어떤 쌍도 동일하지 않다.
  3. " r(v)"에서는 어떤 쌍도 동일시되지 않는다.
  4. " f1 ∧ f2 "에서 v.a == w.b를 f 또는1 f로2 고정하면
  5. " f1 ∨ f2 "에서 v.a == w.b는 f와1 f로2 둘 다 잡으면,
  6. " ¬ f "에서는 어떤 쌍도 동일시되지 않는다.
  7. " ∃ v : H ( f )에서, f와 w<v>와 x<v>로 고정되어 있으면 w.a == x.b를 고정하고,
  8. " ∀ v : H ( f )"에서는 f와 w<v>와 x<v>로 고정되어 있으면 w.a == x.b를 고정시킨다.

그런 다음 쿼리 표현식 {v : H f(v) }이(가) 다음과 같은 경우에 안전하다고 말한다.

  • 각 열 이름 a in H에 대해 v.a가 f의 바운드 쌍과 동일하다는 것을 알 수 있다.
  • ∀ w : G ( g ) 형식의 f의 모든 하위 표현에 대해 우리는 모든 열 이름에 대해 w.a가 g의 바운드 쌍과 동일하다는 것을 도출할 수 있다.
  • ∃ w : G ( g ) 형식의 f의 모든 하위 표현에 대해 우리는 모든 열 이름에 대해 w.a가 g의 바운드 쌍과 동일하다는 것을 도출할 수 있다.

표현될 수 있는 모든 도메인 독립 쿼리는 또한 안전한 쿼리 표현으로 표현될 수 있기 때문에 안전한 쿼리 표현에 대한 제한은 표현성을 제한하지 않는다.이는 스키마 S = (D, R, h), 쿼리 표현식의 상수 K 집합, 튜플 변수 v 및 헤더 H의 경우 값이 활성 도메인에 있음을 나타내는 in H로 모든 쌍 v.a에 대해 안전한 공식을 구성할 수 있음을 보여줌으로써 증명할 수 있다.예를 들어 K={1,2}, R={"r"} 및 h = {("r", {"a, "b"})라고 가정하면 v.b에 해당하는 안전 공식은 다음과 같다.

v.b = 1 ∨ v.b = 2 ∨ w (r(w) ∧ (v.b = w.a ∨ v.b = w.b ) )

그러면 이 공식은 모든 변수 v와 열 이름 a에 대해 이러한 공식을 식에서 사용되는 형식에 추가하여 안전하지 않은 쿼리 표현식을 동등한 안전한 쿼리 표현식으로 다시 쓰는 데 사용할 수 있다.효과적으로 이것은 우리가 모든 변수들이 활성 도메인에 걸쳐 있도록 한다는 것을 의미하는데, 이미 설명한 바와 같이 표현된 질의가 도메인 독립적이라면 의미론도 바꾸지 않는다.null

시스템들

참고 항목

참조