Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

PostgreSQL: Checking occurence of array elements in another array

postgresql array

This topic has been archived. This means that you cannot reply to this topic.
13 replies to this topic

#1 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 15 October 2015 - 09:26 AM

Given a one-dimensional array named A of length X, and a two-dimensional array named B with x one-dimensional arrays inside of different lengths, I want to find out using SQL if all elements of A can be found in B, such that each sub-array in B contains 1 element from A, and all elements of A are divided evenly throughout B. It's not about putting elements into B but checking if the elements of A can already be found in B using these rules.

 

This sounds and is a bit complicated to explain, so I'll give some examples.

A=ARRAY[1,2,3]
B=ARRAY[[2,3],[3,2],[1,4]]

In this case the SQL code would return TRUE, because 2 can be found in B[1], 3 in B[2] and 1 in B[3]. 3 can also be found in B[1], 2 in B[2] and again 1 in B[3], but it just matters that there is at least one way to do this, not which way it is.

A=ARRAY[1,2,5]
B=ARRAY[[2,3],[3,2],[1,4]]

In this case the code would return FALSE; because 5 can not be found in any of the B sub-arrays.

A=ARRAY[1,2,4]
B=ARRAY[[2,3],[3,2],[1,4]]

In this case the code would return FALSE, because both 1 and 4 are only in B[3], so whichever one is chosen for that sub-array, the other one can't be found anywhere else.

 

I hope these examples show what I want to achieve. It seems like it SHOULD be possible to do with a SELECT statement, but I am rather at a loss at how to achieve it. I also have a feeling that this should be a well-known programming problem, such that it has a name (like Knapsack, TSP and such), but I've not been able to find anything about it, and I am not sure what it would be called.

 

So can I get a nudge or some info on how this should or could be done?



#2 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts

Posted 15 October 2015 - 11:59 AM

It's a simple inner join, but the B array needs some clarification.

 

Are the sub array items another table or individual fields?

 

if they are rows from another table, do a union.  If fields, a simple or in the where clause.

 

if the number of items from your inner join match the number of items in the A array, return true, else false.


My Blog: http://forum.codecal...699-blog-77241/
"Women and Music: I'm always amazed by other people's choices." - David Lee Roth

#3 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 16 October 2015 - 06:21 AM

Well, to be honest I am not entirely sure how to do what you say, and I'm also not sure you've understood what I want to do correctly. But I've come up with another way of describing this, which is to consider all permutations of array A, and then for each element see if it is contained in the sub array of B at the same index. So for instance:

A[1]=ANY(B[1])
A[2]=ANY(B[2])

and if this is true for all elements of A for at least one permutation of A; then I will return TRUE, but if it's false for all permutations, then I return FALSE.

 

Also, here's a couple of examples with permutations of the first example in the original post:

A=ARRAY[1,2,3]
B=ARRAY[[2,3],[3,2],[1,4]]

Result:
A[1] is 1
B[1] is [2,3]

A[1] != ANY(B{1])

so return FALSE

A=ARRAY[2,3,1]
B=ARRAY[[2,3],[3,2],[1,4]]

Result:
A[1] is 2, A[2] is 3, A[3] is 1
B[1] is [2,3], B[2] is [3,2], B[3] is [1,4]

A[1] = ANY(B{1])
A[2] = ANY(B{2])
A[3] = ANY(B{3])

so return TRUE.

 

And to answer your question, the sub arrays in B are fields, and both A and B are made from one row each, thus each element in them is a field.

 

If you did understand it correctly the first time, could you then provide me with an SQL example, because I have been trying to work this out from your advice, but as I said, I am not entirely sure what you mean.



#4 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts

Posted 16 October 2015 - 06:38 AM

do you know sql?


My Blog: http://forum.codecal...699-blog-77241/
"Women and Music: I'm always amazed by other people's choices." - David Lee Roth

#5 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 16 October 2015 - 06:49 AM

Yes I do, but I'm not used to working with arrays in SQL, and I can't wrap my mind around how a union or a simple where will solve the problem, if that's why you ask.



#6 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts

Posted 16 October 2015 - 06:49 AM

My first thought: What is the table structure of your database?
 

I suspect you're going to have A be a table with fields X_COORD and VALUE, and B be a table with X_COORD, Y_COORD, and VALUE. Once  you have that, you can start doing various joins on A and B where A.VALUE=B.VALUE.


Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#7 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts

Posted 16 October 2015 - 06:56 AM

If the B array was the result set of many tables, instead of rows, you could use a union to bind them into a usable table for your query.

 

