관계형 데이터베이스 엔진 기반의 'XML' 인덱스 기술

XML(Extensible Markup Language)은 인터넷의 급속한 발전, 특히 전자상거래, 웹 서비스 및 기타 애플리케이션의 광범위한 사용으로 인해 웹 애플리케이션의 데이터 표현 및 데이터 교환을 위한 표준이 되었습니다. 현재의 주류 데이터 형식이 됩니다. 따라서 XML 데이터 관리 기술, 특히 XML 데이터 쿼리 기술은 현재 연구 핫스팟이 되었습니다.

관계형 데이터에 비해 XML은 다양한 장점을 갖고 있지만 가장 큰 단점은 효율성이다. 관계형 데이터 파일에서는 데이터 필드 이름이 한 번만 나타나야 하지만 XML 데이터 파일에서는 요소 이름이 반복적으로 나타나므로 쿼리 효율성에 확실히 영향을 미칩니다. XML의 쿼리 효율성을 최대한 높이기 위해서는 XML 유형에 대한 인덱싱 기능을 제공해야 합니다.

World Wide Web 컨소시엄은 2007년 1월 23일 XPath2.0과 XQuery1.0을 권장 표준으로 확정하여 다양한 쿼리 언어 간의 이전 경쟁을 종료했습니다. 이 표준을 기반으로 기존 제조업체 외에도 다양한 과학 연구 기관에서 다양한 저장 모델, 다양한 쿼리 알고리즘 및 최적화 방법을 사용하여 XPath 및 XQuery(문헌에 12개 이상 언급됨) 구현을 제안했습니다. 이러한 맥락에서 Dameng Database Company는 자체 개발 전략을 기반으로 자체 XML 쿼리 엔진 모델을 제안했으며 현재 Dameng의 XML 쿼리 엔진은 집중적으로 개발되고 있으며 XML 데이터에 대한 효과적인 인덱스를 설정하는 것은 XML에 영향을 미치는 중요한 요소입니다. 데이터 쿼리 성능. 기존 데이터베이스 제품의 인덱싱 기술에 대한 심층적인 분석을 바탕으로 Dameng XML 쿼리 엔진에 대해 보다 합리적인 인덱스 구조를 설계하여 엔진이 최적의 성능을 발휘할 수 있도록 합니다.

XML 인덱싱 기술 소개

현재 XML에 대한 사람들의 연구는 크게 두 가지 측면으로 나누어진다. 하나는 XML과 같은 반구조화된 데이터의 저장, 쿼리 및 관리를 위한 기본 데이터베이스입니다. 데이터와 메타데이터는 완전히 XML 구조로 표현되며 기본 데이터 저장 형식(예: 개체 모델, 관계형 모델)과 관련이 없습니다. , 등.). 다른 하나는 XML 데이터를 처리하기 위해 관계형 데이터베이스의 성숙한 기술을 사용하여 관계형 데이터베이스와 상호 변환하는 것입니다. 후자의 방향이 더 실용적인 의미를 갖기 때문에 XML 연구의 초점이 되었습니다.

스토리지 솔루션과 더불어 인덱스 기술 역시 데이터베이스 시스템을 결정하는 가장 중요한 요소 중 하나입니다. XML 문서에 대한 인덱스 구조가 구축되지 않은 경우 XML 데이터에 대한 쿼리로 인해 전체 문서 트리를 통과하게 될 가능성이 크며, 이 오버헤드는 허용할 수 없습니다. 따라서 XML 인덱스 기술에 대한 연구는 이론적, 실무적 가치가 높다.

전통적인 인덱싱 기술은 장기간 축적된 후 상대적으로 성숙해졌지만, 이러한 유형의 인덱싱 기술은 주로 (특정 관계가 있는 패턴이 아닌) 값을 기반으로 데이터 레코드를 찾는 기능에 중점을 두고 있으며, 데이터 레코드 간의 논리적 관계에 크게 신경 쓰지 않는 경우, XML 데이터 쿼리의 기본 기능은 패턴 특징(정규 경로 표현 형식으로 설명된 구조적 관계)의 입력을 기반으로 패턴에 맞는 데이터를 추출하는 것입니다. XML 인덱스의 주요 내용은 매칭 기술에 적합한 패턴을 디자인하는 것입니다.

XML 인덱스 분류

경로 기반 XML 인덱스

경로 기반 인덱스는 XML 트리 구조에 있는 노드의 경로 정보를 기반으로 특정 축소 방식을 채택합니다. 축소된 트리 구조는 서로 다른 경로 정보만 유지하며 동일한 경로를 갖는 두 개의 노드는 없습니다. 제안된 인덱스로는 DataGuides 인덱스, Index Fabric 인덱스, APEX(Adaptive Path Index for XML Data)가 있습니다.

