2

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:

enter image description here

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
3

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
0

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);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.