Hej!

Har en sql-fråga jag skulle behöva hjälp med. Jag håller på med en applikation där man ska kunna få fram artiklar (på toppnivå) som innehåller andra artiklar man specificerat. Bifogat finns en pdf, www.stefanj.se/articletree.pdf som föreställer ett artikelträd. Databasstrukturen är fast och kan inte ändras. Artikelträdet är skapat genom att i en länktabell specificera barnnoder till föräldernoder.

I nedanstående exempel har jag valt att kolla två artiklar, men man ska lika gärna kunna välja ut ett godtyckligt antal artiklar och söka de artiklar som innehåller dessa.

Scenario 1:
Vilka artiklar ingår artikel 1180 SV och artikel MB0040 i samtidigt?
Argument: ObjectId 2, ObjectId 4
Resultat: ObjectId 1

Scenario 2:
Vilka artiklar ingår artikel FE0067 och AA2250 i samtidigt?
Argument: ObjectId 8, ObjectId 11
Resultat: null, dvs inga artiklar

Scenario 3:
Vilka artiklar ingår AA2250 och AA2251 i samtidigt?
Argument: ObjectId 11, ObjectId 12
Resultat: ObjectId 10

Scenario 4:
Vilka artiklar ingår FE0067 och 1180 SV i samtidigt?
Argument: ObjectId 8, ObjectId 2
Resultat: ObjectId 9, ObjectId 1

Några goda ideer?

/Mvh Stefan

Har svårt att se att detta löses med "ren sql", i synnerhet om du är låst till den skumma strukturen.
För det första är jag tveksam till om din graf är rätt, du verkar ha två stycken MB0040, ingenting i 9 och 8, AA2251 kan jag inte hitta osv. Jag förstår ärligt talat inte vad de tre kolumerna betyder.

Men om jag ändå tolkat dig rätt skulle jag göra en lösning i stil med:

1. För varje input, ta fram "tråden" upp till översta föräldern.
ObjectId 4 -> ObjectId 3 -> ObjectId 1
ObjectId 2 -> ObjectId 1
2. Om vi nu antar att det verkligen är ett träd, och inte har skumma loopar, eller dubletter inne i strukturen, så kan vi dra slutsatsen att varje sista element i "tråden" för varje input måste vara samma, annars inga artiklar, så då returnerar vi det.
3. Annars går vi ner ett steg i taget i varje tråd. Så fort någon av trådarna avviker så vet vi att föregående steg var den lägsta som var gemensam.

hej!

Ajaj... "grafen" är inte rätt. nu är den dock uppdaterad.

I databasen finns en tabell som heter TN_ARTICLES som innehåller alla artiklar som finns i systemet. Fältet OBJECT_ID i denna tabell ger alla artiklar ett unikt id.

I databasen finns också en tabell som heter TDM_LINKS_00676. I denna tabell finns fälten OBJECT_ID, CLASS_ID, OBJECT_ID1, CLASS_ID1, OBJECT_ID2, CLASS_ID2 och ett gäng andra fält. OBJECT_ID är bara ett id fält för var rad i denna tabell. OBJECT_ID1 är en artikels id nummer och OBJECT_ID2 är också en artikels id.

Artikelträdet är skapat genom att object_id1 beskriver en huvudnod och object_id2 är en barnnod till denna huvudnod. Det är dessa tre som finns med i "grafen"; ObjectId (OBJECT_ID), ParentId (OBJECT_ID1) och ChildId (OBJECT_ID2).

Strukturen är en IBM (enovia smarteam) skapelse och man får anta att det finns logik som ser till att det inte skapas loopar....

/tack

Jepp, men då är min algoritm korrekt, om än långsam. Ska detta göras många gånger, eller som del av en vanlig utsökning?

Som sagt tror jag inte det finns något vettigt sätt att i standard sql lösa det, utan något man bör lösa i kod.
pseudo:

<code
list<int> get_parent_string(obj_id)
{
if(obj_id == null){
return [null];
}
else{
parent = sql("SELECT Parent FROM tbl WHERE Child = ?", obj_id);
return get_parent_string(parent) + obj_id;
}
}

