Thread: Google Summer of Code: Full Disjunctions
A little self advertising: Here is a link to my proposal that was sent to google: http://www.technion.ac.il/~tzahi/proposal.txt Full Disjunction is an operator. Without any long introductions (see link above)... An excerpt: Example of an input and output of a full disjunctions: A B C X Y Y Z X Z a | b b | c a | d A,B,C are relations. X,Y,Z are attributes. a,b,c,d are values. Note that A,B,C are connected in a cycle. A is connected to B on attribute Y, B is connected to C on attribute Z, C is connected to A on attribute X. The output of the full disjunctions FD(A,B,C): FD X Y Z a | b | c a | b | d This output cannot be generated using standard SQL statements. The closest operator is a natural outer join and even it cannot generate this output. Following is all the possible ways to use a natural outer join (noj): (A noj B) noj C = C noj (A noj B): X Y Z a | b | c a | Null | d (A noj C) noj B = B noj (A noj C): X Y Z a | b | d Null | b | c (B noj C) noj A = A noj (B noj C): X Y Z Null | b | c a | Null | d a | b | Null As can be clearly seen, we get incomplete information. Regards, Tzahi. -- Tzahi Fadida http://tzahi.blogsite.org | http://tzahi.webhop.info WARNING TO SPAMMERS: see at http://members.lycos.co.uk/my2nis/spamwarning.html
"Tzahi Fadida" <tzahi_ml@myrealbox.com> writes:
> The output of the full disjunctions FD(A,B,C):
> FD
> X Y Z
> a | b | c
> a | b | d
> This output cannot be generated using standard SQL statements.
Does anybody care? Your example looks to me like nothing but a poorly
designed schema. You should show a more compelling use-case if you want
people to take an interest.
regards, tom lane
It's meant for heterogeneous data sources and, as you put it, scheme graph where you want to take out information you did not initially design for. It is not unheard of to have a cycle in your scheme graph, in which case Full disjunction is the only way to pull out all the information with no subsumptions, duplications, loss of information, dealing with nulls. In addition, heterogeneous data source that are found abundantly on the web. For example, xmls, etc... Once they are on your database, you have to do something with them. Most commonly they don't play nice with an ideal design. Not to mention, the classic outside entity that your organization now wants to interface without redisigning the whole database. Here is a simple use case: http://www.technion.ac.il/~tzahi/soc.html In the example you can see the level of information with FD and with natural outer joins. P.s.: The proposal is to put this in the contrib. I already have a working and stable prototype which if the project will be selected, i plan to enhance so it can be used by anyone. Regards, tzahi. > -----Original Message----- > From: pgsql-general-owner@postgresql.org > [mailto:pgsql-general-owner@postgresql.org] On Behalf Of Tom Lane > Sent: Saturday, May 06, 2006 12:26 AM > To: Tzahi Fadida > Cc: pgsql-general@postgresql.org > Subject: Re: [GENERAL] Google Summer of Code: Full Disjunctions > > "Tzahi Fadida" <tzahi_ml@myrealbox.com> writes: > > The output of the full disjunctions FD(A,B,C): > > FD > > X Y Z > > a | b | c > > a | b | d > > > This output cannot be generated using standard SQL statements. > > Does anybody care? Your example looks to me like nothing but a poorly > designed schema. You should show a more compelling use-case > if you want > people to take an interest. > > regards, tom lane > > ---------------------------(end of > broadcast)--------------------------- > TIP 6: explain analyze is your friend > >
Hi Tzahi Since you seem to know about full disjunctions, I was wondering if you could answer this question: Can full disjunction be implemented as a binary operator? The algorithms I've seen for computing it seem to require that all input relations be supplied at once. Even in your message above you specified your example as FD(A,B,C) rather than say (A fd B) fd C. So I was wondering if the latter is possible? The reason I ask is that I'm currently trying to solve a problem that could in principle be solved using FD but it would fit into my current framework much better if it were a binary operator like the other joins. Thanks in advance. Lee
Hi Lee,
First, i have no knowledge of anyone that have implemented full disjunctions(ever) aside
from the theoretical works of my colleagues.
With the exception of a corner case of it, that I believe was a simulation in 96.
(A. Rajaman and J.D. Ullman Integrating information by outerjoins and full-disjunctions).
I'd love to hear about any implementation out there (aside from my colleagues work, which
is mine also: cohen,sagiv, kimelfeld,kanza)
It can never be a binary operation since at the heart of the matter is that you need to take
each subset of the relations and join them. i.e.:
A
B
C
A,B
A,C
B,C
A,B,C
and remove subsumptions, for example if you have {t_A,t_B} from the A,B join,
you will not include just {t_A} or just {t_B} in the result (subsumption).
Usually binary operations allow for a bottom up computation approach, but FD is a TOP down approach
(Galindo-Legaria, C. outerjoins as disjunctions).
The answer what to do is a bit complex and part of it is in a paper that is currently in review,
however:
You take the cyclic component, for example FD(A,B,C,D) and then join it with another relation E.
It's not a trouble to write (A fd B) fd C but it will still have to be computed as one computation -
FD(A,B,C).
Again, note that FD is only useful for cases you can't use natural outer joins.
So only if you have a cycle you use FD.
In my current implementation I do getfdr(A,B,C) to get the RECORD since with FD you cannot
know in advance what will be the eventual RECORD (unless you save the RECORD type for A,B,C
and A,B,C,D etc...)
then I run, for example, FD('A,B,C') as RECORD (a0 int, ....)
As you can see, you can now join other relations to the result, it's a standard recordset.
So (FD('A,B,C') as RECORD (a0 int, ....))
Here is an example of a RUN (ignore all the additional parameters):
select getfdr('rand_1_0,rand_1_1,rand_1_2');
getfdr
---------------------------
(a0 int4,a1 int4,a2 int4)
(1 row)
select * from odmbfd('rand_1_0,rand_1_1,rand_1_2',true,true,100,'random',10,10) AS RECORD (a0 int,
a1 int, a2 int) natural full outer join rand_4_2;
a2 | a0 | a1 | a3
------+------+------+------
1 | | 1813 |
1 | | 3091 |
1 | | 316 |
2 | 2113 | | 2738
3 | | 2924 | 823
3 | | 2924 | 2735
.....
.....
select count(*) from odmbfd('rand_1_0,rand_1_1,rand_1_2',true,true,100,'random',10,10) AS RECORD (a0
int, a1 int, a2 int) natural full outer join rand_4_2;
count
-------
3201
(1 row)
>Hi Tzahi
>
>Since you seem to know about full disjunctions, I was wondering if you
>could answer this question:
>
>Can full disjunction be implemented as a binary operator?
>
>The algorithms I've seen for computing it seem to require that all
>input relations be supplied at once. Even in your message above you
>specified your example as FD(A,B,C) rather than say (A fd B) fd C.
>So I was wondering if the latter is possible?
>
>The reason I ask is that I'm currently trying to solve a problem that
>could in principle be solved using FD but it would fit into my current
>framework much better if it were a binary operator like the other
>joins.
>
>Thanks in advance.
>Lee
> First, i have no knowledge of anyone that have implemented full disjunctions(ever) aside > from the theoretical works of my colleagues. > With the exception of a corner case of it, that I believe was a simulation in 96. > (A. Rajaman and J.D. Ullman Integrating information by outerjoins and full-disjunctions). > I'd love to hear about any implementation out there (aside from my colleagues work, which > is mine also: cohen,sagiv, kimelfeld,kanza) I didn't mean to imply there was. It was the Rajaraman & Ullman paper that got me interested in FD's and then I've looked at the "Computing Full Disjunctions" paper by Kanza & Sagiv which gives a general solution. Obviously from the second paper it's clear that implementing full disjunction (efficiently) is a non-trivial exercise. > It can never be a binary operation since at the heart of the matter is that you need to take > each subset of the relations and join them. i.e.: ... > Usually binary operations allow for a bottom up computation approach, but FD is a TOP down approach > (Galindo-Legaria, C. outerjoins as disjunctions). Right, thanks for clarifying. From a data analysis perspective I would like to be able to look at various subsets, eg. FD(A,B,C), FD(B,C,D), FD(A,B,C,D) etc and so this just means that each subset has too be computed independantly. I can live with that but wasn't sure if I had missed something. In any case, the difficulty of implementing FD precludes me from experimenting with it just yet. Regards Lee
> -----Original Message----- > From: pgsql-general-owner@postgresql.org > [mailto:pgsql-general-owner@postgresql.org] On Behalf Of > ana_cata_hylo@yahoo.com > Sent: Tuesday, May 09, 2006 1:51 AM > To: pgsql-general@postgresql.org > Subject: Re: [GENERAL] Google Summer of Code: Full Disjunctions > > > First, i have no knowledge of anyone that have implemented > full disjunctions(ever) aside > > from the theoretical works of my colleagues. > > With the exception of a corner case of it, that I believe > was a simulation in 96. > > (A. Rajaman and J.D. Ullman Integrating information by > outerjoins and full-disjunctions). > > I'd love to hear about any implementation out there (aside > from my colleagues work, which > > is mine also: cohen,sagiv, kimelfeld,kanza) > > I didn't mean to imply there was. It was the Rajaraman & Ullman paper > that got me interested in FD's and then I've looked at the "Computing > Full Disjunctions" paper by Kanza & Sagiv which gives a general > solution. > Obviously from the second paper it's clear that implementing full > disjunction (efficiently) is a non-trivial exercise. If only all the FD problems would have the same difficulty, Rajaraman & Ullman paper tries to solve. Their paper is actually trying to pinpoint where you can no longer use your standard SQL tools to compute the FD. Commonly, as a rule of thumb, if you have a cycle in your scheme graph, you can no longer use Rajaraman & Ullman method (with some delicate exceptions) of using a series of natural outer joins to compute the FD which is very fast and simple. However, in the general case where you have cycles you can forget about it. The problem becomes very hard to compute and I wouldn't suggest it for huge relations. My work is to see how we can alleviate the common troubles but the problem is still hard. > > > It can never be a binary operation since at the heart of > the matter is that you need to take > > each subset of the relations and join them. i.e.: > ... > > Usually binary operations allow for a bottom up computation > approach, but FD is a TOP down approach > > (Galindo-Legaria, C. outerjoins as disjunctions). > > Right, thanks for clarifying. > > >From a data analysis perspective I would like to be able to look at > various subsets, eg. FD(A,B,C), FD(B,C,D), FD(A,B,C,D) etc and so this > just means that each subset has too be computed independantly. I can > live with that but wasn't sure if I had missed something. Basically you only have to look at FD(A,B,C,D). It includes all the information of FD(A,B,C) and FD(B,C,D). > > In any case, the difficulty of implementing FD precludes me from > experimenting with it just yet. Well, as I said, I already implemented it. What's left is to clean up the code from the statistics of my experiments and improve the coding style and add some improvements I've been meaning to add. The code is pretty big considering. It's about 200kb C code for the one algorithm I want to work on for the gsoc. And bigger if I will have time to add some of the others. > > Regards > Lee > > > ---------------------------(end of > broadcast)--------------------------- > TIP 9: In versions below 8.0, the planner will ignore your desire to > choose an index scan if your joining column's datatypes do not > match > >