[MSSQL] Dubbele ID-paren weghalen

[_Thanatos_]

Hallo mede-tweakers, ik heb weer een SQL-probleempje. Ik heb een selectie gedaan waar uiteindelijk ID-paren uit komen. De bedoeling is dat het een controle doe op kruislinkse verbindingen tussen Parent en ID van een bomstructuur binnen een tabel.

Ik krijg bijv het volgende terug:

code:

ID1         ID2         
----------- ----------- 
30          190
40          50
50          40
190         30

Dit betekent dat records met ID's 30 en 190 kruislinks gekoppeld zijn, en ID's 40 en 50 ook. Nu wil ik dat die dubbele paren eruit gefilterd kunnen worden, maar ik kan me niet indenken hoe. Wie helpt mij?

Ik heb al iets van "WHERE ID1 NOT IN ID2" en "WHERE ID1<>ID2" geprobeerd, maar die werken natuurlijk niet. De bedoeling is dat er iets uitkomt zoals:

code:

ID1         ID2         
----------- ----------- 
30          190
50          40

Ohja, de query die ik gebruik voor het opzoeken van de kruislinke koppelingen:

code:

SELECT A.ID AS ID1, B.ID AS ID2
FROM Tabel AS A
JOIN Tabel AS B ON B.Parent=A.ID AND A.Parent=B.ID

[ Voor 13% gewijzigd door _Thanatos_ op 03-01-2003 14:02 . Reden: de query ]

[Verwijderd]

Hoe weet je welke link je moet weghalen? Bijv. 30, 190 of 190, 30?

Edit:
En hoe zit het met meer complexe relaties, zoals bijv. A->B, B->C en C->A? Kunnen die ook voorkomen?

[ Voor 46% gewijzigd door Verwijderd op 03-01-2003 14:09 ]

[GrimaceODespair]

Het is misschien een optie om van de twee kolommen een primaire sleutel te maken om dubbele paren in de eerste plaats te vermijden?

Edit: ow, shit, ik neem aan dat (40,30) = (30,40).. in dat geval verkoop ik natuurlijk onzin

[ Voor 27% gewijzigd door GrimaceODespair op 03-01-2003 14:05 ]

[GrimaceODespair]

where a.id < b.id ?

[_Thanatos_]

Welke hij weghaalt maakt niet uit, het gaat erom dat er slecht 1 van de parent blijft bestaan.

Complexere relaties kunnen theoretisch wel voorkomen, maarwaag ik me nog niet aan. Het zal dan ook wel een hele ingewikkelde query worden, als het al met een qeury kan.

Hmm, " AND A.ID < B.ID" eraan toevoegen werkt idd wel.
Opgelost

Nu die complexere relaties nog... misschien heeft iemand zoiets al gedaan? ik zou niet weten waar te beginnen, eerlijk gezegd.

[ Voor 28% gewijzigd door _Thanatos_ op 03-01-2003 14:15 ]

[GrimaceODespair]

Complexe relaties is een recursief probleem... weet niet of je dat met 1 SQL query kunt oplossen. Het probleem is dat je niet op voorhand weet hoe diep de paden zijn. De diepte van een pad bepaalt namelijk hoeveel joins je moet doen voordat je dat pad hebt. En bij nader order kun je in ANSI SQL geen dynamische joins doen.
Misschien lukt het wel met TSQL van MSSQL, maar zal dan wel harde dobber zijn (en waarschijnlijk mega-inefficiënt). Nu, oplossing met een recursieve functie (in je aanroepende code) is ook niet erg efficiënt. Je zal volgens mij elk pad afzonderlijk moeten onderzoeken totdat het doodloopt. Denk niet dat je dit erg goed kan optimaliseren in SQL.

[_Thanatos_]

Dan laat ik de complexere relaties wel zitten, de kans je vliegtuig neerstort is groter en het gevolg is kleiner
(applicatie zal hooguit vastlopen)

[Verwijderd]

