기능적 종속성 소개

이 기사에서는 데이터베이스의 기능적 종속성에 대해 설명합니다. 즉, 그것이 무엇인지, 어디에 사용되는지, 이를 찾기 위해 존재하는 알고리즘은 무엇인지에 대해 설명합니다.

관계형 데이터베이스의 맥락에서 기능적 종속성을 고려할 것입니다. 대략적으로 말하면, 이러한 데이터베이스에서는 정보가 테이블 형식으로 저장됩니다. 다음으로, 엄격한 관계 이론에서 상호 교환할 수 없는 대략적인 개념을 사용합니다. 테이블 자체를 관계, 열 - 속성(해당 세트 - 관계 스키마) 및 속성 하위 집합의 행 값 집합이라고 합니다. - 튜플.

예를 들어, 위의 표에서 (벤슨, M, M 오르간)는 속성의 튜플입니다. (환자, 폴, 의사).
보다 공식적으로는 다음과 같이 작성됩니다. [환자, 성별, 의사] = (벤슨, M, M 오르간).
이제 기능적 의존성(FD)의 개념을 소개할 수 있습니다.

정의 1. 관계 R은 임의의 튜플에 대해 연방법 X → Y(여기서 X, Y ⊆ R)를 충족합니다. , ∈ R은 다음을 유지합니다: [엑스] = [X] 그러면 [예] = [와이]. 이 경우 X(결정자 또는 속성 정의 집합)가 기능적으로 Y(종속 집합)를 결정한다고 말합니다.

즉, 연방법의 존재 X → Y 즉, 두 개의 튜플이 있는 경우 R 속성이 일치합니다. X, 그러면 속성이 일치합니다. Y.
그리고 이제 순서대로. 속성을 살펴보자 환자 и 성별 우리는 그들 사이에 종속성이 있는지 여부를 확인하고 싶습니다. 이러한 속성 집합에는 다음과 같은 종속성이 존재할 수 있습니다.

1. 환자 → 성별
2. 성별 → 환자

위에서 정의한 대로 첫 번째 종속성을 유지하려면 각 고유 열 값이 환자 하나의 열 값만 일치해야 합니다. 성별. 그리고 예제 테이블의 경우 실제로 그렇습니다. 그러나 이는 반대 방향으로는 작동하지 않습니다. 즉, 두 번째 종속성이 충족되지 않고 속성이 성별 에 대한 결정 요인이 아닙니다. 인내심 있는. 마찬가지로 의존성을 취하면 의사 → 환자, 값이 위반됨을 알 수 있습니다. 남자 이름 이 속성에는 여러 가지 다른 의미가 있습니다. 엘리스와 그레이엄.

따라서 기능적 종속성을 통해 테이블 ​​속성 집합 간의 기존 관계를 확인할 수 있습니다. 이제부터 우리는 가장 흥미로운 연결, 또는 오히려 그러한 연결을 고려할 것입니다. X → Y그것들은 무엇인가:

• 즉, 종속성의 오른쪽이 왼쪽의 하위 집합이 아닙니다. (Y̸⊆X);
• 최소한, 즉 그러한 의존성이 없습니다. Z → Y그 Z ⊂ X.

이 시점까지 고려된 종속성은 엄격했습니다. 즉, 테이블에 대한 위반을 제공하지 않았지만 그 외에도 튜플 값 사이에 약간의 불일치를 허용하는 종속성도 있습니다. 이러한 종속성은 대략적인 클래스라고 하는 별도의 클래스에 배치되며 특정 수의 튜플에 대해 위반될 수 있습니다. 이 양은 최대 오류 표시기 emax에 의해 규제됩니다. 예를 들어, 오류율 = 0.01은 고려된 속성 세트에서 사용 가능한 튜플의 1%가 종속성을 위반할 수 있음을 의미할 수 있습니다. 즉, 1000개의 레코드에 대해 최대 10개의 튜플이 연방법을 위반할 수 있습니다. 비교되는 튜플의 쌍별로 다른 값을 기반으로 약간 다른 측정항목을 고려해 보겠습니다. 중독의 경우 X → Y 태도에 r 그것은 다음과 같이 간주됩니다 :

오류를 계산해 봅시다. 의사 → 환자 위의 예에서. 속성에 따라 값이 다른 두 개의 튜플이 있습니다. 환자, 그러나 일치 의사: [의사, 환자] = (로빈, 엘리스) 그리고 [의사, 환자] = (로빈, 그레이엄). 오류 정의에 따라 충돌하는 모든 쌍을 고려해야 합니다. 이는 오류 쌍 중 두 개가 있음을 의미합니다., )와 그 역(, ). 이를 공식에 대입하여 다음을 얻습니다.

