Arrays and foreign keys

Well, the two types aren't the same (one is an integer the
other an integer array,) so I wouldn't expect it to work. Note:
This shows another thing it probably should check before allowing
the constraint to be created.

I don't know if these belong in TODO, but this might
be the appropriate entry.
* Make sure that types used in foreign key constraints
are comparable.

Stephan Szabo
sszabo@bigpanda.com

On Tue, 8 Aug 2000, Kaare Rasmussen wrote:

I get exactly the same behavior; it would be really helpful if foreign key
constraints were available for array types!

Tim

Kaare Rasmussen wrote:

Seems that it's not possible to combine arrays and foreign keys ?

CREATE TABLE table1 (
fld1 integer NOT NULL,
number integer,
level integer,
PRIMARY KEY (fld1)
);

CREATE TABLE table2 (
pkey integer NOT NULL,
arvar integer[],
PRIMARY KEY (pkey),
FOREIGN KEY (arvar) REFERENCES table1(fld1)
);

This works, but the following insert complains that

ERROR: Unable to identify an operator '=' for types 'int4' and '_int4'
You will have to retype this query using an explicit cast

--
Kaare Rasmussen --Linux, spil,-- Tlf: 3816 2582
Kaki Data tshirts, merchandize Fax: 3816 2582
Howitzvej 75 �ben 14.00-18.00 Email: kar@webline.dk
2000 Frederiksberg L�rdag 11.00-17.00 Web: www.suse.dk

--
Timothy H. Keitt
National Center for Ecological Analysis and Synthesis
735 State Street, Suite 300, Santa Barbara, CA 93101
Phone: 805-892-2519, FAX: 805-892-2510
http://www.nceas.ucsb.edu/~keitt/

This is an interesting point. Originally postgres integrity rules were
based on a very general rules system where many things were possible to
specify. I'm curious about the more recent addition of referential
integrity to postgres (I know little about it), why it is such a
specific solution and is not based on the more general postgres rules
system?

There are some functions somewhere in contrib that allow you to say
whether something is somewhere within an array, which is generally
useful for an ODBMS style data model and also the example below. Ideally
it could somehow be linked into integrity checks.

"Timothy H. Keitt" wrote:

On Thu, 10 Aug 2000, Chris Bitmead wrote:

This is an interesting point. Originally postgres integrity rules were
based on a very general rules system where many things were possible to
specify. I'm curious about the more recent addition of referential
integrity to postgres (I know little about it), why it is such a
specific solution and is not based on the more general postgres rules
system?

