XML(Extensible Markup Language)은 인터넷의 급속한 발전, 특히 전자 상거래, 웹 서비스 및 기타 응용 프로그램의 광범위한 사용으로 인해 웹 응용 프로그램의 데이터 표현 및 데이터 교환을 위한 표준이 되었습니다. 주류 데이터 형식. 따라서 XML 데이터 관리 기술, 특히 XML 데이터 쿼리 기술은 현재 연구 핫스팟이 되었습니다.
관계형 데이터와 비교하여 XML은 다양한 장점을 가지고 있지만 가장 큰 단점은 효율성입니다. 관계형 데이터 파일에서는 데이터 필드 이름이 한 번만 나타나야 하지만 XML 데이터 파일에서는 요소 이름이 반복적으로 나타나므로 쿼리 효율성에 확실히 영향을 미칩니다. XML의 쿼리 효율성을 최대한 높이기 위해서는 XML 유형에 대한 인덱싱 기능을 제공해야 합니다.
World Wide Web 컨소시엄은 2007년 1월 23일 XPath 2.0과 XQuery 1.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 트리 구조에 있는 노드의 경로 정보를 기반으로 하며, 축소된 트리 구조는 다른 경로 정보만 유지하고 존재하지 않도록 특정 축소 방식을 채택합니다. 같은 길. 제안된 인덱스에는 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 트리에 삽입하여 XML 데이터의 쿼리를 문자열 쿼리에 대한 경로입니다. 쿼리할 때 먼저 쿼리 경로를 문자열 형식으로 인코딩한 후 인덱스 트리에서 검색합니다. Index Fabric 인덱스의 장점은 XML 데이터의 계층적 구조 정보를 저장하고, 스키마 및 스키마 없는 정보로 XML 데이터 검색을 일률적으로 처리하며, 계층과 관련된 XML 데이터를 질의하고 업데이트하는 데 필요한 시간을 보다 효율적으로 만들어준다는 점입니다. 인덱스 키의 길이는 관련이 있습니다. Index Fabric 인덱스의 단점은 요소 노드의 정보만 텍스트 값으로 유지하기 때문에 요소 노드 간의 구조적 관계가 손실된다는 점입니다. 따라서 DataGuides 인덱스와 유사하게 Index Fabric 인덱스는 XPath 표준에 정의된 하위 또는 자체 축을 사용하여 부분적으로 일치하는 쿼리 표현식을 처리하는 데 효율적이지 않습니다.
이를 위해 APEX [14]에서는 XML 데이터 분포에 의존하는 정보를 도입했습니다. query : 자주 발생하는 XML 쿼리문에 해당하는 레이블 노드를 해시 구조에 미리 저장합니다. 그 기능은 캐시의 기능과 유사합니다. 새 쿼리에 처리가 필요할 때 먼저 해시 테이블을 검색하여 만족스러운 노드 세트가 있는지 확인합니다. 하지만 요소 값이나 속성 값이 포함된 쿼리 표현식의 경우 효율성이 떨어집니다.
노드 기반 인덱스
노드 기반 인덱스는 기본적으로 XML 데이터를 데이터 단위의 레코드 세트로 분해하는 동시에 해당 단위의 위치 정보를 XML 데이터에 저장합니다. 경로 기반 인덱스와 달리 노드 기반 인덱스는 레이블 경로를 통해 노드를 찾아야 한다는 제한을 깨고 XML 데이터를 정식 형식의 노드 레코드로 분해합니다. 노드의 위치 정보를 저장하고 성숙한 관계형 데이터베이스 관리 시스템에 잘 통합될 수 있기 때문에 현재 가장 널리 사용되는 색인입니다.
위치 정보의 다양한 인코딩 방식에 따라 노드 기반 인덱스는 일반적으로 다음과 같은 범주로 나눌 수 있습니다.
1.
접두사 기반 인덱스는 주로 Dewey [12] 인코딩과 ORDPATH 인코딩을 기반으로 생성된 인덱스입니다. 유사한 방법을 채택하여 SQL Server 2005의 인덱스 구성에 적용된 ORDPATH를 압축하는 방법을 제시하고 있다.
접두사 코딩의 기본 아이디어는 노드의 부모 노드의 코딩을 노드 코딩의 접두사로 직접 사용하는 것입니다. 접두사 코딩의 경우 노드 v가 다른 노드 u의 자손인지 확인하기만 하면 됩니다. u의 코딩이 v 코딩의 접두어인지 여부. 접두사 코딩 인덱스의 중요한 속성은 사전 순서입니다. 노드 r에 뿌리를 둔 하위 트리의 모든 노드 u에 대해 접두사 코딩 c(u)는 왼쪽 형제 하위 트리(오른쪽 형제 하위 트리)보다 큽니다(작음). 에 있는 모든 노드의 . 따라서 접두사 기반 인덱스는 포함 관계 계산을 효과적으로 지원할 수 있을 뿐만 아니라 문서 위치 관계 계산도 효과적으로 지원할 수 있습니다.
2. 간격 코딩 기반 인덱스
간격 코딩 인덱스의 경우 트리 T의 각 노드에는 간격 코드 [시작, 끝]가 할당되며, 이는 노드의 간격 코드가 해당 하위 노드의 간격 코드를 포함한다는 것입니다. 즉, 트리 T의 노드 u는 노드 v의 조상입니다.
start(u)의 첫 번째 간격 인코딩 체계가 디츠 인코딩인 경우에만 트리 T의 각 노드에는 선순 순회 시퀀스 번호가 할당되고 사후- 순서 순회 시퀀스 번호 튜플 트리 T의 조상 노드 u는 선순 순회(후순 순회)에서 해당 하위 노드 v 이전(뒤)에 나타나야 하므로 노드 u와 v는 상위/하위 관계입니다. , if and only if pre(u)
간격 인코딩 인덱스의 또 다른 일반적인 예는 각 노드에 숫자 쌍을 할당하는 XISS 인덱스입니다. 여기서 순서는 확장된 사전 순서 인코딩이고 크기는 노드 범위의 하위 항목입니다. 문서 트리의 모든 노드 X 및 Y에 대해 order(x)
XISS 인덱스가 원래 쿼리 문을 하위 표현식으로 분해하는 경우에만 해당됩니다. 그런 다음 이러한 하위 표현식에 대한 쿼리를 각각 구현하고 마지막으로 이러한 중간 결과를 결합하여 쿼리 결과 집합을 얻습니다. 이는 와일드카드 문자가 포함된 쿼리 문을 더 효과적으로 지원할 수 있습니다. 그러나 각 중간 결과를 연결한 후 최종 쿼리 결과를 얻습니다. 이러한 방법으로 실제로 모든 와일드카드 문제를 해결할 수 있지만 중간 결과를 연결하는 데 시간이 많이 걸릴 수 있으며, 특히 긴 경로가 있는 간단한 표현식의 경우 더욱 그렇습니다.
두 가지 인덱싱 메커니즘 비교
경로 기반 인덱싱은 주로 노드 병합 전략을 기반으로 하며 노드 동등성 및 경로 동등성 등의 기술을 통해 원래 문서보다 훨씬 작은 인덱스 구조를 얻습니다. , 따라서 쿼리를 처리할 때 결과를 얻으려면 기본적으로 전체 인덱스 트리를 탐색해야 합니다. 경로 기반 인덱스는 단순 경로 표현식 쿼리를 매우 잘 지원할 수 있지만 일반 경로 표현식의 경우에는 잘 작동하지 않습니다.
노드 기반 인덱스는 인코딩 기술을 통해 각 노드를 색인화하며, 인코딩을 통해 일정한 시간 내에 노드 간의 구조적 관계를 파악할 수 있습니다. 일반 경로 표현을 잘 지원할 수 있지만, 긴 경로 표현의 경우, 특히 쿼리 생성 시에는 더욱 그렇습니다. 노드 인덱스의 조인 작업은 비용이 많이 듭니다.
경로 기반 인덱싱과 노드 기반 인덱싱은 각각 장점과 단점이 있지만 서로를 보완할 수 있습니다. 현재 실제 응용 분야에서는 노드 기반 인덱싱이 더 널리 사용되고 있으며 연구가 상대적으로 성숙되어 있습니다. 따라서 Dameng Company의 XML 인덱스 구조에 대한 연구는 주로 노드 기반 인덱싱에 중점을 두고 있으며 경로 기반 인덱싱을 참조하여 적절하게 개선하고 있습니다. .