이제 "이 모든 것이 왜 필요한가?"라는 질문에 답해 보겠습니다. 실제로 연방법은 다릅니다. 첫 번째 유형은 데이터베이스 설계 단계에서 관리자가 결정하는 종속성입니다. 일반적으로 그 수가 적고 엄격하며 주요 응용 프로그램은 데이터 정규화 및 관계형 스키마 디자인입니다.

두 번째 유형은 "숨겨진" 데이터와 이전에 알려지지 않은 속성 간의 관계를 나타내는 종속성입니다. 즉, 이러한 종속성은 설계 당시 고려되지 않았으며 기존 데이터 세트에서 이미 발견되었으므로 나중에 확인된 많은 연방법을 기반으로 저장된 정보에 대한 결론을 도출할 수 있습니다. 우리가 작업하는 것은 바로 이러한 종속성입니다. 이를 기반으로 구축된 다양한 검색 기술과 알고리즘을 사용하여 데이터 마이닝의 전체 분야에서 처리됩니다. 모든 데이터에서 발견된 기능적 종속성(정확하거나 대략적인)이 어떻게 유용할 수 있는지 알아봅시다.

오늘날 종속성의 주요 응용 프로그램 중 하나는 데이터 정리입니다. 여기에는 "더러운 데이터"를 식별하고 수정하는 프로세스를 개발하는 작업이 포함됩니다. "더티 데이터"의 대표적인 예로는 중복, 데이터 오류 또는 오타, 누락된 값, 오래된 데이터, 추가 공백 등이 있습니다.

데이터 오류의 예:

데이터 중복의 예:

예를 들어, 실행해야 하는 연방법 표와 세트가 있습니다. 이 경우 데이터 정리에는 연방법이 정확해지도록 데이터를 변경하는 작업이 포함됩니다. 이 경우 수정 횟수는 최소화되어야 합니다(이 절차에는 자체 알고리즘이 있으므로 이 기사에서는 다루지 않습니다). 다음은 이러한 데이터 변환의 예입니다. 왼쪽에는 필요한 FL이 충족되지 않은 원래 관계가 있습니다(FL 중 하나를 위반한 예는 빨간색으로 강조 표시됨). 오른쪽에는 업데이트된 관계가 있으며, 녹색 셀에는 변경된 값이 표시됩니다. 이 절차 후에 필요한 종속성이 유지되기 시작했습니다.

또 다른 인기 있는 응용 프로그램은 데이터베이스 디자인입니다. 여기서는 정규 형식과 정규화를 기억할 가치가 있습니다. 정규화(Normalization)는 특정 요구사항 세트에 관계를 일치시키는 프로세스이며, 각 요구사항은 고유한 방식으로 정규 형식으로 정의됩니다. 우리는 다양한 정규형의 요구 사항을 설명하지 않을 것입니다(이는 초보자를 위한 데이터베이스 과정의 모든 책에서 수행됩니다). 그러나 각 정규형이 기능적 종속성 개념을 자체 방식으로 사용한다는 점만 참고할 것입니다. 결국 FL은 데이터베이스를 설계할 때 고려되는 본질적으로 무결성 제약 조건입니다(이 작업의 맥락에서 FL은 때때로 슈퍼키라고도 함).

아래 그림의 네 가지 정규 형식에 대한 적용을 고려해 보겠습니다. Boyce-Codd 정규형은 세 번째 형식보다 더 엄격하지만 네 번째 형식보다는 덜 엄격하다는 점을 기억하세요. 후자를 공식화하려면 다중 값 종속성에 대한 이해가 필요하지만 이 기사에서는 흥미롭지 않기 때문에 지금은 후자를 고려하지 않습니다.

종속성이 적용되는 또 다른 영역은 Naive Bayes 분류기 구축, 중요한 기능 식별, 회귀 모델 재매개변수화와 같은 작업에서 기능 공간의 차원을 줄이는 것입니다. 원문에서는 이 작업을 중복성 및 기능 관련성 결정[5, 6]이라고 하며 데이터베이스 개념을 적극적으로 사용하여 해결합니다. 이러한 연구의 출현으로 오늘날 위의 최적화 문제에 대한 데이터베이스, 분석 및 구현을 하나의 도구로 결합할 수 있는 솔루션에 대한 수요가 있다고 말할 수 있습니다[7, 8, 9].