Because unfortunately the SQL spec for referential integrity cannot really
be implemented in the current rules system (or at least not in a way that
is terribly nice). One problem is the fact that they need the option to
be deferred to end of transaction (which we still have problems with now),
plus I'm not sure that MATCH PARTIAL with referential integrity would be
possible with the rewrites without having 2^(number of key elements) rules
per action per constraint (that's the not terribly nice part). And there
are rules about not letting a piece of data get multiply changed due to
circular dependencies that you'd need to work in as well. All in all,
it's a mess.

There are some functions somewhere in contrib that allow you to say
whether something is somewhere within an array, which is generally
useful for an ODBMS style data model and also the example below. Ideally
it could somehow be linked into integrity checks.

For now, you should be able define the element in array as the equality
operator between integer and array of integers which would probably do
it.

The spec generally says that the referenced and referencing values should
be equal (well, there are exceptions more NULLs in various cases). We'd
have to decide whether we'd want to extend that to be equal, except in the
case that the referenced value is an array in which case we use in array
instead. It'd probably be fairly easy probably to make the change
assuming it's easy to tell if a column is an array.

Stephan Szabo wrote:

This is an interesting point. Originally postgres integrity rules were
based on a very general rules system where many things were possible to
specify. I'm curious about the more recent addition of referential
integrity to postgres (I know little about it), why it is such a
specific solution and is not based on the more general postgres rules
system?

Because unfortunately the SQL spec for referential integrity cannot really
be implemented in the current rules system (or at least not in a way that
is terribly nice).

So it wasn't feasible to extend the current rules system to support
these oddities, instead of implementing the specific solution?

At 10:57 AM 8/10/00 +1000, Chris Bitmead wrote:

Stephan Szabo wrote:

This is an interesting point. Originally postgres integrity rules were
based on a very general rules system where many things were possible to
specify. I'm curious about the more recent addition of referential
integrity to postgres (I know little about it), why it is such a
specific solution and is not based on the more general postgres rules
system?

Because unfortunately the SQL spec for referential integrity cannot really
be implemented in the current rules system (or at least not in a way that
is terribly nice).

So it wasn't feasible to extend the current rules system to support
these oddities, instead of implementing the specific solution?

Since Jan apparently knows more about the current rules system than anyone
else on the planet (he's done a lot of work in that area in the past), and
since he designed the RI system, my guess is that the simple answer to your
question is "yes".

- Don Baccus, Portland OR <dhogaza@pacifier.com>
Nature photos, on-line guides, Pacific Northwest
Rare Bird Alert Service and other goodies at
http://donb.photo.net.

Well, the two types aren't the same (one is an integer the
other an integer array,) so I wouldn't expect it to work. Note:

Eh, I could figure that out myself. What I'm asking for is if there is a way to
combine arrays with foreign keys?

I believe the answer for now is 'no', but did like to get it confirmed, and
also draw attention to this if someone wants to make it.

* Make sure that types used in foreign key constraints
are comparable.

And maybe
* Add foreign key constraint for arrays

--
Kaare Rasmussen --Linux, spil,-- Tlf: 3816 2582
Kaki Data tshirts, merchandize Fax: 3816 2582
Howitzvej 75 �ben 14.00-18.00 Email: kar@webline.dk
2000 Frederiksberg L�rdag 11.00-17.00 Web: www.suse.dk

Don Baccus wrote:

At 10:57 AM 8/10/00 +1000, Chris Bitmead wrote:

Stephan Szabo wrote:

This is an interesting point. Originally postgres integrity rules were
based on a very general rules system where many things were possible to
specify. I'm curious about the more recent addition of referential
integrity to postgres (I know little about it), why it is such a
specific solution and is not based on the more general postgres rules
system?

Because unfortunately the SQL spec for referential integrity cannot really
be implemented in the current rules system (or at least not in a way that
is terribly nice).

So it wasn't feasible to extend the current rules system to support
these oddities, instead of implementing the specific solution?

Since Jan apparently knows more about the current rules system than anyone
else on the planet (he's done a lot of work in that area in the past), and
since he designed the RI system, my guess is that the simple answer to your
question is "yes".

"Yes"

Rules are fired before the original query is executed. This
is because otherwise a DELETE (for example) already stamped
it's XID and CID into the max fields of the tuples to delete
and the command counter gets incremented. So the rules scans
would never be able to find them again. From the visibility
point of view they are deleted.

To make rules deferrable in this visibility system, someone
would need to remember the command ID of the original query,
and when later executing the deferred queries modify all the
scan-command ID's of those rangetable-entries, coming from
the original query, to have the original queries CID, while
leaving the others at the current.

Theoretically possible up to here, but as soon as there are
any functions invoked in that query which use SPI, it's over.

Finally there is that problem about "triggered data change
violation". Since only "changing the effective value" of an
FK or PK is considered to be a "data change", each individual
tuple must be checked for it. This cannot be told on the
query level.

I'm sure it cannot be done with the rule system. Thus we
created this "specific solution".

And it is true that with the "very general rules system" of
the "original Postgres 4.2" many things where possible to
specify. But most of them never worked until v6.4. I know
definitely, because I found it out the hard way - fixing it.
And still, many things don't work.

Take some look at the short description of the rule system
internals in the programmers guide. After that, you maybe
come to the same conclusions as I did. Otherwise correct me
by reimplementing SQL3 RI with rules.

Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#================================================== JanWieck@Yahoo.com #

On Thu, 10 Aug 2000, Kaare Rasmussen wrote:

Well, the two types aren't the same (one is an integer the
other an integer array,) so I wouldn't expect it to work. Note:

Eh, I could figure that out myself. What I'm asking for is if there is a way to
combine arrays with foreign keys?

For what you want, maybe. Probably defining an equals operator to make
the two types comparable for equality would allow the constraint to work.

I believe the answer for now is 'no', but did like to get it confirmed, and
also draw attention to this if someone wants to make it.

* Make sure that types used in foreign key constraints
are comparable.

And maybe
* Add foreign key constraint for arrays

Actually, it would be:
* Change foreign key constraint for array -> element to mean element
in array,
since the constraints seem to work on arrays (make two integer
arrays and reference them and it seems to work in my two minute test).

The question is whether or not we want to extend the spec in this way.
It would probably be easy to do, but it's definately an extension, since
the spec says that the two things should be equal, and I don't generally
think of element in array as equality. And, what do we do if neither
the in operator nor equals is defined between array and element?

Kaare Rasmussen wrote:

Well, the two types aren't the same (one is an integer the
other an integer array,) so I wouldn't expect it to work. Note:

