DB의 테이블 구조와 트리와 그래프

프로그램 관련 글은 오랜만에 써 본다.

데이터베이스가 널리 쓰이기 시작한 건, 컴퓨터가 상용화되기 시작한 시점과 거의 비슷하지만, 급격하게 대중화 된 것은 관계형 데이터베이스, 즉, RDBMS가 등장한 이후일 것이다. 관계형 데이터베이스는 독립된 두 테이블을 join하여 결과를 출력할 수 있다는 개념인데, 잘 설계하면, 그렇지 않은 경우보다 저장 용량을 줄이고, 데이터 무결성을 유지하는데 탁월한 효과를 볼 수 있다.

하지만 그 장점만큼이나 단점도 명확한데, 테이블 join에 따른 엄청난 비용이 그것이다. 상용 DBMS마다 이에 대한 대책이 어느 정도 있기는 하겠지만, join은 일종의 '곱집합' 연산으로, 한 테이블의 한 row를 다른 테이블의 모든 row에 대응시키는 연산이고, 때문에 한 번 연산할 때마다 각 테이블의 모든 자료수*자료수만큼의 비용이 든다. 테이블 크기가 증가함에 따라, 또 join하는 테이블의 수가 증가함에 따라 거의 무한대에 가까운 자료 증폭이 일어나서 가끔 곤란한 경우에 처하기도 한다.

데이터베이스의 테이블이 2차원의 매우 정형화된 데이터 구조를 가지고 있다면, 트리 구조는 무한차원의 비정형 데이터를 수용하는 데 탁월하다. 비정형이기 때문에 자료를 한 번 순회하는 데에 재귀적 탐색이 필수라서 익숙하지 못한 개발자들이 다루기에 어렵기는 하지만, 2차원이 아닌 데이터들(그러니까 거의 모든 데이터들)을 수용하기에 적합하다. 이 트리 구조를 오래 전 부터 사용한 것이 모든 운영체제에서 볼 수 있는 '파일 구조'다. 윈도우즈의 탐색기나 리눅스의 파일, 프로세스 계층이 이런 구조를 사용하고 있다(댓글의 대댓글같은 것도 마찬가지 구조다). 최근에는 MCTS(몬테카를로 트리 탐색)과 같이 인공지능 분야에서도 각광을 받고 있다.

트리 구조가 자료의 비정형성을 어느 정도 수용할 수 있다고 해도, 완전히 자유로운 형식이라고는 볼 수 없다. 모든 자료들은 단 하나의 부모노드를 가져야 하고, 다수의 자식노드를 가질 수 있다. 최상위 노드(root 노드)는 부모노드가 없다. 이런 형식이 의미하는 것은 모든 자료들은 계층에 속하며, 자유로운 상호참조가 불가능하다는 것이다. 그리고 어떤 자식노드라도 부모의 죽음은 자식의 죽음을 의미한다.

트리구조는 일정한 변형과정을 거쳐서 데이터베이스의 테이블 구조로 치환될 수 있다. 트리 구조가 보통 다차원 구조를 띠기 때문에, 2차원 테이블로 표현되기 위해서는 자료의 중복 저장이 불가피해서 매우 낭비적이긴 하지만(가령, 동일한 폴더의 두 파일을 묘사하기 위해서 그 상위의 모든 부모 폴더를 명시해야 한다), 자료를 탐색하는데 유리하기 때문에 이런 종류의 전환이 간혹 쓰인다. 윈도우즈의 경우는 어떨지 모르겠지만, 리눅스에서는 i-node라는 테이블이 운영체제 안의 파일 구조를 저장하고 있다.

비계층의 상호참조 가능한 '그래프 구조'는 자료들의 가장 일반적인 형태라고 볼 수 있다. 일반적이기때문에 테이블 구조나 트리 구조를 모두 포용할 수 있는 장점이 있는 반면에, 테이블이나 트리가 가지는 정형성이 부족해서 자료를 탐색하는 데 불리하다. 상호참조가 가능하기 때문에 탐색하다가 무한루프에 빠져서 금방 메모리가 소진될 수 있는 단점도 있다.

하지만 자료를 그래프 구조로 저장하면, 자료의 중복은 거의 완벽하게 제거할 수 있다는 장점이 있다. 가령, 데이터베이스에서 자주 쓰이는 'Y', 'N'이라는 자료는 어떤 특정한 column이나 row에 매우 자주 쓰인다. 어떤 테이블을 select해 보면, Y/N만 가득한 경우도 있다. 만약에 Y나 N을 하나의 노드로 보고, 그것을 특정 row와 column이라는 부모노드에 엣지를 달아 놓으면, Y와 N이 하나만 존재해도, 테이블의 어떤 위치에도 표시할 수 있다. 즉, 테이블은 사라지고 관계만 남는 것이다.

그래프가 자주 쓰이지 않는 것은 그 효율에도 불구하고 추상화 수준이 매우 높아서 일반적인 개발자들이 이해하기가 쉽지 않기 때문이다(이해는 커녕 아직 확립된 이론이나 제품도 없다. 시중에 나와 있는 그래프DB는 이 이야기와 별 상관없는 개념이다). 다만, 이 그래프 구조는 우리의 지능이 사용하는 방식일 가능성은 매우 높다.

가령, 우리가 '사랑'이라는 단어를 떠올리면, 사랑과 관련된 온갖 종류의 생각들(심지어 서로 관계도 없는)이 떠오른다. 이것은 특정한 테이블이나, 특정한 부모 밑에 존재하는 비슷비슷한 자료들과는 다르다. 우리의 지능은 '사랑'이라는 개념을 노드로 만들어 놓고, 다른 어떤 개념이라도 무차별하게 엣지를 달아 놓는 것처럼 보인다. 이것은 그래프 구조에서 볼 수 있는 상호참조와 무정형 참조와 비슷하게 보이는데, 그런 의미에서 지능이 사용하는 방식을 아직 개발 세계에서 완벽하게 이해했다고 보기는 힘들다.

우리가 지능에 더 가깝게 다가가려면, 혹은 자료를 훨씬 더 효율적으로 저장하고 참조해서 사용하려면, 아직 갈 길이 멀다는 것을 느낀다. 데이터베이스나 트리구조만으로는 한계가 있다.

나는 지금 javascript를 이용하여 그래프 구조의 자료 최적화 모듈을 하나 만들고 있는 중인데, 만드는 중에 생각이 나서 그 생각을 정리하여 여기에 남긴다.

== Steem AD ==
"스팀은 역시 jSteem(http://jsteem.com)"