데이터 세트에서 연방법을 검색하기 위한 많은 알고리즘(현대적이거나 최신적이지 않음)이 있습니다. 이러한 알고리즘은 세 그룹으로 나눌 수 있습니다.

• 대수 격자 순회를 사용하는 알고리즘(래티스 순회 알고리즘)
• 합의된 값 검색을 기반으로 하는 알고리즘(차이 및 합의 설정 알고리즘)
• 쌍별 비교 기반 알고리즘(종속성 유도 알고리즘)

각 알고리즘 유형에 대한 간략한 설명은 아래 표에 나와 있습니다.


이 분류에 대해 자세히 알아볼 수 있습니다[4]. 다음은 각 유형에 대한 알고리즘의 예입니다.

현재 기능적 종속성을 찾는 여러 가지 접근 방식을 결합한 새로운 알고리즘이 등장하고 있습니다. 이러한 알고리즘의 예로는 Pyro[2] 및 HyFD[3]가 있습니다. 이들의 작업에 대한 분석은 이 시리즈의 다음 기사에서 기대됩니다. 이 기사에서는 종속성 검색 기술을 이해하는 데 필요한 기본 개념과 보조정리만 살펴보겠습니다.

두 번째 유형의 알고리즘에 사용되는 간단한 차이 집합과 동의 집합부터 시작해 보겠습니다. Difference-set은 동일한 값을 갖지 않는 튜플의 집합이고, 반대로gree-set은 동일한 값을 갖는 튜플입니다. 이 경우 종속성의 왼쪽만 고려한다는 점은 주목할 가치가 있습니다.

위에서 접한 또 다른 중요한 개념은 대수 격자입니다. 많은 최신 알고리즘이 이 개념을 기반으로 작동하므로 그것이 무엇인지에 대한 아이디어가 필요합니다.

격자의 개념을 도입하기 위해서는 부분 순서 집합(partially ordered set, 줄여서 포셋)을 정의할 필요가 있습니다.

정의 2. 모든 a, b, c ∈ S에 대해 다음 속성이 충족되면 집합 S는 이진 관계 ⩽에 의해 부분적으로 정렬된다고 합니다.

1. 재귀성, 즉 a ⩽ a
2. 비대칭성, 즉 a ⩽ b이고 b ⩽ a이면 a = b입니다.
3. 이행성, 즉 a ⩽ b 및 b ⩽ c의 경우 a ⩽ c가 됩니다.

이러한 관계를 (느슨한) 부분 순서 관계라고 하며, 집합 자체를 부분 순서 집합이라고 합니다. 공식 표기법: ⟨S, ⩽⟩.

부분 순서 집합의 가장 간단한 예로, 일반적인 순서 관계 ⩽를 사용하여 모든 자연수 N의 집합을 사용할 수 있습니다. 필요한 모든 공리가 충족되는지 확인하는 것은 쉽습니다.

좀 더 의미 있는 예입니다. 포함 관계 ⊆에 따라 정렬된 모든 부분 집합 {1, 2, 3}의 집합을 생각해 보세요. 실제로 이 관계는 모든 부분 순서 조건을 충족하므로 ⟨P ({1, 2, 3}), ⊆⟩는 부분 순서 집합입니다. 아래 그림은 이 세트의 구조를 보여줍니다. 한 요소가 화살표로 다른 요소에 도달할 수 있으면 순서 관계에 있는 것입니다.

수학 분야에서 상한과 하한이라는 두 가지 간단한 정의가 더 필요합니다.

정의 3. ⟨S, ⩽⟩를 부분 순서 집합 A ⊆ S로 둡니다. A의 상한은 ∀x ∈ S: x ⩽ u를 충족하는 요소 u ∈ S입니다. U를 S의 모든 상한의 집합으로 둡니다. U에 가장 작은 요소가 있는 경우 이를 상한(supremum)이라고 하며 sup A로 표시합니다.

정확한 하한의 개념도 유사하게 도입됩니다.

정의 4. ⟨S, ⩽⟩를 부분 순서 집합 A ⊆ S로 둡니다. A의 하한은 ∀x ∈ S: l ⩽ x를 충족하는 요소 l ∈ S입니다. L을 S의 모든 하한의 집합으로 둡니다. L에 가장 큰 요소가 있는 경우 이를 하한(infimum)이라고 하며 inf A로 표시합니다.

위의 부분 순서 집합 ⟨P ({1, 2, 3}), ⊆⟩를 예로 들어 상한값과 하한값을 찾습니다.

이제 우리는 대수적 격자의 정의를 공식화할 수 있습니다.