int get_common_parent(input_id)
{
lists l;
for each id in input_id
l[id] = get_parent_string(id);

for(depth = 0 to max)
if not all l[*, depth] is identical return l[any, depth-1];
}
</code>

Hänger du med?

Jävlar, det var ju knepigare, det här är ju inget äkta träd, det är ju en DAG, en directed acyclic graph. Men det verkar fortfarande inte vara helt rätt i bilden, i så fall kan det ju inte finnas flera ObjectID.

Jag tror du kan använda samma grundprincip, men att du får bygga träd nerifrån, och sen göra mer komplicerade jämförelser, alternativt bara ta alla tänkbara varianter.

Annars skulle man kunna tänka sig en variant i stil med ett förberedelsesteg:
1. För ett givet ID, räkna ut alla nivåer som det kan ligga på. 1180 SV är bara 2, men FE0067 är alltså både 2 och 3.
2. En gemensam parent till alla input har bara _en_ viss nivå. Så börja med alla noder på lägsta nivån. Om vi har FE0067 och 1180SV så ser vi att den absolut lägsta nivån är 3.
3. Eftersom inte alla input har något på den nivån (alltså 1180SV har ingen på nivå 3) kan inte en gemensam parent ligga på nivå 3.
4. Ta varje nod som ligger på nivå 3 (bara ena FE0067), leta upp dess parentnod (1080SV). Nu har vi två input med vardera två noder, och alla noder ligger på samma nivå.

Sen får man gå uppåt med alla noder, jämföra alla kombinationer, och så fort man får en match mellan alla input tar man bort alla inblandade noder (som är samma) och lägga till den just borttagna noden till "nuvarande lista".


Ytterligare en variant (och jag lutar nog mest mot den nu) är att göra sökning uppåt, precis som i ursprungsförslaget, och "färga" alla ingående noder med inputid. Sen letar man igenom trädet efter de noderna som har alla inputid och ligger längst ner.

I SQLServer skulle man kanske kunna lösa det så här:

Vi tar först fram en fråga som ger som resultat en tabell bestående av
nod, förälder, avstånd

(avstånd är avståndet mellan nod och förälder)

Därefter hittar vi de poster som har samma förälder med minsta möjliga summa av avstånd, där alla valda noder finns med.

Skulle kunna se ut så här:
(Skriver direkt från huvudet så är säkert nåt jag glömt)

-- Skapa fråga med node, parent, distance
WITH NodeParentDist (node, parent, distance) AS (
-- Första nivån (alla noder som har en förälder)
SELECT node, parent, 1
FROM nodes
WHERE node <> parent
UNION ALL
-- För varje på tidigare nivå, hämta förälderns förälder
SELECT leaf.node, parents.parent, leaf.distance + 1
FROM nodes AS parents INNER JOIN
NodeParentDist As leaf ON leaf.parent = parents.node AND parents.node <> parents.parent
),
-- Hämta summan och antalet för varje förälder
SumCount (parent, NodeCount, DistanceSum) AS (
SELECT parent, Count(node), Sum(distance)
FROM NodeParentDist
WHERE node IN (list of nodes)
GROUP BY parent
)
-- Äntligen kan vi hämta den gemensamma föräldern
SELECT TOP 1 parent
FROM SumCount
WHERE NodeCount = (antalet noder vi söker efter)
ORDER BY DistanceSum ASC

niklas:
Sökningen kommer inte göras särskilt ofta. I nuläget finns det en kille som manuellt kollar på olika bottom-up träd för matchningar. Eftersom detta är väldigt osmidigt görs kanske maximalt 10 sådana på en månad...

Du har rätt... suck. Ja det är kvar ett fel i trädet. Under 1080 SV ska såklart MB0040 ha objectid 4. Alla artiklar har såklart unika objectid.

Ska försöka sätta mig in i era förslag under dagen. Väldigt uppskattat!

Har uppdaterat trädet med korrekta värden www.stefanj.se/articletreenew.pdf

det går framåt, men lite sakta pga att jag haft lite hög arbetsbelastning i veckan...

för den intresserade har jag ställt samma fråga även på sqlservercentral, se http://www.sqlservercentral.com/Forums/Topic506823-23-1.aspx.

återkommer.