I am trying to design a database model related to the small world (or six
degree of separation) phenomenon.

With this design, I should be able to write two queries efficiently:

a) How many degrees of separation are there between two people.
(assuming they are connected). You may assume that you do not have to check
for more than 6 degrees.

b) Who are all the people that have x degrees of separation from a
given person.



If anybody has any idea on how to do this, or any references, please let me
know.

Thanks!

On Jul 31, 2:37 pm, "John Ruan" <rds1... (AT) sh163 (DOT) net> wrote:
People
pid key
name varchar

Pair
pair_id key
pid1 key
pid2 key

Distance
pair_id key
distance int

i think this is a fairly good structure. I have a Pair table so that
you can have
key1234 jane jim
key1234 jim jane
as two rows, in case space isn't a consideration

i hope that this makes sense! I could see the pair table getting huge
tho. It'd be nice if the pair_id could somehow be a hash that you
compute given pid1 and pid2 that is the same whether pid1 is the first
key or pid2 is the first key.

With your structure, how can you write queries for a) and b)?


<jamie.ly (AT) gmail (DOT) com> wrote

Get a copy of the White Paper I did for Cogito on this topic
(www.cogitoinc.com). They make a product for searching networks. I
wrote SQL for the "Kevin Bacon" problem to compare them against SQL;
they won by orders of magnitude. The fundamental problem is a
Cartesian explosion in SQL that examines all possible paths.

On Aug 2, 11:38 pm, --CELKO-- <jcelko... (AT) earthlink (DOT) net> wrote:
The articles in the link(www.cogitoinc.com), there was .....
By using sample data from IMDB.com, IMDB Analyzer shows how quickly
and easily Cogito can find not only the "Six Degrees of Kevin Bacon"
but the "Six Degrees of All Things Movies."

But, I couldn't find the White Paper that shows DDL and DML, the link
for that or the DDL/DML itself from that page. I saw (http://
www.cogitoinc.com/), (http://www.cogitoinc.com/famous.html), (http://
www.ancestry.com/), (http://www.cogitoinc.com/solutions.html).
I must be not so capable to find the information from internet.

Celko,
Would you show me the sample DDL and DML(SELECT statement) or the
direct link to see them?

They hold the copyrights, but I can ask them to do something. I will
cut and paste this thread and forward it.

I am also interested in the table design and the SELECT statement.
I guess that some functions or procedures have to be defined and used.

I would like to see how it is implemented in MySql.

Thanks!
"--CELKO--" <jcelko212 (AT) earthlink (DOT) net> wrote

The example at www.dbfordummies.com/temp/ExPathBetwPersons.asp shows
how to model relationships between persons and determine the shortest
path between any two using dbd, a lightweight, memory-resident
database. Dbd isn't based on the relational data model. Instead, it
stores data as a network of nodes where each node is equivalent to an
AND gate.

Below is dbd's script to model relationships between a small number of
persons and determine the shortest path between any two:

(; Create persons)
(new 'john 'person)
(new 'mary 'person)
(new 'mickey 'person)
(new 'sue 'person)
(new 'bob 'person)
(new 'jill 'person)
(new 'jack 'person)

(; Create types of relationships)
(new 'friend 'relationship)
(new 'father 'relationship)
(new 'mother 'relationship)
(new 'husband 'relationship)
(new 'wife 'relationship)
(new 'son 'relationship)
(new 'daughter 'relationship)
(new 'brother 'relationship)
(new 'sister 'relationship)
(new 'employer 'relationship)
(new 'employee 'relationship)

(; Note: relationships between persons
forms a Y figure with mickey at center)
(set mickey daughter mary)
(set mary father mickey)

(set mary husband john)
(set john wife mary)

(set mickey friend sue)
(set sue friend mickey)

(set sue brother bob)
(set bob sister sue)

(set mickey daughter jill)
(set jill father mickey)

(set jill employer jack)
(set jack employee jill)


/
************************************************** ***************************
************************************************** ***************************/
#define kMaxDeg 6

int main()
{
int* pMickey = AStr_getDefN(_T("mickey"));
int* pJohn = AStr_getDefN(_T("john"));
PathBetwPersons_get(pMickey, pJohn, kMaxDeg);
}

/
************************************************** ***************************
************************************************** ***************************/
int* PathBetwPersons_get(int* pPer1, int* pPer2, int nMax)
{
int* pP[kMaxDeg] = {0, 0, 0, 0, 0, 0};
int pathInx = 0;
int* pSP[kMaxDeg] = {0, 0, 0, 0, 0, 0};
int sPathInx = 999;
if (PathBetwPersons_getSub(pPer1, pPer2, nMax, pP, pathInx, pSP,
sPathInx)){
// Create ie
// "path from john to mary is (john friend matt) (matt sister
mary)"
// in db
int* pA1[256]; int* p1 = (int*)pA1;
int* pPath = AStr_getDefN(_T("path"));
if (!pPath){
pPath = N_create();
N_Name_setWithAStr(pPath, _T("path"));
N_SVO_set(pDbDb_g, pItem_g, pPath);
}
int* pB[13] = {Xp_Node(pPath, p1),
Xp_Node(pPrepFrom_g, p1),
Xp_Node(pPer1, p1),
Xp_Node(pPrepTo_g, p1),
Xp_Node(pPer2, p1),
Xp_Node(pTenseIs_g, p1)};
for (int x=0; x < kMaxDeg; ++x){
if (pSP[x]){
pB[x+6] = Xp_Node(pSP[x], p1);
}
else{
pB[x+6] = NULL;
}
}
pB[12] = NULL;

int* eQ2 = Xp_SeqX_getElseCreate((int*)pB, p1);
return Xp_execute(eQ2);
}

return NULL;
}

