You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
그래프(Graph)는 연결되어 있는 원소간의 관계를 표현하는 자료구조이다. 나와 연관된 인간 관계를 나타내는 인맥 지도, 수도 배관에 대한 배수 시스템, 물질의 분자 구조 등은 연결 구조가 다양하기 때문에 선형 자료 구조나 트리로는 표현 할 수가 없다.
그래프는 연결할 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. 그래프 G를 _G=(V,E)_로 정의하는데, V는 그래프에 있는 정점들의 집합을 의미하고, E는 정점을 연결하는 간선들의 집합을 의미한다.
1) 그래프의 종류
무방향 그래프(undirected graph)
두 정점을 연결하는 간선의 방향이 없는 그래프이다. 무방향 그래프에서 정점 _Vi_와 정점 _Vj_을 연결하는 간선을 _(Vi, Vj)_로 표현하고, _(Vi, Vj)_와 _(Vj, Vi)_는 같은 간선을 나타낸다. V(G)={A,B,C,D}, _E(G)={(A,B),(A,D),(B,C),(B,D),(C,D)}_와 같이 정점의 집합 _V(G)_와 간선의 집합 _E(G)_로 나타낼 수 있다.
방향 그래프(directed graph)
방향 그래프는 다이그래프(di-graph)라고도 하는데, 간선이 있는 그래프를 의미한다. 정점 _Vi_에서 정점 _Vj_를 연결하는 간선, 즉, Vi->_Vj_를 로 표현하고 화살표로 나타낸다. 이때 _Vi_를 꼬리(tail), _Vj_를 머리(head)라고 한다. 방향 그래프 와 ``는 서로 다른 간선이 된다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
관계형 데이터베이스의 설계에서 중복을 최소화하게 데이터를 구조화하는 프로세스를 정규화라고 한다. 데이터베이스 정규화의 목표는 이상이 있는 관계를 재구성하여 작고 잘 조직된 관계를 생성하는 것에 있다. 일반적으로 정규화란 크고, 제대로 조직되지 않은 테이블들과 관계들을 작고 잘 조직된 테이블과 관계들로 나누는 것을 포함한다. 정규화의 목적은 하나의 테이블에서의 데이터의 삽입, 삭제, 변경이 정의된 관계들로 인하여 데이터베이스의 나머지 부분들로 전파되게 하는 것이다.
비정규화
정규화는 되도록 중복된 데이터를 제거해서 성능 향상에 도움을 주것을 목표로 하고 있다. 그러나 과도한 정규화로 인해서 테이블의 수가 증가하게 되면, 다수의 JOIN이 발생함에 따라서 성능 저하가 발생할 수 있다. 보통의 경우 정규화 과정을 모두 거친 다음 마지막 단계에서 비정규화를 실시한다. 단, 테이블을 합치는 것만이 비정규화는 아니다.
그룹에 대한 합계와 같은 값을 미리 계산하여 테이블에 저장해 둔다. (얍 플레이스를 예로 들면, 사용자가 좋아요를 하거나 리뷰를 남기면 통계 관련 작업을 해주는데, 통계 테이블을 생성하여 관리하는 것 또한 비정규화라고 해석할 수 있다.)
하나의 테이블에서 자주 사용되는 행(레코드)와 그렇지 않은 행들을 분리하여 두 개의 테이블로 나눈다. (이런 경우에는 UNION으로 다시 연결시킨다.)
다른 테이블에 의존적이지만 자주 JOIN하여 사용하는 컬럼을 중복하여 테이블 안에 하나 더 생성한다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters