KR102138627B1

KR102138627B1 - 데이터 쿼리 방법 및 장치, 및 데이터베이스 시스템

Info

Publication number: KR102138627B1
Application number: KR1020187017354A
Authority: KR
Inventors: 구오핑 왕; 준후아 주
Original assignee: 후아웨이 테크놀러지 컴퍼니 리미티드
Priority date: 2015-11-30
Filing date: 2015-11-30
Publication date: 2020-07-28
Anticipated expiration: 2035-11-30
Also published as: JP6628455B2; US10885034B2; KR20180083927A; SG11201804544QA; BR112018010857B1; EP3373154A4; CN107251013A; JP2019504390A; BR112018010857A2; WO2017091925A1; EP3373154A1; CN107251013B; US20180276277A1; BR112018010857A8

Abstract

데이터 쿼리 방법 및 장치, 및 데이터베이스 시스템이 제공된다. 이러한 방법은, 데이터 쿼리 요청을 수신하는 단계(S1110); 데이터 쿼리 요청에 따라 원본 쿼리 계획을 생성하는 단계(S1120); 원본 쿼리 계획에 따라 후보 쿼리 계획 세트를 획득하는 단계(S1130); 원본 쿼리 계획에서 결합 술어를 재구성하는 단계(S1140); 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보를 결정하는 단계(S1150); 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건을 결정하는 단계(S1160); 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 단계(S1170); 및 원본 쿼리 계획에 대한 등가 쿼리 계획에 따라 쿼리를 수행하는 단계(S1180)를 포함한다. 이러한 데이터 쿼리 방법 및 장치, 및 이러한 데이터베이스 시스템에 따르면, 데이터 쿼리 성능이 향상될 수 있다.

Description

데이터 쿼리 방법 및 장치, 및 데이터베이스 시스템

본 발명은 정보 기술들의 분야에, 보다 구체적으로, 데이터 쿼리 방법 및 장치, 및 데이터베이스 시스템에 관한 것이다.

구조화된 쿼리 언어(Structured Query Language, SQL)는 관계형 데이터베이스 관리 시스템의 표준 언어이다. 이러한 구조화된 쿼리 언어는 고급 설명형 비-절차적 언어이다. 즉, 구조화된 쿼리 언어는 사용자가 상위 계층 데이터 구조 상에서 요구되는 데이터를 획득할 수 있게 하지만, 구조화된 쿼리 언어는 사용자가 데이터를 획득하기 위한 방법, 즉, 일반적 의미로 쿼리 계획을 명시할 것을 요구하지 않는다. 이러한 쿼리 계획은 트리로 표현될 수 있다. 트리의 리프 노드는 입력 표를 표시하고, 중간 노드는 연산을 표시한다. SQL 쿼리는 많은 등가 쿼리 계획들을 일반적으로 갖고, 상이한 쿼리 계획들의 실행 시간들은 다르다. 따라서, 데이터베이스 시스템에는, 최적의 (즉, 실행 시간이 가장 짧은) 쿼리 계획을 선택하기 위한 쿼리 최적화기 컴포넌트가 존재한다.

쿼리 최적화기의 주요 기능은 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 것 및 최적의 쿼리 계획을 선택하는 것이다. 그러나, 종래 기술에서는, 일부 등가 쿼리 계획들이 생략되고, 결과적으로 쿼리 성능이 영향을 받는다.

본 발명은 데이터 쿼리 방법 및 장치, 및 데이터베이스 시스템을 제공하여, 데이터 쿼리 성능을 향상시킨다.

제1 양태에 따르면, 본 발명의 실시예는 데이터 쿼리 방법을 제공하고, 본 방법은 데이터베이스 시스템에 의해 실행되고, 이러한 데이터베이스 시스템은 컴퓨터 디바이스 상에서 실행되고, 본 방법은,

데이터 쿼리 요청을 수신하는 단계;

데이터 쿼리 요청에 따라 원본 쿼리 계획을 생성하는 단계;

원본 쿼리 계획에서 결합 술어를 재구성하는 단계;

원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보를 결정하는 단계;

결합 연산 규칙에 기초하여, 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건을 결정하는 단계;

원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 단계; 및

원본 쿼리 계획에 대한 등가 쿼리 계획에 따라 쿼리를 수행하는 단계를 포함한다.

본 발명의 실시예들에서는, 술어의 기본 정보 및 결합 연산 규칙에 기초하여 획득되는 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획이 결정되고, 원본 쿼리 계획에 대한 비교적 많은 양의 등가 쿼리 계획들이 획득될 수 있으므로, 데이터 쿼리 성능이 향상될 수 있다.

일부 구현들에서, 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 단계는,

원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획 세트를 결정하는 단계를 포함하고;

원본 쿼리 계획에 대한 등가 쿼리 계획에 따라 쿼리를 수행하는 단계는,

등가 쿼리 계획 세트로부터 쿼리 계획을 선택하여 쿼리를 수행하는 단계를 포함한다.

일부 구현들에서, 본 방법은,

원본 쿼리 계획에 따라 후보 쿼리 계획 세트를 획득하는 단계-

원본 쿼리 계획에 대한 후보 쿼리 계획들은 여기서 가능한 많이 획득되어야 하고; 바람직하게는, 쿼리 계획 열거 알고리즘이 원본 쿼리 계획에 대한 모든 후보 쿼리 계획들을 열거하는데 사용될 수 있고, 예를 들어, IBM System R에서 사용되는 동적 프로그래밍 알고리즘인 통상적인 열거 알고리즘이 사용될 수 있음 -를 추가로 포함하고;

원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획 세트를 결정하는 단계는,

원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 후보 쿼리 계획 세트로부터 등가 쿼리 계획 세트를 결정하는 단계를 포함한다.

본 발명의 실시예들에서는, 술어의 기본 정보 및 결합 연산 규칙에 기초하여 획득되는 제약 조건에 따라 후보 쿼리 계획 세트로부터 원본 쿼리 계획에 대한 등가 쿼리 계획이 결정되고, 원본 쿼리 계획에 대한 모든 등가 쿼리 계획들이 획득될 수 있으므로, 데이터 쿼리 성능이 추가로 향상될 수 있다.

일부 구현들에서, 원본 쿼리 계획에서 결합 술어를 재구성하는 단계는,

원본 쿼리 계획에서의 내부 결합 연산의 모든 결합 술어들을 접속사 정규 형태로 변환하는 단계, 및 동일한 입력 표를 갖는 결합 술어들을 조합하는 단계; 및

원본 쿼리 계획에서의 비-내부 결합 연산의 모든 결합 술어들을 하나의 결합 술어로 조합하는 단계를 포함한다.

일부 구현들에서, 결합 술어의 기본 정보는 결합 술어의 입력 표, 결합 술어가 위치되는 결합 연산의 좌측 서브트리에 포함되는 결합 술어의 입력 표, 결합 술어가 위치되는 결합 연산의 우측 서브트리에 포함되는 결합 술어의 입력 표, 및 결합 술어가 위치되는 결합 연산의 결합 타입을 포함한다.

일부 구현들에서, 결합 연산 규칙은 연산 레벨 규칙 및 술어 레벨 규칙을 포함하고, 연산 레벨 규칙은 연산 레벨 교환 규칙: e₁ o^a _p12 e₂ = e₂ o^a _p12 e₁, 연산 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p23 e₃ = e₁ o^a _p12 (e₂ o^b _p23 e₃), 연산 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13 e₃ = (e₁ o^b _p13 e₃) o^a _p12 e₂, 및 연산 레벨 우측 치환 규칙: e₁ o^a _p13 (e₂ o^b _p23 e₃) = e₂ o^b _p23(e₁ o^a _p13 e₃)을 포함하고, 술어 레벨 규칙은 술어 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p _∧p23 e₃ = e₁ o^a _p12 _∧p (e₂ o^b _p23 e₃), 술어 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13 _∧p e₃ = (e₁ o^b _p13 e₃) o^a _p12 _∧p e₂, 및 술어 레벨 우측 치환 규칙: e₁ o^a _p _∧p13 (e₂ o^b _p23 e₃) = e₂ o^b _p _∧p23 (e₁ o^a _p13 e₃)를 포함하고, e_i은 쿼리 표현이고, o^a 및 o^b는 결합 연산들이고, pij는 e_i와 e_j 사이의 결합 술어이다.

일부 구현들에서, 결합 연산 규칙에 기초하여, 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건을 결정하는 단계는,

원본 쿼리 계획에서의 각각의 결합 연산 노드 o^B에 대해, o^B를 루트 노드로서 사용하는 서브트리에서의 각각의 결합 연산 노드 o^A를 횡단하는 단계; 및

o^B를 루트 노드로서 사용하는 서브트리의 좌측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제1 제약 조건을 추가하는 단계; 및 o^A 및 o^B가 연산 레벨 좌측 치환 규칙 및 술어 레벨 좌측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제2 제약 조건을 추가하는 단계; 또는

o^B를 루트 노드로서 사용하는 서브트리의 우측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제2 제약 조건을 추가하는 단계; 및 o^A 및 o^B가 연산 레벨 우측 치환 규칙 및 술어 레벨 우측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제1 제약 조건을 추가하는 단계를 포함하고;

제1 제약 조건은 T(e₂)->T(e₁)∩T(p_a1∧p_a2∧...∧p_an)이고, 제2 제약 조건은 T(e₁)->T(e₂)∩T(p_a1∧p_a2∧...∧p_an)이고, T(e₁) 는 o^A를 루트 노드로서 사용하는 서브트리의 좌측 서브트리 e₁에 포함되는 원본 입력 표를 표시하고, T(e₂) 는 o^A를 루트 노드로서 사용하는 서브트리의 우측 서브트리 e₂에 포함되는 원본 입력 표를 표시하고, T(p_a1∧p_a2∧...∧p_an)는 o^A 상에 재구성되는 결합 술어 p_a1∧p_a2∧...∧p_an에 포함되는 원본 입력 표를 표시하고, T₁->T₂는 T₁->T₂에 의해 제약되는 결합 술어가 위치되는 결합 연산을 루트 노드로서 사용하는 제1 서브트리가 T₁에서의 임의의 입력 표를 포함하면, 제1 서브트리가 T₂에서의 모든 입력 표들을 포함한다는 점을 표시한다.

제1 후보 쿼리 계획 P'는 P'가 이하의 조건들을 충족시키면 원본 쿼리 계획 P에 대한 등가 쿼리 계획이라고 결정하는 단계를 포함한다-