Eh, I could figure that out myself. What I'm asking for is if there is a way to
combine arrays with foreign keys?

I believe the answer for now is 'no', but did like to get it confirmed, and
also draw attention to this if someone wants to make it.

* Make sure that types used in foreign key constraints
are comparable.

And maybe
* Add foreign key constraint for arrays

The major problem isn't that we do not have a comparision
operator for int4 vs. _int4. The bigger one is that there is
no easy way to build an index on them, and that there is no
way to define what a referential action should really do in
the case of cascaded operations.

For a primary key containing an array, the values of all
array elements of all rows must be unique and NOT NULL. So
there must be a unique index on the elements, the array
itself cannot be NULL, no element of the array can be NULL
and there must be at least one element.

And for a foreign key containing an array, what to do when ON
DELETE CASCADE is requested? DELETE the FK row? Remove the
element from the array? DELETE the row then when the array
get's empty or not?

Are these questions answered by the standard? If not, do we
want to answer them ourself and take the risk the standard
someday answers them different?

For the meantime, I suggest normalize your schema if you want
referential integrity.

Jan

--

#======================================================================#
# It's easier to get forgiveness for being wrong than for being right. #
# Let's break this rule - forgive me. #
#================================================== JanWieck@Yahoo.com #

Stephan Szabo wrote:

Actually, it would be:
* Change foreign key constraint for array -> element to mean element
in array,
since the constraints seem to work on arrays (make two integer
arrays and reference them and it seems to work in my two minute test).

The question is whether or not we want to extend the spec in this way.
It would probably be easy to do, but it's definately an extension, since
the spec says that the two things should be equal, and I don't generally
think of element in array as equality. And, what do we do if neither
the in operator nor equals is defined between array and element?

Maybe the syntax should be extended to support this concept. Thus
instead of having....

CREATE TABLE table2 (
pkey integer NOT NULL,
arvar integer[],
PRIMARY KEY (pkey),
FOREIGN KEY (arvar) REFERENCES table1(fld1)
);

We instead have....

CREATE TABLE table2 (
pkey integer NOT NULL,
arvar integer[],
PRIMARY KEY (pkey),
FOREIGN KEY (arvar) REFERENCES table1(fld1[])
);

The extra [] meaning that it references a member of fld1, but we don't
know which. That would leave strict equality intact, but still provide
this very useful extension.

On Fri, 11 Aug 2000, Chris Bitmead wrote:

Stephan Szabo wrote:

Actually, it would be:
* Change foreign key constraint for array -> element to mean element
in array,
since the constraints seem to work on arrays (make two integer
arrays and reference them and it seems to work in my two minute test).

