그래프는 실세계의 많은 문제를 효과적으로 모델링하여 해를 구할 수 있는 강력한 방법을 제공하기 때문에 그래프의 표현 방법과 알고리즘 개발에 다양한 연구가 진행되어 왔다. 하지만, 대부분의 연구가 메인 메모리에 수용 가능한 크기를 갖는 그래프만을 고려하였기 때문에 큰 문제에 적용하기 위해서는 아직도 많은 어려움이 존재한다. 이를 극복하기 위하여 본 논문에서는 관계형 데이타베이스 이론에 기반하여 그래프를 표현하고 그래프 알고리즘을 정의할 수 있는 방법을 제안한다. 이 방법에서 그래프는 릴레이션으로 표현되며 그래프의 각 정점과 간선은 이 릴레이션의 튜플로서 저장된다. 이렇게 저장된 그래프에 대한 알고리즘은 추출, 선택, 죠인과 같은 관계대수 연산을 이용하여 정의되며 SQL과 같은 데이타베이스 언어를 사용하여 구현될 수 있다. 또한, 본 논문은 그래프의 저장 및 관리뿐만 아니라 다양한 응용프로그램 개발에도 사용될 수 있는 기본적인 그래프 함수들을 라이브러리화 하였다. 이와 같은 데이터베이스에 기반한 방법은 메모리에 수용되지 않는 크기의 그래프를 효과적으로 처리할 수 있는 방법을 제공할 뿐만 아니라 다양한 응용프로그램 개발을 용이하게 할 것이다. 또한, 데이타베이스가 제공하는 기본적인 기능인 다중사용자에 의한 동시공용 등과 같은 많은 장점을 가진다.
그래프는 실세계의 많은 문제를 효과적으로 모델링하여 해를 구할 수 있는 강력한 방법을 제공하기 때문에 그래프의 표현 방법과 알고리즘 개발에 다양한 연구가 진행되어 왔다. 하지만, 대부분의 연구가 메인 메모리에 수용 가능한 크기를 갖는 그래프만을 고려하였기 때문에 큰 문제에 적용하기 위해서는 아직도 많은 어려움이 존재한다. 이를 극복하기 위하여 본 논문에서는 관계형 데이타베이스 이론에 기반하여 그래프를 표현하고 그래프 알고리즘을 정의할 수 있는 방법을 제안한다. 이 방법에서 그래프는 릴레이션으로 표현되며 그래프의 각 정점과 간선은 이 릴레이션의 튜플로서 저장된다. 이렇게 저장된 그래프에 대한 알고리즘은 추출, 선택, 죠인과 같은 관계대수 연산을 이용하여 정의되며 SQL과 같은 데이타베이스 언어를 사용하여 구현될 수 있다. 또한, 본 논문은 그래프의 저장 및 관리뿐만 아니라 다양한 응용프로그램 개발에도 사용될 수 있는 기본적인 그래프 함수들을 라이브러리화 하였다. 이와 같은 데이터베이스에 기반한 방법은 메모리에 수용되지 않는 크기의 그래프를 효과적으로 처리할 수 있는 방법을 제공할 뿐만 아니라 다양한 응용프로그램 개발을 용이하게 할 것이다. 또한, 데이타베이스가 제공하는 기본적인 기능인 다중사용자에 의한 동시공용 등과 같은 많은 장점을 가진다.
Graphs have provided a powerful methodology to solve a lot of real-world problems, and therefore there have been many proposals on the graph representations and algorithms. But, because most of them considered only memory-based graphs, there are still difficulties to apply them to large-scale proble...
Graphs have provided a powerful methodology to solve a lot of real-world problems, and therefore there have been many proposals on the graph representations and algorithms. But, because most of them considered only memory-based graphs, there are still difficulties to apply them to large-scale problems. To cope with the difficulties, this paper proposes a graph representation and graph algorithms based on the well-developed relational database theory. Graphs are represented in the form of relations which can be visualized as relational tables. Each vertex and edge of a graph is represented as a tuple in the tables. Graph algorithms are also defined in terms of relational algebraic operations such as projection, selection, and join. They can be implemented with the database language such as SQL. We also developed a library of basic graph operations for the management of graphs and the development of graph applications. This database approach provides an efficient methodology to deal with very large- scale graphs, and the graph library supports the development of graph applications. Furthermore, it has many advantages such as the concurrent graph sharing among users by virtue of the capability of database.
Graphs have provided a powerful methodology to solve a lot of real-world problems, and therefore there have been many proposals on the graph representations and algorithms. But, because most of them considered only memory-based graphs, there are still difficulties to apply them to large-scale problems. To cope with the difficulties, this paper proposes a graph representation and graph algorithms based on the well-developed relational database theory. Graphs are represented in the form of relations which can be visualized as relational tables. Each vertex and edge of a graph is represented as a tuple in the tables. Graph algorithms are also defined in terms of relational algebraic operations such as projection, selection, and join. They can be implemented with the database language such as SQL. We also developed a library of basic graph operations for the management of graphs and the development of graph applications. This database approach provides an efficient methodology to deal with very large- scale graphs, and the graph library supports the development of graph applications. Furthermore, it has many advantages such as the concurrent graph sharing among users by virtue of the capability of database.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 기존의 데이타 모델이나 질의어의 변경 없이 관계형 데이타베이스에 기반하여 그래프를 표현하고 그래프 알고리즘을 정의하는 방법을 제안한다. 이 방법에서 그래프는 릴레이션(1.
본 논문은 그래프의 표현과 알고리즘을 정의하기 위한 방법을 제안하였다. 이 방법은 관계형 데이타모델과 관계대수에 기반하고 있다.
XSQL이라는 확장된 SQL을 제안하였다. 즉, 계통(genealogies), 네트워크(networks), 개념계층(concept hierarchies) 등 그래프 관계에 기반한 다양한 타입의 질의에 대한 분석을 한 후 이를 효율적으로 처리하기 위하여 기존의 SQL을 확장하였다 특히, SQL과 같은 기존의 데이타베이스 언어는 경로(path)와 같은 회귀(recursion) 적인 정보를 검색하는 데는 적합하지 않을 수 있기 때문에 이에 대한 질의가 가능하도록 하였다. 우선, 그래프릴레이션에 대한 질의가 다음의 3단계로 구성됨을 파악하였다 튜플 시퀀스(tuple sequence)인 경로들의 집합을 생성한다, 조건에 맞는 경로들을 선택한다, 원하는 출력을 추출한다.
가설 설정
1) 각 그래프의 메타 정보를 저장하는 테이블은 gmBz项伪이다. 각각의 그래프를 고유하게 식별하는 그래프 식별자(g_H丿를 기본키로 하고, 그래프의 이름 (gename), 그래프에 대한 키워드(施矿W), 그래프작성 시작 날짜(s切七如y)와 최종수정날짜 (.
물론, 추가적인 다른 열을 고려하더라도 알고리즘의 핵심은 유사하게 된다. 다음의 정의 또는 알고리즘에서 특별한 언급이 없는 경우에는 무방향그래프를 가정한다.
제안 방법
질의어를 제안하였다. 그래프를 표현하기 위하여 정점, 간선, 경로 각각에 대응되는 단순 클래스(simple class), 링크 클래스(link class), 경로 클래스(path class) 를 제안하였다. 그래프에 대한 질의를 위해서는 부 그래프(sub-graph)를 참조할 수 있도록 기존 질의어를 확장하였다.
기존의 연구에서는 그래프 라이브러리에 대한 고려를 하지 않았지만, 본 연구에서는 그래프를 데이타베이스에 저장하고 처리하기 위한 기본적인 함수들을 라이브러리화 하였다. 이는 본 논문에서 정의한 알고리즘의 구현뿐만 아니라 응용 프로그램 개발에도 매우 유용하게 사용될 것이다.
따라서, 본 실험에서는 정점의 개수를 500개에서 2,000개까지 바꿔가면서 완전그래프에 대하여 실험하였다 (그림 5
4장에서 그래프를 데이타베이스에 저장하고 처리하는 기본적인 그래프 함수들의 라이브러리 개발에 관하여 기술한다. 또한, 이를 이용한 그래프 알고리즘의 구현 및 실험결과를 제시하고 이를 기존의 연구들과 비교 고찰한다. 5장에서는 결론과 향후 연구과제를 제시한다.
또한, 정점의 개수가 정해졌을 때 그래프의 크기에 따른 실행시간을 알아보기 위하여, 정점의 개수가 1,000개고 간선의 개수가 500, 000개인 완전 그래프에 대하여 하나의 간선의 크기를 lOObyte에서 400byte까지 바꿔가면서 실험하였다 (그림 5
본 논문에서 제시하는 그래프 연산과 알고리즘의 관계 대수 표현에서, 정점릴레이션 V에서는 정점식별자 以d만을 고려하고 간선릴레이션 E에서는 d汕과 勇 c 必만을 고려한다. 물론, 추가적인 다른 열을 고려하더라도 알고리즘의 핵심은 유사하게 된다.
본 논문에서 제안한 개념을 구현하기 위하여 3래프의 각종 부가적인 정보를 다룰 수 있도록 테이블을 좀 더 상세하게 설계하였으며, 그래프를 처리하기 위한 기본적인 그래프 함수를 라이브러리의 형태로 개발하였다. 이 라이브러리는 다양한 다른 응용프로그램 개발에도 사용될 수 있다.
데이타베이스 관리시스템은 Oracle-8을, 개발언어는 C와 Pro*C를 사용하였다. 실험에서는 대표적인 그래프 알고리즘인 최단경로 알고리즘과 최소비용 신장 트리를 고려하였다.
즉, 계통(genealogies), 네트워크(networks), 개념계층(concept hierarchies) 등 그래프 관계에 기반한 다양한 타입의 질의에 대한 분석을 한 후 이를 효율적으로 처리하기 위하여 기존의 SQL을 확장하였다 특히, SQL과 같은 기존의 데이타베이스 언어는 경로(path)와 같은 회귀(recursion) 적인 정보를 검색하는 데는 적합하지 않을 수 있기 때문에 이에 대한 질의가 가능하도록 하였다. 우선, 그래프릴레이션에 대한 질의가 다음의 3단계로 구성됨을 파악하였다 튜플 시퀀스(tuple sequence)인 경로들의 집합을 생성한다, 조건에 맞는 경로들을 선택한다, 원하는 출력을 추출한다. 이와 같은 과정은 기존 SQL 의 “SELECT … FROM … WHERE …”의 기본 구문과 일치하기 때문에 새로운 질의어를 제안하기보다는 SQL 을 확장하여 사용하였다.
위에서 제안한 그래프 테이블과 그래프 기본 함수을 사용하여 관계대수로 표현된 그래프 알고리즘을 구현하고 그 성능을 실험하였다. 구현 환경으로 SUN Enterprise-450 컴퓨터와 Solaris~2.
위의 연구들은 그래프를 데이타베이스화 하고 그 연산을 최적화하기 위하여 기존의 데이타베이스 질의어를 확장하든지 새로운 질의어를 제안하는데 주안점을 두었다. 하지만, 이와 같은 접근 방법은 표준 데이타베이스 시스템을 그대로 사용할 수 없기 때문에 호환성이나 이식성이 떨어지게 된다.
위의 테이블들은 데이타베이스 생성시에 만들어지게 되며, 각 그래프에 관한 정보를 이 테이블들에 저장하고 처리할 수 있는 기본 함수를 개발하여 라이브러리화 하였다. 라이브러리의 구성은 그래프, 정점, 간선, 정점 속성, 간선속성 정보 각각에 대하여 생성, 갱산, 삭제, 검색 연산 등으로 구성된다.
이 장에서는 데이타 모델이나 질의어를 확장한 기존연구와는 달리 표준의 관계형 모델을 이용하여 그래프를 표현하고 표준의 관계대수를 이용하여 그래프 연산이냐 알고리즘을 정의하는 방법을 제안한다.
이를 위하여 그래프 테이블을 설계하였으며 기본적인 그래프 연산을 라이브러리화하였다. 이러한 라이브러리를 이용하여 중요한 알고리즘을 구현하였으며 그 성능을 실험 분석하였다. 이러한 데이타베이스를 이용한 접근방법은 기존의 방법에 비하여 많은 장점을 가지고 있다.
이렇게 표현된 그래프와 알고리즘은 관계형 데이타베이스를 사용하여 구현될 수 있다. 이를 위하여 그래프 테이블을 설계하였으며 기본적인 그래프 연산을 라이브러리화하였다. 이러한 라이브러리를 이용하여 중요한 알고리즘을 구현하였으며 그 성능을 실험 분석하였다.
이러한 방법은 관계형 데이타베이스에 기반하여 쉽게 구현될 수 있다. 이를 위하여 본 논문에서는 그래프의 저장을 위한 데이타베이스를 설계하였고, 그래프를 처리하기 위한 생성, 갱신, 삭제, 검색 등의 연산을 라이브러리화 함으로써 효과적으로 그래프를 실세계에 응용할 수 있는 방법을 제안하였다. 이를 이용하여 그래프 알고리즘을 구현하고 실험하였다.
예를 들면, 41 genealogy [ parent, child「'라는 테이블에서 “'CodcT의 모든 조상들을 찾아라」'는 질의는 "SELECT START FROM PATHS OVER genealogy WHERE GOAL='Codd'" 라는 XSQL 문장으로 표현된다. 이와 같이 확장된 질의어를 처리할 수 있도록 질의처리 과정 내부에 이행적 폐포(transitive closure) 및 관련된 연산을 추가하였으며 이 연산을 수행함에 있어서 페이지 액세스(page access) 를 최소화하기 위한 기법들을 제시하였다.
생성하였다. 정점의 개수가 주어졌을 때, 간선의 개수에 따른 알고리즘 실행시간의 상관관계를 실험하였다. 즉, 정점의 개수가 500개(그림 4(a))와 1, 000개(그림 4(b))인 두 가지 경우에 대하여 각각의 간선의 개수를 바꿔가면서 실험하였다.
나아가, 그래프 연산을 라이브러리화한 연구로서 Knuth[12]는 다양한 형태의 그래프를 조작하고 시험할 수 있는 데이타세트와 프로그램 라이브러리를 제안하였다. 즉, 그래프에 기반한 여러 가지 문제를 풀기 위한 예제 데이타 화일, 자료구조 및 입출력 등 커널 루틴, 기본적인 그래프 및 평면 그래프 등의 생성을 위한 그래프 생성 루틴, 최단 경로 및 최소신장 트리 등의 예제 루틴 등으로 구성된 그래프 라이브러리를 제안하였다.
데이터처리
것이다. 또한, 객체관계 또는 객체지향 데이타 모델에 기반하여 그래프를 모델링하고 알고리즘을 정의한 후 그 효율성을 본 연구와 상호 비교 평가할 것이다.
이론/모형
즉, 그래프는 관계형 데이타모델의 릴레이션으로 모델링되며, 그래프의 각 정점과 간선은 이 릴레이션의 튜플로 표현된다. 또한, 그래프 연산과 알고리즘은 관계대수 연산올 이용하여 정의하였다. 이러한 방법은 관계형 데이타베이스에 기반하여 쉽게 구현될 수 있다.
여기서는 Dijkstra 알고리즘(3)을 이용하였다.
다음과 같이 정의된다. 여기서는 Kruskal 알고리즘[ 3] 이 사용되었다.
이를 위하여 본 논문에서는 그래프의 저장을 위한 데이타베이스를 설계하였고, 그래프를 처리하기 위한 생성, 갱신, 삭제, 검색 등의 연산을 라이브러리화 함으로써 효과적으로 그래프를 실세계에 응용할 수 있는 방법을 제안하였다. 이를 이용하여 그래프 알고리즘을 구현하고 실험하였다.
성능/효과
그림 5(a)의 실험결과에서 알 수 있듯이 실행 시간은 간선의 개수에 거의 비례함을 알 수 있다. 이는 메모리 기반과 마찬가지로 최소비용 신장트리 알고리즘이 간선비용의 분포에 따라 실행시간이 달라지고 간선이 랜덤하게 생성되었기 때문이다.
2) 그래프에 관한 정보를 삽입하기 위한 기능으로서, 그래프 생성 함수는 c厂厂何가/)이匸上 정점에 관한 정보를 삽입하기 위하여 정점 자체를 삽입하는 함수 inserteertexO, 정점에 부가된 속성들을 삽입하는 함 )는 함수 등이 있다. 간선에 관한 정보를 삽입하기 위하여 간선 자체를 삽입하는 함수 insert_edge0, 간선에 부가된 속성들을 삽입하는 함수 insert_edge_attr(9^ 함수 등이 있다.
2) 정점에 관한 정보를 저장하는 테이블은 정점의 기본정보를 저장하는 vertex 테이블과 정점에 부가된 각종 속성들과 그 값을 저장하는 vertex_att 테이블로 구성된다. 이렇게 두 개의 테이블로 분리한 이유는 한 정점에 여러개의 속성이 존재할 수 있기 때문이다.
3) 간선에 관한 정보를 저장하기 위한 테이블은 간선의 기본정보를 저장하는 edge 테이블과 간선에 부가된 각종 속성들과 그 값을 저장하는 edge_att 테이블로 구성된다. 이렇게 두 개의 테이블로 분리한 이유는 한 간선에 여러 개의 속성이 존재할 수 있기 때문이다.
3) 그래프에 관한 정보를 삭제하기 위한 기능으로서, 그래프 삭제 함수 del_graph0 는 graph_info 테이블에서 해당 그래프를 삭제하고, vertex 테이블, vertex_att 테이블, edge 테이블, edge_att 테이블에서 삭제된 그래프에 속하는 모든 튜플들도 삭제한다. 정점 삭제 함수는 vertex 테이블에서 해당 정점을 삭제하고, vertex_att 테이블, edge 테이블에서 삭제된 정점을 참조하는 모든 튜플들도 삭제한다.
6) 트랜잭션 처리 라이브러리는 일련의 그래프 연산이나 알고리즘 수행을 하나의 트랜잭션으로 처리할 수 있도록 지원한다. 복구 함수인 rollba애〔0은 잘못 수행한 작업을 작업수행 이전상태로 복구한다.
또한, 그림 5(b)에서 알 수 있듯이 정점과 간선의 개수가 동일할 때, 하나의 간선의 크기(즉, 그래프의 크기)가 증가하더라도 실행시간은 소폭으로만 증가하는 것을 알 수 있다. 따라서, 데이타베이스에 기반한 알고리즘이 정점과 간선에 많은 속성이 부가된 대용량 그래프를 처리하는데 상대적으로 더 효율적임을 알 수 있다.
정리하였다. 본 논문을 포함하여 많은 연구에서 관계형 또는 객체지향형 데이타베이스를 채택하였는데 이는 새로운 데이타베이스 시스템을 개발하는 것보다 이미 검증되고 최적화된 데이타베이스를 사용하는 것이 타당함을 알 수 있다.
후속연구
Chiang[4]은 그래프 문제에 적용 가능한 외부-메모리 알고리즘을 설계하는 방법들을 제안하였다. 또한, 이 기법들이 최소 신장트리 (minimum spanning tree) 등과 같은 응용에 적용될 수 있음을 보였다. Nodian[5]은 외부-메모리 그래프를 처리함에 있어서 블록 전송을 최소화하기 위한 블록킹방법에 관한 연구를 하였다.
하였다. 이는 본 논문에서 정의한 알고리즘의 구현뿐만 아니라 응용 프로그램 개발에도 매우 유용하게 사용될 것이다.
이러한 데이타베이스 기반 방법은 메모리에 수용되지 않는 크기를 갖는 그래프를 효과적으로 처리할 수 있을 뿐만 아니라 그래프 라이브러리는 응용프로그램 개발을 용이하게 할 것이다. 또한, 데이타베이스가 제공하는 기본적인 기능인 다중사용자에 의한 그래프의 동시 공용 등과 같은 많은 장점을 가진다.
향후 연구과제는 제안한 방법을 실제 응용분야에 적용하여 그 효용성을 검증하고 성능을 분석하는 것이다. 또한, 객체관계 또는 객체지향 데이타 모델에 기반하여 그래프를 모델링하고 알고리즘을 정의한 후 그 효율성을 본 연구와 상호 비교 평가할 것이다.
참고문헌 (15)
R. Gould, Graph Theory, The Benjamin/Cummings Publiching, Menlo Park, CA. 1988
J. A. Mchugh, Algorithmic Graph Theory, Prentice-Hall, 1990
E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C, Computer Science Press, New York, 1993
Y. J. Chiang, M. T. Goodrich, E. F. Grove, and R. Tamassia, 'External Memory Graph Algorithms,' Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 1995
M. H. Nodian, M. T. Goodrich, and J. S. Vitter, 'Blocking for External Graph Searching,' Algorithmica, Vol.16, No.2, pp.181-214, Aug. 1996
M. V. Mannino and L. D. Shapiro, 'Extensions to Query Languages for Graph Traversal Problems,' IEEE Trans. on Knowledge and Data Engineering, Vol.2, No.3, pp.353-363, Sept. 1990
R. H. Guting, 'GraphDB: Modeling and Querying Graphs in Databases,' Proc. of the 20th Conference on VLDB, pp.297-308, 1994
L. Sheng, Z. M. Ozsoyoglu, and G. Ozsoyoglu, 'A Graph Query Language and Its Query Processing,' Proc. of 15th Conference on Data Engineering, pp.572-581, 1999
N. Kiesel, A. Schuerr, and B. Westfechtel, 'GRAS, A Graph-Oriented(Software) Engineering Database System,' Information Systems, Vol.20, No.1, pp.21-52, 1995
※ AI-Helper는 부적절한 답변을 할 수 있습니다.