P'의 각각의 제1 결합 연산의 결합 타입은 내부 결합이고, 제1 결합 연산은 적어도 2개의 재구성되는 결합 술어들을 갖는 결합 연산이고, P에 있고 적어도 2개의 재구성되는 결합 술어들에서의 각각의 결합 술어에 대응하는 결합 연산의 결합 타입은 내부 결합임;

P'에서의 각각의 결합 연산 o^b' 상의 각각의 결합 술어 p에 대해,

o^b'가 연산 레벨 교환 규칙을 충족시키지 않을 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같음- T_l(p)는 p가 위치되는 결합 연산의 좌측 서브트리에 포함되는 p의 입력 표를 표시하고, T_r(p)는 p가 위치되는 결합 연산의 우측 서브트리에 포함되는 p의 입력 표를 표시함 -; 또는

o^b'가 연산 레벨 교환 규칙을 충족시킬 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같거나; 또는 P'에서의 T_l(p) 및 P에서의 T_r(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_l(p)은 같음; 및

P'에서의 각각의 결합 연산 o^b' 상의 각각의 결합 술어 p에 대해, p는 P에서의 p에 대한 제약 조건을 충족시킴 -.

일부 구현들에서, 등가 쿼리 계획 세트로부터 쿼리 계획을 선택하여 쿼리를 수행하는 단계는,

등가 쿼리 계획 세트로부터 비용이 최소인 쿼리 계획을 선택하여 쿼리를 수행하는 단계를 포함한다.

제2 양태에 따르면, 본 발명의 실시예는 데이터 쿼리 장치를 제공한다. 본 장치는 제1 양태에 따른 방법을 실행하기 위한 모듈을 포함한다.

제3 양태에 따르면, 본 발명의 실시예는 데이터 쿼리 장치를 제공한다. 본 장치는 프로세서, 메모리, 및 통신 인터페이스를 포함한다. 프로세서는 메모리 및 통신 인터페이스에 연결된다. 메모리는 명령어를 저장하도록 구성되고, 프로세서는 명령어를 실행하도록 구성되고, 통신 인터페이스는 프로세서의 제어 하에 다른 네트워크 엘리먼트와 통신하도록 구성된다. 프로세서가 명령어를 실행할 때 프로세서는 제1 양태에 따른 방법을 실행한다.

제4 양태에 따르면, 본 발명의 실시예는 데이터베이스 시스템을 제공한다. 이러한 데이터베이스 시스템은 제2 양태 또는 제3 양태에 따른 데이터 쿼리 장치 및 데이터베이스를 포함한다.

일부 구현들에서, 원본 쿼리 계획에 대한 등가 쿼리 계획은 4개의 연산 레벨 규칙들 및 3개의 술어 레벨 규칙들 중 적어도 하나를 사용하여 변환에 의해 원본 쿼리 계획으로부터 획득되는 쿼리 계획이다.

일부 구현들에서, 등가 쿼리 계획 공간은 4개의 연산 레벨 규칙들 및 3개의 술어 레벨 규칙들 중 적어도 하나를 사용하여 변환에 의해 원본 쿼리 계획으로부터 획득되는 쿼리 계획을 포함한다.

본 발명의 실시예들에서의 기술적 해결책들을 보다 명확히 설명하기 위해, 이하는 본 발명의 실시예들을 설명하는데 요구되는 첨부 도면들을 간단히 설명한다. 명백하게, 이하의 설명에서의 첨부 도면들은 단지 본 발명의 일부 실시예들을 도시하고, 해당 분야에서의 통상의 기술자는 창의적인 노력들 없이도 이러한 첨부 도면들로부터 다른 도면들을 여전히 도출할 수 있다.
도 1a 및 도 1b는 본 발명의 실시예에 따른 적용 시나리오들의 개략도들이다.
도 1c는 본 발명의 실시예에 따른 결합 연산의 예이다.
도 2는 본 발명의 실시예에 따른 등가 쿼리 계획의 예이다.
도 3은 본 발명의 실시예에 따른 연산 레벨 교환 규칙의 예이다.
도 4는 본 발명의 실시예에 따른 연산 레벨 조합 규칙의 예이다.
도 5는 본 발명의 실시예에 따른 연산 레벨 좌측 치환 규칙의 예이다.
도 6은 본 발명의 실시예에 따른 연산 레벨 우측 치환 규칙의 예이다.
도 7은 본 발명의 실시예에 따른 술어 레벨 조합 규칙의 예이다.
도 8은 본 발명의 실시예에 따른 술어 레벨 좌측 치환 규칙의 예이다.
도 9는 본 발명의 실시예에 따른 술어 레벨 우측 치환 규칙의 예이다.
도 10은 본 발명의 실시예에 따른 등가 쿼리 계획의 예이다.
도 11은 본 발명의 실시예에 따른 데이터 쿼리 방법의 개략 흐름도이다.
도 12는 본 발명의 실시예에 따른 쿼리 계획의 예이다.
도 13a 및 도 13b는 본 발명의 실시예에 따른 원본 쿼리 계획에서 술어의 제약 조건을 결정하는 흐름도이다.
도 14는 본 발명의 실시예에 따른 제약 조건을 추가하는 개략도이다.
도 15는 본 발명의 실시예에 따른 제약 조건을 추가하는 다른 개략도이다.
도 16은 본 발명의 실시예에 따른 등가 쿼리 계획을 결정하는 예이다.
도 17은 본 발명의 실시예에 따른 데이터 쿼리 장치의 개략 블록도이다.
도 18은 본 발명의 실시예에 따른 데이터베이스 시스템의 개략 블록도이다.
도 19는 본 발명의 실시예에 따른 데이터 쿼리 장치의 개략 구조도이다.

이하는 본 발명의 실시예들에서의 첨부 도면들을 참조하여 본 발명의 실시예들에서의 기술적 해결책들을 명백하고 완전하게 설명한다. 명백하게, 설명되는 실시예들은 본 발명의 실시예들 전부가 아니라 일부이다. 창의적인 노력들 없이 본 발명의 실시예들에 기초하여 해당 분야에서의 통상의 기술자에 의해 획득되는 모든 다른 실시예들은 본 발명의 보호 범위 내에 있을 것이다.

본 발명의 실시예들에서의 기술적 해결책들은 데이터베이스 시스템에 적용될 수 있다. 도 1a 및 도 1b는 본 발명의 실시예에 따른 적용 시나리오들의 개략도들이다. 도 1a는 단일 서버가 있는 데이터베이스 시스템이고, 도 1b는 분산형 데이터베이스 시스템이다.

도 1a에 도시되는 바와 같이, 단일 서버가 있는 데이터베이스 시스템(즉, 서버)은 데이터베이스 관리 시스템 및 데이터베이스를 포함하고, 클라이언트의 쿼리 요청을 처리하도록 그리고 쿼리 결과를 클라이언트에 리턴하도록 구성된다. 데이터베이스 관리 시스템은 쿼리 최적화기와 같은 관리 컴포넌트를 포함하고, 데이터베이스 시스템을 관리하도록 구성된다. 이러한 시나리오에 대해, 본 발명의 실시예들에서의 방법은, 서버, 또는 서버에서의 데이터베이스 관리 시스템, 또는 데이터베이스 관리 시스템에서의 쿼리 최적화기에 의해 실행될 수 있다.

도 1b에 도시되는 바와 같이, 분산형 데이터베이스 시스템은 복수의 서버들 및 분산형 관리 시스템을 포함하고, 클라이언트의 쿼리 요청을 처리하도록 그리고 쿼리 결과를 클라이언트에 리턴하도록 구성된다. 각각의 서버는 데이터베이스 관리 시스템 및 데이터베이스를 포함하고, 분산형 관리 시스템은 쿼리 최적화기와 같은 관리 컴포넌트를 포함하고, 분산형 데이터베이스 시스템을 관리하도록 구성된다. 이러한 시나리오에 대해, 본 발명의 실시예들에서의 방법은, 분산형 데이터베이스 시스템, 또는 분산형 데이터베이스 시스템에서의 분산형 관리 시스템, 또는 분산형 관리 시스템에서의 쿼리 최적화기에 의해 실행될 수 있다.

본 발명의 실시예들을 이해하기 쉽게 하기 위해, 이하는 데이터베이스 시스템에 관련되는 용어들을 먼저 설명한다.

본 발명의 다양한 실시예들에서, 결합 연산은 연산 또는 결합이라고 또한 지칭될 수 있고, 이러한 결합 연산은 데이터베이스에서의 2개 이상의 표들을 하나의 결과 표로 조합한다. 결합 술어는 술어라고 또한 지칭될 수 있고, 이러한 결합 술어는 2개 이상의 표들에서의 컬럼들의 관계를 설명하는데 사용된다. 결합 연산은 결합 술어를 사용하여 데이터베이스에서의 표들을 조합한다.

결합 연산은 내부 결합(inner join), 좌측/우측 외부 결합(left/right outer join), 전체 외부 결합(full outer join), 좌측/우측 반 결합(left/right semi-join), 및 좌측/우측 반대 결합(left/right anti-join)으로 분류된다.

내부 결합(inner join)은 데이터베이스에서 가장 흔한 결합 연산이다. 내부 결합은 결합 술어에 기초하여 2개의 표들(예를 들어, R 및 S)의 컬럼들을 함께 조합하여, 새로운 결과 표를 생성한다. 이러한 연산은 표 R의 각각의 로우를 표 S의 각각의 로우와 비교하고, 결합 술어를 충족시키는 조합을 찾는다. 결합 술어가 충족될 때, R 및 S에서의 매칭된 로우들은 컬럼별로(나란히) 결과 표에서의 하나의 로우로 조합된다.

좌측 외부 결합(left outer join)은 내부 결합의 확장이다. 좌측 외부 결합과 내부 결합 사이의 차이는, 2개의 표들 R과 S에 대해 좌측 외부 결합이 수행되면, 결합 술어를 충족시키는 좌측 표(즉, 표 R)에서의 로우에 대해 매칭되는 로우가 우측 표 S에 존재하지 않으면, 내부 결합에서 좌측 표에서의 로우에서의 값을 직접 폐기하는 대신에, 좌측 외부 결합이 레코드를 여전히 리턴하는 것이고, 이러한 레코드는 좌측 표에서의 모든 컬럼 값들을 보유하지만, 우측 표로부터의 로우에 대응하는 각각의 컬럼에서의 값은 널(NULL)이다. 우측 외부 결합(right outer join)은 좌측 외부 결합과 유사하고, 유일한 차이는, 우측 표에서의 로우에 대해 매칭되는 로우가 좌측 표에 존재하지 않으면, 연산에 의해 리턴되는 레코드에서 좌측 표로부터의 각각의 컬럼에서의 값이 널이라는 것이다. 전체 외부 결합(full outer join)은 좌측/우측 외부 결합과 유사하고, 유일한 차이는, 좌측 표 또는 우측 표에 상관없이, 해당 표에서의 로우에 대해 매칭되는 로우가 존재하지 않으면, 연산은 레코드를 리턴하고, 이러한 레코드에서 매칭되는 로우가 없는 표에서의 컬럼 값은 널이라는 것이다.

좌측 반 결합(left semi-join)은 우측 표에서의 매칭되는 로우들을 갖는(즉, 결합 술어를 충족시키는), 좌측 표에서의, 로우들만을 리턴한다. 우측 반 결합(right semi-join)은 좌측 표에서의 매칭되는 로우들을 갖는(즉, 결합 술어를 충족시키는), 우측 표에서의, 로우들만을 리턴한다.

좌측 반대 결합(left anti-join)은 우측 표에서의 매칭되는 로우를 갖지 않는(즉, 결합 술어를 충족시키지 않는), 좌측 표에서의, 로우들만을 리턴한다. 우측 반대 결합(right anti-join)은 좌측 표에서의 매칭되는 로우를 갖지 않는(즉, 결합 술어를 충족시키는), 우측 표에서의, 로우들만을 리턴한다. 반 결합과 반대 결합의 정의들로부터 반대 결합과 반 결합은 서로에 대해 상보적인 세트들이라는 점을 알 수 있다.

도 1c는 전술한 다양한 결합 연산들의 예들을 도시한다. 도 1c에서는, 표 R 및 표 S에 대해 결합 연산이 수행되는 것이 예로서 사용된다. 결합 술어는 R.b = S.c이고, 다양한 결합 연산들의 결과들이 도 1c에 도시된다.

도 2는 등가 쿼리 계획의 예를 도시한다. 도 2에 도시되는 바와 같이, SQL 쿼리에 대해 R₁∞_p12R₂∞_p23R₃, R₁, R₂, 및 R₃은 입력 표들을 표현하고, ∞는 내부 결합 연산을 표현하고, p12 및 p23은 R₁과 R₂ 사이의 결합 술어 및 R₂와 R₃ 사이의 결합 술어를 각각 표현한다. 도 2에서의 2개의 쿼리 계획들 양자 모두 쿼리에 대한 등가 쿼리 계획들이다.

본 발명의 다양한 실시예들에서, 결합 연산 규칙은 연산 레벨 규칙 및 술어 레벨 규칙을 포함한다. 연산 레벨 규칙은 연산 레벨 교환 규칙, 연산 레벨 조합 규칙, 연산 레벨 좌측 치환 규칙, 및 연산 레벨 우측 치환 규칙을 포함한다. 술어 레벨 규칙은 술어 레벨 조합 규칙, 술어 레벨 좌측 치환 규칙, 및 술어 레벨 우측 치환 규칙을 포함한다. 이하의 설명에서, 각각의 부호의 의미가 표 1에 도시된다.

연산 레벨 교환 규칙은 e₁ o^a _p12 e₂ = e₂ o^a _p12 e₁이다. 도 3은 연산 레벨 교환 규칙의 예이다. 표 2는 연산 레벨 교환 규칙의 결합 연산 표이고, 각각의 결합 연산이 연산 레벨 교환 규칙을 충족시키는지 보여준다. +는 결합 연산이 연산 레벨 교환 규칙을 충족시킨다는 점을 표시하고, -는 결합 연산이 연산 레벨 교환 규칙을 충족시키지 않는다는 점을 표시한다. 우측 외부 결합, 우측 반 결합, 및 우측 반대 결합은 대응하는 좌측 결합 연산들로 변환될 수 있고, 따라서 본 명세서에서는 좌측 결합 연산들만 고려된다는 점이 이해되어야 한다.

연산 레벨 조합 규칙은 (e₁ o^a _p12 e₂) o^b _p23 e₃ = e₁ o^a _p12 (e₂ o^b _p23 e₃)이다. 도 4는 연산 레벨 조합 규칙의 예이다. 표 3은 연산 레벨 조합 규칙의 결합 연산 표이고, 임의의 2개의 결합 연산들이 연산 레벨 조합 규칙을 충족시키는지 보여준다. +는 2개의 결합 연산들이 연산 레벨 조합 규칙을 충족시킨다는 점을 표시하고, -는 2개의 결합 연산들이 연산 레벨 조합 규칙을 충족시키지 않는다는 점을 표시한다. 첨자가 있는 +는 조건 하에서 조합 규칙이 충족된다는 점을 표시한다. 즉, 첨자에서의 조건이 충족될 때만, 2개의 대응하는 결합 연산들이 조합 규칙을 충족시킬 수 있다.

연산 레벨 좌측 치환 규칙은 (e₁ o^a _p12 e₂) o^b _p13 e₃ = (e₁ o^b _p13 e₃) o^a _p12 e₂이다. 도 5는 연산 레벨 좌측 치환 규칙의 예이다. 표 4는 연산 레벨 좌측 치환 규칙의 결합 연산 표이고, 임의의 2개의 결합 연산들이 연산 레벨 좌측 치환 규칙을 충족시키는지 보여준다. +는 2개의 결합 연산들이 연산 레벨 좌측 치환 규칙을 충족시킨다는 점을 표시하고, -는 2개의 결합 연산들이 연산 레벨 좌측 치환 규칙을 충족시키지 않는다는 점을 표시한다. 첨자가 있는 +는 조건 하에서 좌측 치환 규칙이 충족된다는 점을 표시한다. 즉, 첨자에서의 조건이 충족될 때만, 2개의 대응하는 결합 연산들이 좌측 치환 규칙을 충족시킬 수 있다.

연산 레벨 우측 치환 규칙은 e₁ o^a _p13 (e₂ o^b _p23 e₃) = e₂ o^b _p23(e₁ o^a _p13e₃)이다. 도 6은 연산 레벨 우측 치환 규칙의 예이다. 표 5는 연산 레벨 우측 치환 규칙의 결합 연산 표이고, 임의의 2개의 결합 연산들이 연산 레벨 우측 치환 규칙을 충족시키는지 보여준다. +는 2개의 결합 연산들이 연산 레벨 우측 치환 규칙을 충족시킨다는 점을 표시하고, -는 2개의 결합 연산들이 연산 레벨 우측 치환 규칙을 충족시키지 않는다는 점을 표시한다. 첨자가 있는 +는 조건 하에서 우측 치환 규칙이 충족된다는 점을 표시한다. 즉, 첨자에서의 조건이 충족될 때만, 2개의 대응하는 결합 연산들이 우측 치환 규칙을 충족시킬 수 있다.

전술한 연산 레벨 규칙에서, 연산에서의 결합 술어와 연산은 함께 결속된다, 즉, 결합 술어가 연산들 사이에서 이동할 수 없다. 연산 레벨 규칙과 상이하게, 술어 레벨 규칙에서는, 술어가 연산들 사이에서 이동할 수 있다.

술어 레벨 조합 규칙은 (e₁ o^a _p12 e₂) o^b _p _∧p23 e₃ = e₁ o^a _p12 _∧p (e₂ o^b _p23 e₃)이다. ∧는 AND 논리 연산을 표시하고, p는 p23을 제외한 결합 술어를 표시하고, p는 널이 아니다. 도 7은 술어 레벨 조합 규칙의 예이다.

술어 레벨 좌측 치환 규칙은 (e₁ o^a _p12 e₂) o^b _p13 _∧p e₃ = (e₁ o^b _p13 e₃) o^a _p12 _∧p e₂이다. ∧는 AND 논리 연산을 표시하고, p는 p13을 제외한 결합 술어를 표시하고, p는 널이 아니다. 도 8은 술어 레벨 좌측 치환 규칙의 예이다.

술어 레벨 우측 치환 규칙은 e₁ o^a _p _∧p13 (e₂ o^b _p23 e₃) = e₂ o^b _p _∧ _p23(e₁ o^a _p13 e₃)이다. ∧는 AND 논리 연산을 표시하고, p는 p13을 제외한 결합 술어를 표시하고, p는 널이 아니다. 도 9는 술어 레벨 우측 치환 규칙의 예이다.

표 6은 술어 레벨 규칙의 결합 연산 표이고, 임의의 2개의 결합 연산들이 술어 레벨 규칙을 충족시키는지 표시한다. +는 2개의 결합 연산들이 술어 레벨 규칙을 충족시킨다는 점을 표시하고, -는 2개의 결합 연산들이 술어 레벨 규칙을 충족시키지 않는다는 점을 표시한다. 전술한 3개의 술어 레벨 규칙들의 결합 연산 표들은 동일하다, 즉, 표 6은 모든 3개의 술어 레벨 규칙들의 결합 연산 표들을 표현한다.

본 발명의 실시예들에서, 전술한 연산 레벨 규칙들 또는 술어 레벨 규칙들을 사용하여 변환에 의해 획득될 수 있는 모든 쿼리 계획들은 등가 쿼리 계획들이다. 즉, 본 발명의 실시예들에서 등가 쿼리 계획 공간은 4개의 연산 레벨 규칙들 및 3개의 술어 레벨 규칙들 중 적어도 하나를 사용하여 변환에 의해 획득될 수 있는 모든 쿼리 계획들이다. 연산들 사이에 규칙이 충족되는지는 해당 규칙의 결합 연산 표를 쿼리하여 결정될 수 있다.

연산 레벨 규칙만을 사용하여 변환에 의해 획득되는 등가 쿼리 계획 공간에 비해, 본 발명의 실시예에서의 등가 쿼리 계획 공간은 보다 완전하다. 즉, 연산 레벨 규칙만 사용하여 변환이 수행되면, 모든 등가 쿼리 계획들이 획득될 수 있는 것은 아니다. 예를 들어, 도 10에 도시되는 바와 같이, 좌측 원본 쿼리 계획에 대해, 연산들 사이의 결합 술어는 2개의 우측 후보 쿼리 계획들에서 이동되고, 따라서 2개의 후보 쿼리 계획들은 전술한 4개의 연산 레벨 규칙들을 사용하여 좌측 원본 쿼리 계획을 변환하여 획득될 수 없다. 그러나, 2개의 우측 후보 쿼리 계획들은 좌측 원본 쿼리 계획과 실제로 등가이다.

본 발명의 실시예들에서, 원본 쿼리 계획에 대한 등가 쿼리 계획은 연산 레벨 규칙들 및 술어 레벨 규칙들에 기초하여 결정되고, 원본 쿼리 계획에 대한 모든 등가 쿼리 계획들이 획득될 수 있다.

도 11은 본 발명의 실시예에 따른 데이터 쿼리 방법(1100)의 개략 흐름도이다. 본 방법(1100)은 데이터베이스 시스템에 의해 실행되고, 이러한 데이터베이스 시스템은 컴퓨터 디바이스 상에서 실행된다. 구체적으로는, 본 방법은 컴퓨터 상에서 실행되는 데이터 쿼리 장치에 의해 실행된다. 이러한 데이터 쿼리 장치는, 쿼리 최적화기와 같은, 데이터베이스 시스템에서의 장치일 수 있거나, 또는 데이터베이스 시스템일 수 있다.

S1110. 데이터 쿼리 요청을 수신함.

예를 들어, 이러한 데이터 쿼리 요청은 SQL 언어를 사용하여 사용자에 의해 입력되는 데이터 쿼리 요청일 수 있다.

S1120. 데이터 쿼리 요청에 따라 원본 쿼리 계획을 생성함.

데이터 쿼리 요청이 수신된 이후, 원본 쿼리 계획을 획득하도록 데이터 쿼리 요청이 파싱된다.

선택적으로, S1130. 원본 쿼리 계획에 따라 후보 쿼리 계획 세트를 획득함.

이러한 후보 쿼리 계획 세트는 원본 쿼리 계획에 대한 모든 후보 쿼리 계획들을 포함한다. 이러한 단계에서는, 원본 쿼리 계획에 대한 모든 후보 쿼리 계획들을 열거하는데 쿼리 계획 열거 알고리즘이 사용될 수 있다. 예를 들어, 통상적인 열거 알고리즘은 IBM System R에서 사용되는 동적 프로그래밍 알고리즘을 포함한다.

원본 쿼리 계획에 대한 모든 후보 쿼리 계획들이 열거된 이후, 원본 쿼리 계획에 대한 등가 쿼리 계획이 모든 후보 쿼리 계획들로부터 결정될 수 있다.

이러한 단계는 선택적 단계이다. 즉, 본 발명의 이러한 실시예에서는, 등가 쿼리 계획 또는 등가 쿼리 계획 세트가 이하의 단계를 사용하여 원본 쿼리 계획으로부터 직접 획득될 수 있거나, 또는 등가 쿼리 계획 세트가 이하의 단계를 사용하여 후보 쿼리 계획 세트로부터 획득될 수 있다.

S1140. 원본 쿼리 계획에서 결합 술어를 재구성함.

구체적으로, 원본 쿼리 계획에서의 내부 결합 연산의 모든 결합 술어들이 접속사 정규 형태로 변환되고, 동일한 입력 표를 갖는 결합 술어들이 조합되고; 원본 쿼리 계획에서의 비-내부 결합 연산의 모든 결합 술어들이 하나의 결합 술어로 조합된다.

즉, 재구성하는 방식은 원본 쿼리 계획에서의 각각의 결합 연산 노드를 횡단하는 것이고, 이하의 2개의 경우들에서 결합 연산 노드의 결합 타입에 따라 처리가 수행된다:

결합 연산이 내부 결합이면, 결합 연산에서의 모든 술어들이 접속사 정규 형태(conjunctive normal form, CNF), 즉, p₁∧p₂∧...∧p_n 형태로 변환되고, 동일한 입력 표를 갖는 술어들이 조합된다.

결합 연산이 내부 결합이 아니면, 결합 연산에서의 모든 술어들이 하나의 술어로 조합된다.

S1150. 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보를 결정함.

본 발명의 다양한 실시예들에서, 결합 술어의 기본 정보는 결합 술어의 입력 표, 결합 술어가 위치되는 결합 연산의 좌측 서브트리에 포함되는 결합 술어의 입력 표, 결합 술어가 위치되는 결합 연산의 우측 서브트리에 포함되는 결합 술어의 입력 표, 및 결합 술어가 위치되는 결합 연산의 결합 타입을 포함한다.

구체적으로, 술어 p에 대해, 술어 p의 기본 정보는,

T(p): p에 포함되는 입력 표;

T_l(p): p가 위치되는 연산의 좌측 서브트리에 포함되는 p의 입력 표;

T_r(p): p가 위치되는 연산의 우측 서브트리에 포함되는 p의 입력 표; 및

O(p): p가 위치되는 연산의 결합 타입을 포함한다.

예를 들어, 도 12에 도시되는 루트 노드의 결합 술어 p = {R1.a + R2.b = R3.c}에 대해, p의 기본 정보는 이하와 같다:

T(p): {R1, R2, R3};

T_l(p): {R1, R2};

T_r(p): {R3}; 및

O(p): 내부 결합.

S1160. 결합 연산 규칙에 기초하여, 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건을 결정함.

구체적으로, 원본 쿼리 계획에서의 각각의 결합 연산 노드 o^B에 대해, o^B를 루트 노드로서 사용하는 서브트리에서의 각각의 결합 연산 노드 o^A가 횡단되고;

o^B를 루트 노드로서 사용하는 서브트리의 좌측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제1 제약 조건이 추가되고; o^A 및 o^B가 연산 레벨 좌측 치환 규칙 및 술어 레벨 좌측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제2 제약 조건이 추가되고;

o^B를 루트 노드로서 사용하는 서브트리의 우측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙과 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제2 제약 조건이 추가되고; o^A 및 o^B가 연산 레벨 우측 치환 규칙 및 술어 레벨 우측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제1 제약 조건이 추가되고;

제1 제약 조건은 T(e₂)->T(e₁)∩T(p_a1∧p_a2∧...∧p_an)이고, 제2 제약 조건은 T(e₁)->T(e₂)∩T(p_a1∧p_a2∧...∧p_an)이고, T(e₁)는 o^A를 루트 노드로서 사용하는 서브트리의 좌측 서브트리 e₁에 포함되는 원본 입력 표를 표시하고, T(e₂) 는 o^A를 루트 노드로서 사용하는 서브트리의 우측 서브트리 e₂에 포함되는 원본 입력 표를 표시하고, T(p_a1∧p_a2∧...∧p_an)는 o^A 상에 재구성되는 결합 술어 p_a1∧p_a2∧...∧p_an에 포함되는 원본 입력 표를 표시하고, T₁->T₂는 T₁->T₂에 의해 제약되는 결합 술어가 위치되는 결합 연산을 루트 노드로서 사용하는 제1 서브트리가 T₁에서의 임의의 입력 표를 포함하면, 제1 서브트리는 T₂에서의 모든 입력 표들을 포한다는 점을 표시하고, ∩는 교집합 세트 부호이다.

예를 들어, 도 13a 및 도 13b는 원본 쿼리 계획에서 술어의 제약 조건을 결정하는 흐름도를 도시한다. 도 13a 및 도 13b에 도시되는 절차는 2개 계층 횡단을 포함한다. 외부 계층에 대해, 원본 쿼리 계획에서의 각각의 연산 노드 o^B(o^B 상에 재구성되는 술어는 p_b1∧p_b2∧...∧p_bn임)가 횡단되고; 내부 계층에 대해, o^B를 루트 노드로서 사용하는 쿼리 서브트리에서의 각각의 연산 노드 o^A(o^A 상에 재구성되는 술어는 p_a1∧p_a2∧...∧p_an임)가 횡단된다. 다음으로, 이하의 2개의 경우들에서 o^A 및 o^B 사이의 관계에 따라 o^B 상의 각각의 술어에 제약 조건이 추가된다.

o^A가 o^B의 좌측 서브트리에 있으면, 도 14에 도시되는 방법에 따라 o^B 상의 각각의 술어 p_bi에 제약 조건이 추가된다.

o^A가 o^B의 우측 서브트리에 있으면, 도 15에 도시되는 방법에 따라 o^B 상의 각각의 술어 p_bi에 제약 조건이 추가된다.

S1170. 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정함.

선택적으로, 원본 쿼리 계획에 대한 등가 쿼리 계획 세트는 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 결정될 수 있다. 등가 쿼리 계획 세트에서의 쿼리 계획은 원본 쿼리 계획에 대한 등가 쿼리 계획이다.

이러한 단계에서, 선택적으로, 원본 쿼리 계획에 대한 후보 쿼리 계획 세트가 열거 방식으로 획득되면, 등가 쿼리 계획 세트는 후보 쿼리 계획 세트로부터 결정될 수 있다, 즉, 각각의 후보 쿼리 계획이 원본 쿼리 계획에 대한 등가 쿼리 계획인지 결정된다. 후보 쿼리 계획 세트가 존재하지 않으면, 후보 쿼리 계획은 매번 원본 쿼리 계획으로부터 획득될 수 있고, 후보 쿼리 계획이 원본 쿼리 계획에 대한 등가 쿼리 계획인지 결정된다.

구체적으로, 제1 후보 쿼리 계획 P'는 P'가 이하의 조건들을 충족시키면 원본 쿼리 계획 P에 대한 등가 쿼리 계획이라고 결정된다:

P'의 각각의 제1 결합 연산의 결합 타입은 내부 결합이고, 제1 결합 연산은 적어도 2개의 재구성되는 결합 술어들을 갖는 결합 연산이고, P에 있고 적어도 2개의 재구성되는 결합 술어들에서의 각각의 결합 술어에 대응하는 결합 연산의 결합 타입은 내부 결합임(이러한 조건은 결합 타입 일관성이라고 지칭될 수 있음);

o^b'가 연산 레벨 교환 규칙을 충족시키지 않을 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같음- T_l(p)는 p가 위치되는 결합 연산의 좌측 서브트리에 포함되는 p의 입력 표를 표시하고, T_r(p)는 p가 위치되는 결합 연산의 우측 서브트리에 포함되는 p의 입력 표를 표시함 -;

o^b'가 연산 레벨 교환 규칙을 충족시킬 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같거나; 또는 P'에서의 T_l(p) 및 P에서의 T_r(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_l(p)은 같음(이러한 조건은 입력 표 정보 일관성이라고 지칭될 수 있음); 및

P'에서의 각각의 결합 연산 o^b' 상의 각각의 결합 술어 p에 대해, p는 P에서의 p에 대한 제약 조건을 충족시킴(이러한 조건은 제약 조건 일관성이라고 지칭될 수 있음), 그리고, 원본 쿼리 계획에 대한 후보 쿼리 계획 세트가 이전에 획득되면, 여기서 제1 후보 쿼리 계획 P'는 후보 쿼리 계획 세트에서의 임의의 후보 쿼리 계획일 수 있음.

원본 쿼리 계획에 대한 모든 등가 쿼리 계획들이 전술한 방식으로 획득할 수 있다. 즉, 본 발명의 실시예에서 획득되는 등가 쿼리 계획 세트는 가장 완전하다.

S1180. 원본 쿼리 계획에 대한 등가 쿼리 계획에 따라 쿼리를 수행함.

선택적으로, 등가 쿼리 계획 세트로부터 쿼리 계획이 선택되어 쿼리를 수행할 수 있다. 즉, 전술한 획득된 등가 쿼리 계획 세트로부터 쿼리 계획이 선택되어 쿼리를 수행한다. 구체적으로, 등가 쿼리 계획 세트로부터 비용이 최소인 쿼리 계획이 선택되어 쿼리를 수행할 수 있고, 쿼리 결과가 리턴된다.

본 발명의 이러한 실시예에서의 등가 쿼리 계획 세트는 원본 쿼리 계획에 대한 모든 등가 쿼리 쿼리 계획들을 포함하기 때문에, 최적의 쿼리 계획이 본 발명의 이러한 실시예에서 선택될 수 있다. 상이한 쿼리 계획들은 수십 또는 심지어 수백 배의 성능 차이가 있다는 점을 고려하면, 본 발명의 이러한 실시예에서의 방법을 사용하여 데이터 쿼리 성능이 상당히 향상될 수 있다.

따라서, 본 발명의 이러한 실시예에서의 데이터 쿼리 방법에 따르면, 술어의 기본 정보 및 결합 연산 규칙에 기초하여 획득되는 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획이 결정되고, 원본 쿼리 계획에 대한 모든 등가 쿼리 계획들이 획득될 수 있으므로, 데이터 쿼리 성능이 향상될 수 있다.

본 발명의 이러한 실시예에서의 등가 쿼리 계획 세트는 4개의 연산 레벨 규칙들 및 3개의 술어 레벨 규칙들 중 적어도 하나를 사용하여 변환에 의해 원본 쿼리 계획으로부터 획득될 수 있는 모든 쿼리 계획들을 포함한다. 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하기 위한 방법은 전술한 단계 S1140 내지 단계 S1170에서 주어진다. 이하는 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하기 위한 방법을 구체적인 예를 참조하여 상세히 설명한다. 이것은 단지 해당 분야에서의 기술자가 본 발명의 이러한 실시예를 더 잘 이해하는 것을 도우려고 의도되는 것일 뿐이고, 본 발명의 이러한 실시예의 범위를 제한하려고 의도되는 것은 아니라는 점이 주목되어야 한다.

도 16은 3개의 쿼리 계획들 P, P', 및 P''를 도시한다. ∞는 내부 결합 연산을 표현하고, ▷는 좌측 반대 결합을 표현하고, P는 원본 쿼리 계획이고, P' 및 P''는 후보 쿼리 계획들이다. 후보 쿼리 계획들 P' 및 P''가 원본 쿼리 계획 P와 등가인지가 이하의 방식으로 결정될 수 있다.

1. 원본 쿼리 계획 P에서의 결합 술어들이 재구성되고, 재구성되는 결합 술어들의 기본 정보가 결정됨- P는 총 3개의 결합 연산들(즉, ∞_p14∧p34, ▷_p23, 및 ∞_p12)을 포함함 -. 결합 연산 ∞_p14∧p34에 대해, 결합 연산은 내부 결합이기 때문에, 결합 연산의 술어들이 접속사 정규 형태로 변환될 필요가 있다(p14∧p34의 접속사 정규 형태는 p14∧p34 임). p14 및 p34의 입력 표들이 상이하기 때문에, p14 및 p34가 하나의 술어로 조합될 수 없다. 결합 연산 ▷_p23에 대해, 결합 연산은 내부 결합이 아니기 때문에, 결합 연산의 술어(즉, p23)는 하나의 술어로서 고려된다. 유사하게, 결합 연산 ∞_p12의 술어는 재구성된 이후에도 여전히 p12이다. 술어가 재구성된 이후, 재구성되는 술어들의 기본 정보가 결정된다. 표 7은 P에서 재구성되는 술어들의 기본 정보를 나열한다.

2. 재구성되는 결합 술어들의 제약 조건들이 결정됨: 연산 ∞_p14∧p34는 2개의 자손 연산들(즉, ∞_p12 및 ▷_p23)을 갖고, 따라서 이러한 2개의 자손 연산들 및 해당 연산이 대응하는 규칙을 충족시키는지가 결정되어 술어들 p14 및 p34의 제약 조건들을 획득할 필요가 있다. 자손 연산 ∞_p12 및 연산 ∞_p14∧p34는 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키고, 연산 레벨 좌측 치환 규칙 및 술어 레벨 좌측 치환 규칙을 추가로 충족시키고, 따라서 제약 규칙이 추가될 필요가 없다. 자손 연산 ▷_p23 및 연산 ∞_p14∧p34는 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않고, 따라서 p14 및 p34에 규칙 R₃->R₂가 추가될 필요가 있다. 또한, ▷_p23 및 연산 ∞_p14∧p34는 술어 레벨 좌측 치환 규칙을 충족시키지는 않지만, 연산 레벨 좌측 치환 규칙을 충족시키고, 따라서 제약 규칙이 추가로 추가될 필요가 없다. 유사하게, 연산들 ∞_p12 및 ▷_p23의 술어들의 제약 조건들과 연산들 ∞_p12 및 ▷_p23의 자손 연산들은 연산들 ∞_p12 및 ▷_p23와 연산들 ∞_p12 및 ▷_p23의 자손 연산들이 대응하는 규칙을 충족시키는지 결정하여 획득될 수 있다. 표 8은 원본 쿼리 계획 P에서 재구성되는 술어의 제약 조건들을 나열한다.

3. 등가 쿼리 계획이 기본 정보 및 술어들의 제약 조건들에 따라 결정됨: 후보 쿼리 계획 P'는 P'가 결합 타입 일관성을 위반하기 때문에 원본 쿼리 계획 P에 등가가 아니다(P'의 루트 노드에 대한 연산은 2개의 술어들을 포함하지만, 노드의 연산 타입은 내부 결합이 아니고, P에 있고 p23에 대응하는 연산의 결합 타입은 내부 결합이 아님). 후보 쿼리 계획 P''는 결합 타입 일관성(P''에서의 연산 ∞_p12∧p34는 내부 결합이고, p12 및 p34에 대응하는 원본 쿼리 P에서의 연산들 또한 내부 결합들임), 입력 표 정보 일관성(P''에서의 술어의 입력 표 정보 및 해당 표에서의 술어의 입력 표 정보가 일관됨), 및 제약 조건 일관성(P''에서의 술어가 표에 도시되는 제약 조건을 충족시킴)을 충족시키고, 따라서 P''는 원본 쿼리 계획 P와 등가이다.

본 발명의 이러한 실시예에서의 등가 쿼리 계획을 결정하기 위한 방법에 따르면, 원본 쿼리 계획에 대한 모든 등가 쿼리 계획들이 획득될 수 있고, 데이터 쿼리 성능이 향상될 수 있다.

전술한 프로세스들의 시퀀스 번호들이 본 발명의 다양한 실시예들에서의 실행 시퀀스들을 의미하는 것은 아니라는 점이 이해되어야 한다. 프로세스들의 실행 시퀀스들은 프로세스들의 기능들 및 내부 로직에 따라 결정되어야 하고, 본 발명의 실시예들의 구현 프로세스들에 대한 어떠한 제한으로도 해석되어서는 안 된다.

전술한 것은 본 발명의 실시예에 따른 데이터 쿼리 방법을 상세히 설명하였다. 이하는 본 발명의 실시예에 따른 데이터 쿼리 장치 및 데이터베이스 시스템을 설명한다. 이러한 데이터 쿼리 장치 및 데이터베이스 시스템은 본 발명의 전술한 실시예에서의 데이터 쿼리 방법을 실행할 수 있다.

도 17은 본 발명의 실시예에 따른 데이터 쿼리 장치(1700)의 개략 블록도이다. 이러한 장치(1700)는 데이터베이스 시스템에서의 장치, 예를 들어, 쿼리 최적화기일 수 있다. 도 17에 도시되는 바와 같이, 이러한 장치(1700)는,

데이터 쿼리 요청을 수신하도록 구성되는 수신 모듈(1710);

데이터 쿼리 요청에 따라 원본 쿼리 계획을 생성하도록 구성되는 생성 모듈(1720);

원본 쿼리 계획에서 결합 술어를 재구성하도록 구성되는 재구성 모듈(1740);

원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보를 결정하도록; 결합 연산 규칙에 기초하여, 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건을 결정하도록; 그리고 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하도록 구성되는 결정 모듈(1750); 및

원본 쿼리 계획에 대한 등가 쿼리 계획에 따라 쿼리를 수행하도록 구성되는 쿼리 모듈(1780)을 포함한다.

본 발명의 이러한 실시예에서의 데이터 쿼리 장치에 따르면, 술어의 기본 정보 및 결합 연산 규칙에 기초하여 획득되는 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획이 결정되고, 원본 쿼리 계획에 대한 모든 등가 쿼리 계획들이 획득될 수 있으므로, 데이터 쿼리 성능이 향상될 수 있다.

선택적으로, 본 발명의 실시예에서, 결정 모듈(1750)은 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 원본 쿼리 계획에 대한 등가 쿼리 계획 세트를 결정하도록 구체적으로 구성되고;

쿼리 모듈(1780)은 등가 쿼리 계획 세트로부터 쿼리 계획을 선택하여 쿼리를 수행하도록 구체적으로 구성된다.

선택적으로, 본 발명의 실시예에서, 이러한 장치(1700)는,

원본 쿼리 계획에 따라 후보 쿼리 계획 세트를 획득하도록 구성되는 획득 모듈(1730)을 추가로 포함할 수 있고;

이러한 경우, 결정 모듈(1750)은 원본 쿼리 계획에서 재구성되는 결합 술어의 기본 정보 및 원본 쿼리 계획에서 재구성되는 결합 술어의 제약 조건에 따라 후보 쿼리 계획 세트로부터 등가 쿼리 계획 세트를 결정하도록 구체적으로 구성된다.

선택적으로, 본 발명의 실시예에서, 재구성 모듈(1740)은 구체적으로,

원본 쿼리 계획에서의 내부 결합 연산의 모든 결합 술어들을 접속사 정규 형태로 변환하도록, 그리고 동일한 입력 표를 갖는 결합 술어들을 조합하도록; 그리고

원본 쿼리 계획에서의 비-내부 결합 연산의 모든 결합 술어들을 하나의 결합 술어로 조합하도록 구성된다.

선택적으로, 본 발명의 실시예에서, 결합 술어의 기본 정보는 결합 술어의 입력 표, 결합 술어가 위치되는 결합 연산의 좌측 서브트리에 포함되는 결합 술어의 입력 표, 결합 술어가 위치되는 결합 연산의 우측 서브트리에 포함되는 결합 술어의 입력 표, 및 결합 술어가 위치되는 결합 연산의 결합 타입을 포함한다.

선택적으로, 본 발명의 실시예에서, 결합 연산 규칙은 연산 레벨 규칙 및 술어 레벨 규칙을 포함하고, 연산 레벨 규칙은 연산 레벨 교환 규칙: e₁ o^a _p12 e₂ = e₂ o^a _p12 e₁, 연산 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p23 e₃ = e₁ o^a _p12 (e₂ o^b _p23 e₃), 연산 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13 e₃ = (e₁ o^b _p13 e₃) o^a _p12 e₂, 및 연산 레벨 우측 치환 규칙: e₁ o^a _p13 (e₂ o^b _p23 e₃) = e₂ o^b _p23(e₁ o^a _p13 e₃)을 포함하고, 술어 레벨 규칙은 술어 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p _∧p23 e₃ = e₁ o^a _p12 _∧p (e₂ o^b _p23 e₃), 술어 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13 _∧p e₃ = (e₁ o^b _p13 e₃) o^a _p12 _∧p e₂, 및 술어 레벨 우측 치환 규칙: e₁ o^a _p _∧p13 (e₂ o^b _p23 e₃) = e₂ o^b _p _∧p23 (e₁ o^a _p13 e₃)를 포함하고, e_i은 쿼리 표현이고, o^a 및 o^b는 결합 연산들이고, pij는 e_i와 e_j 사이의 결합 술어이다.

선택적으로, 본 발명의 실시예에서, 결정 모듈(1750)은 구체적으로,

원본 쿼리 계획에서의 각각의 결합 연산 노드 o^B에 대해, o^B를 루트 노드로서 사용하는 서브트리에서의 각각의 결합 연산 노드 o^A를 횡단하도록; 그리고

o^B를 루트 노드로서 사용하는 서브트리의 좌측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제1 제약 조건을 추가하도록; 그리고 o^A 및 o^B가 연산 레벨 좌측 치환 규칙 및 술어 레벨 좌측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제2 제약 조건을 추가하도록;

o^B를 루트 노드로서 사용하는 서브트리의 우측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제2 제약 조건을 추가하도록; 그리고 o^A 및 o^B가 연산 레벨 우측 치환 규칙 및 술어 레벨 우측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성되는 결합 술어에 제1 제약 조건을 추가하도록 구성되고;

제1 후보 쿼리 계획 P'는 P'가 이하의 조건들을 충족시키면 원본 쿼리 계획 P에 대한 등가 쿼리 계획이라고 결정하도록 구성된다-

선택적으로, 본 발명의 실시예에서, 쿼리 모듈(1780)은 구체적으로,

등가 쿼리 계획 세트로부터 비용이 최소인 쿼리 계획을 선택하여 쿼리를 수행하도록 구성된다.

본 발명의 이러한 실시예에 따른 데이터 쿼리 장치(1700)는 본 발명의 실시예들에 따른 데이터 쿼리 방법의 실행 본체에 대응할 수 있고, 이러한 장치(1700)에서의 모듈들의 전술한 그리고 다른 연산들 및/또는 기능들은 전술한 방법들의 대응하는 프로시저들을 구현하는데 각각 사용된다. 간결성을 위해, 상세 사항들이 여기서 다시 설명되지는 않는다.

도 18은 본 발명의 실시예에 따른 데이터베이스 시스템(1800)의 개략 블록도를 도시한다. 도 18에 도시되는 바와 같이, 데이터베이스 시스템(1800)은 본 발명의 실시예들에 따른 전술한 데이터 쿼리 장치(1700) 및 데이터베이스(1810)를 포함한다. 데이터베이스 시스템(1800)은 본 발명의 실시예들에 따른 데이터 쿼리 방법을 실행할 수 있고, 데이터베이스(1810)에서의 쿼리를 수행할 수 있다.

도 19는 본 발명의 다른 실시예에 따른 데이터 쿼리 장치의 구조를 도시한다. 이러한 장치는 적어도 하나의 프로세서(1902)(예를 들어, CPU), 적어도 하나의 네트워크 인터페이스(1905) 또는 다른 통신 인터페이스, 메모리(1906), 및 이러한 장치들 사이의 접속 및 통신을 구현하도록 구성되는 적어도 하나의 통신 버스(1903)를 포함한다. 프로세서(1902)는, 컴퓨터 프로그램과 같은, 메모리(1906)에 저장되는 실행 가능 모듈을 실행하도록 구성된다. 메모리(1906)는 고속 랜덤 액세스 메모리(RAM, Random Access Memory)를 포함할 수 있고, 적어도 하나의 자기 디스크 메모리와 같은 비-휘발성 메모리(non-volatile memory)를 추가로 포함할 수 있다. 적어도 하나의 다른 네트워크 엘리먼트와의 통신 접속은 (유선 또는 무선일 수 있는) 적어도 하나의 네트워크 인터페이스(1905)를 사용하여 구현된다.

일부 구현들에서, 메모리(1906)는 프로그램(19061)을 저장하고, 프로세서(1902)는 프로그램(19061)을 실행하여 본 발명의 전술한 실시예에 따른 데이터 쿼리 방법을 실행한다.

본 발명의 이러한 실시예에서 "및/또는(and/or)"이라는 용어는 연관된 오브젝트들을 설명하기 위한 연관 관계만을 설명하고 3개의 관계들이 존재할 수 있다는 것을 표현한다는 점이 이해되어야 한다. 예를 들어, A 및/또는 B는 이하의 3개의 경우들을 표현할 수 있다: A만 존재함, A와 B 양자 모두 존재함, 및 B만 존재함. 또한, 본 명세서에서 문자 "/"는 연관된 오브젝트들 사이의 "또는(or)" 관계를 일반적으로 표시한다.

해당 분야에서의 통상의 기술자는, 본 명세서에 개시되는 실시예들에서 설명되는 예들과 조합하여, 전자 하드웨어, 컴퓨터 소프트웨어, 또는 이들의 조합에 의해 유닛들 및 알고리즘 단계들이 구현될 수 있다는 점을 인지할 수 있다. 하드웨어와 소프트웨어 사이의 상호 교환 가능성을 명확하게 설명하기 위해, 전술한 내용은 기능들에 따라 각각의 예의 구성들 및 단계들을 일반적으로 설명했다. 기능들이 하드웨어 또는 소프트웨어에 의해 수행되는지는 기술적 해결책들의 특정 적용들 및 설계 제약 조건들에 의존한다. 해당 분야에서의 기술자는 각각의 특정 적용에 대해 설명되는 기능들을 구현하는데 상이한 방법들을 사용할 수 있지만, 이러한 구현이 본 발명의 범위를 벗어나는 것으로 고려되어서는 안 된다.

편리하고 간략한 설명의 목적으로, 전술한 시스템, 장치, 및 유닛의 상세한 작업 프로세스에 대해서는, 전술한 방법 실시예들에서의 대응하는 프로세스가 참조될 수 있다는 점이 해당 분야에서의 기술자에 의해 명확하게 이해될 수 있고, 상세 사항들은 여기서 다시 설명되지는 않는다.

본 출원에서 제공되는 몇몇 실시예들에서, 개시된 시스템, 장치, 및 방법은 다른 방식들로 구현될 수 있다는 점이 이해되어야 한다. 예를 들어, 설명되는 장치 실시예는 단지 예일 뿐이다. 예를 들어, 유닛 구분은 단지 논리적인 기능 구분일 뿐이고 실제 구현에서는 다른 구분일 수 있다. 예를 들어, 복수의 유닛들 또는 컴포넌트들이 조합되거나 다른 시스템에 통합될 수 있거나, 또는 일부 특징들이 무시되거나 수행되지 않을 수 있다. 또한, 디스플레이되거나 논의되는 상호 연결들 또는 직접 연결들 또는 통신 접속들은 일부 인터페이스들, 장치들과 유닛들 사이의 간접 연결들 또는 통신 접속들, 또는 전기적 접속들, 기계적 접속들, 또는 다른 형태들의 접속들을 통해 구현될 수 있다.

별개의 부분들로서 설명되는 유닛들은 물리적으로 별개일 수 있거나 그렇지 않을 수 있고, 유닛들로서 디스플레이되는 부분들은 물리적 유닛들일 수 있거나 그렇지 아닐 수 있고, 하나의 위치에 위치될 수 있거나, 또는 복수의 네트워크 유닛들 상에 분산될 수 있다. 이러한 유닛들의 일부 또는 전부는 본 발명의 실시예들의 해결책들의 목적들을 달성하기 위해 실제 필요에 따라 선택될 수 있다.

또한, 본 발명의 실시예들에서의 기능 유닛들은 하나의 처리 유닛에 통합될 수 있거나, 또는 이러한 유닛들 각각이 물리적으로 단독으로 존재할 수 있거나, 또는 2개 이상의 유닛들이 하나의 유닛에 통합된다. 이러한 통합 유닛은 하드웨어의 형태로 구현될 수 있거나, 또는 소프트웨어 기능 유닛의 형태로 구현될 수 있다.

집적 유닛들이 소프트웨어 기능 유닛의 형태로 구현되고 독립적 제품으로서 판매되거나 또는 사용될 때, 이러한 집적 유닛은 컴퓨터 판독 가능 저장 매체에 저장될 수 있다. 이러한 이해에 기초하여, 본질적으로 본 발명의 기술적 해결책들, 또는 종래 기술에 기여하는 부분, 또는 기술적 해결책들의 전부 또는 일부는 소프트웨어 제품의 형태로 구현될 수 있다. 이러한 소프트웨어 제품은 저장 매체에 저장되고, (개인용 컴퓨터, 서버, 또는 네트워크 디바이스일 수 있는) 컴퓨터 디바이스에게 본 발명의 실시예들에서 설명되는 방법들의 단계들의 전부 또는 일부를 수행하라고 명령하기 위한 여러 명령어들을 포함한다. 전술한 저장 매체는, USB 플래시 드라이브, 이동식 하드 디스크, 판독 전용 메모리(ROM, Read-Only Memory), 랜덤 액세스 메모리(RAM, Random Access Memory), 자기 디스크, 또는 광 디스크와 같은, 프로그램 코드를 저장할 수 있는 임의의 매체를 포함한다.

전술한 설명들은 단지 본 발명의 구체적인 실시예들일 뿐이고, 본 발명의 보호 범위를 제한하려고 의도되는 것은 아니다. 본 발명에 개시되는 기술적 범위 내에서 해당 분야에서의 기술자에 의해 용이하게 이해되는 임의의 수정 또는 대체는 본 발명의 보호 범위 내에 있을 것이다. 따라서, 본 발명의 보호 범위는 청구항들의 보호 범위에 따를 것이다.

Claims

데이터 쿼리 방법으로서,
상기 방법은 데이터베이스 시스템에 의해 실행되고, 이러한 데이터베이스 시스템은 컴퓨터 디바이스 상에서 실행되고, 상기 방법은,
데이터 쿼리 요청을 수신하는 단계;
상기 데이터 쿼리 요청에 따라 원본 쿼리 계획을 생성하는 단계 - 상기 원본 쿼리 계획은 데이터베이스에서 데이터를 획득하기 위해 상기 데이터 쿼리 요청을 파싱(parsing)함으로써 생성되는 쿼리 계획임 -;
상기 원본 쿼리 계획 내의 결합 술어를 재구성하는 단계 - 상기 결합 술어는 상기 데이터베이스 내의 2개 이상의 표 내의 컬럼들의 관계를 설명하는데 사용되고 상기 데이터베이스 내의 2개 이상의 표를 하나의 결과 표로 조합하는데 사용되는 술어임 -;
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 기본 정보를 결정하는 단계;
결합 연산 규칙에 기초하여, 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 제약 조건을 결정하는 단계 - 상기 제약 조건은 상기 결합 연산 규칙이 충족되지 않는 경우에 상기 원본 쿼리 계획 내의 재구성된 결합 술어에 추가되는 조건임 -;
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 단계 - 상기 등가 쿼리 계획은 연산 레벨 규칙들 또는 술어 레벨 규칙들을 사용하여 변환에 의해 상기 원본 쿼리 계획으로부터 획득되는 쿼리 계획임 -; 및
상기 원본 쿼리 계획에 대한 상기 등가 쿼리 계획에 따라 쿼리를 수행하는 단계
를 포함하는 방법.
제1항에 있어서,
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 단계는,
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획 세트를 결정하는 단계를 포함하고;
상기 원본 쿼리 계획에 대한 등가 쿼리 계획에 따라 쿼리를 수행하는 단계는,
상기 등가 쿼리 계획 세트로부터 쿼리 계획을 선택하여 쿼리를 수행하는 단계를 포함하는 방법.
제2항에 있어서,
상기 방법은,
상기 원본 쿼리 계획에 따라 후보 쿼리 계획 세트를 획득하는 단계를 추가로 포함하고;
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획 세트를 결정하는 단계는,
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 후보 쿼리 계획 세트로부터 상기 등가 쿼리 계획 세트를 결정하는 단계를 포함하는 방법.
제1항 내지 제3항 중 어느 한 항에 있어서,
상기 원본 쿼리 계획 내의 결합 술어를 재구성하는 단계는,
상기 원본 쿼리 계획 내의 내부 결합 연산의 모든 결합 술어들을 접속사 정규 형태로 변환하는 단계, 및 동일한 입력 표를 갖는 결합 술어들을 조합하는 단계; 및
상기 원본 쿼리 계획 내의 비-내부 결합 연산의 모든 결합 술어들을 하나의 결합 술어로 조합하는 단계를 포함하는 방법.
제1항에 있어서,
상기 결합 술어의 상기 기본 정보는 상기 결합 술어의 입력 표, 상기 결합 술어가 위치되는 결합 연산의 좌측 서브트리에 포함되는 상기 결합 술어의 입력 표, 상기 결합 술어가 위치되는 상기 결합 연산의 우측 서브트리에 포함되는 상기 결합 술어의 입력 표, 및 상기 결합 술어가 위치되는 상기 결합 연산의 결합 타입을 포함하는 방법.
제1항에 있어서,
상기 결합 연산 규칙은 연산 레벨 규칙 및 술어 레벨 규칙을 포함하고, 상기 연산 레벨 규칙은 연산 레벨 교환 규칙: e₁ o^a _p12 e₂ = e₂ o^a _p12 e₁, 연산 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p23 e₃ = e₁ o^a _p12 (e₂ o^b _p23 e₃), 연산 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13 e₃ = (e₁ o^b _p13 e₃) o^a _p12 e₂, 및 연산 레벨 우측 치환 규칙: e₁ o^a _p13 (e₂ o^b _p23 e₃) = e₂ o^b _p23(e₁ o^a _p13 e₃)을 포함하고, 상기 술어 레벨 규칙은 술어 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p∧p23 e₃ = e₁ o^a _p12∧p (e₂ o^b _p23 e₃), 술어 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13∧p e₃ = (e₁ o^b _p13 e₃) o^a _p12∧p e₂, 및 술어 레벨 우측 치환 규칙: e₁ o^a _p∧p13 (e₂ o^b _p23 e₃) = e₂ o^b _p∧p23 (e₁ o^a _p13 e₃)를 포함하고, e_i은 쿼리 표현이고, o^a 및 o^b는 결합 연산들이고, pij는 e_i와 e_j 사이의 결합 술어인 방법.
제6항에 있어서,
상기 결합 연산 규칙에 기초하여, 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 제약 조건을 결정하는 단계는,
상기 원본 쿼리 계획 내의 각각의 결합 연산 노드 o^B에 대해, o^B를 루트 노드로서 사용하는 서브트리에서의 각각의 결합 연산 노드 o^A를 횡단하는 단계; 및
o^B를 루트 노드로서 사용하는 서브트리의 좌측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제1 제약 조건을 추가하는 단계; 및 o^A 및 o^B가 연산 레벨 좌측 치환 규칙 및 술어 레벨 좌측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제2 제약 조건을 추가하는 단계; 또는
o^B를 루트 노드로서 사용하는 서브트리의 우측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제2 제약 조건을 추가하는 단계; 및 o^A 및 o^B가 연산 레벨 우측 치환 규칙 및 술어 레벨 우측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제1 제약 조건을 추가하는 단계를 포함하고;
상기 제1 제약 조건은 T(e₂)->T(e₁)∩T(p_a1∧p_a2∧...∧p_an)이고, 상기 제2 제약 조건은 T(e₁)->T(e₂)∩T(p_a1∧p_a2∧...∧p_an)이고, T(e₁) 는 o^A를 루트 노드로서 사용하는 서브트리의 좌측 서브트리 e₁에 포함되는 원본 입력 표를 표시하고, T(e₂) 는 o^A를 루트 노드로서 사용하는 서브트리의 우측 서브트리 e₂에 포함되는 원본 입력 표를 표시하고, T(p_a1∧p_a2∧...∧p_an)는 o^A 상에 재구성된 결합 술어 p_a1∧p_a2∧...∧p_an에 포함되는 원본 입력 표를 표시하고, T₁->T₂는 T₁->T₂에 의해 제약되는 결합 술어가 위치되는 결합 연산을 루트 노드로서 사용하는 제1 서브트리가 T₁에서의 임의의 입력 표를 포함하면, 상기 제1 서브트리가 T₂에서의 모든 입력 표들을 포함한다는 점을 표시하는 방법.
제1항에 있어서,
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 단계는,
제1 후보 쿼리 계획 P'는 P'가 이하의 조건들을 충족시키면 원본 쿼리 계획 P에 대한 등가 쿼리 계획이라고 결정하는 단계를 포함하는-
P'의 각각의 제1 결합 연산의 결합 타입은 내부 결합이고, 상기 제1 결합 연산은 적어도 2개의 재구성된 결합 술어들을 갖는 결합 연산이고, P에 있고 상기 적어도 2개의 재구성된 결합 술어들에서의 각각의 결합 술어에 대응하는 결합 연산의 결합 타입은 내부 결합임;
P'에서의 각각의 결합 연산 o^b' 상의 각각의 결합 술어 p에 대해,
o^b'가 연산 레벨 교환 규칙을 충족시키지 않을 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같음- T_l(p)는 p가 위치되는 결합 연산의 좌측 서브트리에 포함되는 p의 입력 표를 표시하고, T_r(p)는 p가 위치되는 결합 연산의 우측 서브트리에 포함되는 p의 입력 표를 표시함 -; 또는
o^b'가 연산 레벨 교환 규칙을 충족시킬 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같거나; 또는 P'에서의 T_l(p) 및 P에서의 T_r(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_l(p)은 같음; 및
P'에서의 각각의 결합 연산 o^b' 상의 각각의 결합 술어 p에 대해, p는 P에서의 p에 대한 제약 조건을 충족시킴 - 방법.
제2항에 있어서,
상기 등가 쿼리 계획 세트로부터 쿼리 계획을 선택하여 쿼리를 수행하는 단계는,
상기 등가 쿼리 계획 세트로부터 비용이 최소인 쿼리 계획을 선택하여 쿼리를 수행하는 단계를 포함하는 방법.
데이터 쿼리 장치로서,
데이터 쿼리 요청을 수신하도록 구성되는 수신 모듈;
상기 데이터 쿼리 요청에 따라 원본 쿼리 계획을 생성하도록 구성되는 생성 모듈 - 상기 원본 쿼리 계획은 데이터베이스에서 데이터를 획득하기 위해 상기 데이터 쿼리 요청을 파싱함으로써 생성되는 쿼리 계획임 -;
상기 원본 쿼리 계획 내의 결합 술어를 재구성하도록 구성되는 재구성 모듈 - 상기 결합 술어는 상기 데이터베이스 내의 2개 이상의 표 내의 컬럼들의 관계를 설명하는데 사용되고 상기 데이터베이스 내의 2개 이상의 표를 하나의 결과 표로 조합하는데 사용되는 술어임 -;
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 기본 정보를 결정하도록; 결합 연산 규칙에 기초하여, 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 제약 조건을 결정하도록 - 상기 제약 조건은 상기 결합 연산 규칙이 충족되지 않는 경우에 상기 원본 쿼리 계획 내의 재구성된 결합 술어에 추가되는 조건임 -; 그리고 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하도록 구성되는 결정 모듈 - 상기 등가 쿼리 계획은 연산 레벨 규칙들 또는 술어 레벨 규칙들을 사용하여 변환에 의해 상기 원본 쿼리 계획으로부터 획득되는 쿼리 계획임 -; 및
상기 원본 쿼리 계획에 대한 등가 쿼리 계획에 따라 쿼리를 수행하도록 구성되는 쿼리 모듈
을 포함하는 장치.
제10항에 있어서,
상기 결정 모듈은 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획 세트를 결정하도록 구체적으로 구성되고;
상기 쿼리 모듈은 상기 등가 쿼리 계획 세트로부터 쿼리 계획을 선택하여 쿼리를 수행하도록 구체적으로 구성되는 장치.
제11항에 있어서,
상기 장치는,
상기 원본 쿼리 계획에 따라 후보 쿼리 계획 세트를 획득하도록 구성되는 획득 모듈을 추가로 포함하고;
상기 결정 모듈은 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 후보 쿼리 계획 세트로부터 상기 등가 쿼리 계획 세트를 결정하도록 구체적으로 구성되는 장치.
제10항 내지 제12항 중 어느 한 항에 있어서,
상기 재구성 모듈은 구체적으로,
상기 원본 쿼리 계획 내의 내부 결합 연산의 모든 결합 술어들을 접속사 정규 형태로 변환하도록, 그리고 동일한 입력 표를 갖는 결합 술어들을 조합하도록; 그리고
상기 원본 쿼리 계획 내의 비-내부 결합 연산의 모든 결합 술어들을 하나의 결합 술어로 조합하도록 구성되는 장치.
제10항에 있어서,
상기 결합 술어의 기본 정보는 상기 결합 술어의 입력 표, 상기 결합 술어가 위치되는 결합 연산의 좌측 서브트리에 포함되는 상기 결합 술어의 입력 표, 상기 결합 술어가 위치되는 상기 결합 연산의 우측 서브트리에 포함되는 상기 결합 술어의 입력 표, 및 상기 결합 술어가 위치되는 상기 결합 연산의 결합 타입을 포함하는 장치.
제10항에 있어서,
상기 결합 연산 규칙은 연산 레벨 규칙 및 술어 레벨 규칙을 포함하고, 상기 연산 레벨 규칙은 연산 레벨 교환 규칙: e₁ o^a _p12 e₂ = e₂ o^a _p12 e₁, 연산 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p23 e₃ = e₁ o^a _p12 (e₂ o^b _p23 e₃), 연산 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13 e₃ = (e₁ o^b _p13 e₃) o^a _p12 e₂, 및 연산 레벨 우측 치환 규칙: e₁ o^a _p13 (e₂ o^b _p23 e₃) = e₂ o^b _p23(e₁ o^a _p13 e₃)을 포함하고, 상기 술어 레벨 규칙은 술어 레벨 조합 규칙: (e₁ o^a _p12 e₂) o^b _p∧p23 e₃ = e₁ o^a _p12∧p (e₂ o^b _p23 e₃), 술어 레벨 좌측 치환 규칙: (e₁ o^a _p12 e₂) o^b _p13∧p e₃ = (e₁ o^b _p13 e₃) o^a _p12∧p e₂, 및 술어 레벨 우측 치환 규칙: e₁ o^a _p∧p13 (e₂ o^b _p23 e₃) = e₂ o^b _p∧p23 (e₁ o^a _p13 e₃)를 포함하고, e_i은 쿼리 표현이고, o^a 및 o^b는 결합 연산들이고, pij는 e_i와 e_j 사이의 결합 술어인 장치.
제15항에 있어서,
상기 결정 모듈은 구체적으로,
상기 원본 쿼리 계획 내의 각각의 결합 연산 노드 o^B에 대해, o^B를 루트 노드로서 사용하는 서브트리에서의 각각의 결합 연산 노드 o^A를 횡단하도록; 그리고
o^B를 루트 노드로서 사용하는 서브트리의 좌측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제1 제약 조건을 추가하도록; 그리고 o^A 및 o^B가 연산 레벨 좌측 치환 규칙 및 술어 레벨 좌측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제2 제약 조건을 추가하도록; 또는
o^B를 루트 노드로서 사용하는 서브트리의 우측 서브트리에 o^A가 있을 때, o^A 및 o^B가 연산 레벨 조합 규칙 및 술어 레벨 조합 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제2 제약 조건을 추가하도록; 그리고 o^A 및 o^B가 연산 레벨 우측 치환 규칙 및 술어 레벨 우측 치환 규칙을 충족시키지 않으면, o^B 상에 각각 재구성된 결합 술어에 제1 제약 조건을 추가하도록 구성되고;
상기 제1 제약 조건은 T(e₂)->T(e₁)∩T(p_a1∧p_a2∧...∧p_an)이고, 상기 제2 제약 조건은 T(e₁)->T(e₂)∩T(p_a1∧p_a2∧...∧p_an)이고, T(e₁) 는 o^A를 루트 노드로서 사용하는 서브트리의 좌측 서브트리 e₁에 포함되는 원본 입력 표를 표시하고, T(e₂) 는 o^A를 루트 노드로서 사용하는 서브트리의 우측 서브트리 e₂에 포함되는 원본 입력 표를 표시하고, T(p_a1∧p_a2∧...∧p_an)는 o^A 상에 재구성된 결합 술어 p_a1∧p_a2∧...∧p_an에 포함되는 원본 입력 표를 표시하고, T₁->T₂는 T₁->T₂에 의해 제약되는 결합 술어가 위치되는 결합 연산을 루트 노드로서 사용하는 제1 서브트리가 T₁에서의 임의의 입력 표를 포함하면, 상기 제1 서브트리가 T₂에서의 모든 입력 표들을 포함한다는 점을 표시하는 장치.
제10항에 있어서,
상기 결정 모듈은 구체적으로,
제1 후보 쿼리 계획 P'는 P'가 이하의 조건들을 충족시키면 원본 쿼리 계획 P에 대한 등가 쿼리 계획이라고 결정하도록 구성되는-
P'의 각각의 제1 결합 연산의 결합 타입은 내부 결합이고, 상기 제1 결합 연산은 적어도 2개의 재구성된 결합 술어들을 갖는 결합 연산이고, P에 있고 상기 적어도 2개의 재구성된 결합 술어들에서의 각각의 결합 술어에 대응하는 결합 연산의 결합 타입은 내부 결합임;
P'에서의 각각의 결합 연산 o^b' 상의 각각의 결합 술어 p에 대해,
o^b'가 연산 레벨 교환 규칙을 충족시키지 않을 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같음- T_l(p)는 p가 위치되는 결합 연산의 좌측 서브트리에 포함되는 p의 입력 표를 표시하고, T_r(p)는 p가 위치되는 결합 연산의 우측 서브트리에 포함되는 p의 입력 표를 표시함 -; 또는
o^b'가 연산 레벨 교환 규칙을 충족시킬 때, P'에서의 T_l(p) 및 P에서의 T_l(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_r(p)은 같거나; 또는 P'에서의 T_l(p) 및 P에서의 T_r(p)은 같고, P'에서의 T_r(p) 및 P에서의 T_l(p)은 같음; 및
P'에서의 각각의 결합 연산 o^b' 상의 각각의 결합 술어 p에 대해, p는 P에서의 p에 대한 제약 조건을 충족시킴 - 장치.
제11항에 있어서,
상기 쿼리 모듈은 구체적으로,
상기 등가 쿼리 계획 세트로부터 비용이 최소인 쿼리 계획을 선택하여 쿼리를 수행하도록 구성되는 장치.
데이터베이스 시스템으로서,
제10항에 따른 데이터 쿼리 장치 및 데이터베이스를 포함하는 데이터베이스 시스템.
프로그램이 기록되는 컴퓨터 판독 가능 기록 매체로서,
상기 프로그램은, 실행될 때, 컴퓨터로 하여금,
데이터 쿼리 요청을 수신하는 단계;
상기 데이터 쿼리 요청에 따라 원본 쿼리 계획을 생성하는 단계 - 상기 원본 쿼리 계획은 데이터베이스에서 데이터를 획득하기 위해 상기 데이터 쿼리 요청을 파싱함으로써 생성되는 쿼리 계획임 -;
상기 원본 쿼리 계획 내의 결합 술어를 재구성하는 단계 - 상기 결합 술어는 상기 데이터베이스 내의 2개 이상의 표 내의 컬럼들의 관계를 설명하는데 사용되고 상기 데이터베이스 내의 2개 이상의 표를 하나의 결과 표로 조합하는데 사용되는 술어임 -;
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 기본 정보를 결정하는 단계;
결합 연산 규칙에 기초하여, 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 제약 조건을 결정하는 단계 - 상기 제약 조건은 상기 결합 연산 규칙이 충족되지 않는 경우에 상기 원본 쿼리 계획 내의 재구성된 결합 술어에 추가되는 조건임 -;
상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 기본 정보 및 상기 원본 쿼리 계획 내의 재구성된 결합 술어의 상기 제약 조건에 따라 상기 원본 쿼리 계획에 대한 등가 쿼리 계획을 결정하는 단계 - 상기 등가 쿼리 계획은 연산 레벨 규칙들 또는 술어 레벨 규칙들을 사용하여 변환에 의해 상기 원본 쿼리 계획으로부터 획득되는 쿼리 계획임 -; 및
상기 원본 쿼리 계획에 대한 상기 등가 쿼리 계획에 따라 쿼리를 수행하는 단계
를 실행할 수 있게 하는 컴퓨터 판독 가능 기록 매체.