But since you said it's one table with many rows, it's a simple inner join based on the value matching either column1 or column 2.

 

SELECT Count(A.id) 

FROM A

INNER JOIN B

ON A.id = b.column1 OR a.id = b.column2

 

In the example, I'm assuming column names (id, column1 and column2) they can be any column names you need.


My Blog: http://forum.codecal...699-blog-77241/
"Women and Music: I'm always amazed by other people's choices." - David Lee Roth

#8 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 16 October 2015 - 07:14 AM

Okay but as I said at the beginning, the arrays are of length X, and the sub arrays in B of differing length. My examples are just that, examples to illustrate what I mean.

 

Also, I convert rows to arrays because I figured it would be easier to get the wanted result with arrays. But as far as my table structure goes, it is just like the arrays. The table that is turned into array A, simply has X columns (in my example X=2), each column an integer. The table for array B also has X columns, each column an integer array.

 

So for instance, if X was 5, I would have to try all permutations of ordering the 5 columns against the 5 columns in B, thus adding 600 constraints, which is excessive. Hence I convert each row to an array, because I figured there would be some array functions that could be used for this, maybe somehow using slices? But I just can't wrap my head around how to do that.



#9 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts

Posted 16 October 2015 - 07:24 AM

This is why I asked if they are fields.  If they are fields, it's an OR in the inner join.  If they are indeed tables on varying length, then you can join them together and make a single table via a UNION.

 

The key is the have an idea of the database structure.  Without it, we're flying blind and we can't help you.


My Blog: http://forum.codecal...699-blog-77241/
"Women and Music: I'm always amazed by other people's choices." - David Lee Roth

#10 ThemePark

ThemePark

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 147 posts

Posted 16 October 2015 - 07:42 AM

I feel like I have already explained my table structure in detail, which shouldn't matter anyway, as I will convert the rows to arrays first, and thus do the work on the arrays, but I will reiterate then.

 

There's table A, from which array A is made. Table A has X columns. I don't know yet what X will be, just that it will not change once I have figured out its value. Each column in table A will be an integer column. So the A array is simply a row from table A that has been nested.

 

For table B, there are also X columns. Each column here is an integer array. But the array put into each column will be of differing length. If there were two columns in table B, the first may have an integer array with 2 elements, and the second column could have an integer array of 3 elements. But again, I convert each row in table B to an array using nesting. So the only unknown is X, thus the number of columns table A and B would have, but they would all be integer and integer array columns, regardless of X, and table A and B will always have the same number of columns, i.e. X.

 

Whatever X turns out to be, I would need X! * X constraints if I make the SELECT manually, if I do it your way, lespauled. Let's say X was 2, and both tables had columns named column1 and column2, then the constraints would be

(A.column1=ANY(B.column1) AND A.column2=ANY(B.column2)) OR (A.column2=ANY(B.column1) AND A.column1=ANY(B.column2))

But if X was 5, adding 600 constraints would be a pain, especially if I made a typing error, as that would be hard to catch. That's why I figure there's a generic solution to this for X, and that's why I'm using arrays in the first place, because there are a lot of functions for those, and because I can refer to an array or an array slice without knowing its dimensions. A solution where I can check all permutations of array A against its corresponding sub-array in array B, without having to write out every single element check.



#11 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts

Posted 16 October 2015 - 08:08 AM

Step 1: I think your table structure is wrong for the problem. A table is NOT an array. You can see this in particular when you go to 3 or higher dimensioned arrays.

Step 2: What defines a member of an array is its location in the array and its value. Array A (1-dimensional) needs 2 data values to represent each member: X and VALUE, with X being the primary key. Array B (2-dimensional) needs 3 data values to represent each member: X, Y, and VALUE, with X and Y combined as the primary key.

Step 3: Once this is done, you can use SELECT * FROM A LEFT OUTER JOIN B ON (A.VALUE=B.VALUE); to see where elements of A appear in B and which items don't appear in B. To see just the missing values, add a where clause of WHERE B.VALUE IS NULL. To see how many are missing, change it from SELECT * to SELECT COUNT(*)

 


Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#12 lespauled

lespauled

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1360 posts

Posted 16 October 2015 - 08:18 AM

I feel like I have already explained my table structure in detail, which shouldn't matter anyway, as I will convert the rows to arrays first, and thus do the work on the arrays, but I will reiterate then.

...

 

Although it may be frustration, the scent of belligerence, makes me say good luck finding a solution.  This is where I check out of the conversation.  


My Blog: http://forum.codecal...699-blog-77241/
"Women and Music: I'm always amazed by other people's choices." - David Lee Roth