Finding Matches for Keyword Search

query에서 specify된 keyword를 {K1, K2, ..., Kk}로 놓는다

Keyword search는 3개의 단계를 가진다

1. query의 keyword를 하나라도 포함하는 DB table을(columns와 cells) identify하기 위해서 symbol table이 검색된다(생성된 SQL을 통하여)
2. join trees를 열거하고
3. match하는 row를 identify(확인, 감정, 식별) 한다

 

 2번과정을 상세히 보면

이 단계는 모든 symbol table granularity(시스템의 세분화 정도)와 유사하다

query keyword를 하나라도 포함하는 DB tables의 set을 MachedTables로 놓자

만약, schema graph G를 undirected graph로 본다면, 이 단계는 join trees를 열거한다.

즉, G의 sub-tree

(a) leaves(단말노드) belong to(부속하다) MatchedTables

(b) together, the leaves contain all keywords of the query

그러므로, 만약 join tree에서 발생한 tables을 join하면 결과 relation은 모든 potential rows(query에서 specify된 모든 keywords를 가진)를 포함할 것이다

이 단계는 검색의 다음 단계로 전달될 data의 많은 쓸모없는 join scenarios를 제거할 것이다

 

예를 들면, 5개 table을 포함하는 그림 4의 schema graph G를 보자

 

 

query keywords를 { K1, K2, K3 }로 놓자. 검은색 node는 MatchedTables set을 나타낸다

K1, K2, K3가 모두 T2의 다른 columns에서 발생한다고 가정하자

K2는 T4, K3는 T5에서 발생한다고 가정하자

이 가정하에 가능한 4개의 join tree는 우측의 그림과 같다.

여기서, T2 혼자서도 join tree가 가능한 반면 { T4, T3, T5 }에서 유도되는 tree는 join tree가 될 수 없다.

왜냐하면, 이 tables는 모든 keywords를 포함하지 않기 때문이다.

 

이것은 join tree를 열거하는 알고리즘을 요약한 것이다. 단순한 exposition(전시, 진열, 보여주기)을 위해 G자신이 tree라고 가정했다

먼저, 반복적으로 white 단말노드(leaves)를 제거하며 모든 단말노드가 black으로 될때까지 G를 pruning한다

(이것은 universal relations에서 window functions를 computing하는 ear removal operation과 유사하다)

결과 tree G'는 모든 matching join tree를 잠재적으로 포함한다

 

 다음 단계는 G'의 모든 qualifying(후보) sub-trees를 열거한다. 즉, sub-trees such that all keywords in the query occur among the black nodes of the sub-tree.

효율성을 위하여 추천되는 후보 sub-trees의 first-node 선택에 다음과 같은 heuristic을 적용한다

G'에서 fewest black node 에서 발생하는 keyword를 선택한다.(We pick the keyword that occurs in the fewest black nodes of G')

이제 앞에서 indentify된 각각의 black node에서 G'의 모든 sub-trees에 breath-first 열거를 실행한다 그리고 그것이 qualifying sub-tree인지 검사한다

이 heuristic의 이용은 열거되는 trees의 수를 상당히 감소시킨다

만약, G가 tree라고 가정할 수 없다면(즉, cycle을 가진다면), join tree 열거는 G의 bi-connected component decomposition(상당한 정신적 스트레스가 가중될 문서ㅡㅡ;)을 필요로 한다.

 

 

 

Undirected graph

: Edge(변)이 방향을 가지지 않고 두 개의 꼭지점을 연결하는 graph

• 단순 그래프(simple graph)

꼭지점 집합 V와 변의 집합인 E로 이루어지는 단순 그래프 는 두 개의 꼭지점 과 사이에 최대한 한 개의 변만을 허용하고 각 변은 서로 다른 두 꼭지점에 접하여야 하는 무향그래프이다.

(예) 가 단순그래프이고, , 일 때, 라면, 이다.

• 다중 그래프(multigraph)

다중 그래프는 단순 그래프와 비슷하지만, 두 개의 꼭지점 사이에 여러 개의 변이 있을 수 있다.

(예) , ,

 

Directed graph

• 유향 그래프(directed graph)

유향 그래프는 변이 방향성을 지닌다.

(예)일 때, 이다.

• 유향다중 그래프(directed multigraph)

다중 그래프와 같이, 유향다중 그래프는 동일한 두 개의 꼭지점을 잇는 변이 여러 개 있을 수 있다.

 

 

leaf(leaves): tree의 마지막 노드

 

DB table: columns + rows

columns: property?

rows: instance?

 

Granularity

시스템의 세분화 정도, 세분화 정도가 클 수록 선택 할 수 있는 증분(세분화 된 값) 크기가 더 작아져 증분 수가 늘어나기 때문에 시스템 사용자 정의에 더 유연해 진다

 

Join Tree

전통적으로 join tree는 주어진 query를 위해 query optimizer에 의해 결정되는 join operation의 ordering을 나타낸다

하지만 여기서는 schema(where edges depict key foreign key relationship)의 subgraph의 종류를 나타낸다

이 글은 스프링노트에서 작성되었습니다.