함수 종속성 소개

이 글에서는 데이터베이스의 함수적 종속성에 대해 알아보겠습니다. 함수적 종속성이 무엇인지, 어디에 사용되는지, 그리고 함수적 종속성을 찾는 알고리즘은 무엇인지 알아보겠습니다.

관계형 데이터베이스의 맥락에서 함수 종속성을 고려해 보겠습니다. 대략적으로 말하면, 이러한 데이터베이스에서는 정보가 테이블 형태로 저장됩니다. 또한, 엄격한 관계 이론에서는 서로 호환되지 않는 대략적인 개념을 사용하겠습니다. 테이블 자체를 릴레이션(Relation), 열(Column)을 속성(Attribute)(속성 집합을 릴레이션 스키마(Relation Scheme)라고 하며, 속성의 부분 집합에 대한 행 값 집합을 튜플(Tuple)이라고 합니다.

예를 들어, 위의 표에서, (Benson, M, M 오르간)는 속성의 튜플입니다 (환자, 폴, 의사).
좀 더 공식적으로 말하면 다음과 같습니다. [환자, 폴, 의사] = (벤슨, M, M 오르간).
이제 함수적 종속성(FD)의 개념을 소개할 수 있습니다.

정의 1. 관계 R이 FD X → Y(여기서 X, Y ⊆ R)를 만족하는 것은 오직 튜플에 대해서만 가능합니다. , ∈ R이 만족되는 경우: [엑스] = [X], 그러면 [Y] = [Y]. 이러한 경우 X(결정인자 또는 속성의 정의 집합)가 Y(종속 집합)를 함수적으로 결정한다고 합니다.

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

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

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

따라서 함수적 종속성을 통해 테이블 ​​속성 집합 간의 기존 연결을 파악할 수 있습니다. 이제 가장 흥미로운 연결, 더 정확히는 다음과 같은 연결들을 살펴보겠습니다. X → Y, 그들은 다음과 같습니다:

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

지금까지 고려된 종속성은 엄격했습니다. 즉, 표에서 위반 사항을 허용하지 않지만, 그 외에도 튜플 값 간에 불일치를 허용하는 종속성도 있습니다. 이러한 종속성은 근사치(approximate)라는 별도의 클래스에 배치되며, 특정 개수의 튜플에 대해 위반이 허용됩니다. 이 개수는 최대 오차 지표 emax에 의해 결정됩니다. 예를 들어, 오차의 비율은 = 0.01은 고려된 속성 집합에 대해 사용 가능한 튜플의 1%가 종속성을 위반할 수 있음을 의미할 수 있습니다. 즉, 1000개의 레코드에 대해 최대 10개의 튜플이 종속성 위반을 할 수 있습니다. 비교 대상 튜플의 쌍별 고유 값을 기반으로 약간 다른 지표를 고려하겠습니다. 종속성의 경우 X → Y 태도에 대하여 r 계산 방법은 다음과 같습니다.

오차를 계산해보자 의사 → 환자 위의 예에서. 속성에서 값이 다른 두 개의 튜플이 있습니다. 환자, 하지만 그들은 일치한다 의사: [의사, 환자] = (로빈, 엘리스) 그리고 [의사, 환자] = (로빈, 그레이엄). 오류의 정의에 따라 모든 상충되는 쌍을 고려해야 하며, 이는 두 쌍이 존재함을 의미합니다. (, ) 및 그 역전(, ). 공식에 대입하면 다음과 같습니다.

이제 "이 모든 것이 무엇에 쓰이는가?"라는 질문에 답해 보겠습니다. 사실, FD에는 여러 유형이 있습니다. 첫 번째 유형은 데이터베이스 설계 단계에서 관리자가 정의하는 종속성입니다. 일반적으로 종속성은 수가 적고 엄격하며, 주로 데이터 정규화 및 관계 체계 설계에 사용됩니다.

두 번째 유형은 "숨겨진" 데이터와 이전에 알려지지 않은 속성 간의 관계를 나타내는 종속성입니다. 즉, 이러한 종속성은 설계 시점에는 고려되지 않았으며, 기존 데이터 집합에서 발견되어 나중에 식별된 함수 종속성 집합을 기반으로 저장된 정보에 대한 결론을 도출할 수 있습니다. 바로 이러한 종속성을 활용하여 작업합니다. 이러한 종속성은 다양한 검색 기술과 이를 기반으로 구축된 알고리즘을 사용하는 데이터 마이닝 분야에서 다룹니다. 어떤 데이터에서든 발견된 함수 종속성(정확하거나 근사적인)이 어떻게 유용하게 활용될 수 있는지 알아보겠습니다.

오늘날 데이터 정리는 종속성 활용의 주요 분야 중 하나입니다. 이는 "더티 데이터"를 식별하고 수정하는 프로세스를 개발하는 것을 포함합니다. "더티 데이터"의 일반적인 예로는 중복, 데이터 오류 또는 오타, 누락된 값, 오래된 데이터, 불필요한 공백 등이 있습니다.

데이터 오류의 예:

데이터의 중복 예:

예를 들어, 실행해야 할 테이블과 일련의 FD가 있다고 가정해 보겠습니다. 이 경우 데이터 정리는 FD가 정확해지도록 데이터를 변경하는 것을 포함합니다. 이 경우 수정 횟수는 최소화해야 합니다(이 절차에 대한 알고리즘이 있지만, 이 글에서는 다루지 않겠습니다). 아래는 이러한 데이터 변환의 예입니다. 왼쪽은 필요한 FD가 실행되지 않은 원래 관계입니다(FD 중 하나를 위반한 예는 빨간색으로 강조 표시되어 있습니다). 오른쪽은 변경된 관계로, 녹색 셀은 변경된 값을 나타냅니다. 이러한 절차 후, 필요한 종속성이 유지되기 시작했습니다.

또 다른 인기 있는 응용 분야는 데이터베이스 설계입니다. 여기서 정규형과 정규화에 대해 다시 생각해 볼 가치가 있습니다. 정규화는 관계를 특정 요구 사항 집합에 맞게 만드는 과정이며, 각 요구 사항은 고유한 방식으로 정규형에 의해 정의됩니다. 다양한 정규형의 요구 사항에 대해서는 설명하지 않겠지만(이는 초보자를 위한 DB 과정의 모든 책에 나와 있습니다), 각 정규형이 고유한 방식으로 함수 종속성 개념을 사용한다는 점만 언급하겠습니다. 결국, FD는 본질적으로 데이터베이스 설계 시 고려되는 무결성 제약 조건입니다(이 작업에서는 FD를 슈퍼키라고 부르기도 합니다).

아래 그림의 네 가지 정규형에 이들을 적용해 보겠습니다. 보이스-코드 정규형은 세 번째 정규형보다 엄격하지만 네 번째 정규형보다는 덜 엄격하다는 점을 기억하세요. 마지막 정규형은 다중값 종속성에 대한 이해가 필요하므로 지금은 고려하지 않겠습니다. 이 글에서는 다중값 종속성에 대해 다루지 않습니다.

종속성이 적용되는 또 다른 영역은 나이브 베이즈 분류기 구축, 특징 추출, 회귀 모델 재매개변수화와 같은 작업에서 특징 공간 차원 축소입니다. 초기 논문에서는 이 작업을 특징 중복성 및 특징 관련성[5, 6]이라고 하며, 데이터베이스 개념을 적극적으로 활용하여 해결합니다. 이러한 연구의 등장으로, 오늘날 데이터베이스, 분석, 그리고 위의 최적화 문제 구현을 단일 도구로 통합할 수 있는 솔루션에 대한 수요가 증가하고 있다고 할 수 있습니다[7, 8, 9].

데이터 집합에서 연방법 검색을 위한 다양한 알고리즘(최신 알고리즘과 그렇지 않은 알고리즘 모두)이 존재합니다. 이러한 알고리즘은 세 가지 그룹으로 나눌 수 있습니다.

• 격자 탐색 알고리즘을 사용하는 알고리즘
• 차이 및 동의 설정 알고리즘
• 종속성 유도 알고리즘

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


이 분류에 대한 자세한 내용은 [4]에서 확인할 수 있습니다. 각 유형에 대한 알고리즘의 예는 다음과 같습니다.

현재 함수 종속성을 찾는 여러 접근법을 결합한 새로운 알고리즘들이 등장하고 있습니다. 이러한 알고리즘의 예로는 Pyro [2]와 HyFD [3]가 있습니다. 이 시리즈의 다음 글에서는 이러한 알고리즘의 작동 방식에 대한 분석을 제공할 예정입니다. 이 글에서는 종속성 탐지 기법을 이해하는 데 필요한 기본 개념과 보조정리(lemma)에 대해서만 분석합니다.

두 번째 유형의 알고리즘에 사용되는 간단한 차이 집합과 동의 집합부터 시작해 보겠습니다. 차이 집합은 값이 일치하지 않는 튜플들의 집합이고, 동의 집합은 그 반대, 즉 값이 일치하는 튜플들의 집합입니다. 이 경우 종속성의 왼쪽 부분만 고려한다는 점에 유의해야 합니다.

위에서 언급한 또 다른 중요한 개념은 대수 격자입니다. 많은 현대 알고리즘이 이 개념으로 작동하기 때문에, 대수 격자가 무엇인지 먼저 알아둘 필요가 있습니다.

격자의 개념을 소개하기 위해서는 부분 순서 집합(또는 poset)의 정의가 필요합니다.

정의 2. 집합 S가 이진 관계에 의해 부분적으로 정렬되어 있다고 하는 것은 모든 a, b, c ∈ 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를 대수 격자라고 한다. 여기서 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}을 통해 구해집니다.