The question is whether or not we want to extend the spec in this way.
It would probably be easy to do, but it's definately an extension, since
the spec says that the two things should be equal, and I don't generally
think of element in array as equality. And, what do we do if neither
the in operator nor equals is defined between array and element?

Maybe the syntax should be extended to support this concept. Thus
instead of having....

CREATE TABLE table2 (
pkey integer NOT NULL,
arvar integer[],
PRIMARY KEY (pkey),
FOREIGN KEY (arvar) REFERENCES table1(fld1)
);

We instead have....

CREATE TABLE table2 (
pkey integer NOT NULL,
arvar integer[],
PRIMARY KEY (pkey),
FOREIGN KEY (arvar) REFERENCES table1(fld1[])
);

The extra [] meaning that it references a member of fld1, but we don't
know which. That would leave strict equality intact, but still provide
this very useful extension.

Actually, it's the other way around right, arvar is the array, fld1 is
just an integer, so I'd guess
FOREIGN KEY (arvar[]) REFERENCES table1(fld1)
would be it.

There are the issues of the referential integrity actions. If I were
to hazard a guess at the behavior one would expect from this, I'd guess...

ON UPDATE CASCADE - The particular referencing element changes.
ON UPDATE SET NULL - The particular referencing element is set null
ON UPDATE SET DEFAULT - For now the same as set null since i don't think
array elements can default
ON UPDATE NO ACTION|RESTRICT - disallow changing of the value if there
exists an array element reference
ON DELETE CASCADE - Remove referencing element, drop row if the array
is emptied
ON DELETE ... - Pretty much as on update.

But (and this is a really big but) -- This is going to be slow as hell,
and perhaps slower than that, since for any update or delete, you would
have to go through every row on the other table doing the array in until
we can get an index on all the elements in all of the arrays.

Then there are other problematic issues like:
{1,2,3} -> {1,3,4} -- Is this a delete of 2 and an insert of 4 or
two updates?
{1,2,3} -> {3,4,1} -- What about this one?

---
This of course brings up, well, what about an element that wants to
reference an array, or what about arrays that you want to say, this array
must be a subset of the referenced array, but we can get into that
later... :)

Stephan Szabo wrote:

But (and this is a really big but) -- This is going to be slow as hell,
and perhaps slower than that, since for any update or delete, you would
have to go through every row on the other table doing the array in until
we can get an index on all the elements in all of the arrays.

Then there are other problematic issues like:
{1,2,3} -> {1,3,4} -- Is this a delete of 2 and an insert of 4 or
two updates?
{1,2,3} -> {3,4,1} -- What about this one?

Probably the only useful use of arrays in conjunction with referential
integrity is to treat the array as an unordered collection.

{1,2,3} -> {1,3,4} -- Is a delete of 2 and an insert of 4.

{1,2,3} -> {3,4,1} -- Is a delete of 2 and an insert of 4.

For that reason I'm not sure that it has to be slow. When an array is
updated find the elements that have changed (according to the above
definition of changed) and only check on those ones.

On Fri, 11 Aug 2000, Chris Bitmead wrote:

Stephan Szabo wrote:

But (and this is a really big but) -- This is going to be slow as hell,
and perhaps slower than that, since for any update or delete, you would
have to go through every row on the other table doing the array in until
we can get an index on all the elements in all of the arrays.

Then there are other problematic issues like:
{1,2,3} -> {1,3,4} -- Is this a delete of 2 and an insert of 4 or
two updates?
{1,2,3} -> {3,4,1} -- What about this one?

Probably the only useful use of arrays in conjunction with referential
integrity is to treat the array as an unordered collection.

{1,2,3} -> {1,3,4} -- Is a delete of 2 and an insert of 4.

{1,2,3} -> {3,4,1} -- Is a delete of 2 and an insert of 4.

For that reason I'm not sure that it has to be slow. When an array is
updated find the elements that have changed (according to the above
definition of changed) and only check on those ones.