Als het hier gaat om een tree, dan maakt het wel degelijk uit welke van de twee je verwijdert. Het zal niet in 1 query te verwijderen zijn, en ik raad je aan een stuk code te schrijven die, vanaf de root node tot de laatste leaf node de boom doorloopt en cyclische relaties verwijdert.

Als ik mijn dictaat Grafentheorie nog had, zou ik je kunnen helpen aan een algoritme en een bewijs van het ontbreken van cyclische nodes, maar helaas ...

[GrimaceODespair]

_Thanatos_ schreef op 03 januari 2003 @ 14:27:
Dan laat ik de complexere relaties wel zitten, de kans je vliegtuig neerstort is groter en het gevolg is kleiner
(applicatie zal hooguit vastlopen)

Euhm... dit soort programmeren probeer ik doorgaans te vermijden Als het voor eigen gebruik of wat spielerij is, maakt het natuurlijk niet zoveel uit, maar code groeit je sneller boven het hoofd als je lief is.

Ik weet natuurlijk niet wat je aan het schrijven bent, maar ik zou eens kijken of je niet langs een andere weg je probleem kunt oplossen (of gaat het je net om de uitdaging dit specifieke probleem op te lossen?)

[Verwijderd]

kan je even het datamodel geven? en de query zoals je nu gebouwd heb, dan snap ik misschien waar je heen wilt. Mail anders even naar [e-mail] . en natuurlijk even verwijderspam doen voordat je mailt Ik kijk er dan wel even naar!

[Verwijderd]

offtopic:
Dus bij CGEY zitten er ook mensen zich te vervelen ...

[Creepy]

Verwijderd schreef op 03 januari 2003 @ 14:36:
kan je even het datamodel geven? en de query zoals je nu gebouwd heb, dan snap ik misschien waar je heen wilt. Mail anders even naar [e-mail] . en natuurlijk even verwijderspam doen voordat je mailt Ik kijk er dan wel even naar!

En natuurlijk vergeet jij dan niet om hier de eventuele oplossing hier neer te zetten zodat we er allemaal wat aan hebben

[Verwijderd]

Verwijderd schreef op 03 January 2003 @ 14:39:

offtopic:
Dus bij CGEY zitten er ook mensen zich te vervelen ...

LOL! Nee, echt druk heb ik het nu niet. Laat ik me dan maar nuttig maken he!


En ja, als ik een oplossing heb (zit nog niks in mijn mailbox), plaats ik 'm ook hier *)

[_Thanatos_]

Als het hier gaat om een tree, dan maakt het wel degelijk uit welke van de twee je verwijdert.

Met "verwijderen" bedoel ik niet de node uit de tabel verwijderen, maar uit het lijstje met gevonden nodes. Er wordt een melding op het scherm gezet die aangeeft welke nodes er dan dubbel zijn en de programmeur mag het dan fixen.

De dubbele nodes onstaan gelukkig niet tijdens de loop van de applicatie, maar alleen tijdens ontwikkelen. De nodes worden nml tot nu toe handmatig in de tabel gezet, waardoor er vergissingen kunnen onstaan en dus fouten. Ik wil dus geen dagen werk gaan steken in iets wat je zonder dat script sneller kan zien. Dus complexere relatief hoef ik niet per se op te vangen. Zeker niet gezien het aantal records in zo'n tabel nooit boven de 1000 uit kan komen.

[_Thanatos_]

Patrickje, u hebt mail

[GrimaceODespair]

Dit lijkt iets langer te duren dan verhoopt, geloof ik

[_Thanatos_]

Och, het heeft geen haast en zo is die jongen ook weer van de straat

[Verwijderd]

ik ga er strax ff naar kijken! Kwam weer vanalles tussen natuurlijk

[Verwijderd]

Even uit mijn hoofd, en op de Oracle SQL manier (zou ver hetzelfde moeten zijn):

select t1.id, t1.parent
from tabel t1
where t1.parent not in ( select t2.id from tabel where t2.id != t1.id )