정의 5. ⟨P,⩽⟩를 모든 두 요소로 구성된 부분 집합이 상한과 하한을 갖는 부분적으로 정렬된 집합이라고 가정합니다. 그러면 P를 대수적 격자(algebraic lattice)라고 합니다. 이 경우, sup{x, y}는 x ∨ y로, inf {x, y}는 x ∧ y로 작성됩니다.

작업 예제 ⟨P ({1, 2, 3}), ⊆⟩가 격자인지 확인해 보겠습니다. 실제로 임의의 a, b ∈ P ({1, 2, 3})에 대해 a∨b = a∪b 및 a∧b = a∩b입니다. 예를 들어, 집합 {1, 2} 및 {1, 3}을 고려하고 해당 집합의 극한과 극한을 찾습니다. 만약 우리가 그것들을 교차한다면, 우리는 극한이 될 집합 {1}을 얻게 될 것입니다. 우리는 {1, 2, 3}을 결합하여 최고점을 얻습니다.

물리적 문제를 식별하기 위한 알고리즘에서 검색 공간은 격자 형태로 표현되는 경우가 많습니다. 여기서 하나의 요소 집합(검색 격자의 첫 번째 수준을 읽으세요. 여기서 종속성의 왼쪽은 하나의 속성으로 구성됨)은 각 속성을 나타냅니다. 원래 관계의.
먼저, ∅ → 형식의 종속성을 고려합니다. 단일 속성. 이 단계에서는 어떤 속성이 기본 키인지 결정할 수 있습니다(이러한 속성의 경우 결정자가 없으므로 왼쪽은 비어 있습니다). 또한 이러한 알고리즘은 격자를 따라 위쪽으로 이동합니다. 전체 격자를 탐색할 수는 없다는 점은 주목할 가치가 있습니다. 즉, 원하는 왼쪽의 최대 크기가 입력에 전달되면 알고리즘은 해당 크기의 수준 이상으로 진행되지 않습니다.

아래 그림은 FZ를 찾는 문제에서 대수적 격자가 어떻게 사용될 수 있는지 보여줍니다. 여기서 각 모서리(엑스, XY)는 종속성을 나타냅니다. X → Y. 예를 들어, 우리는 첫 번째 단계를 통과했으며 중독이 유지된다는 것을 알고 있습니다. A → B (이를 정점 사이의 녹색 연결로 표시합니다. A и B). 이는 또한 격자를 따라 위로 이동할 때 종속성을 확인하지 못할 수도 있음을 의미합니다. A, C → B, 더 이상 최소가 아니기 때문입니다. 마찬가지로 종속성이 유지되었는지 확인하지 않습니다. ㄷ → ㄴ.

또한 일반적으로 연방법 검색을 위한 모든 최신 알고리즘은 파티션(원래 소스에서 제거된 파티션 [1])과 같은 데이터 구조를 사용합니다. 파티션의 공식적인 정의는 다음과 같습니다.

정의 6. X ⊆ R을 관계 r에 대한 속성 집합으로 설정합니다. 클러스터는 X에 대해 동일한 값을 갖는 r의 튜플 인덱스 집합입니다. 즉, c(t) = {i|ti[X] = t[X]}입니다. 파티션은 단위 길이의 클러스터를 제외한 클러스터 집합입니다.

간단히 말해서 속성에 대한 파티션입니다. X 각 목록에는 동일한 값을 가진 줄 번호가 포함된 목록 집합입니다. X. 현대 문헌에서는 파티션을 나타내는 구조를 PLI(Position List Index)라고 합니다. 단위 길이 클러스터는 항상 쉽게 식별할 수 있는 고유한 값을 가진 레코드 번호만 포함하는 클러스터이기 때문에 PLI 압축 목적에서 제외됩니다.

예를 살펴보겠습니다. 환자가 있는 동일한 테이블로 돌아가서 열에 대한 파티션을 구축해 보겠습니다. 환자 и 성별 (테이블 행 번호가 표시된 새 열이 왼쪽에 나타납니다):

또한 정의에 따르면 열의 파티션은 환자 단일 클러스터가 파티션에서 제외되므로 실제로는 비어 있습니다.

파티션은 여러 속성으로 얻을 수 있습니다. 이를 수행하는 방법에는 두 가지가 있습니다. 테이블을 검토하여 필요한 모든 속성을 사용하여 한 번에 파티션을 구축하거나 속성 하위 집합을 사용하여 파티션 교차 작업을 사용하여 구축합니다. 연방법 검색 알고리즘은 두 번째 옵션을 사용합니다.