Remember, his structure was the array referenced the integer, not the
other way around. So, if you say, delete one of the integers from the
referenced table you need to find any array element that referenced that
integer in all rows of the referencing table, that's the slow part.

Stephan Szabo wrote:

Remember, his structure was the array referenced the integer, not the
other way around. So, if you say, delete one of the integers from the
referenced table you need to find any array element that referenced that
integer in all rows of the referencing table, that's the slow part.

Ah yes. I guess that's a problem crying out for a new indexing solution.

On Fri, 11 Aug 2000, Chris Bitmead wrote:

Stephan Szabo wrote:

Remember, his structure was the array referenced the integer, not the
other way around. So, if you say, delete one of the integers from the
referenced table you need to find any array element that referenced that
integer in all rows of the referencing table, that's the slow part.

Ah yes. I guess that's a problem crying out for a new indexing solution.

Yeah, and it would probably need some associated cost estimation stuff,
since you'd need to know something about the element value rarity
instead of the array value rarity if you wanted to make intelligent guesses
as to whether the index scan is better than the sequential scan.

You could kind of store the information in a secondary relation, but that
seems like a major point of locking contention, plus it'd either end up
being the reverse index (element->array of oids) or the normalized,
element->oid rows at which point are you better off than if you
normalized the original relation.

Does any version of SQL have meaningful arrays, and do they actually
specify any behavior for this? Or for that matter, what about other
dbs. What do they do with these cases...

Stephan Szabo wrote:

Ah yes. I guess that's a problem crying out for a new indexing solution.

Yeah, and it would probably need some associated cost estimation stuff,
since you'd need to know something about the element value rarity
instead of the array value rarity if you wanted to make intelligent guesses
as to whether the index scan is better than the sequential scan.

You could probably do some kind of quick hack with regular indexes, just
have more than one entry for each tuple when indexing arrays.

You could kind of store the information in a secondary relation, but that
seems like a major point of locking contention, plus it'd either end up
being the reverse index (element->array of oids) or the normalized,
element->oid rows at which point are you better off than if you
normalized the original relation.

Does any version of SQL have meaningful arrays, and do they actually
specify any behavior for this? Or for that matter, what about other
dbs. What do they do with these cases...

All ODBMSes by necessity support arrays. I'm not aware of any attempt to
index them in this way or support referential integrity. It would
probably be a postgresql first.

On Fri, 11 Aug 2000, Chris Bitmead wrote:

You could probably do some kind of quick hack with regular indexes, just
have more than one entry for each tuple when indexing arrays.