Dit is de "nette" manier, is niet altijd even goed qua performance. Maar langs de andere kant, dit soort statements zijn alleen noodzakelijk als de data-entry niet waterdicht is. En zoals je zelf zei: het zijn maar testdata en dan gebeurt dat
Trouwens, die methode van t1.id < t1.parent lijkt ook te werken maar ergens heb ik het gevoel dat er iets verkeerd kan gaan op die manier. Vraag me niet wat!

Weet niet of je er wat aan had, maar ik had beloofd mijn oplossing hier te verzinnen als ik die had.....

[GrimaceODespair]

Met "net" lijk je hier te bedoelen dat je de query hebt gebouwd zodat ie zo dicht mogelijk bij de semantiek ervan aanleunt (als ik enigszins duidelijk ben). Voor SQL heb ik het "net" van jou al een tijd geleden afgezworen, omdat naar mijn ervaringen met SQL de taal zich te moelijk voor 1-op-1 vertalingen leent (semantiek -> SQL).

Het feit dat

code:

t1.id < t1.parent

je gevoelsmatig minder correct lijkt, spruit volgens mij hieruit voort. Het is wel degelijk correct, maar geen letterlijke SQL-vertaling van het probleem. Het is bovendien zelfs vrij generiek, aangezien het altijd correct zal blijven, zolang id en parent maar vergelijkbare kolommen zijn.

Immers: of 'a < b', of 'NOT (a < b)'. Dit is consequent zo, dwz, als 'a < b' dan zal nooit zomaar ineens ergens anders 'NOT (a < b)'. Toegepast op onze query betekent dit dat er nooit per ongeluk 2 dezelfde paren kunnen weggehaald worden of eentje kan overgeslagen worden.

[ajslaghu]

EXIST

[edie]

Heb ik zelf ook veel moeten doen.
Je moet even spelen met LEFT JOINS, RIGHT JOINS en (NOT) NULL in je WHERE clause

[_Thanatos_]

Patrickje, ik ga het dinsdag uitproberen... dan moet ik weer werken.

Ben benieuwd.

[_Thanatos_]

Query van patrickje geeft niets terug... niet bij twee records die naar elkaar verwijzen en ook niet bij diepere cross-links.

edit:
mooi gezegd, GrimaceODespair

[ Voor 15% gewijzigd door _Thanatos_ op 07-01-2003 12:48 ]

[GrimaceODespair]

tnx

[Verwijderd]

Hhhm, toch ff reageren.

_Thanatos_ : ik zie inderdaad een foutje, miste even de trial-and-error met dit soort vraagstukjes.

GrimaceODespair: Ja ik weet dat het soms handiger is om een oplossing te gebruiken die niets met de symantiek van het probleem te maken heeft maar wel het goede resultaat oplevert. Als "t1.id < t1.parent" werkt moet je die in dit geval ook gewoon gebruiken en handmatig controleren of het juist is. Probleem opgelost.

Even terug komen op de query:

select t1.id, t1.parent
from tabel t1
where not exist ( select 'x' from tabel t2 where t2.id != t1.parent )

Dit zou meer op moeten leveren. Rite?

[Goodielover]

Twee vragen:
1. Als je een cycle hebt in je relaties heb je beide richtingen de cycle?
2. Zijn de relaties transitief en afgesloten in de je DB, dus is
(als A->B en B->C dan ook A->C) waar en bevindt de relatie A->C zich dan ook in de DB.

PS in Oracle los je zulke vraagstukken op met een CONNECT BY

[ Voor 16% gewijzigd door Goodielover op 07-01-2003 13:39 . Reden: PS toegevoegd ]

[_Thanatos_]

1. Als je een cycle hebt in je relaties heb je beide richtingen de cycle?
2. Zijn de relaties transitief en afgesloten in de je DB, dus is
(als A->B en B->C dan ook A->C) waar en bevindt de relatie A->C zich dan ook in de DB.

