SQL help requested - "linked list"

#1

Hi Everyone,

I have a query I'm trying to do, and with my limited SQL knowledge I
don't know how to go about it.

Here's a simplified description of my challenge. I have data in a table
that forms sets you might describe as singly-linked lists. For example,
the table contains columns ID and NEXTID, where NEXTID points to the ID
of some other row. The linked list ends when NEXTID has a zero value.

Given one of the ID values (they're unique), I want to select the IDs
that occur before and after in that particular linked list. In a
differnet language I would approach this using a recursive function. Is
this possible in SQL?

-Mia

#2

"Mia" <nospam (AT) cox (DOT) net> wrote

Quote:

Hi Everyone,

I have a query I'm trying to do, and with my limited SQL knowledge I
don't know how to go about it.

Here's a simplified description of my challenge. I have data in a table
that forms sets you might describe as singly-linked lists. For example,
the table contains columns ID and NEXTID, where NEXTID points to the ID
of some other row. The linked list ends when NEXTID has a zero value.

Given one of the ID values (they're unique), I want to select the IDs
that occur before and after in that particular linked list. In a
differnet language I would approach this using a recursive function. Is
this possible in SQL?

select id as prev_id
from sometable
where nextid = ?
;

select nextid as next_id
from sometable
where id = ?
;

Am I missing something?

#3

Thanks Bob,

In my mind I was thinking one thing but I did not state it very well. I
want to select not just the immediate previous and next IDs, but all the
ID's - the previous to the previous and the next of the next, and so on,
all the way to the ends of the list.

-Mia

#4

"Mia" <nospam (AT) cox (DOT) net> wrote

Quote:

Thanks Bob,

In my mind I was thinking one thing but I did not state it very well. I
want to select not just the immediate previous and next IDs, but all the
ID's - the previous to the previous and the next of the next, and so on,
all the way to the ends of the list.

In that case, the answer will depend on the dbms you are using. In general,
SQL does not support recursive queries; although, many products do.

I assume you cannot guarantee (nextid > id) for all rows in each table. I
suggest you consider a solution that directly models order using ordered
values instead of recreating physical order logically.

#5

Mia <nospam (AT) cox (DOT) net> wrote

Quote:

Hi Everyone,

I have a query I'm trying to do, and with my limited SQL knowledge I
don't know how to go about it.

Here's a simplified description of my challenge. I have data in a table
that forms sets you might describe as singly-linked lists. For example,
the table contains columns ID and NEXTID, where NEXTID points to the ID
of some other row. The linked list ends when NEXTID has a zero value.

Given one of the ID values (they're unique), I want to select the IDs
that occur before and after in that particular linked list. In a
differnet language I would approach this using a recursive function. Is
this possible in SQL?

-Mia

What database are you using? In Oracle and DB2 you can express
recursion. I'm only familiar with DB2, so here's one variant:

create table list (
id int not null primary key,
nextid int
);

-- chain 1
insert into list (id, nextid) values
(1,2), (2,3), (3,9), (9,14);
insert into list (id) values (14);

-- chain 2
insert into list (id, nextid) values
(6,12), (12,13), (13,19), (19,24);
insert into list (id) values (24);

-- retrive chain for id = 3

with before_chain (id, seq) as (
values (3,0)
union all
select l.id,seq-1 from before_chain c, list l where l.nextid =
c.id
), after_chain (id, seq) as (
values (3,0)
union all
select nextid,seq+1 from after_chain c, list l where l.id = c.id
) select * from before_chain
union
select * from after_chain where id is not null
order by 2

ID SEQ
----------- -----------
SQL0347W The recursive common table expression "JON.AFTER_CHAIN" may
contain
an infinite loop. SQLSTATE=01605

1 -2
2 -1
3 0
9 1
14 2

5 record(s) selected with 1 warning messages printed.

HTH
/Lennart

#6

Thanks again Bob,

I'm using Oracle.

I don't actually care about the order. I just want to get the IDs.
I'm thinking I might want to know which IDs occur pervious versus which
ones occur after, but that's not a requirement in my case.

-Mia

Bob Badour wrote:

Quote:

"Mia" <nospam (AT) cox (DOT) net> wrote

Thanks Bob,

In my mind I was thinking one thing but I did not state it very well. I
want to select not just the immediate previous and next IDs, but all the
ID's - the previous to the previous and the next of the next, and so on,
all the way to the ends of the list.

In that case, the answer will depend on the dbms you are using. In general,
SQL does not support recursive queries; although, many products do.

I assume you cannot guarantee (nextid > id) for all rows in each table. I
suggest you consider a solution that directly models order using ordered
values instead of recreating physical order logically.

#7

Lennart Jonsson wrote:

Quote:

Mia <nospam (AT) cox (DOT) net> wrote

Hi Everyone,

I have a query I'm trying to do, and with my limited SQL knowledge I
don't know how to go about it.

Here's a simplified description of my challenge. I have data in a table
that forms sets you might describe as singly-linked lists. For example,
the table contains columns ID and NEXTID, where NEXTID points to the ID
of some other row. The linked list ends when NEXTID has a zero value.

Given one of the ID values (they're unique), I want to select the IDs
that occur before and after in that particular linked list. In a
differnet language I would approach this using a recursive function. Is
this possible in SQL?

-Mia

What database are you using? In Oracle and DB2 you can express
recursion. I'm only familiar with DB2, so here's one variant:

create table list (
id int not null primary key,
nextid int
);

-- chain 1
insert into list (id, nextid) values
(1,2), (2,3), (3,9), (9,14);
insert into list (id) values (14);

-- chain 2
insert into list (id, nextid) values
(6,12), (12,13), (13,19), (19,24);
insert into list (id) values (24);

-- retrive chain for id = 3

with before_chain (id, seq) as (
values (3,0)
union all
select l.id,seq-1 from before_chain c, list l where l.nextid =
c.id
), after_chain (id, seq) as (
values (3,0)
union all
select nextid,seq+1 from after_chain c, list l where l.id = c.id
) select * from before_chain
union
select * from after_chain where id is not null
order by 2

ID SEQ
----------- -----------
SQL0347W The recursive common table expression "JON.AFTER_CHAIN" may
contain
an infinite loop. SQLSTATE=01605

1 -2
2 -1
3 0
9 1
14 2

5 record(s) selected with 1 warning messages printed.

HTH
/Lennart

Thanks Lennart!

Thats seems to do what I want. Now, if I could just figure out HOW.
Can someone help out with an Oracle equivalent?

-Mia

#8

Mia <nospam (AT) cox (DOT) net> wrote

Quote:

Lennart Jonsson wrote:
Mia <nospam (AT) cox (DOT) net> wrote

[...]

Quote:

Thanks Lennart!

Thats seems to do what I want. Now, if I could just figure out HOW.
Can someone help out with an Oracle equivalent?

I cant help you there, but I think the construct is called CONNECT BY.
Try google for that.

/Lennart

[...]

#9

"Mia" <nospam (AT) cox (DOT) net> wrote

Quote:

Thanks again Bob,

I'm using Oracle.

As I recall, the Oracle syntax for expressing recursion uses a CONNECT BY
clause.

Quote:

I don't actually care about the order. I just want to get the IDs.

Au contraire. If you want to get the IDs that come before or to get the IDs
that come after a particular ID, you care only about order.

What, if not implicit order, does the juxtaposition of ID and NEXTID
provide?

One must ask: What does this implicit order mean? How does it arise in the
first place? If a human puts the rows into some order, upon what information
does the human base the decisions? Can one represent this information
directly?

An ID/NEXTID relation might be the best possible way to model this data, and
one must know all of the business requirements to decide. I think the
decision is sufficiently suspect, however, to justify additional scrutiny. I
would definitely consider it a decision of last resort.

I am basing these comments on your description of the data as a linked list.
I assume from this that each ID has at most one immediate successor and at
most one immediate predecessor. I also assume cycles are prohibited. The
constraints for unique immediate predecessors and successors are easy. How
are you going to declare the constraint prohibiting cycles? If you do not
prohibit cycles, how do you expect your proposed queries to react in the
presence of cycles?

Quote:

I'm thinking I might want to know which IDs occur pervious versus which
ones occur after, but that's not a requirement in my case.

Isn't that exactly the question you started with? Am I missing something?

Quote:

-Mia

Bob Badour wrote:
"Mia" <nospam (AT) cox (DOT) net> wrote

Thanks Bob,

In my mind I was thinking one thing but I did not state it very well. I
want to select not just the immediate previous and next IDs, but all the
ID's - the previous to the previous and the next of the next, and so on,
all the way to the ends of the list.

In that case, the answer will depend on the dbms you are using. In
general,
SQL does not support recursive queries; although, many products do.

I assume you cannot guarantee (nextid > id) for all rows in each table.
I
suggest you consider a solution that directly models order using ordered
values instead of recreating physical order logically.

#10

Quote:

Given one of the ID values (they're unique), I want to select the
IDs

that occur before and after in that particular linked list. In a
differnet language I would approach this using a recursive function.
Is this possible in SQL? <<

Yes, but very ugly.

1) Use a cursor and travel up and down the list, like a proceudral
language

2) Use a nested sets model for trees (google it) and allow only one
child per parent node.