체이스(알고리즘)

추적은 데이터베이스 시스템에서 데이터 의존성을 테스트하고 영향을 적용하는 단순한 고정 소수점 알고리즘입니다.그것은 실제로뿐만 아니라 데이터베이스 이론에서도 중요한 역할을 한다.데이터베이스를 설계하는 사람들에 의해 매일 직간접적으로 사용되며, 상용 시스템에서 ^{[citation needed]}데이터 설계의 일관성과 정확성을 추론하기 위해 사용됩니다.메타데이터 관리 및 데이터 교환에 대한 새로운 응용 프로그램이 여전히 발견되고 있습니다.

그 추적은 알프레드 5세가 쓴 1979년의 두 개의 중요한 논문에서 비롯되었다. 아호, 캐트리엘 비어리, 그리고 제프리 D. 울만과^[1] 다른 하나는 데이비드 메이어, 알베르토 O. 멘델존과 예호수아 ^[2]사기브요

가장 간단한 어플리케이션에서 추적은 주어진 분해에 대한 기능 의존성에 의해 제약된 관계 스키마의 투영을 투영에 다시 결합함으로써 회복할 수 있는지 여부를 테스트하기 위해 사용된다.${\displaystyle {S{}_{}}_{}}$ ${\displaystyle {{1\mathrm{}}_{}}_{}}$(${\displaystyle R}$ ) ${\displaystyle 、}$ ${\displaystyle {S{}_{}}_{}{{2\mathrm{}}_{}}_{}}$ (${\displaystyle }$R )${\displaystyle .}$、 .${\displaystyle 、}$ ${\displaystyle {S{}_{}}_{}{k_{}}_{}}$ (${\displaystyle R}$) 、 \ $displaystyle \pi$_ { $S$_ { S _ {1$}$ （ $R$） \ $bowtie \pi$_ {$S$_ { $2$} （ R ） \ $bowtie ...$의 태플이 됩니다.기능 의존성(강제 통풍)의 R은 관계와 F\bowtie \pi _{S_{km그리고 4.9초 만}}(R)}의 세트이다. 만약 R에서 tuples t1,..., tk로 나타냅니다, 각 피자의 돌출부에 조인이π S에서 나는{\displaystyle \pi_{S_{나는}}(R)(R)동의해야 한다}제가 거기 정도 1,2,..., k. 만약 tiπ S나는(R){\displaystyle \pi에 없습니다._{S$_{i}}(R$ 값을 알 수 없습니다.

추적은 tableau(tableau 쿼리에서 사용되는 형식과 동일)를 그려서 수행할 수 있습니다.R에 A, B, ... 속성이 있고 t의 성분이 a, b, …라고 가정합니다.S에_i 있는_i 성분에 t와 같은 문자를 사용하고 성분이 S에 없는_i 경우 i를 첨자로 붙입니다.그러면_ii S에 있으면 t에 동의하고 그렇지 않으면 고유한 값을 갖게 됩니다.

추적 과정은 합류하는 것이다.추적 ^[3]알고리즘의 구현이 존재하며, 그 중 일부는 오픈 ^[4]소스이기도 합니다.

예

R(A, B, C, D)을 함수 종속성 F = {A→B, B→C, CD→A}에 따르는 것으로 알려진 관계 스키마라고 하자.R을 세 개의 관계 스키마₁ S = {A, D}, S₂ = {A, C} 및₃ S = {B, C, D}로 분해한다고 가정하면, 이 분해가 무손실인지 아닌지는 아래와 같이 추격을 통해 판단할 수 있다.

이 분해의 첫 번째 표는 다음과 같습니다.

A	B	C	D
a	b1.	c1.	d
a	b2.	c	d2
1개3	b	c	d

첫 번째 행은 S를 나타냅니다₁.속성 A 및 D에 대한 구성요소는 스크립팅 해제되고 속성 B 및 C에 대한 구성요소는 i = 1에 스크립팅됩니다.두 번째 행과 세 번째 행은 각각 S와₃ S로 같은₂ 방식으로 채워집니다.

이 검정의 목적은 주어진 F를 사용하여 t = (a, b, c, d)가 실제로 R에 있음을 증명하는 것입니다.이를 위해 FD를 F에 적용하여 테이블로의 기호를 동일하게 함으로써 테이블로를 추적할 수 있습니다.t와 같은 행이 있는 최종 표에서는 투영 결합의 모든 태플 t가 실제로는 R의 태플임을 나타냅니다.
추적 테스트를 수행하려면 먼저 F의 모든 FD를 분해하여 각 FD가 "화살표" 오른쪽에 단일 속성을 갖도록 합니다(이 예에서는 모든 FD가 오른쪽에 단일 속성을 이미 가지고 있으므로 F는 변경되지 않습니다).F = {A→B, B→C, CD→A}).

두 기호를 동일시할 때, 두 기호 중 하나가 스크립트가 없는 경우, 다른 기호를 동일하게 하여 최종 표가 t = (a, b, c, d)와 정확히 동일한 행을 가질 수 있도록 합니다.둘 다 고유한 첨자가 있는 경우 다른 첨자로 변경합니다.그러나 혼란을 피하기 위해 모든 발생을 변경해야 합니다.
먼저 테이블로에 A→B를 바른다.첫 번째 행은 (a, b₁, c₁, d)입니다.여기서 a는 스크립트 해제되고₁ b는 1로 서브스크립트 됩니다.첫 번째 행과 두 번째 행을 비교하여 b를 b로₁ 변경합니다₂.세 번째 행에는 a가 있으므로₃ 세 번째 행의 b는 동일하게 유지됩니다.결과는 다음과 같습니다.

A	B	C	D
a	b1.	c1.	d
a	b1.	c	d2
1개3	b	c	d

B→C를 고려합니다.첫 번째 행과 두 번째 행 모두 b가 있고₁ 두 번째 행에 스크립트되지 않은 c가 있음을 알 수 있습니다.따라서 첫 번째 행은 (a, b₁, c, d)로 바뀝니다.그 결과, 다음과 같이 됩니다.

A	B	C	D
a	b1.	c	d
a	b1.	c	d2
1개3	b	c	d

이제 CD→A에 대해 생각해 보겠습니다.첫 번째 행에는 스크립트되지 않은 c와 스크립트되지 않은d가 있습니다.이것은 세 번째 행과 동일합니다.즉, 1행과 3행의 A 값도 같아야 합니다.따라서 세 번째 행의 a를 a로 변경합니다₃.결과는 다음과 같습니다.

A	B	C	D
a	b1.	c	d
a	b1.	c	d2
a	b	c	d

이 시점에서 세 번째 행은 t와 같은 (a, b, c, d)입니다.따라서 이것은 주어진 R과 F와의 추적 테스트의 최종 표입니다.따라서 R이 S, S₂, S에₁₃ 투영되었다가 다시 결합될 때마다 결과는 R이 됩니다. 특히 결과 튜플은 {B, C, D}에 투영된 R의 튜플과 동일합니다.

레퍼런스

• 세르게이 아비테불, 리처드 B. Hull, Victor Vianu: 데이터베이스의 기초.애디슨 웨슬리, 1995년
• A. V. Aho, C.비어리와 J.D. 울만:관계형 데이터베이스의 결합 이론.ACM Transactions on Database Systems 4(3): 297-314, 1979.
• J. D. Ullman: 데이터베이스와 놀리지 베이스 시스템의 원리, 제1권.컴퓨터 사이언스 프레스, 뉴욕, 1988년
• J. D. Ullman, J. Widom: 데이터베이스 시스템 첫 번째 코스 (제3판). 페이지 96~99.Pearson Frentice Hall,
• 마이클 베네딕트, 조지 콘스탄티니디스, 얀살바토레 메카, 보리스 모티크, 파올로 파포티, 도나텔로 산토로, 에프티미아 차모우라:Chase 벤치마킹2017년 PODS의 Proc.에서.

추가 정보

• Sergio Greco; Francesca Spezzano; Cristian Molinaro (2012). Incomplete Data and Data Dependencies in Relational Databases. Morgan & Claypool Publishers. ISBN 978-1-60845-926-1.