FD를 감지하는 알고리즘에서 검색 공간은 종종 격자 형태로 표현되는데, 여기서 한 요소의 집합(종속성의 왼쪽이 한 속성으로 구성된 검색 격자의 첫 번째 수준을 읽어보세요)은 원래 관계의 각 속성을 나타냅니다.
시작 시 ∅ → 유형의 종속성이 고려됩니다. 단일 속성. 이 단계를 통해 어떤 속성이 기본 키인지 확인할 수 있습니다(이러한 속성에 대한 결정자가 없으므로 왼쪽은 비어 있음). 그런 다음 이러한 알고리즘은 격자를 따라 위로 이동합니다. 전체 격자를 순회하는 것은 불가능하다는 점에 유의해야 합니다. 즉, 원하는 왼쪽의 최대 크기가 입력으로 전달되면 알고리즘은 해당 크기의 수준을 넘어갈 수 없습니다.

아래 그림은 FD를 구하는 문제에서 대수 격자를 어떻게 사용할 수 있는지 보여줍니다. 여기서 각 변(엑스, 엑스이에이)는 종속성입니다 X → Y예를 들어, 우리는 첫 번째 레벨을 통과했고 중독이 유지되고 있다는 것을 알고 있습니다. A → B (이것을 정점 사이의 녹색 연결로 표시합니다. A и B). 이는 그리드를 더 위로 이동하면 종속성을 확인할 수 없음을 의미합니다. A, C → B더 이상 최소값이 아니기 때문입니다. 마찬가지로, 종속성이 유지된다면 이를 확인하지 않을 것입니다. ㄷ → ㄴ.

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

