Basically, I have a bunch of entries in a database. Call em movies. Each is 
tagged with a collection of arbitrary tags: release date, studio, genre, 
etc. There's no specific collection of tags, but each tag is either present 
or absent, with no other associated value.

Now I want to represent groups of movies. I want to be able to say, for 
example, movies that are from Warner Brothers, and that have arabic *or* 
french subtitles, but aren't rated R, that are out on DVD or out on VHS, ...

So, basically, I want to be able to express a fairly general boolean 
equation on an arbitrary collection of variables and store it as a SQL table.

However, I haven't been able to figure out the google terms that might 
actually give me something other than a tutorial for using the boolean type 
in SQL.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Darren New wrote:
> So, basically, I want to be able to express a fairly general boolean 
> equation on an arbitrary collection of variables and store it as a SQL 
> table.

Just to clarify, this doesn't have to be fast. I'm just looking for a 
structured representation. I'm happy to do multiple searches and such, since 
the result will be cached and only regenerated for the collections that 
change or when movies are added or whatever.

I'm just trying to avoid storing the selection criterion as a big TEXT blob 
that looks like an equation.

I'm thinking like a table of "has all of", a table of "has some of" and a 
table of "has none of", for example, except I'm not sure that's flexible enough.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Completely unrelated to what you wrote, but it reminded me of something
I wondered some time ago:

  Assume you have a table with movie names and another with actor names,
and a relationship between the two telling which actors have acted in which
movies.

  Problem: Can you write an SQL statement which solves the "six degrees of
Kevin Bacon" relationship between any two given actors?

  In other words, you give it two actor names and it tells you how many
steps apart they are from each other, via common movies they have acted in.
(Ie. if they have acted in the same movie, their degree of separation is 1,
if they haven't acted in the same movie but have acted with the same third
person, their degree of separation is 2, and so on.)

-- 
                                                          - Warp

Post a reply to this message

Darren New wrote:

> So, basically, I want to be able to express a fairly general boolean 
> equation on an arbitrary collection of variables and store it as a SQL 
> table.
> 
> However, I haven't been able to figure out the google terms that might 
> actually give me something other than a tutorial for using the boolean 
> type in SQL.

Damn, where's Gail when you need her?

(Actually, apparently she doesn't read povray.off-topic any more, due to 
some technical issue that I don't remember the details of now...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:

>   Problem: Can you write an SQL statement which solves the "six degrees of
> Kevin Bacon" relationship between any two given actors?
> 
>   In other words, you give it two actor names and it tells you how many
> steps apart they are from each other, via common movies they have acted in.
> (Ie. if they have acted in the same movie, their degree of separation is 1,
> if they haven't acted in the same movie but have acted with the same third
> person, their degree of separation is 2, and so on.)

Or, in a similar problem, if you have a table telling you parent/child 
relationships, can you find all recorded descendants of a specified person?

As far as I can tell, you can construct an SQL statement that will find 
all people X generations below a given person, but you cannot write a 
statement that will search to an unbounded depth. The search is 
recursive, and SQL doesn't seem to be able to do that. Each recursion 
requires a sub-select, so the number of sub-selects you type is the 
number of generations it searches.

On the other hand, this kind of problem is trivial (and jaw-droppingly 
inefficient) in Prolog...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:
>   Problem: Can you write an SQL statement which solves the "six degrees of
> Kevin Bacon" relationship between any two given actors?

This is basically representing trees in SQL. And it's easy to google for. ;-)

You can do it, but I think you need a new query for each degree, which you 
can cache in a table if you like.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

Le 24/06/2010 21:48, Warp nous fit lire :
>   Completely unrelated to what you wrote, but it reminded me of something
> I wondered some time ago:
> 
>   Assume you have a table with movie names and another with actor names,
> and a relationship between the two telling which actors have acted in which
> movies.
> 
>   Problem: Can you write an SQL statement which solves the "six degrees of
> Kevin Bacon" relationship between any two given actors?
> 
>   In other words, you give it two actor names and it tells you how many
> steps apart they are from each other, via common movies they have acted in.
> (Ie. if they have acted in the same movie, their degree of separation is 1,
> if they haven't acted in the same movie but have acted with the same third
> person, their degree of separation is 2, and so on.)
> 
That's a graph exploration.

With 2 actor's names and wanting the minimal distance between them is
best solved with dijkstra SPF, not SQL. (double the distance, it's one
actor-one movie-one actor... path)

SQL would be better at generating view of increasing distance, sort of a
breadth first flooding.
First view would be the set of actors that have a distance of 1.

pseudo SQL:
Select distinct(actor.*),1 as hop from actor, relationship as a,
relationship as b where actor.id = a.actor_id and b.actor_id =
id_of_Kevin_Bacon and b.film_id = a.film_id order by actor.id ;

You can continue with a recursive:

Select distinct(actor.*),2 as hop from actor, relatiionship as a,
relationship as b where actor.id = a.actor_id and b.actor_id in (select
x.actor_id from relationship as x, relationship as y where y.actor_id =
id_of_Kevin_Bacon and x.film_id = y.film_id) and b.film_id = y.film_id ;

If you want to avoid seeing people at multiple ranges, an additional
filter is needed ( and a.actor_id not in (select .... ))

you can continue like that, using union select to make a single big huge
query. (but it's going deeper & deeper, better done with a graphical
editor of query)

(So far, it does not give you the movie/actor path... it might just be a
concat() construct from the movie table with the previous level query)

Even with a starting Actor, it would be simpler to use the database as
the source of vertex & edge and use a classical dijkstra SPF to generate
a full tree.

If you allow populating intermediate tables (with insert statements),
you can have a representation of the SPF tree for any starting point.
(but replacing Kevin Bacon with Michael Jackson would force to drop the
tables and restart the filling): you fill the level 1 table, then the
level 2 table,... and so on, each filling being restricted to not add an
entry already in a lower table.

Post a reply to this message

Le_Forgeron wrote:
> (but replacing Kevin Bacon with Michael Jackson would force to drop the
> tables and restart the filling):

Aye!

Oh, you said tables, not trousers.

Nevermind.

-- 
Darren New, San Diego CA, USA (PST)
    Eiffel - The language that lets you specify exactly
    that the code does what you think it does, even if
    it doesn't do what you wanted.

Post a reply to this message

>> (but replacing Kevin Bacon with Michael Jackson would force to drop the
>> tables and restart the filling):
> 
> Aye!
> 
> Oh, you said tables, not trousers.
> 
> Nevermind.

As required: http://xkcd.com/327/

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Le_Forgeron <jgr### [at] freefr> wrote:
> With 2 actor's names and wanting the minimal distance between them is
> best solved with dijkstra SPF, not SQL.

  I didn't quite get that. You are comparing an algorithm to a language.
It's like saying "sorting an array is best done with merge sort, not Java."
Makes little sense.

-- 
                                                          - Warp

Post a reply to this message