/
************************************************** ***************************
Finds shortest path between persons (pPer1 & pPer2)
and stores it in db as
"path from pPer1 to pPer2 is (pPer1 rel1 pPerX) ... (pPerX rel2
pPer2)"
where rel1, rel2, ... are intances of relationship (ie friend, father,
etc).

For example:
"path from john to mary is (john friend suzy) (suzy sister mary)"

nMax - maximum number of relationships to search.
pP - an array that holds current path from pPer1 to pPer2
pathInx - index at which next relationship can be stored in pP.
caller must init to 0.
pSP - an array that holds shortest path from pPer1 to pPer2.
sPathInx - short path index.
************************************************** ***************************/
int* PathBetwPersons_getSub(int* pPer1, int* pPer2, int nMax,
int* pP[kMaxDeg], int &pathInx,
int* pSP[kMaxDeg], int
&sPathInx)
{
// If no path between pPer1 and pPer2 in nMax relationships
if (nMax <= pathInx){
// Terminate recursions
return NULL;
}

// Get person that starts current relationship
int* pPerS = pPer1;
if (pathInx){
pPerS = N_getElem(pP[pathInx-1]);
}

// (get perA (get relationship instance *) per2)
int* pA1[128]; int* p1 = (int*)pA1;
int* pRel = AStr_getDefN(_T("relationship"));
int* eRel = Xp_Node(pRel, p1);
int* eInst = Xp_Node(pInst_g, p1);
int* eQ1 = Xp_SV_getO(eRel, eInst, p1);
int* ePerA = Xp_Node(pPerS, p1);
int* ePer2 = Xp_Node(pPer2, p1);
int* eQ2 = Xp_SVO_get(ePerA, eQ1, ePer2, p1);
int* pSVO = Xp_execute(eQ2);
if (pSVO){
// Path found, store in array
pP[pathInx++] = pSVO;

// If new path is shorter
if (pathInx < sPathInx){
// Save new shortest path
for (int x=0; x < kMaxDeg; ++x){
pSP[x] = pP[x];
}
sPathInx = pathInx;
}

return pSVO;
}

// No relationship between pPerS and pPer2 found
// Loop thru all relationships between pPerS and pPerX
int* eQ3 = Xp_SV_getSVO(ePerA, eQ1, p1);
Xp_Inps_reset(eQ3, FALSE);
while (int* pPerS_Rel_PerX=Xp_execute(eQ3)){
// Continue if PerX already in stored path
int* pPerX = N_getElem(pPerS_Rel_PerX);
if (pPerX == pPer1){
continue;
}
for (int x=0; x < nMax; ++x){
if (pP[x]){
if (pPerX == N_getElem(pP[x])){
continue;
}
}
}

// Recurse
pP[pathInx++] = pPerS_Rel_PerX;
if (int* pFnd=PathBetwPersons_getSub(pPer1, pPer2, nMax,
pP, pathInx, pSP, sPathInx)){
return pFnd;
}
pP[--pathInx] = NULL;
}

return NULL;
}