Maybe, it depends on how the code is structured. Plus, it may mean
changes to the stuff that handles arrays as well, since you're not
indexing the data value, but the set (actually, not a set i guess since
there's nothing preventing duplicates) that's there, so {1,2}->{1,3} means
an index delete for the 2 and index insert for the 3.

You could kind of store the information in a secondary relation, but that
seems like a major point of locking contention, plus it'd either end up
being the reverse index (element->array of oids) or the normalized,
element->oid rows at which point are you better off than if you
normalized the original relation.

Does any version of SQL have meaningful arrays, and do they actually
specify any behavior for this? Or for that matter, what about other
dbs. What do they do with these cases...

All ODBMSes by necessity support arrays. I'm not aware of any attempt to
index them in this way or support referential integrity. It would
probably be a postgresql first.

Well, one of Jan's concerns was defining all of this behavior in a way
that was different from a current or reasonably likely spec (I'd guess he
was most concerned with SQL, but...).

I think perhaps we're overreaching for the moment. The ri stuff isn't
even completely finished for the cases that are specified by the SQL
specification, and there are still problems with what's there, so we
should probably get it working with an eye towards this possible
direction.

And whatever is done should leave arrays with the same meaning they
currently have for people who use them in other ways. I'm almost
thinking that we want a set rather than an array here where sets have
different semantics that make more sense for this sort of behavior.
It just seems to make more sense to me that a set would be indexed
by its elements than array, since position is supposed to be meaningful
for arrays, and that set(1,2) is equal to the set(2,1) whereas the
indexes aren't. Of course, I guess that's not much different from
the normalized table case.

Stephan Szabo wrote:

And whatever is done should leave arrays with the same meaning they
currently have for people who use them in other ways. I'm almost
thinking that we want a set rather than an array here where sets have
different semantics that make more sense for this sort of behavior.
It just seems to make more sense to me that a set would be indexed
by its elements than array, since position is supposed to be meaningful
for arrays, and that set(1,2) is equal to the set(2,1) whereas the
indexes aren't. Of course, I guess that's not much different from
the normalized table case.

Probably a collection rather than a set. No sense in excluding
duplicates.

What often happens in an ODBMS is that some general purpose collection
classes are written based on arrays. A simple example would be...

class Set<type> {
RefArray<type> array;
}

Where RefArray<Object> gets mapped to something like oid[] in the odbms.
Then when you want a class that has a set..

class Person {
Set<Car> owns;
}

which gets flattened and mapped to
create table Person (owns oid[]);

The set semantics being enforced by the language bindings.

On Fri, 11 Aug 2000, Chris Bitmead wrote:

Stephan Szabo wrote:

And whatever is done should leave arrays with the same meaning they
currently have for people who use them in other ways. I'm almost
thinking that we want a set rather than an array here where sets have
different semantics that make more sense for this sort of behavior.
It just seems to make more sense to me that a set would be indexed
by its elements than array, since position is supposed to be meaningful
for arrays, and that set(1,2) is equal to the set(2,1) whereas the
indexes aren't. Of course, I guess that's not much different from
the normalized table case.

Probably a collection rather than a set. No sense in excluding
duplicates.

Probably not, at least for the referencing thing anyway. (To do this
to a referenced object would require that the values in all elements
of all the sets be unique, not just within one since the spec we're
going with assumes unique key values.)

What often happens in an ODBMS is that some general purpose collection
classes are written based on arrays. A simple example would be...

class Set<type> {
RefArray<type> array;
}

Where RefArray<Object> gets mapped to something like oid[] in the odbms.
Then when you want a class that has a set..

class Person {
Set<Car> owns;
}

which gets flattened and mapped to
create table Person (owns oid[]);

The set semantics being enforced by the language bindings.

Right, but doing something like this ri stuff would require some
collection semantics being enforced by the database, since we'd
be treating this array as a set in some cases, even if it wasn't
a set. It might not matter so much for this case, but let's say
that at some point someone wanted to extend general purpose triggers
in some similar fashion. Then it would become important whether
something was a delete or update, and treating an array as a set
in that case would be a bad idea.

Well, the two types aren't the same (one is an integer the
other an integer array,) so I wouldn't expect it to work. Note:

Eh, I could figure that out myself. What I'm asking for is if there is a way to
combine arrays with foreign keys?

I believe the answer for now is 'no', but did like to get it confirmed, and
also draw attention to this if someone wants to make it.

* Make sure that types used in foreign key constraints
are comparable.

And maybe
* Add foreign key constraint for arrays

Added to TODO.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

And maybe
* Add foreign key constraint for arrays

Actually, it would be:
* Change foreign key constraint for array -> element to mean element
in array,

TODO updated.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

There is some stuff which last time I looked is in contrib that allows
queries to test if something is in an array. Something vaguely like
SELECT * from part, box where IN(part.num, box.array).

Having this integrated in the foreign key stuff would certainly be
important for object databases, which by definition use these kinds of
arrays.

Bruce Momjian wrote:

I think that was the agreement on the best way to do it (although the
operator is even easier looking, just replace = with whatever the operator
is.). This would mean moving the array code from contrib into the real
source tree probably though, or having the foreign key stuff figure out if
you had it installed and use it only in those cases.

On Fri, 13 Oct 2000, Chris wrote: