데이터베이스에서 기능적 종속성을 효율적으로 찾습니다.

데이터의 함수적 종속성을 찾는 것은 데이터베이스 관리, 데이터 정리, 데이터베이스 리버스 엔지니어링, 데이터 탐색 등 다양한 데이터 분석 분야에서 사용됩니다. 우리는 이미 종속성 자체에 대해 게시했습니다. статью 아나스타샤 비릴로와 니키타 보브로프. 이번에는 올해 컴퓨터 과학 센터를 졸업한 아나스타샤가 그녀가 센터에서 옹호했던 연구의 일환으로 이 작업의 개발 과정을 공유했습니다.

작업 선택

CS 센터에서 공부하는 동안 저는 데이터베이스에 대해 심도 있게 연구하기 시작했습니다. 특히, 기능적 종속성과 차등 종속성을 검색하는 것에 관심이 많았습니다. 이 주제는 대학에서 제가 수강한 과정 주제와 관련이 있었기 때문에 과정을 진행하면서 데이터베이스의 다양한 종속성에 대한 기사를 읽기 시작했습니다. 나는 이 지역에 대한 리뷰를 썼습니다. 내 첫 리뷰 중 하나였습니다. 조항 영어로 작성하여 SEIM-2017 컨퍼런스에 제출했습니다. 그녀가 합격했다는 소식을 들었을 때 나는 매우 기뻤고, 그 주제에 대해 더 깊이 연구하기로 결심했습니다. 이 개념 자체는 새로운 것이 아닙니다. 90년대에 사용되기 시작했지만 지금도 많은 분야에서 사용되고 있습니다.

센터에서 보낸 두 번째 학기에 저는 함수적 종속성을 찾는 알고리즘을 개선하는 연구 프로젝트를 시작했습니다. 저는 JetBrains Research에서 상트페테르부르크 국립대학교 대학원생인 니키타 보브로프와 함께 이 작업을 진행했습니다.

함수 종속성 검색의 계산 복잡도

가장 큰 문제는 계산상의 복잡성이다. 가능한 최소 및 비사소한 종속성의 수는 위에서 값에 의해 제한됩니다. 어디에서 — 테이블 속성의 수. 알고리즘의 실행 시간은 속성의 수뿐만 아니라 줄의 수에 따라서도 달라집니다. 90년대에는 일반적인 데스크톱 PC에서 연방법률을 검색하는 알고리즘이 최대 20개의 속성과 수만 개의 줄이 포함된 데이터 세트를 최대 수 시간 동안 처리할 수 있었습니다. 멀티코어 프로세서에서 실행되는 최신 알고리즘은 수백 개의 속성(최대 200개)과 수십만 개의 행으로 구성된 데이터 세트에 대한 종속성을 거의 동일한 시간 안에 검색합니다. 하지만 이것만으로는 충분하지 않습니다. 대부분의 실제 응용 프로그램에서는 이러한 시간이 허용되지 않습니다. 따라서 우리는 기존 알고리즘의 속도를 높이는 방법을 개발했습니다.

파티션 교차를 위한 캐싱 계획

논문의 첫 번째 부분에서는 파티션 교차 방법을 사용하는 알고리즘 클래스에 대한 캐싱 계획을 개발했습니다. 속성에 대한 파티션은 목록의 집합으로, 각 목록에는 주어진 속성에 대해 동일한 값을 갖는 행 번호가 포함되어 있습니다. 이러한 각 목록을 클러스터라고 합니다. 많은 현대 알고리즘은 종속성이 유지되는지 여부를 판별하기 위해 파티션을 사용합니다. 즉, 종속성이라는 레마를 준수합니다. 유지되는 경우 . 여기에 파티션이 지정되고 파티션 크기 개념(파티션 내 클러스터 수)이 사용됩니다. 파티션을 사용하는 알고리즘은 종속성이 위반되면 종속성의 왼쪽에 추가 속성을 추가한 다음 이를 다시 계산하여 파티션 교차 연산을 수행합니다. 이런 작업을 기사 전문화라고 합니다. 하지만 여러 라운드의 특수화 이후에만 유지되는 종속성에 대한 파티션은 적극적으로 재사용될 수 있으며, 이는 교차 연산이 비용이 많이 들기 때문에 알고리즘의 실행 시간을 크게 줄일 수 있다는 것을 발견했습니다.

