# Strategy to find the unique bivariate polynomials

I have table that stores Tutte polynomials of a large set of graphs. These are bivariate polynomials with integer coefficients. An example of a polynomial taken from Wikipedia is: Since the polynomial may be "sparse", I've saved the data for each graph in an SQLITE table as:

``````CREATE TABLE IF NOT EXISTS tutte_polynomial(
graph_id   INTEGER,
x_degree   UNSIGNED INTEGER,
y_degree   UNSIGNED INTEGER,
coeff      INTEGER
);
``````

What I'd like to do now is determine the number of unique polynomials over the `graph_id`. When my database was small, I used a python script to store each polynomial as a tuple in a dictionary - this solution runs out of memory for larger databases.

• This is my first post on this SE. If I've inadvertently violated any etiquette or this isn't the right place for this question, please let me know and I'll try to rectify any problems! – Hooked Aug 1 '14 at 18:42
• What is the definition of "unique polynomial over a graph"? Do you mean that 2 graphs may have the same polynomial (so these 2 would count as 1)? – ypercubeᵀᴹ Aug 1 '14 at 18:49
• @ypercube Yes. Two polynomials are the same if they have the same coefficients for each degree. I want to find the number of unique polynomials in the database. – Hooked Aug 1 '14 at 19:02
• I've seen similar questions for other DBMS. Let me check if I can find the links. – ypercubeᵀᴹ Aug 1 '14 at 19:03
• This is a similar question but I doubt it would be of much help, as it is for SQL-Server: How to find parent rows that have indentical sets of child rows? – ypercubeᵀᴹ Aug 1 '14 at 19:26

The number of polynomials is the number of distinct `graph_id` values. (You probably have a separate table for graphs; in this case, the `SELECT DISTINCT` subqueries can be replaced with `SELECT graph_id FROM graph`.)

To count unique polynomials, we exclude any that are duplicates.

A polynomial is a duplicate if there exists any other polynomial with a smaller ID (the smallest ID would be the non-duplicate) and with the same coefficients.

Two polynomials have the same coefficients if there are not any differences in the possible x/y/coefficient combinations for both, i.e., for each row of one polynomial, the same row must exist for the other polynomial. In other words, there must not exist any row that does not have a match for the other polynomial.

And now that we have the description in the language of set theory, we can translate it directly into SQL. (I've used compound SELECTs for the innermost comparisons to avoid yet another level of negated subquery lookups.)

``````SELECT COUNT(*)
FROM (SELECT DISTINCT graph_id
FROM tutte_polynomial) AS a
WHERE NOT EXISTS (SELECT 1
FROM (SELECT DISTINCT graph_id
FROM tutte_polynomial) AS b
WHERE b.graph_id < a.graph_id
AND NOT EXISTS (SELECT x_degree, y_degree, coeff
FROM tutte_polynomial
WHERE graph_id = a.graph_id
EXCEPT
SELECT x_degree, y_degree, coeff
FROM tutte_polynomial
WHERE graph_id = b.graph_id)
AND NOT EXISTS (SELECT x_degree, y_degree, coeff
FROM tutte_polynomial
WHERE graph_id = b.graph_id
EXCEPT
SELECT x_degree, y_degree, coeff
FROM tutte_polynomial
WHERE graph_id = a.graph_id))
``````

If computing the count dynamically is too slow, you could try to create a temporary table that contains the data in a format that is easier to count:

``````CREATE TABLE polys_as_string AS
SELECT group_concat(data)
FROM (SELECT graph_id,
x_degree || '|' || y_degree || '|' coeff AS data
FROM tutte_polynomial
ORDER BY graph_id, x_degree, y_degree)
GROUP BY graph_id;

CREATE INDEX polys_as_string_index on polys_as_string(data);

SELECT COUNT(DISTINCT data) FROM polys_as_string;
``````
• Thank you for the well thought out answer, breaking it down really helped me understand the query. While it works as advertised with a low memory overhead (and thus I'll accept), it takes MUCH longer to complete. On a small case using my old method it takes 2 seconds, with your code it takes about 90 minutes. Sadly, I'll have to find another way to compute the distinct items. Is it because of the inner loops? – Hooked Aug 3 '14 at 5:23
• You need an index on `graph_id`. – CL. Aug 3 '14 at 7:05
• Even with an index on `graph_id` the performance is terrible. Right now, I've found a solution by dumping the data to disk and sorting the text keys externally. This avoids the memory overhead of the python solution at the expense of temp disk space. If you like, I can upload a sample database for you to verify this, it is possible I'm missing something obvious. – Hooked Aug 3 '14 at 15:40
• @Hooked: Note that conventionally, by accepting CL's answer instead of just up-voting it you are advertising to the rest of the community that you are no longer interested in seeing alternative solutions and answers. Many (most) of us don't even look at questions with accepted answers unless we are particularly interested in seeing the accepted solution. – Pieter Geerkens Aug 3 '14 at 15:55
• @PieterGeerkens point noted. I'm removing my checkmark since the answer, while pedagogic, is not useful for my case. – Hooked Aug 3 '14 at 15:58

Amend your table definition as following to add two additional indices (My apologies for the SQL Server syntax - it's all I have here at the moment):

``````CREATE TABLE IF NOT EXISTS tutte_polynomial(
graph_id   INTEGER,
x_degree   UNSIGNED INTEGER,
y_degree   UNSIGNED INTEGER,
coeff      INTEGER

,primary key clustered (graph_id,x_degree,y_degree,coeff)

,unique nonclustered(x_degree,y_degree,coeff,graph_id)
);
``````

and try this sql:

``````SELECT count(*)
FROM (
SELECT DISTINCT
x_degree,y_degree,coeff
FROM tutte_polynomial
) as T;
``````

Update: Here is the SQLLite syntax to add the two additional indices:

``````CREATE UNIQUE INDEX if not exists PK_tutte_polynomial
on tutte_polynomial(graph_id,x_degree,y_degree,coeff);

CREATE UNIQUE INDEX if not exists AK_tutte_polynomial
on tutte_polynomial(x_degree,y_degree,coeff,graph_idx);
``````