index.md (5932B)
1 --- 2 title: "“Friends” (Undirected Graph Connections) in Rails" 3 date: 2021-06-09T00:00:00+00:00 4 draft: false 5 canonical_url: https://www.viget.com/articles/friends-undirected-graph-connections-in-rails/ 6 featured: true 7 exclude_music: true 8 references: 9 - title: "Storing graphs in the database: SQL meets social network - Inviqa" 10 url: https://inviqa.com/blog/storing-graphs-database-sql-meets-social-network 11 date: 2024-01-03T21:44:24Z 12 file: inviqa-com-kztbkj.txt 13 --- 14 15 No, sorry, not THOSE friends. But if you're interested in how to do 16 some graph stuff in a relational database, SMASH that play button and 17 read on. 18 19 <!--more--> 20 21 <audio controls src="/elsewhere/friends-undirected-graph-connections-in-rails/friends.mp3"></audio> 22 23 My current project is a social network of sorts, and includes the 24 ability for users to connect with one another. I've built this 25 functionality once or twice before, but I've never come up with a 26 database implementation I was perfectly happy with. This type of 27 relationship is perfect for a [graph 28 database](https://en.wikipedia.org/wiki/Graph_database), but we're 29 using a relational database and introducing a second data store 30 wouldn't be worth the overhead. 31 32 The most straightforward implementation would involve a join model 33 (`Connection` or somesuch) with two foreign key columns pointed at the 34 same table (`users` in our case). When you want to pull back a user's 35 contacts, you'd have to query against both foreign keys, and then pull 36 back the opposite key to retrieve the list. Alternately, you could store 37 connections in both directions and hope that your application code 38 always inserts the connections in pairs (spoiler: at some point, it 39 won't). 40 41 But what if there was a better way? I stumbled on [this article that 42 talks through the problem in 43 depth](https://inviqa.com/blog/storing-graphs-database-sql-meets-social-network), 44 and it led me down the path of using an SQL view and the 45 [`UNION`](https://www.postgresqltutorial.com/postgresql-union/) 46 operator, and the result came together really nicely. Let's walk 47 through it step-by-step. 48 49 First, we'll model the connection between two users: 50 51 ```ruby 52 class CreateConnections < ActiveRecord::Migration[6.1] 53 def change 54 create_table :connections do |t| 55 t.references :sender, null: false 56 t.references :receiver, null: false 57 58 t.timestamps 59 end 60 61 add_foreign_key :connections, :users, column: :sender_id, on_delete: :cascade 62 add_foreign_key :connections, :users, column: :receiver_id, on_delete: :cascade 63 64 add_index :connections, 65 "(ARRAY[least(sender_id, receiver_id), greatest(sender_id, receiver_id)])", 66 unique: true, 67 name: :connection_pair_uniq 68 end 69 end 70 ``` 71 72 I chose to call the foreign keys `sender` and `receiver`, not that I 73 particularly care who initiated the connection, but it seemed better 74 than `user_1` and `user_2`. Notice the index, which ensures that a 75 sender/receiver pair is unique *in both directions* (so if a connection 76 already exists where Alice is the sender and Bob is the receiver, we 77 can't insert a connection where the roles are reversed). Apparently 78 Rails has supported [expression-based 79 indices](https://bigbinary.com/blog/rails-5-adds-support-for-expression-indexes-for-postgresql) 80 since version 5. Who knew! 81 82 With connections modeled in our database, let's set up the 83 relationships between user and connection. In `connection.rb`: 84 85 ```ruby 86 belongs_to :sender, class_name: "User" 87 belongs_to :receiver, class_name: "User" 88 ``` 89 90 In `user.rb`: 91 92 ```ruby 93 has_many :sent_connections, 94 class_name: "Connection", 95 foreign_key: :sender_id 96 has_many :received_connections, 97 class_name: "Connection", 98 foreign_key: :receiver_id 99 ``` 100 101 Next, we'll turn to the 102 [Scenic](https://github.com/scenic-views/scenic) gem to create a 103 database view that normalizes sender/receiver into user/contact. Install 104 the gem, then run `rails generate scenic:model user_contacts`. That'll 105 create a file called `db/views/user_contacts_v01.sql`, where we'll put 106 the following: 107 108 ```sql 109 SELECT sender_id AS user_id, receiver_id AS contact_id 110 FROM connections 111 UNION 112 SELECT receiver_id AS user_id, sender_id AS contact_id 113 FROM connections; 114 ``` 115 116 Basically, we're using the `UNION` operator to merge two queries 117 together (reversing sender and receiver), then making the result 118 queryable via a virtual table called `user_contacts`. 119 120 Finally, we'll add the contact relationships. In `user_contact.rb`: 121 122 ```ruby 123 belongs_to :user 124 belongs_to :contact, class_name: "User" 125 ``` 126 127 And in `user.rb`, right below the 128 `sent_connections`/`received_connections` stuff: 129 130 ```ruby 131 has_many :user_contacts 132 has_many :contacts, through: :user_contacts 133 ``` 134 135 And that's it! You'll probably want to write some validations and unit 136 tests but I can't give away all my tricks (or all of my client's 137 code). 138 139 Here's our friendship system in action: 140 141 ``` 142 [1] pry(main)> u1, u2 = User.first, User.last 143 => [#<User id: 1 first_name: "Ross" …>, #<User id: 7 first_name: "Rachel" …>] 144 [2] pry(main)> u1.sent_connections.create(receiver: u2) 145 => #<Connection:0x00007f813cde5f70 146 id: 1, 147 sender_id: 1, 148 receiver_id: 7> 149 [3] pry(main)> UserContact.all 150 => [#<UserContact:0x00007f813ccbefc0 user_id: 7, contact_id: 1>, 151 #<UserContact:0x00007f813cca40f8 user_id: 1, contact_id: 7>] 152 [4] pry(main)> u1.contacts 153 => [#<User id: 7 first_name: "Rachel" …>] 154 [5] pry(main)> u2.contacts 155 => [#<User id: 1 first_name: "Ross" …>] 156 [6] pry(main)> # they're lobsters 157 [7] pry(main)> 158 ``` 159 160 So there it is, a simple, easily queryable vertex/edge implementation in 161 a vanilla Rails app. I hope you have a great day, week, month, and even 162 year. 163 164 ------------------------------------------------------------------------ 165 166 [Network Diagram Vectors by 167 Vecteezy](https://www.vecteezy.com/free-vector/network-diagram) 168 169 [*"I'll Be There for You" (Theme from 170 Friends)*](https://archive.org/details/tvtunes_31736) © 1995 The 171 Rembrandts