1. Wat bedoel je precies? Als je bedoelt dat als A->B bestaat, dan ook B->A, dan ja. Daar gaat het probleem over
2. als A->B bestaat, dan kan A->C nooit bestaan, omdat A, B, en C, zoals jij ze noemt, ieder maar 1 keer voor kunnen komen, omdat het primary keys zijn (getallen in mijn geval).

PS in Oracle los je zulke vraagstukken op met een CONNECT BY

Maar hier gaat het om MSSQL... dat gebruikt onze provider (en wij zelf ook) nou eenmaal. Het is btw MSSQL2000, daarvan mogen specifieke features gebruikt worden, mochten die van toepassing zijn.

[Goodielover]

Zoals jij het nu zegt kan dan de situatie a->b, b->c, c->a niet voorkomen.
Want als a->b is opgenomen is ook b->a opgenomen.

Eerder schreef jij:

_Thanatos_ schreef op 03 January 2003 @ 14:12:
Welke hij weghaalt maakt niet uit, het gaat erom dat er slecht 1 van de parent blijft bestaan.

Complexere relaties kunnen theoretisch wel voorkomen, maarwaag ik me nog niet aan. Het zal dan ook wel een hele ingewikkelde query worden, als het al met een qeury kan.

Hmm, " AND A.ID < B.ID" eraan toevoegen werkt idd wel.
Opgelost

Nu die complexere relaties nog... misschien heeft iemand zoiets al gedaan? ik zou niet weten waar te beginnen, eerlijk gezegd.

Maar zoals je het nu zegt kan het ook theoretisch niet.
Je hebt dus gewoon een 1:1 relatie tussen twee entiteiten. (soort monogaam huwelijk)

[_Thanatos_]

Ik zeg niet dat als A->B bestaat, dat dan B->A ook moet bestaan. Ik zeg alleen dat het daarmee een cross-link is. Maar A->B,B->C,C->A is ook een cross-link. En A->B,B->C,C->D,D->A ook, enz.

[Goodielover]

Deze cross links mogen dus wel. Je hebt dus cycles met 2,3,4,5,6,... nodes.
Als je dit hebt en niet alleen theoretisch, hoe moet je overzicht er dan uitzien.
a->b
b->c
c->d
d->a

e->f

of

a->b->c->d
e->f

of

....

[ Voor 15% gewijzigd door Goodielover op 08-01-2003 15:00 ]

[_Thanatos_]

Huh? "deze cross-links mogen wel"? Geen enkele cross-link mag.

Laat ik het nog een keer uitleggen dan:
Ieder record is een node in een treeview. In ieder record is z'n parent opgeslagen die verwijst naar de ID van die parent.

Dus: geen enkele node mag een van z'n subnodes als parent hebben. Zou dat wel zo zijn, zou je in feite een oneindige tree krijgen, omdat twee of meer nodes zeggen dat ze elkaars parents zijn. Beetje kip/ei probleem bedenk ik me net

Hoe de tabel eruit hoort te zien, sja. Een simpele treeview gewoon:

code:

           ID  Parent
Node        1    NULL
|-Node      2       1
| \-Node    8       2
|-Node      3       1
| |-Node    5       3
| | \-Node  7       5
| \-Node    6       3
\-Node      4       1

[edie]

zoiets?

code:

create table xtest( id int, parent int )

insert into xtest values( 1, 0 )
insert into xtest values( 2, 1 )
insert into xtest values( 3, 2 )
insert into xtest values( 4, 2 )
insert into xtest values( 5, 0 )
insert into xtest values( 6, 5 )
insert into xtest values( 7, 0 )
insert into xtest values( 8, 7 )
insert into xtest values( 5, 6 ) // Dubbel
insert into xtest values( 7, 8 ) // Dubbel

select *
from xtest
where parent = 0
union all(
    select x1.*
    from xtest as x1
    left join xtest as x2 
    on x1.parent = x2.id
    where x1.id != x2.parent
)

Resultaat:

code:

id          parent      
----------- ----------- 
1           0
5           0
7           0
2           1
3           2
4           2
6           5
8           7

(8 row(s) affected)

Eerst de 'super' parents, dan de childs.