Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let's assume (for the examples) that the friend table contains these rows.</p> <pre><code>ID1 ID2 --- --- a b a c b a b c b d c b </code></pre> <p>First, start with identifying the 'full friend' tuples from the friend table, with a query like this:</p> <pre><code>SELECT fa.ID1 , fa.ID2 FROM friend fa JOIN friend fb ON fb.ID1 = fa.ID2 AND fb.ID2 = fa.ID1 fa.ID1 fa.ID2 ------ ------ a b b a b c c b </code></pre> <p>This result shows us that a is friends with b, and b is friends with c. The <code>(a,c)</code> and <code>(b,d)</code> rows are omitted because there is no inverse, <code>(c,a)</code> or <code>(d,b)</code>.</p> <p>For the time being, we'll refer to this set as "<code>ft</code>" (friend tuples). Now we can write a query against that set (ft), to get all the "a->b->c" and "c->b->a" friend pairs.</p> <pre><code>SELECT fx.ID1 , fy.ID2 FROM ft fx JOIN ft fy ON fy.ID1 = fx.ID2 AND fy.ID2 &lt;&gt; fx.ID1 fx.ID1 fy.ID2 ------ ------ a c c a </code></pre> <p>But, we need to be sure that we don't duplicate any rows that are already in the friend table, so we could use a NOT IN or a NOT EXISTS predicate, or we can use an anti-join pattern, to eliminate rows that match a row already in the friend table.</p> <pre><code>SELECT fx.ID1 , fy.ID2 FROM ft fx JOIN ft fy ON fy.ID1 = fx.ID2 AND fy.ID2 &lt;&gt; fx.ID1 -- eliminate rows that match LEFT JOIN friend fe ON fe.ID1 = fx.ID1 AND fe.ID2 = fy.ID2 WHERE fe.ID1 IS NULL fx.ID1 fy.ID2 ------ ------ c a </code></pre> <p>Now, we can replace the references to <code>ft</code> with the query (as an inline view) that produces the set:</p> <pre><code>SELECT fx.ID1 , fy.ID2 FROM ( SELECT fa.ID1 , fa.ID2 FROM friend fa JOIN friend fb ON fb.ID1 = fa.ID2 AND fb.ID2 = fa.ID1 ) fx JOIN ( SELECT fc.ID1 , fc.ID2 FROM friend fc JOIN friend fd ON fd.ID1 = fc.ID2 AND fd.ID2 = fc.ID1 ) fy ON fy.ID1 = fx.ID2 AND fy.ID2 &lt;&gt; fx.ID1 -- eliminate rows that match LEFT JOIN friend fe ON fe.ID1 = fx.ID1 AND fe.ID2 = fy.ID2 WHERE fe.ID1 IS NULL GROUP BY fx.ID1 , fy.ID2 </code></pre> <p>(I'm thinking as long as we are guaranteed that (ID1,ID2) is unique, that this query won't generate any duplicates. And I'm thinking that this query will generate only the matches specified, and not any extra matches. Some additional test cases would be in order to confirm. If the query does produce any duplicates, then adding a <code>GROUP BY fx.ID1, fy.ID2</code> to the query would eliminate them.)</p> <p>Finally, to put those rows into the friend table, precede the query with:</p> <pre><code>INSERT INTO friend (ID1,ID2) </code></pre> <hr> <p><strong>UPDATE</strong></p> <p>The result we want returned really depends on how a "friendship" is represented.</p> <p>I was assuming that "friend" pair was represented in the <code>friend</code> table by the existence of two tuples: both <code>(a,b)</code> and (b,a) have to exist. (A friendship is formed when "a friends b", and "b friends a).</p> <p>If only one of the rows exists, it's not a real friendship, only a halfway friendship.</p> <p>I ran several test cases. It's kind of tedious working through them. I expanded the query by adding an ORDER BY to get the rows back in a deterministic order, and adding additional columns in the SELECT list, to verify the "path" (shared friend). I commented out the WHERE clause, so I could see all the potential friends.</p> <p>I did find that I needed to add a <code>GROUP BY</code> to eliminate duplicates. We can derive the <code>a-c</code> friendship from two or more shared friends e.g. <code>b</code> and <code>r</code>. Both <code>a-b + b-c</code> and <code>a-r + r-c</code> result in <code>a-c</code>.</p> <p>This is the final query I tested. It's essentially equivalent to the previous, except for the addition of the GROUP BY.</p> <pre><code>SELECT fx.ID1 , fy.ID2 -- , fx.ID1&gt;fy.ID2 AS d -- , fx.ID1 AS x1 -- , fx.ID2 As x2 -- , fy.ID1 AS y1 -- , fy.ID2 As y2 -- , fe.ID1 AS e1 -- , fe.ID2 AS e2 FROM ( SELECT fa.ID1 , fa.ID2 , fa.ID1&gt;fa.ID2 AS d FROM friend fa JOIN friend fb ON fb.ID1 = fa.ID2 AND fb.ID2 = fa.ID1 -- ORDER -- BY LEAST(fa.ID1,fa.ID2) -- , GREATEST(fa.ID1,fa.ID2) -- , fa.ID1&gt;fa.ID2 ) fx JOIN ( SELECT fc.ID1 , fc.ID2 FROM friend fc JOIN friend fd ON fd.ID1 = fc.ID2 AND fd.ID2 = fc.ID1 -- ORDER -- BY LEAST(fc.ID1,fc.ID2) -- , GREATEST(fc.ID1,fc.ID2) -- , fc.ID1&gt;fc.ID2 ) fy ON fy.ID1 = fx.ID2 AND fy.ID2 &lt;&gt; fx.ID1 -- eliminate rows that match existing row LEFT JOIN friend fe ON fe.ID1 = fx.ID1 AND fe.ID2 = fy.ID2 WHERE fe.ID1 IS NULL GROUP BY fx.ID1 , fy.ID2 ORDER BY LEAST(fx.ID1,fy.ID2) , GREATEST(fx.ID1,fy.ID2) , fx.ID1&gt;fy.ID2 </code></pre> <hr> <p>If a full friendship is represented by the existence of just one tuple "(a,b)" implies "(b,a)", then the query would need to be changed.</p> <p>The inline view query for <code>fx</code> and <code>fy</code> would need to be expanded to return the "missing" inverse tuples... if (a,b) is in the friend table, our query needs to return both (a,b) and (b,a). We'd accomplish that by doing a UNION ALL operation between two identical queries, with just the order of the columns in the SELECT list reversed. (Here, we could actually make use of UNION instead of UNION ALL to eliminate any duplicates.) The inline view query for <code>fx</code> and <code>fy</code> would be something like:</p> <pre><code>SELECT fa.ID1, fa.ID2 FROM ... UNION ALL SELECT fa.ID2, fa.ID1 FROM ... </code></pre> <p>The check to eliminate matching rows in the friend table would also need to be changed (we'd want to eliminate both (a,b) and (b,a) from the resultset if we found an existing (a,b) or (b,a) row)</p> <pre><code>ON ( fe.ID1 = fx.ID1 AND fe.ID2 = fy.ID2 ) OR ( fe.ID1 = fy.ID2 AND fe.ID2 = fx.ID1 ) </code></pre> <p>And the SELECT list and GROUP BY would need to be changed to eliminate the "extra" inverse tuple. We could use an expression like in the ORDER BY </p> <pre><code>SELECT LEAST(fx.ID1,fy.ID2) AS ID1 , GREATEST(fx.ID1,fy.ID2) AS ID2 ... GROUP BY LEAST(fx.ID1,fy.ID2) , GREATEST(fx.ID1,fy.ID2) </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POEliminate tuples with reverse relation and no primary Key
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USspencer7593
    1. USspencer7593
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POEliminate tuples with reverse relation and no primary Key
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHuge thanks for such a detailed answer. But unfortunately, this is not giving the desired result. Instead of 2 more values as I was getting, this is giving 1 more value for the number of friends for 3 persons. I still am trying to figure out where this query goes wrong. I will get back with a more detailed answer, sorry for my limitation of better explanation right now !
      singulars
      1. PO
      1. USRijul
    2. CO@Rijul: The result really depends on how a "friendship" is represented. I was assuming that "friend" pair was represented in the friend table by the existence of two tuples: both `(A,B)` and `(B,A)` have to exist. (A friendship is formed when A "friends" B, and B "friends" A). If only one of the rows exists, it's only a halfway friendship.
      singulars
      1. PO
      1. USspencer7593
    3. COThis was superb. I had totally missed the possibility of duplicates through two or more relations. This worked perfectly. Thanks a lot. I hope you also Liked solving this question, It took my 2 days of trials !
      singulars
      1. PO
      1. USRijul
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload