Finding Circular Dominance (A beats B beats C beats A) using SQL/PGQ

Circular Dominance, or more commonly known as Circle of Parity in sports contexts, demonstrates that rankings or competitive relationships aren’t always linear - just because Team A is better than Team B, and Team B is better than Team C, it doesn’t necessarily mean Team A is better than Team C.

Sometimes this is also referred to as a non-transitive relationship. The “non-transitive” part is important. Transitivity would mean that if A > B and B > C, then A must be better than C. But in Circular Dominance this is not true. This concept is sometimes compared to the game Rock, Paper, Scissors, which is probably the most well-known example of an intransitive relationship, where rock beats scissors, scissors beats paper, and paper beats rock.


In the above example Austin beats Boston, Boston beats Cleveland, but Cleveland also beats Austin. So we can not say that Austin is better than Cleveland because the transitivity does not hold true in this case.

Finding Circular Dominance in a dataset of tournaments can be tricky using procedural programing languages or even using SQL. However this problem is easily solvable SQL/PGQ or GQL.

Let’s say you have a table called matches with columns winner and loser. Here’s how you can detect cycles using SQL/PGQ or GQL:

Let’s create some sample data:

create table teams (team_name varchar(80));
create table matches (match_id  NUMBER GENERATED by default on null as IDENTITY, winner varchar(80), loser varchar(80));
insert into teams values ('austin'), ('boston'), ('cleveland'), ('dover'), ('emeryville'), ('fremont');
insert into matches(winner, loser) values ('austin', 'boston'), ('boston', 'cleveland'), ('cleveland', 'austin'), ('dover', 'emeryville'), ('emeryville', 'fremont');

Next let’s create a Property Graph as following:

CREATE or replace PROPERTY GRAPH dominance_graph
VERTEX TABLES (
 teams KEY (team_name) PROPERTIES ARE ALL COLUMNS
)
EDGE TABLES (
 matches as team_wins_against
 KEY (match_id) 
 SOURCE KEY (winner ) REFERENCES teams(team_name)
 DESTINATION KEY (loser) REFERENCES teams(team_name)
 PROPERTIES ARE ALL COLUMNS
);

Now let’s query the Property Graph:

select team1_name || ' > ' || team2_name || ' > ' || team3_name || ' > ' || team4_name as circular_dominance
from GRAPH_TABLE(dominance_graph
match (team1 is teams) - [e1 is team_wins_against] -> (team2 is teams)
    - [e2 is team_wins_against] -> (team3 is teams)
    - [e3 is team_wins_against] -> (team4 is teams)
where team1.team_name = team4.team_name
COLUMNS ( team1.team_name as team1_name
        --  , e1.match_id as match_id
          , team2.team_name as team2_name
          , team3.team_name as team3_name
          , team4.team_name as team4_name
          )
);

Running the above SQL/PGQ query would return: