위로
아래
그래프
그래프
- 사물을 연결하는 기본 개념.
- 노드 사이의 연결을 보여준다.
- 규칙이 없는 트리 노드처럼 보인다. (트리 구조를 최소화된 그래프의 형태로 여기기도 한다)
- 매우 구조화된 트리 구조와 달리, 그래프는 서로 상호작용하는 현실 세계에 존재하는 연결관계를 더 잘 표현한다.
무향 그래프, 유향 그래프, 가중치 그래프
그래프
- 노드 : 객체(object) 또는 정점(vertex, 두 선의 교차점)
- 에지 : 정점들을 연결하는 선
- 에지로 연결된 정점들은 서로 인접한 상태.
- 다수의 노드가 다수의 에지로 연결된 형태로, 객체(노드)사이의 관계를 보디에 유용하다.
유향 그래프(Directed graph)
- 다이그래프(digraph)라고도 부른다.
- 다른 노드로의 방향성을 가지는 에지를 지닌 그래프
- 유향 에지(directed edge) : 각각 하나의 방향을 가지고 있으며 화살표가 붙어 있는 에지
무향 그래프(Undirected graph)
- 방향성이 없는 에지를 지닌 그래프
- 노드 양쪽으로 에지를 타고 이동할 수 있다.
- 경로(path) : 에지를 타고 다른 정점으로 넘어가는 길
- 루프(loop) : 에지가 정점 하나에서 시작하여 다시 해당 정점으로 돌아가는 형태
- 서브그래프(subgraph) : 하위그래프. 더 큰 그래프의 일부.
가중치 그래프(weighted graph)
- 에지가 가중치를 갖는 그래프
- 에지가 양방향이면 무향 가중치 그래프
- 에지가 방향성이 있으면 유향 가중치
그래프 데이터베이스 발전 과정
파일 시스템
- 연산 실행이 제한적
- 데이터 형식이 제각각
- 데이터 중복 발생
- 보안성 허술
관계형 데이터베이스 관리 시스템(RDBMS, relational database management system)
- 행과 열로 구성된 테이블에 데이터를 저장하여 파일 시스템의 결함 개선
- 스키마 : 데이터베이스의 테이블 속성과 저장되는 데이터를 설명.
- 키 시스템 : 조건을 만족하는 데이터를 찾거나 정렬할 때 기준이 되는 속성을 담은 키를 이용.
- 기본 키 : 데이터를 식별하는 속성이 담겨 널 값이면 안 되는 키
- 외래 키 : 다른 테이블과의 관게를 참조한느 속성 정보를 담은 키
- 기본 키 하나를 갖는 테이블 각각은 다른 테이블과 관계를 맺을 수 있고, 테이블 사이의 관계는 외래 키를 사용한다.
- 데이터베이스가 확장될 때 많은 자원을 필요로 하여 시스템에 부하가 온다.
그래프 데이터베이스
- RDBMS의 문제를 개선하는 방법으로 떠오르고 있다.
- RDBMS는 데이터베이스를 연결해서 검색하는 조인(join)을 사용하는데, 조인이 너무 많아지면 검색 속도에 차질이 생긴다.
- 그래프 데이터베이스는 테이블이 아닌, 데이터 중심으로 직접 연결되도록 구성되어 있어 데이터베이스의 작업 속도가 빠르다.