따라서 우리는 섀넌 엔트로피와 지니 불확실성을 기반으로 한 휴리스틱과 역엔트로피라고 불리는 지표를 제안했습니다. 이는 섀넌 엔트로피를 약간 변형한 것으로, 데이터 세트의 고유성이 높아질수록 증가합니다. 제안된 휴리스틱은 다음과 같습니다.

여기에 — 최근 계산된 파티션의 고유성 정도 과 는 각 속성의 고유성 정도의 중앙값입니다. 위에 설명된 세 가지 측정 항목은 모두 고유성 측정 항목으로 테스트되었습니다. 또한 휴리스틱에는 두 개의 수정자가 있다는 점도 주목할 만합니다. 첫 번째는 현재 파티션이 기본 키에 얼마나 가까운지를 나타내며 후보 키에서 멀리 떨어진 파티션을 더 많이 캐싱할 수 있도록 합니다. 두 번째 수정자를 사용하면 캐시 점유율을 추적할 수 있으므로 여유 공간이 있을 때 캐시에 더 많은 파티션을 추가하도록 권장합니다. 이 문제를 성공적으로 해결함으로써 데이터 세트에 따라 PYRO 알고리즘을 10-40% 가속화할 수 있었습니다. 이 분야에서 가장 성공적인 알고리즘은 PYRO라는 점은 주목할 만합니다.

아래 그림은 제안된 휴리스틱을 적용한 결과와 기본적인 동전 던지기 캐싱 방식을 비교한 결과를 보여줍니다. X축은 대수축입니다.

파티션을 저장하는 대체 방법

그런 다음 우리는 파티션을 저장하는 대체 방법을 제안했습니다. 파티션은 클러스터의 집합으로, 각 클러스터에는 특정 속성에 대해 동일한 값을 갖는 튜플의 개수가 저장됩니다. 예를 들어, 테이블의 데이터가 정렬되어 있는 경우 이러한 클러스터에는 튜플 번호의 긴 시퀀스가 ​​포함될 수 있습니다. 따라서 우리는 파티션을 저장하기 위한 압축 방식, 즉 파티션 클러스터에 값을 간격별로 저장하는 방식을 제안했습니다.

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{첫 번째~간격}, underbrace{7, 8}_{두 번째~간격}, 10}}\ downarrow{압축}\ pi(X) = {{underbrace{$, 1, 5}_{첫 번째~간격}, underbrace{7, 8}_{두 번째~간격}, 10}}$$display$$

이 방법을 사용하면 TANE 알고리즘을 실행하는 동안 메모리 소비를 1~25% 줄일 수 있었습니다. TANE 알고리즘은 FD를 검색하기 위한 고전적인 알고리즘입니다. 운영 중에는 파티션을 사용합니다. 실제 상황에서는 PYRO 등에서 간격 저장을 구현하는 것보다 TANE 알고리즘을 선택했는데, 이를 통해 제안된 접근 방식이 작동하는지 평가할 수 있었습니다. 얻어진 결과는 아래 그림에 나타나 있다. X축은 대수축입니다.

ADBIS-2019 컨퍼런스

해당 연구 결과를 바탕으로 2019년 XNUMX월에 논문을 발표했습니다. 효율적인 기능 종속성 검색을 위한 스마트 캐싱 제23회 유럽 데이터베이스 및 정보 시스템 발전 컨퍼런스(ADBIS-2019)에서. 프레젠테이션 중에 데이터베이스 분야의 유명인사인 베르나르트 탈하임이 이 작업에 주목했습니다. 본 연구 결과는 상트페테르부르크 국립대학교 수학 및 기계학부 석사 과정에서 제 논문의 기초가 되었으며, 이 과정에서 두 가지 제안된 접근 방식(캐싱과 압축)이 TANE과 PYRO 두 알고리즘 모두에 구현되었습니다. 게다가, 두 알고리즘 모두 메모리 소비량이 상당히 감소했을 뿐만 아니라 알고리즘 실행 시간도 상당히 단축되었기 때문에, 제안된 접근 방식이 보편적이라는 것이 결과를 통해 입증되었습니다.

출처 : habr.com