Dataguides 인덱스는 루트 노드에서 시작하는 구체화입니다. 에지 레이블을 연결하여 형성된 문자열 경로는 데이터 가이드에서 한 번만 설명됩니다. 데이터 가이드는 경로 쿼리를 순회할 때 필요한 노드 수를 줄이고 루트에서 XML 문서를 순회하는 데 효율적입니다. 그러나 와일드카드 문자가 포함된 경로 쿼리나 XPath 표준에 정의된 하위 또는 자체 축이 있는 경로 쿼리에는 여러 연결 작업이 필요하므로 쿼리 효율성과 데이터 중복성이 낮습니다.

그런 다음 이 두 개의 큰 필드에 대해 Java 개체 파일 TestLob.java를 작성하고 유형을 CLOB로 정의하고 BLOB 속성 필드를 각각 String 및 byte[]로 정의합니다. CLOB는 큰 텍스트 유형이므로 다음에 해당합니다. Java에서는 String 유형을 사용합니다. BLOB는 엄격하게 정의되지 않고 바이너리 스트림 형식으로 저장되는 일부 대용량 파일을 처리하므로 byte[] 유형을 사용하도록 한 다음 이 두 속성의 Getter 및 Setter 메서드를 정의합니다. 해당 코드는 각각 다음과 같습니다.

Dataguides 인덱스는 루트 노드에서 시작하여 정제된 경로의 구조적 요약입니다. 에지 레이블을 연결하여 형성된 문자열 경로는 데이터 가이드에서 한 번만 설명됩니다. 데이터 가이드는 경로 쿼리를 순회할 때 필요한 노드 수를 줄이고 루트에서 XML 문서를 순회하는 데 효율적입니다. 그러나 와일드카드 문자가 포함된 경로 쿼리나 XPath 표준에 정의된 하위 또는 자체 축이 있는 경로 쿼리에는 여러 연결 작업이 필요하므로 쿼리 효율성과 데이터 중복성이 낮습니다.

Index Fabric은 Patricia Trie 트리에서 개발된 인덱스 구조로 각 요소 노드에 대한 각 마크 경로를 문자열로 인코딩한 후 이러한 인코딩된 값을 Patricia Trie Go에 삽입하여 쿼리를 변환합니다. 문자열 쿼리에 대한 경로에 따른 XML 데이터입니다. 쿼리할 때 먼저 쿼리 경로를 문자열 형식으로 인코딩한 후 인덱스 트리에서 검색합니다. Index Fabric 인덱스의 장점은 XML 데이터의 계층적 구조 정보를 저장하고, 스키마 및 스키마 없는 정보로 XML 데이터 검색을 일률적으로 처리하며, 계층과 관련된 XML 데이터를 질의하고 업데이트하는 데 필요한 시간을 보다 효율적으로 만들어준다는 점입니다. 인덱스 키의 길이는 관련이 있습니다. Index Fabric 인덱스의 단점은 요소 노드의 정보만 텍스트 값으로 유지하기 때문에 요소 노드 간의 구조적 관계가 손실된다는 점입니다. 따라서 DataGuides 인덱스와 유사하게 Index Fabric 인덱스는 XPath 표준

에 정의된 하위 또는 자체 축을 사용하여 부분 일치 쿼리 표현식을 처리하는 데 효율적이지 않습니다. 이러한 이유로 APEX [14]에서는 종속성 XML을 도입했습니다. 데이터 쿼리 분포 정보: 자주 발생하는 XML 쿼리문에 해당하는 레이블 노드를 해시 구조로 미리 저장합니다. 그 기능은 캐시의 기능과 유사합니다. 새 쿼리에 처리가 필요할 때 먼저 해시 테이블을 검색하여 만족스러운 노드 세트가 있는지 확인합니다. 하지만 요소 값이나 속성 값이 포함된 쿼리 표현식의 경우 효율성이 떨어집니다.

노드 기반 인덱스

노드 기반 인덱스는 기본적으로 XML 데이터를 데이터 단위의 레코드 세트로 분해하는 동시에 해당 단위의 위치 정보를 XML 데이터에 저장합니다. 기록. 경로 기반 인덱스와 달리 노드 기반 인덱스는 레이블 경로를 통해 노드를 찾아야 한다는 제한을 깨고 XML 데이터를 정식 형식의 노드 레코드로 분해합니다. 노드의 위치 정보를 저장하고 성숙한 관계형 데이터베이스 관리 시스템에 잘 통합될 수 있기 때문에 현재 가장 널리 사용되는 색인입니다.

위치 정보의 인코딩 방식에 따라 노드 기반 색인은 일반적으로 다음과 같은 범주로 나눌 수 있습니다.

1. 접두사 기반 색인

