June 28, 2011 at 2:03 am
Hi Guys,
As per our requirement we have two list in UI.
1. Source
2. Target
Both the lists are populated with the user created tables within DB. Now the requirement say when user clicks on "Navigate" button we have to show all the possible ways to reach from Source to Target using system information (PK-FK). To do this we consider the sys.foreign_keys system table to find the navigation.
To make clear I have attached one sample design in which the Source is "T2" and Target is "T5".
per design I can reach to T5 using below paths...
1. T2 > T1 > T3 > T3_T5 > T5
2. T2 > T1 > T4 > T4_T5 > T5
3. T2 > T1 > T6 > T5
4. T2 > T6 > T5
Now process to get all the possible ways is to navigate through out the hierarchy "Upward & Downward". I am bit confused here how to achive this. I did some workaround will share that with you. But meanwhile can anybody give any suggestions please?
Thanks in advance...
Abhijit - http://abhijitmore.wordpress.com
June 28, 2011 at 6:47 am
Thats bit strange ! No one replied with any suggestions :w00t:?
I am still struggling with the issue...
Abhijit - http://abhijitmore.wordpress.com
June 28, 2011 at 9:15 am
Surely with almost 900 points you should know how NOT to post a question. There are no details for anybody else to go on. We can't see over your shoulder and we are not familiar with your project. Help us help you. Provide ddl, sample data (insert statements) and desired output based on your sample. Read the link in my signature for best practices on posting questions.
_______________________________________________________________
Need help? Help us help you.
Read the article at http://www.sqlservercentral.com/articles/Best+Practices/61537/ for best practices on asking questions.
Need to split a string? Try Jeff Modens splitter http://www.sqlservercentral.com/articles/Tally+Table/72993/.
Cross Tabs and Pivots, Part 1 – Converting Rows to Columns - http://www.sqlservercentral.com/articles/T-SQL/63681/
Cross Tabs and Pivots, Part 2 - Dynamic Cross Tabs - http://www.sqlservercentral.com/articles/Crosstab/65048/
Understanding and Using APPLY (Part 1) - http://www.sqlservercentral.com/articles/APPLY/69953/
Understanding and Using APPLY (Part 2) - http://www.sqlservercentral.com/articles/APPLY/69954/
June 28, 2011 at 10:32 am
Probably the easiest way to get that data is a recursive hierarchy query. I'd need to have table definitions in order to suggest anything more detailed than that. A recursive CTE could do it pretty easily (actually, you'd need two: one for up, one for down).
If you're looking for "best path" calculations, I recommend you start over and don't calculate all possible paths. There are better algorithms for that, usually covered in a good Comp Sci curriculum.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
June 29, 2011 at 1:48 am
Sean
Sorry about not providing the dll. I have attached the sample script. We dn't need any data with as we need to get the metadata information. Its not excatly the meta data information just the structure information. and output I am looking for is possible ways to reach from one entity to another.
GSquared
I have tried the recursive CTE but it didn't gave me all possible ways. I agree with you to get "best path" calculation but as per requirement I have to get all possible ways.
IF OBJECT_ID('T1') IS NOT NULL
DROP TABLE T1
IF OBJECT_ID('T2') IS NOT NULL
DROP TABLE T2
IF OBJECT_ID('T3') IS NOT NULL
DROP TABLE T3
IF OBJECT_ID('T4') IS NOT NULL
DROP TABLE T4
IF OBJECT_ID('T5') IS NOT NULL
DROP TABLE T5
IF OBJECT_ID('T6') IS NOT NULL
DROP TABLE T6
IF OBJECT_ID('T3_T5') IS NOT NULL
DROP TABLE T3_T5
IF OBJECT_ID('T3_T5') IS NOT NULL
DROP TABLE T4_T5
CREATE TABLE T6(
T6_IdINT IDENTITY(1, 1) NOT NULL PRIMARY KEY,
T6_Name CHAR(5) NOT NULL
)
CREATE TABLE T2(
T2_IdINT IDENTITY(1, 1) NOT NULL PRIMARY KEY,
T2_Val1CHAR(5) NOT NULL,
T2_Val2CHAR(5),
T6_IdINT FOREIGN KEY REFERENCES T6(T6_Id) NOT NULL
)
CREATE TABLE T1(
T1_IdINT IDENTITY(1, 1) PRIMARY KEY,
T2_IdINT FOREIGN KEY REFERENCES T2(T2_Id) NOT NULL,
T6_IdINT FOREIGN KEY REFERENCES T6(T6_Id) NOT NULL
)
CREATE TABLE T3(
T1_IdINT FOREIGN KEY REFERENCES T1(T1_Id) NOT NULL PRIMARY KEY,
T3_Col1CHAR(5) NOT NULL,
T3_Col2CHAR(5)
)
CREATE TABLE T4(
T1_IdINT FOREIGN KEY REFERENCES T1(T1_Id) NOT NULL PRIMARY KEY,
T4_ColValCHAR(5) NOT NULL
)
CREATE TABLE T5(
T5_IdINT IDENTITY(1, 1) PRIMARY KEY,
T5_DateDATETIME NOT NULL,
T6_IdINT FOREIGN KEY REFERENCES T6(T6_Id) NOT NULL
)
CREATE TABLE T3_T5(
T3_T5_Id INT IDENTITY(1, 1) PRIMARY KEY,
T1_IdINT FOREIGN KEY REFERENCES T3(T1_Id) NOT NULL,
T5_IdINT FOREIGN KEY REFERENCES T5(T5_Id) NOT NULL
)
CREATE TABLE T4_T5(
T4_T5_Id INT IDENTITY(1, 1) PRIMARY KEY,
T1_IdINT FOREIGN KEY REFERENCES T4(T1_Id) NOT NULL,
T5_IdINT FOREIGN KEY REFERENCES T5(T5_Id) NOT NULL
)
Abhijit - http://abhijitmore.wordpress.com
June 29, 2011 at 6:34 am
Guessing from the table structure you provided, this isn't a hierarchy at all. You're querying from one table to another. Is that what you're doing?
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
June 29, 2011 at 12:17 pm
What if there's a cycle (i.e., a loop) in the FKs? That would cause an infinite number of possible paths.
That is, if:
T1 => T2
T2 => T3
T3 => T4
T3 => T2
Then your paths would be:
1. T1>T2>T3>T4
2. T1>T2>T3>T2>T3>T4
3. T1>T2>T3>T2>T3>T2>T3>T4
...
and so on, ad infinitum?
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]
June 29, 2011 at 12:36 pm
May I ask what the purose of this request is?
Different "paths" may lead to different result (e.g. duplicate rows of the target table due to a 1:n relationship somewhere in between on one path vs. unique rows when using another path).
What if a foreign key reference has been dropped (either on purpose or by accident)? The path would still exist but would no longer be available.
June 29, 2011 at 3:28 pm
See http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290
N 56°04'39.16"
E 12°55'05.25"
June 29, 2011 at 3:42 pm
*facepalm* This is not pretty.
As to your first comment, your first post was at ~1:30 AM, and the next at ~5:45 AM for me. I was asleep while you waited. 😉
Next, what you're discussing is known in AI circles as pathing. Think about video games for a moment and the process of moving a mobile from location A to location B. It needs to figure out the ways to get there and then decide on the best one.
Now, you only need the first half of that component. Most of those algorithms (Google A* or A Star pathing for a well known algorithm) will determine by a distance calculation, which you won't have. You don't even have a grid to follow, just next connection paths. What this means is you're going to have to explode EACH node across possible paths until all possibilities are found. Since you're not trying to do this realtime in a game, this can be done but it's going to be very chewy.
Look into pathing algorithms to find your start. You're going to need to make sure you cover node reversing (Moving to node 2 and then back to node 1 recursively) and node re-usage (A-B-C-D-B-C...) as mentioned previously. There are probably a dozen names for those concepts but you get the drift, I've been out of touch with AI pathing for a few years.
You've got a lot of work ahead of you to find your best algorithm in this. I'm very curious as to what you come up with though. If you get stuck, post your DDL for your subtable that you're using off sys.foreign_keys, the proc until the point where you get jammed, and we'll see if we can get your recursion back on track. This is going to be a recursive structure, there's no avoiding that.
EDIT: I should mention the reason I'm sending you to the game developers to learn the algorithm is they have spent decades trying to get this process cleaner. It's not simple, it's not easy, and you're going to get immersed in some pretty heavy duty concepts that wouldn't be easy to transfer via a forum.
Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.
For better assistance in answering your questions[/url] | Forum Netiquette
For index/tuning help, follow these directions.[/url] |Tally Tables[/url]
Twitter: @AnyWayDBA
June 29, 2011 at 6:08 pm
He's right. I would say this is one of those jobs better handled outside SQL.
__________________________________________________
Against stupidity the gods themselves contend in vain. -- Friedrich Schiller
Stop, children, what's that sound? Everybody look what's going down. -- Stephen Stills
June 30, 2011 at 1:24 am
I tried some ways to do this but I am not getting the expected result as mentioned in trail. Here is some workaround (see the attachment)
Abhijit - http://abhijitmore.wordpress.com
Viewing 12 posts - 1 through 11 (of 11 total)
You must be logged in to reply to this topic. Login to reply