확률적 데이터베이스

Probabilistic database

대부분의 실제 데이터베이스는 정확성이 불확실한 데이터를 포함하고 있다. 그러한 데이터로 작업하기 위해서는 데이터의 무결성을 정량화할 필요가 있다. 이것은 확률론적 데이터베이스를 사용하여 달성된다.

확률론적 데이터베이스는 가능한 세계가 관련된 확률을 갖는 불확실한 데이터베이스다. 확률론적 데이터베이스 관리 시스템은 현재 활발한 연구 영역이다. "현재 상업적 확률론적 데이터베이스 시스템은 없지만 여러 연구 프로토타입이 존재한다.."[1]

확률적 데이터베이스는 ANSI-SPARC 아키텍처에서 관계형 데이터베이스와 마찬가지로 논리적 데이터 모델과 데이터의 물리적 표현을 구별한다. 확률론적 데이터베이스에서 이러한 데이터베이스는 종종 하나의 세계 크기(클래식 데이터베이스)에서 기하급수적으로 매우 많은 수의 가능한 세계를 나타내야 하기 때문에 이것은 훨씬 더 중요하다.[2][3]

용어.

확률론적 데이터베이스에서 각 튜플은 0과 1 사이의 확률과 연관되며, 0은 데이터가 확실히 부정확함을 나타내고, 1은 확실히 정확함을 나타낸다.

가능한 세계

확률론적 데이터베이스는 여러 주에 존재할 수 있다. 예를 들어, 데이터베이스에 튜플의 존재에 대한 불확실성이 있는 경우, 데이터베이스는 해당 튜플과 관련하여 두 개의 다른 상태에 있을 수 있다. 즉, 첫 번째 상태는 튜플을 포함하고 두 번째 상태는 그렇지 않다. 마찬가지로 속성이 x, y 또는 z 값 중 하나를 취할 수 있는 경우, 데이터베이스는 해당 속성에 대해 세 가지 다른 상태에 있을 수 있다.

이들 각 주는 가능한 세계라고 불린다.

다음 데이터베이스를 고려하십시오.

불완전한 데이터베이스
A B
a1 b1
a2 b2
a3 {b3, b3′, b3′′}

(여기서 {b3, b3′, b3′}은 속성이 b3, b3′ 또는 b3′′ 값 중 하나를 취할 수 있음을 나타낸다.)

  • 첫 번째 튜플에 대한 불확실성, 두 번째 튜플에 대한 확실성, 세 번째 튜플의 속성 B 값에 대한 불확실성이 있다고 가정한다.

그러면 데이터베이스의 실제 상태는 첫 번째 튜플을 포함할 수도 있고 아닐 수도 있다(정확한지에 따라 달라짐). 마찬가지로 속성 B의 값은 b3, b33 또는 b3′일 수 있다.

따라서 데이터베이스에 해당하는 가능한 월드는 다음과 같다.

월드 1
A B
a1 b1
a2 b2
a3 b3
월드 2
A B
a1 b1
a2 b2
a3 b3′
월드3
A B
a1 b1
a2 b2
a3 b3′′
월드4
A B
a2 b2
a3 b3
월드5
A B
a2 b2
a3 b3′
월드 6
A B
a2 b2
a3 b3′′

불확실성의 유형

아래 표에 설명된 대로 확률론적 데이터베이스에 존재할 수 있는 불확실성에는 기본적으로 두 가지 종류가 있다.

불확실성의 유형
투플레-레벨 불확실성 속성 수준의 불확실성
튜플이 올바른지 아닌지 여부, 즉 튜플이 데이터베이스에 존재해야 하는지 여부. 튜플의 속성이 취할 수 있는 값에 대한 불확실성, 즉 몇 가지 가능한 값 중 하나를 취할 수 있다.
각각의 불확실한 튜플에 대응하여, 두 개의 가능한 세계가 있다: 하나는 튜플을 포함하고 다른 하나는 그렇지 않다. a1,...,an 값을 가질 수 있는 각각의 불확실한 속성에 대응하여 가능한 세계가 없다.
튜플 수준 불확실성은 각 불확실한 튜플과 연관된 부울 랜덤 변수로 볼 수 있다. 속성 수준의 불확실성은 값1 a, ...,a를n 취할 수 있는 불확실한 각 속성과 연관된 랜덤 변수로 볼 수 있다.

데이터 항목과 관련된 랜덤 변수에 값을 할당함으로써 가능한 여러 월드를 나타낼 수 있다.

역사

"확률론적 데이터베이스"라는 용어의 처음 출판된 용어는 아마도 카발로와 피타렐리가 쓴 1987년 VLDB 회의지 "확률론적 데이터베이스 이론"에 있었을 것이다.[4] (8페이지 분량의 논문 중) 제목은 데이비드 마이어의 600페이지 분량의 모노그래프 <관계 데이터베이스론>이 당시 회의 참가자와 회의 진행의 독자들 대부분에게 친숙했을 것이기 때문에 약간 우스갯소리로 의도된 것이었다.

참조

  1. ^ 비노드 무투사미, 하이펑 류, 한스-아르노 제이콥센: 예측 출판/구독 매칭 토론토의 대학교.
  2. ^ Nilesh N. Dalvi, Dan Suciu: 확률론적 데이터베이스에 대한 효율적인 질의 평가. VLDB J. 16(4): 523-544(2007)
  3. ^ 류블레나 앙투바, 크리스토프 코흐, 댄 올테아누: 10^(10^6) 세계 이상: 불완전한 정보의 효율적인 표현과 처리. ICDE 2007: 606-615
  4. ^ 로저 카발로, 마이클 피타렐리: 확률론적 데이터베이스 이론. VLDB'87, 1987년 9월 1일부터 4일까지 제13차 대규모 데이터 베이스 국제 컨퍼런스 진행, Brighton: 71-81(1987)

외부 링크