접두사 기반 색인 주로 Dewey[12] 인코딩을 기반으로 생성된 인덱스이며 문헌[13]의 ORDPATH 인코딩도 유사한 방법을 사용하며, ORDPATH를 압축하는 방법을 제공하며 이 방법은 SQL Server의 인덱스 구성에 적용되었다. 2005.

접두사 인코딩의 기본 아이디어는 노드의 상위 노드의 인코딩을 노드 인코딩의 접두사로 직접 사용하여 노드 v가 노드의 자손인지 확인하는 것입니다. 다른 노드 u를 결정하세요. u의 인코딩은 v 인코딩의 접두어입니다. 접두사 코딩 인덱스의 중요한 속성은 사전 순서입니다. 노드 r에 뿌리를 둔 하위 트리의 모든 노드 u에 대해 접두사 코딩 c(u)는 왼쪽 형제 하위 트리(오른쪽 형제 하위 트리)보다 큽니다(작음). 에 있는 모든 노드의 . 따라서 접두사 기반 인덱스는 포함 관계 계산을 효과적으로 지원할 수 있을 뿐만 아니라 문서 위치 관계 계산도 효과적으로 지원할 수 있습니다.

2. 간격 코딩 기반 인덱스

간격 코딩 인덱스의 경우 트리 T의 각 노드에는 다음을 충족하는 간격 코딩 [시작, 끝]이 할당됩니다. 인코딩에는 하위 노드의 간격 인코딩이 포함됩니다. 즉, start(u)

첫 번째 간격 인코딩 체계가 Dietz 인코딩인 경우에만 트리 T의 노드 u가 노드 v의 조상입니다. 트리 T에는 선순 순회 번호와 후순 순회 번호가 있는 튜플이 할당됩니다. 트리 T의 조상 노드 u는 선순 ​​순회(후순 순회)에 나타나야 하므로 그 하위 노드 v는 다음과 같습니다. 따라서 이전(이후), 노드 u와 v는 조상/하위 관계입니다. PRe(u)

간격 인코딩 인덱스의 또 다른 일반적인 예는 XISS 인덱스입니다. 이는 각각에 숫자 쌍을 할당합니다. 여기서 order는 확장된 사전 주문 코드이고 size는 노드의 하위 항목 범위입니다. 문서 트리의 모든 노드 X 및 Y에 대해 order(x)

XISS 인덱스가 원래 쿼리 문을 하위 표현식으로 분해하는 경우에만 해당됩니다. 그런 다음 이러한 하위 표현식에 대한 쿼리를 각각 구현하고 마지막으로 이러한 중간 결과를 결합하여 쿼리 결과 집합을 얻습니다. 이는 와일드카드 문자가 포함된 쿼리 문을 더 효과적으로 지원할 수 있습니다. 그러나 각 중간 결과를 연결한 후 최종 쿼리 결과를 얻습니다. 이러한 방법으로 실제로 모든 와일드카드 문제를 해결할 수 있지만 중간 결과를 연결하는 데 시간이 많이 걸릴 수 있으며, 특히 긴 경로가 있는 간단한 표현식의 경우 더욱 그렇습니다.

두 가지 인덱싱 메커니즘 비교

경로 기반 인덱싱은 주로 노드 병합 전략을 기반으로 하며 노드 동등성, 경로 동등성 등의 기술을 통해 원본보다 훨씬 작은 인덱스 구조를 갖습니다. 문서를 가져오더라도 해당 구조는 여전히 트리이므로 쿼리를 처리할 때 기본적으로 결과를 얻으려면 전체 인덱스 트리를 탐색해야 합니다. 경로 기반 인덱스는 단순 경로 표현식 쿼리를 매우 잘 지원할 수 있지만 일반 경로 표현식의 경우에는 잘 작동하지 않습니다.

노드 기반 인덱스는 인코딩 기술을 통해 각 노드를 인덱스합니다. 인코딩을 통해 노드 간의 구조적 관계를 일정한 시간에 확인할 수 있습니다. 일반 경로 표현식을 잘 지원할 수 있지만, 특히 쿼리가 생성될 때 긴 경로 표현식의 경우 더욱 그렇습니다. 중간 결과가 많으면 노드 인덱스의 조인 작업에 비용이 많이 듭니다.

경로 기반 인덱싱과 노드 기반 인덱싱은 각각 장점과 단점이 있지만 서로를 보완할 수 있습니다. 현재 실제 응용 분야에서는 노드 기반 인덱싱이 더 널리 사용되고 있으며 연구가 상대적으로 성숙되어 있습니다. 따라서 Dameng Company의 XML 인덱스 구조에 대한 연구는 주로 노드 기반 인덱싱에 중점을 두고 있으며 경로 기반 인덱싱을 참조하여 적절하게 개선하고 있습니다. .

위 내용은 관계형 데이터베이스 엔진 기반의 "XML" 인덱싱 기술에 대한 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!