결막조회

데이터베이스 이론에서, 접속 쿼리는 논리 접속사 연산자를 이용한 1차 질의의 제한된 형태다.많은 1차 질의는 접속 질의로 작성할 수 있다.특히 관계형 데이터베이스에 대해 발행된 질의의 상당 부분을 이런 식으로 표현할 수 있다.또한 결막 쿼리는 더 큰 클래스의 쿼리(예: 관계 대수 쿼리)가 공유하지 않는 다수의 바람직한 이론적 특성을 가지고 있다.

정의

결막질문은 (도메인 독립) 공식 집합이 주는 (도메인 독립) 1차 논리학의 단편으로서, 접속사 ∧과 실존적 계량 ∃을 이용하여 원자 공식으로 구성할 수 있지만, 분리 ∨, 부정 ¬, 보편적 계량 ∀을 사용하지 않는다.그러한 각각의 공식은 혼전 정상형식으로 동등한 공식으로 다시 쓰일 수 있다(효율적으로). 따라서 이 형식은 보통 간단히 가정된다.

따라서 접속 질의는 다음과 같은 일반적인 형태를 띤다.

${\$$\cHB x_{k+1},\ldots x_{m}.$$A_{1}\wedge \ldots \wedge A_{r$

자유 변수 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle x_{}}$ ${\displaystyle {}_{}}$ ${\$을 구분 변수라고 하고$$, 바운드 변수 $x{\displaystyle {}_{}}$k + ${\displaystyle 1_{}}$, ${\displaystyle \dots ,}$ ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$ ${\$을 구분되지 않은 변수라고 한다$$.${\displaystyle A_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle A_{}}$ ${\displaystyle {}_{}}$ ${\$는 원자 공식이다.

도메인 독립형 1차 로직의 제한이 중요한 이유의 예로서, $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$.${\displaystyle {}_{}\mathrm{\exists }}$ x ${\displaystyle {2\mathrm{}}_{}}$. R${\displaystyle }$( ${\displaystyle x}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle x_{1$}를 고려하십시오$.$$\cHB x_{2}.$$도메인$ 독립적이지 $않은$ R(x_${2})$$.$ Codd의 정리를 참조하십시오.관계대수의 선택-프로젝트-조인 부분에서는 이 공식을 실행할 수 없으므로, 결합 질의로 간주해서는 안 된다.

접속 질의는 관계형 데이터베이스에서 자주 발행되는 질의의 많은 부분을 표현할 수 있다.예를 들어 학생, 주소, 수강 과정 및 성별에 대한 정보를 저장하는 관계형 데이터베이스를 상상해 보십시오.여학생이 수강하는 강좌에 수강하는 모든 남학생과 그 주소를 찾아내는 것은 다음과 같은 결벽적인 질의를 통해 표현된다.

(재명, 주소) . attends (재명, 코스) student (재명, 코스) ∧ 성별 (재명, '남성') attends 성별 (재명, 주소) ∧ 생활 (재명, 주소)

관심 있는 유일한 실체는 남학생과 그의 주소이므로, 이러한 변수만이 구별되는 반면, 변수들은 유일한 구별되는 변수라는 점에 유의하십시오.course,student2실존적으로 수량화되었을 뿐이다. 즉, 구별되지 않았다.

조각

구분 변수가 없는 결막 쿼리를 부울 결막 쿼리라고 한다.모든 변수가 구별되는 결막 쿼리를 관계형 대수(결과의 모든 열을 선택할 때)의 등가 관계형 미적분학에서 등가형이기 때문에 (결과의 모든 열을 선택할 때) 등가형 쿼리를 등가형 쿼리라고 한다.^[1]

다른 쿼리 언어와의 관계

또한 결막 쿼리는 관계 대수(즉, 운용 조합이나 차이를 사용하지 않는 관계 대수 쿼리)의 선택-프로젝트-조인 쿼리와 위치 조건이 원자 평등 조건의 독점 접속사(즉, 열 이름에서 생성된 조건)를 사용하는 SQL의 선택-거점 쿼리에도 해당한다.그리고 "="를 제외한 다른 비교 연산자를 사용하지 않는 상수는 "및"을 사용하여 결합한다.특히, 집합과 서브쿼리의 사용은 제외된다.예를 들어, 위의 쿼리는 다음과 같이 접속 쿼리 파편의 SQL 쿼리로 작성할 수 있다.

선발하다 l.학생, l.주소를 쓰다 로부터   참석하다 a1, 성별 g1,        참석하다 a2, 성별 g2,        삶 l 어디에  a1.학생 = g1.학생 그리고        a2.학생 = g2.학생 그리고        l.학생 = g1.학생 그리고        a1.코스 = a2.코스 그리고        g1.성별 = '남성' 그리고        g2.성별 = '여성'; 

데이터로그

그들의 논리 표기법 외에도, 접속 쿼리는 데이터로그 규칙으로도 쓰일 수 있다.실제로 많은 저자들은 위의 쿼리에 대해 다음과 같은 데이터로그 표기법을 선호한다.

 결과(학생, 주소를 쓰다) :- 참석하다(학생, 코스),  성별(학생, 남성),                              참석하다(학생2, 코스), 성별(학생2, 여성),                              삶(학생, 주소를 쓰다). 

이 표기법에는 정량자가 없지만, 규칙의 머리 속에 나타나는 변수는 여전히 암묵적으로 보편적으로 정량화된 반면, 규칙의 본문에만 나타나는 변수는 여전히 암묵적으로 실존적으로 정량화된 것이다.

어떤 접속 쿼리는 데이터로그 규칙으로 쓸 수 있지만, 모든 데이터로그 프로그램이 접속 쿼리로 쓰일 수 있는 것은 아니다.사실 확장 술어 기호에 대한 단일 규칙만 등가 접속 질의로 쉽게 다시 쓸 수 있다.주어진 데이터로그 프로그램에 대해 등가 비복구 프로그램(긍정적 관계 대수 질의에 대응하거나, 동등하게 존재론적 1차 순서 논리의 공식이나, 특수한 경우로서 결막 질의에 대응함)이 있는지 결정하는 문제는 데이터로그 경계성 문제로 알려져 있으며, 이해할 수 없는 것이다.^[2]

확장

더 표현력을 포착하는 접속 질의의 확장에는 다음이 포함된다.

• 양수(즉, 부정이 없는) 관계 대수(relative)와
• 결합과 부정으로 확장된 결막 질의는 Codd의 정리에 의해 관계 대수학 및 1차 논리학에 해당한다.
• 기본 제공 술어(예: 산술 술어)가 있는 결합 질의
• 집계 함수와 결합 질의

이러한 모든 확장에 대한 공식적인 연구는 관계형 데이터베이스에 대한 적용에 의해 정당화되며 데이터베이스 이론의 영역에 있다.

복잡성

결벽 질의 평가의 계산적 복잡성에 대한 연구를 위해서는 두 가지 문제를 구분해야 한다.첫 번째는 질의와 데이터베이스가 모두 입력의 일부로 간주되는 관계형 데이터베이스에서 접속 질의를 평가하는 문제다.이 문제의 복잡성은 대개 결합 복잡성이라고 하는 반면, 질의가 고정된 것으로 가정되는 관계형 데이터베이스에 대한 질의를 평가하는 문제의 복잡성을 데이터 복잡성이라고 한다.^[3]

결합 질의는 복합적인 복잡성과 관련하여 NP-완전한 반면,^[4] 결합 질의의 데이터 복잡성은 LOGSPACE 및 다항 시간에 포함된 병렬 복잡도 클래스 AC0에서 매우 낮다.관계 대수학 및 SQL은 결막 질의를 엄격히 요약하고 따라서 최소한 그만큼 어렵기 때문에(사실 관계 대수학은 결합 복잡성에 대해 PSPACE-완전하므로 광범위하게 보유되는 복잡성 이론적 가정 하에서 더욱 어렵다.) 결막 질의의 NP-강성은 놀라운 것으로 보일 수 있다.그러나 일반적인 애플리케이션 시나리오에서 데이터베이스는 큰 반면 쿼리는 매우 작은 반면, 데이터 복잡성 모델은 그들의 어려움을 연구하고 설명하는데 적합할 수 있다.

비 부울 결막 질의에 대한 모든 답변을 열거하는 문제는 열거 알고리즘의 맥락에서 연구되어 왔으며, 각 솔루션 간의 선형 시간 사전 처리 및 일정한 지연으로 열거할 수 있는 질의의 특성화(일부 계산 경도 가정 하에서)가 연구되었다.특히 이것들은 자유 연결 조건도 만족시키는 순환 접속 질의들이다.^[5]

형식 특성

결찰 질의는 계산적으로 어렵거나 더 큰 종류의 질의에 대해 불식할 수 없는 많은 흥미로운 문제들이 결찰 질의에 실현 가능하다는 점에서 데이터베이스 이론의 큰 성공 사례 중 하나이다.^[6]예를 들어, 쿼리 차단 문제를 고려하십시오.We write ${\displaystyle R\subseteq S}$ for two database relations ${\displaystyle R,S}$ of the same schema if and only if each tuple occurring in ${\displaystyle R}$ also occurs in ${\displaystyle S}$. Given a query ${\displaystyle Q}$ and a relational database instance ${\displaystyle I}$,인스턴스에 대한${\displaystyle \mathrm{쿼리}}$를 단순히 Q ( I $){\displaystyle$ Q$(I$)}로 평가하는 결과 관계를 쓴다$.$ Q 1 {\$displaystyle Q_{1$}, ${\displaystyle Q_{}}$ 2 ${\$}}개의 쿼리와 데이터베이스 스키마가 주어진다면, 쿼리 격납 문제는 가능한 모든 데이터베이스 인스턴스 $I{\displaystyle }$ ${\d$}에 대한 여부를 결정하는 문제다$.$${\displaystyle {입력}_{}}$ 데이터베이스 스키마 $위$의 ${\displaystyle \mathrm{Isplaystyle}}$ I$},$ $Q{\displaystyle {}_{}}$ 1${\displaystyle {}_{}}$( I${\displaystyle }$)${\displaystyle }$⊆ Q ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle I}$) ${\displaystyle Q_{1}(I)\subseteq Q_{2}(I)}$.질의 격납의 주요 적용은 질의 최적화에 있다.상호 격납 확인만으로 두 질의의 등가 여부를 결정할 수 있다.

질의 격납 문제는 관계 대수 및 SQL에 대해 불분명하지만, 접속 질의에 대해서는 해독이 가능하고 NP-완전하다.실제로 결벽 질의에 대한 질의 격납 문제는 질의 평가 문제와 정확히 동일한 문제인 것으로 나타났다.^[6]질의가 작은 경향이 있기 때문에, 이곳의 NP-완전성은 일반적으로 허용될 수 있는 것으로 간주된다.접속 질의에 대한 질의 격납 문제 또한 제약 만족 문제와 동일하다.^[7]

다항식 시간 결합 복잡성을 갖는 중요한 접속 질의 종류는 반복 접속 질의다.^[8]쿼리 평가, 즉 쿼리 격납은 LOGCFL-완전하므로 다항식 시간이다.^[9]결막 질의의 반복성은 질의의 하이퍼그래프에 대해 정의되는 질의의 구조적 속성이다:^[6] 결막 질의는 비대폭 1이 있는 경우에만 반복된다.사용된 모든 관계가 2진수인 결막질문의 특별한 경우, 이 개념은 쿼리에 있는 변수의 종속성 그래프의 트리 너비에 해당한다(즉, 쿼리의 변수를 노드로 가지고 있는 그래프와 두 변수 사이의$$ 비방향 에지${\displaystyle }${${\displaystyle x}$, ${\displaystyle y}$ ${\displaystyle \}}$ ${\displaystyle \{x,y\}).$쿼리의 $원자{\displaystyle }$공식 ${\displaystyle R(x}$, y$$) {\$displaystyle R(x,$y$$$$)} $또는{\displaystyle }$R${\displaystyle (y}$, x$$) {\$displaystyle R(y,$x)}이(가) 있으며, 종속성 그래프가 반복적인 경우에만 결막 쿼리가 반복된다.

악순환의 중요한 일반화는 경계가 있는 비대폭의 개념으로, 이는 그래프에서 경계가 있는 나무 폭과 유사하게 하이퍼그래프가 얼마나 악순환에 가까운지를 나타내는 척도다.경계 트리 너비의 결막 쿼리는 LOGCFL 결합 복잡성을 갖는다.^[10]

트리 데이터에 대한 제한 없는 결합 질의(즉, 트리 노드에 라벨을 붙이기 위한 단항 관계뿐만 아니라 트리의 이진 하위 관계로 구성된 관계형 데이터베이스)는 다항식 시간 결합 복잡성을 가진다.^[11]

참조

외부 링크

• 울먼, J. D.논리적 보기를 사용한 정보 통합 이론 컴퓨터 과학, 2000, 239, 189-210^{[데드링크]}
• Georg Gottlob, 결벽 질의의 효율적인 평가를 위한 구조 분해 방법 발표(PDF)