정의 6. X ⊆ R을 관계 r의 속성 집합이라 하자. 클러스터는 r에 있는 X에 대해 동일한 값을 갖는 튜플들의 인덱스 집합, 즉 c(t) = {i|ti[X] = t[X]}이다. 분할은 길이가 1인 클러스터를 제외한 클러스터들의 집합이다.

간단히 말해서, 속성에 대한 분할 X 각 목록에 동일한 값을 갖는 행의 개수가 포함된 목록 집합입니다. X현대 문헌에서 파티션을 나타내는 구조를 위치 목록 색인(PLI)이라고 합니다. 길이가 1인 클러스터는 PLI 압축에서 제외되는데, 이는 항상 쉽게 판별할 수 있는 고유한 값을 가진 레코드 번호만 포함하는 클러스터이기 때문입니다.

예를 들어 보겠습니다. patients가 있는 동일한 테이블로 돌아가서 열에 대한 파티션을 만들어 보겠습니다. 환자 и 성별 (왼쪽에 새로운 열이 나타났으며, 여기에 표의 행 번호가 표시되어 있습니다):

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

여러 속성을 통해 파티션을 얻을 수 있습니다. 이를 수행하는 방법에는 두 가지가 있습니다. 테이블을 탐색하여 필요한 모든 속성을 기준으로 한 번에 파티션을 구성하거나, 속성의 부분 집합을 기준으로 파티션의 교집합 연산을 사용하여 파티션을 구성하는 것입니다. FZ를 검색하는 알고리즘은 두 번째 방법을 사용합니다.

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

예를 살펴보겠습니다.

첫 번째 경우에는 빈 파티션이 생성되었습니다. 표를 자세히 살펴보면 두 속성에 동일한 값이 없다는 것을 알 수 있습니다. 표를 약간 수정하면(오른쪽의 경우) 이미 비어 있지 않은 교집합이 생성됩니다. 이 경우, 1번 줄과 2번 줄에는 실제로 두 속성에 대해 동일한 값이 포함되어 있습니다. 성별 и 의사.

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

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

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

레마 1. 종속성 A, B → C는 다음 경우에만 성립합니다.

레마에 따르면 종속성이 유지되는지 확인하려면 다음 4단계를 수행해야 합니다.

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

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

이 글에서는 함수 종속성, 근사 함수 종속성과 같은 개념을 살펴보고, 이러한 개념들이 어디에 사용되는지, 그리고 함수 종속성을 검색하는 알고리즘은 무엇인지 고찰했습니다. 또한, 최신 함수 종속성 검색 알고리즘에서 활발하게 사용되는 기본적이지만 중요한 개념들을 자세히 살펴보았습니다.

문헌 링크:

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

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

출처 : habr.com