Graph model

Concept

기본적으로 그래프는 Node(Vertex) - Edge - Node(Vertex) 으로 이루어져있다. (Graph Theory 참고)

Node와 Node가 이어진 그래프(edge)에 따라 direct/undirected가 결정된다. Edge는 특수한 경우 weight를 가진다.

민트프레소에 저장되는 데이터들의 특성상 모두 model(actor), action, model(target) 으로 표현가능하다. 만약 action 수에 비해 상대적으로 적은 수의 model이 있다면 read/filter에서 일반적인 성능 향상(cost efficient)이 된다. 또한, Twitter와 같이 A follows B 와 B is followed by A 를 나타내는 bidirectional; functioning in two directions 관계를 표현하고 쿼리할때 그래프를 저장하는게 매우 효율적이다. 하지만, Facebook 같이 as a friend, A and B know each other 같이 unidirectional; functioning in a single direction 쿼리를 나타내기에는 RDBMS도 충분한데 이 경우 edge의 weight와 그래프에 적용가능한 neighbor search를 잘 이용한다면 실시간 데이터 마이닝의 현실적 문제를 해결할 수 있다.

서비스 이용 특성상 민트프레소가 저장해야할 그래프는 전혀 symmetric하지 않다. 즉, pure한 구현을 한다면 node의 수에 따라 adjancency matrix가 n × n (n by n)으로 늘어나고 데이터베이스 상 필드가 nⁿ개로 늘어난 다는 말이다. 지나치게 커지는 데이터를 간소화 시키기위해 우리는 Create-Read-Update-Delete(CRUD)중에서 update, delete를 버렸다. Read도 실제로 사용자가 cache나 mining result를 가져오게되는 수동적인 방향을 취하게 된다. Update의 경우 timestamp와 factor value에 따라 유효한 것을 가리게되는 delete의 경우 너무 오래되면 '유효성이 떨어져서, 무시해도 되는 데이터'가 되었을 때 내부적으로 삭제하게된다.

프로토타입에 이용할 RDBMS(MySQL or PostgreSQL)에 최적화 하기위해 node에 type을 두어 indexing을 이용한다.

Data Model

Edge

영어 문법과 같이, 간단히 Subject + Verb + Object (S+V+O)를 기준으로 한다.

name	data type	used for
id	bigint	primary key of a row
sId	bigint
sType	tinyint
v	string
oId	bigint
oType	bigint
createdAt	datetime	timestamp를 저장함. 나중에 GMT/UTC에 맞게 표시

Point

Subject, Object 노드들을 point라고 부른다. 나중에 data mapping/aggregation 에 용어를 이용하기 위함

name	data type	used for
id	bigint	primary key of a row
accId	bigint	Account ID를 이용하여 소유한 node가 아닌 경우 edge를 만들지 못하게 한다.
type	tinyint
createdAt	datetime	node가 만들어진 시간
updatedAt	datetime	node 정보인 data가 업데이트된 시간
referencedAt	datetime	node가 최근에 edge에 의해 참조된 시간
data	string	JSON을 stringify하여 저장함