간단히 말해서, 예를 들어 열별로 파티션을 얻으려면 ABC, 당신은 파티션을 취할 수 있습니다 AC и B (또는 서로 분리된 하위 집합의 다른 집합) 서로 교차합니다. 두 파티션의 교차 작업은 두 파티션에 공통된 가장 긴 길이의 클러스터를 선택합니다.

예를 살펴보겠습니다:

첫 번째 경우에는 빈 파티션을 받았습니다. 표를 자세히 살펴보면 실제로 두 속성에 대해 동일한 값이 없습니다. 테이블을 약간 수정하면(오른쪽 사례) 이미 비어 있지 않은 교차점을 얻게 됩니다. 또한 1행과 2행에는 실제로 속성에 대해 동일한 값이 포함되어 있습니다. 성별 и 의사.

다음으로 파티션 크기와 같은 개념이 필요합니다. 공식적으로:

간단히 말해서, 파티션 크기는 파티션에 포함된 클러스터의 수입니다(단일 클러스터는 파티션에 포함되지 않는다는 점을 기억하세요!).

이제 주어진 파티션에 대해 종속성이 유지되는지 여부를 결정할 수 있는 주요 정리 중 하나를 정의할 수 있습니다.

기본정리 1. 종속성 A, B → C는 다음과 같은 경우에만 유지됩니다.

기본 정리에 따르면 종속성이 유지되는지 확인하려면 다음 네 단계를 수행해야 합니다.

1. 종속성의 왼쪽에 대한 파티션을 계산합니다.
2. 종속성의 오른쪽에 대한 파티션을 계산합니다.
3. 첫 번째 단계와 두 번째 단계의 곱을 계산합니다.
4. 첫 번째 단계와 세 번째 단계에서 얻은 파티션의 크기를 비교하세요.

다음은 이 보조정리에 따라 종속성이 유지되는지 확인하는 예입니다.

이 글에서는 기능적 의존성, 근사적 기능적 의존성 등의 개념을 검토하고, 이들이 어디에 사용되는지, 물리적 기능을 검색하는 알고리즘에는 어떤 것이 있는지 살펴보았습니다. 또한 연방법 검색을 위해 현대 알고리즘에서 적극적으로 사용되는 기본적이면서도 중요한 개념에 대해 자세히 조사했습니다.

참고자료:

1. Huhtala Y. et al. TANE: 기능적 및 대략적인 종속성을 검색하기 위한 효율적인 알고리즘 //컴퓨터 저널. – 1999. – T. 42. – 아니. 2. – 100-111페이지.
2. Kruse S., Naumann F. 대략적인 종속성의 효율적인 발견 // VLDB 기부금 절차. – 2018. – T. 11. – 아니. 7. – 759-772페이지.
3. Papenbrock T., Naumann F. 기능적 종속성 검색에 대한 하이브리드 접근 방식 // 2016년 데이터 관리에 관한 국제 컨퍼런스 진행. – ACM, 2016. – pp. 821-833.
4. Papenbrock T. et al. 기능적 종속성 발견: 2015가지 알고리즘에 대한 실험적 평가 //VLDB 기부금 절차. – 8. – T. 10. – 아니. 1082. – pp. 1093-XNUMX.
5. Kumar A. et al. 가입할 것인가 말 것인가?: 기능 선택 전에 조인에 대해 두 번 생각하기 //2016 데이터 관리에 관한 국제 컨퍼런스 진행. – ACM, 2016. – pp. 19-34.
6. Abo Khamis M.et al. 희소 텐서를 사용한 데이터베이스 내 학습 //데이터베이스 시스템 원리에 관한 37차 ACM SIGMOD-SIGACT-SIGAI 심포지엄 진행. – ACM, 2018. – pp. 325-340.
7. Hellerstein J.M.et al. MADlib 분석 라이브러리: 또는 MAD 기술, SQL //VLDB 기부금 절차. – 2012. – T. 5. – 아니. 12. – 1700-1711페이지.
8. Qin C., Rusu F. 테라스케일 분산 경사하강법 최적화를 위한 추측적 근사 //클라우드의 데이터 분석에 관한 제2015차 워크숍 진행. – ACM, 1. – XNUMX페이지.
9. Meng X. et al. Mllib: Apache Spark의 기계 학습 //The Journal of Machine Learning Research. – 2016. – T. 17. – 아니요. 1. – pp. 1235-1241.

기사 작성자: 아나스타샤 비릴로, 연구원 JetBrains 연구, CS센터 학생 и 니키타 보브로프, 연구원 JetBrains 연구

출처 : habr.com