During the summer break, Suraz is planning to go for a summer vacation and decided on the cities that he and his family want to visit. But he has not finalized in which order he wants to visit them yet. Please help Suraz to solve this dilemma and help him with all the possible orders he can visit these cities. Note that he neither wants to visit the same city again nor he wants to skip any city in his travel plan.
Write a SQL query to list out all different possible orders suraz can visit these cities.
We have been given a City table having h City_Name as an entity.
|1||Goa -> Manali -> Ooty -> Shimla|
|2||Goa -> Manali -> Shimla -> Ooty|
|3||Goa -> Ooty -> Manali -> Shimla|
|4||Goa -> Ooty -> Shimla -> Manali|
|5||Goa -> Shimla -> Manali -> Ooty|
|6||Goa -> Shimla -> Ooty -> Manali|
|7||Manali -> Goa -> Ooty -> Shimla|
|8||Manali -> Goa -> Shimla -> Ooty|
|9||Manali -> Ooty -> Goa -> Shimla|
|10||Manali -> Ooty -> Shimla -> Goa|
|11||Manali -> Shimla -> Goa -> Ooty|
|12||Manali -> Shimla -> Ooty -> Goa|
|13||Ooty -> Goa -> Manali -> Shimla|
|14||Ooty -> Goa -> Shimla -> Manali|
|15||Ooty -> Manali -> Goa -> Shimla|
|16||Ooty -> Manali -> Shimla -> Goa|
|17||Ooty -> Shimla -> Goa -> Manali|
|18||Ooty -> Shimla -> Manali -> Goa|
|19||Shimla -> Goa -> Manali -> Ooty|
|20||Shimla -> Goa -> Ooty -> Manali|
|21||Shimla -> Manali -> Goa -> Ooty|
|22||Shimla -> Manali -> Ooty -> Goa|
|23||Shimla -> Ooty -> Goa -> Manali|
|24||Shimla -> Ooty -> Manali -> Goa|
This solution is implemented using recursive CTE as we need to find all the possible combinations. As we need to have a plan with all the four cities, we are filtering only the plan that has four cities.
Before jumping into the final query Let's discuss What is Recursive CTE and how it works?
A recursive CTE references itself. It returns the result subset, then it repeatedly (recursively) references itself, and stops when it returns all the results. The syntax for a recursive CTE is not too different from that of a non-recursive CTE.
Recursive CTE Syntax:
cte_query_definition (the anchor member)
cte_query_definition (the recursive member)
SELECT * FROM cte_name;
At the beginning of your, CTE is the
WITH clause. However, if you want your CTE to be recursive, then after
WITH you write the
RECURSIVE keyword. Then it’s business as usual:
AS is followed by the parentheses with the CTE query definition. This first query definition is called the anchor member.
To connect the anchor member with the recursive member, you need to use the
UNION ALL command. The recursive member is, obviously, the recursive part of CTE that will reference the CTE itself. You’ll see how it works in an example very soon.
Recursive CTEs are used primarily when you want to query hierarchical data or graphs. This could be a company’s organizational structure, a family tree, a restaurant menu, or various routes between cities.
Now that we have understood how recursive CTEs work, let’s look into the final solution now.
SET @total_cities = (SELECT COUNT(1) FROM City);
WITH RECURSIVE travel (travel_plan, level) AS
SELECT City.City_Name AS travel_plan,
1 AS level FROM City
SELECT CONCAT(travel.travel_plan ,' -> ' ,City.City_Name) AS travel_plan,
level + 1
FROM City, travel
WHERE travel.level < @total_cities AND POSITION(City.City_Name IN travel.travel_plan) = 0
SELECT row_number() OVER(ORDER BY travel_plan) AS id, travel_plan
FROM travel WHERE level = @total_cities ORDER BY id;
The CTE starts with
WITH RECURSIVE, followed by its name and the query definition. This time, I’ll use the anchor member of the recursive query to create some data. The columns are
travel_plan. This is the point(with level =1) at which I want the recursion to start.
The UNION ALL connects this with the recursive member. This
SELECT statement will select the city, concatenate the cities with the travel plan, and the query will increase the
level column by one with every recursion. It will do that for every
city visited.The recursion will be performed for up to four cities (i.e. until it reaches the condition
WHERE level< 4).To achieve all that, I’ve joined the CTE with the table
Then comes the
SELECT a statement that pulls data from the CTE. It will select all the possible travel_plan ordered by id in ascending order.
Thanks for reading. I hope you enjoyed this fun little case study - it was fun for me to create!. You can also share your approach to solve this problem.