Ordering SQL results based on predecessor

I have the following table in my database:

create table (
    name 开发者_Python百科       varchar(25),
    value       int,
    predecessor varchar(25)
);

with sample data:

name           | value | predecessor
---------------+-------+---------------
buyingredients | 10    | null
eat            |  3    | cook
cook           | 12    | mixingredients
mixingredients |  5    | buyingredients

I want an SQL query that selects name and value, ordered so that the item with the predecessor null is first, and then the row with who's predecessor is equal to that row's name is next and so on (i.e. buyingredients, mixingredients, cook, eat).

The ordering is strictly linear - the behaviour if two rows have the same value of predecessor is undefined.

I'm struggling to find an SQL query that will produce the ordering I want. I don't really know where to start.

I'm using an Informix database, though any variant of SQL would be a useful starting point.

updated to reflect the fact the ordering is not alphabetical

In Transact-SQL with common table expressions:

WITH LinkedList (name, value, predecessor, ordering)
AS
(
    SELECT a.name, a.value, a.predecessor, 0
    FROM   YourTable a
    WHERE  a.predecessor IS NULL
    UNION ALL
    SELECT b.name, b.value, b.predecessor, c.ordering + 1
    FROM   YourTable b
    INNER JOIN LinkedList c
    ON     b.predecessor = c.name
)
SELECT d.name, d.value
FROM   LinkedList d
ORDER BY d.ordering, d.name

I don't know whether Informix has this construct, but what you are asking is in essence a recursive query, which common table expressions give you in Transact-SQL.

Informix does not support a WITH clause, much less WITH RECURSIVE. That makes those approaches inoperable. There isn't a particularly clean way of doing it. It is not entirely clear what should happen if you have two or three lists, nor is it entirely clear whether you are dealing with simple lists (the example is a list) or a more general tree structure.

However, you could create a temporary table and populate that with a loop in a stored procedure, and then select from the temporary table in an appropriate order. This is fiddly rather than dreadfully difficult. You do a breadth-first search of the table. I note that you did not give your table a name - so it is hereinafter called 'anonymous'.

CREATE TEMP TABLE Flattened
(
    Hierarchy   SERIAL,
    Level       INTEGER,
    Name        VARCHAR(25),
    Value       INTEGER,
    Predecessor VARCHAR(25)
);

CREATE TEMP TABLE Intermediate
(
    Hierarchy   SERIAL,
    Level       INTEGER,
    Name        VARCHAR(25),
    Value       INTEGER,
    Predecessor VARCHAR(25)
);

INSERT INTO Flattened(Hierarchy, Level, Name, Value, Predecessor)
   SELECT 0, 0, name, value, predecessor
     FROM Anonymous
    WHERE Predecessor IS NULL;

WHILE ...any rows were inserted into table...
    INSERT INTO Intermediate(Hierarchy, Level, Name, Value, Predecessor)
        SELECT F.Hierarchy, F.Level + 1, A.Name, A.Value, A.Predecessor
          FROM Flattened AS F, Anonymous AS A
         WHERE F.Name = A.Predecessor
           AND F.Level = (SELECT MAX(Level) FROM Flattened);
    INSERT INTO Flattened SELECT * FROM Intermediate;
    DELETE FROM Intermediate;
END WHILE

DROP TABLE Intermediate;

Now you can use:

SELECT Name, Value, Predecessor
  FROM Flattened
 ORDER BY Hierarchy, Level, Name;

The only residual tricky bit is working out how many rows were inserted. In a stored procedure, it is probably simplest to do:

SELECT COUNT(*) INTO n_count FROM Flattened;

and

LET o_count = n_count - 1;
WHILE o_count != n_count
    ...as above - two INSERT operations and a DELETE operation
    LET o_count = n_count;
    SELECT COUNT(*) INTO n_count FROM Flattened;
END WHILE;

Putting it all together, this works for me (in a logged database).

BEGIN;

CREATE TABLE Anonymous
(
     Name        VARCHAR(25),
     Value       INTEGER,
     Predecessor VARCHAR(25)
);

INSERT INTO Anonymous VALUES("buyingredients", 10, NULL);
INSERT INTO Anonymous VALUES("eat", 3, "cook");
INSERT INTO Anonymous VALUES("cook", 12, "mixingredients");
INSERT INTO Anonymous VALUES("mixingredients", 5, "buyingredients");

CREATE PROCEDURE Flatten_Anonymous()

    DEFINE old_count INTEGER;
    DEFINE new_count INTEGER;

    CREATE TEMP TABLE Flattened
    (
        Hierarchy   SERIAL,
        Level       INTEGER,
        Name        VARCHAR(25),
        Value       INTEGER,
        Predecessor VARCHAR(25)
    );

    CREATE TEMP TABLE Intermediate
    (
        Hierarchy   SERIAL,
        Level       INTEGER,
        Name        VARCHAR(25),
        Value       INTEGER,
        Predecessor VARCHAR(25)
    );

    INSERT INTO Flattened(Hierarchy, Level, Name, Value, Predecessor)
       SELECT 0, 0, name, value, predecessor
         FROM Anonymous
        WHERE Predecessor IS NULL;

    SELECT COUNT(*) INTO new_count FROM Flattened;
    LET old_count = new_count - 1;
    WHILE old_count != new_count
        INSERT INTO Intermediate(Hierarchy, Level, Name, Value, Predecessor)
            SELECT F.Hierarchy, F.Level + 1, A.Name, A.Value, A.Predecessor
              FROM Flattened AS F, Anonymous AS A
             WHERE F.Name = A.Predecessor
               AND F.Level = (SELECT MAX(Level) FROM Flattened);
        INSERT INTO Flattened SELECT * FROM Intermediate;
        DELETE FROM Intermediate;
        LET old_count = new_count;
        SELECT COUNT(*) INTO new_count FROM Flattened;
    END WHILE

    DROP TABLE Intermediate;

END PROCEDURE;

EXECUTE PROCEDURE Flatten_Anonymous();

SELECT Name, Value, Predecessor
  FROM Flattened
 ORDER BY Hierarchy, Level, Name;

DROP TABLE Flattened;

ROLLBACK;

The output is:

buyingredients     10
mixingredients      5  buyingredients
cook               12  mixingredients
eat                 3  cook

Test platform: Informix 11.70.FC2 running on MacOS X 10.6.7.

Not formally tested with multiple independent hierarchies, or with tree-structured hierarchies instead of simple lists.

I'm using an Informix database, though any variant of SQL would be a useful starting point.

I know nothing about Informix so here is a version for SQL Server. @T is table variable I use as a test table. To chain the rows I use a recursive CTE.

declare @T table
(
  name varchar(25),
  value int,
  predecessor varchar(25)
)  

insert into @T
select 'buyingredients', 10, null union all
select 'cook',           12, 'mixingredients' union all
select 'mixingredients',  5, 'buyingredients' union all
select 'eat',             3, 'cook'

;with cte as 
(
  select T.name,
         T.value,
         T.predecessor,
         1 as sortorder
  from @T as T
  where T.predecessor is null
  union all
  select T.name,
         T.value,
         T.predecessor,
         C.sortorder+1 as sortorder
  from @T as T
    inner join cte as C
      on T.predecessor = C.name
)
select C.name,
       C.value,
       C.predecessor
from cte as C
order by C.sortorder

You can try it out here: https://data.stackexchange.com/stackoverflow/q/102534/recursive-cte-to-build-a-chain

Edit

I still don't know anything about Informix but perhaps you can do something using Node DataBlade Module

I think the way to do what you want is to construct a temporary table with a "depth" field for every item, then use that depth field to order your results.