1 2 Previous Next 27 Replies Latest reply: Jun 17, 2013 5:13 AM by popovitsj RSS

    Query to find previous Activity in STM

    popovitsj
      I have a database to reflect a State Transition Machine (STM). It contains 3 tables: Activity, Node and Transition.

      The Node and Transition tables are the configuration of the STM. They define the different possible states and the possible transitions between states.

      The path I take through the STM is recorded in the Activity Table. A record is created for every Node visited.

      I need a query that uses the id of my current Activity to find my previous activity, i.e. the activity that directly preceded me. The following rules apply:
      - My Id is meaningless
      - It has to work for different configurations of the transition and node tables, but:
      - The Start Node is always Node 'A'.
      - There are no recursive transitions, e.g. ('B','B');
      - There are no circular transitions, e.g. ('B','C') and ('C','B')
      - The transition and node tables will never change between the creation of the first activity and the execution of the query.
      - The path reflected by the Activity table is always a valid path.
      - My current activity is always the last activity.

      For the dataset below, find the previous activity of activity with id=4. The correct answer is 'C'.
      DROP TABLE Transition;
      DROP TABLE Activity;
      DROP TABLE Node;
      
      CREATE TABLE Node
      (
           Id VARCHAR2(1) PRIMARY KEY
      );
      
      CREATE TABLE Activity
      (
           Id Number(8,0) PRIMARY KEY,
           Node_Id VARCHAR2(1)
      );
      
      CREATE TABLE Transition
      (
           FromNode_Id VARCHAR2(1),
           ToNode_Id VARCHAR2(1)
      );
      
      ALTER TABLE Activity
      ADD FOREIGN KEY
      (Node_Id) REFERENCES Node(Id);
      
      ALTER TABLE Transition
      ADD FOREIGN KEY
      (FromNode_Id) REFERENCES Node(Id);
      
      ALTER TABLE Transition
      ADD FOREIGN KEY
      (ToNode_Id) REFERENCES Node(Id);
      
      INSERT INTO Node VALUES ('A');
      INSERT INTO Node VALUES ('B');
      INSERT INTO Node VALUES ('C');
      INSERT INTO Node VALUES ('D');
      
      INSERT INTO Transition VALUES ('A','B');
      INSERT INTO Transition VALUES ('B','C');
      INSERT INTO Transition VALUES ('B','D');
      INSERT INTO Transition VALUES ('C','D');
      
      INSERT INTO Activity VALUES (1,'A');
      INSERT INTO Activity VALUES (2,'B');
      INSERT INTO Activity VALUES (3,'C');
      INSERT INTO Activity VALUES (4,'D');
      Desired output:
      ID
      -
      C
        • 1. Re: Query to find previous Activity in STM
          jeneesh
          This?
          select t.fromnode_id
          from transition t,activity a
          where t.tonode_id = a.node_id
          and a.id = 4;
          If not, please explain the logic to reach at the output...

          Edited by: jeneesh on May 2, 2013 6:39 PM
          • 2. Re: Query to find previous Activity in STM
            popovitsj
            No, that's not correct. That returns both C and B, whereas it should return only C.

            I'm not sure myself what the best way is to reason this, but a possible way is like this:

            I can only reach D through C and B. I visited both of them. I can't reach B through C, so C must be my previous node.
            • 3. Re: Query to find previous Activity in STM
              AlbertoFaenza
              Hi popovitsj,

              your post would be easier to understand if you specify your expected output for the sample data you have posted.

              Regards.
              Al

              Edited by: Alberto Faenza on May 2, 2013 3:14 PM
              • 4. Re: Query to find previous Activity in STM
                Frank Kulash
                Hi,

                I'm not sure I understand the problem.
                popovitsj wrote:
                - My Id is meaningless
                Are you saying that Activity.Id is completely meaningless?
                If Activity.Id indicates the order of the steps (not necessarily consecutive integers), but otherwise has no meaning, then you can say:
                SELECT     MIN (Node_Id) KEEP (DENSE_RANK LAST ORDER BY Id)
                             AS prev_id
                FROM     activity
                WHERE     Id     < 4
                ;
                If Activity.Id is completely meaningless, are you saying that Activity will always contain a single, complete path through the graph, but you have to figure out the one path that includes all the rows in Activity?

                Thanks for posting the sample data so clearly.
                Whenever you have a problem, also say which version of Oracle you're using (e.g., 11.2.0.2.0). This is always important, but especially so in this problem. Graph traversal usually means CONNECT BY, and every version since Oracle 7 has had major changes in this area. Even the difference between Oracle 11.1 and 11.2 can be enormous, if the problem calls for a recursive WITH clause.
                Edited by: Frank Kulash on May 2, 2013 9:25 AM
                • 5. Re: Query to find previous Activity in STM
                  AlbertoFaenza
                  popovitsj wrote:
                  No, that's not correct. That returns both C and B, whereas it should return only C.

                  I'm not sure myself what the best way is to reason this, but a possible way is like this:
                  I'm afraid I'm not the only one that don't understand your explanation:
                  I can only reach D through C and B. I visited both of them
                  This is clear as the transition are either
                  B to D
                  or
                  C to D
                  I can't reach B through C, so C must be my previous node.
                  This I don't understand. I see a transition
                  B to C
                  As far as I see state D can be reached from state C or state B. What are criteria why you say the answer has to be C?

                  Regards.
                  Al
                  • 6. Re: Query to find previous Activity in STM
                    popovitsj
                    @Frank Kulash: That is exactly the problem I am faced with.
                    • 7. Re: Query to find previous Activity in STM
                      popovitsj
                      @Alberto Faenza: The transition (B,C) means that there is a possible transition from B to C, but not from C to B. Therefore, C can be reached through B, but B cannot be reached through C.
                      • 8. Re: Query to find previous Activity in STM
                        popovitsj
                        Just to be sure this is clear, Frank described the problem perfectly:

                        >
                        Activity will always contain a single, complete path through the graph, but you have to figure out the one path that includes all the rows in Activity.
                        • 9. Re: Query to find previous Activity in STM
                          Frank Kulash
                          Hi,

                          Assuming Activity_id tells us nothing about the path, but that all the rows in Activity together form a single, complete path, we can get the desired results this way:
                          WITH     all_paths    AS
                          (
                               SELECT     'A' || SYS_CONNECT_BY_PATH (a.Node_id, '/')
                                        || '/'     AS node_id_path
                               FROM     Transition  t
                               JOIN     Activity    a  ON  a.Node_Id  = t.ToNode_Id
                               WHERE     LEVEL             = (
                                                      SELECT  COUNT (*)
                                                   FROM     activity
                                                   ) - 1
                               START WITH  t.FromNode_Id  = 'A'
                               CONNECT BY  t.FromNode_Id  = PRIOR t.ToNode_Id
                          )
                          SELECT       REGEXP_SUBSTR ( node_id_path
                                           , '([^/]+)/' || (
                                                              SELECT  Node_Id
                                                       FROM    activity
                                                       WHERE   Id     = 4  -- target_id
                                                          )
                                                   || '/'
                                         , 1
                                         , 1
                                         , NULL
                                         , 1
                                         )     AS prev_id
                          FROM       all_paths
                          ;
                          This assumes there is some character (I used '/' above) that we know never appears in Activity.Node_Id.

                          Since there are no loops in Transition, there can not be more than 1 path that involves all the rows in Activity. If there are N rows in Activity, that complete path will be the one that extends to LEVEL = N-1. (That's N-1, not N, because the join between Activity and Transition will always leave out the 1 row in Activity that has Node_Id = 'A'.) Once we have the complete path (which is node_id_path in the 1 row produced by all_paths), we just need to figure out what was the Node_Id that corresponds to the target id (4 in this example), and find the previous node_id from the delimited node_id_path.
                          • 10. Re: Query to find previous Activity in STM
                            jeneesh
                            If I understood your rules correctly..
                            select fromnode_id
                            from
                            (
                              select t.fromnode_id,t.tonode_id,level l
                              from transition t
                              start with fromnode_id = 'A'
                              connect by prior tonode_id = fromnode_id
                            )
                            where (tonode_id,l+1 ) =
                               (
                                 select max(decode(id,4,node_id)),count(*)
                                 from activity
                               );
                            
                            F
                            -
                            C
                            Edited by: jeneesh on May 2, 2013 7:34 PM
                            • 11. Re: Query to find previous Activity in STM
                              popovitsj
                              @Frank: thx a lot :) I'm gonna take my sweet time to figure out how that one works :p. I've tried it with a little bit more complex graph and it still produces the right result.

                              I did get a 'Too many arguments exception' btw, but removing the last "1" resolved that. Like this:
                              WITH     all_paths    AS
                              (
                                   SELECT     'A' || SYS_CONNECT_BY_PATH (a.Node_id, '/')
                                            || '/'     AS node_id_path
                                   FROM     Transition  t
                                   JOIN     Activity    a  ON  a.Node_Id  = t.ToNode_Id
                                   WHERE     LEVEL             = (
                                                          SELECT  COUNT (*)
                                                       FROM     activity
                                                       ) - 1
                                   START WITH  t.FromNode_Id  = 'A'
                                   CONNECT BY  t.FromNode_Id  = PRIOR t.ToNode_Id
                              )
                              SELECT       REGEXP_SUBSTR ( node_id_path
                                               , '([^/]+)/' || (
                                                                  SELECT  Node_Id
                                                           FROM    activity
                                                           WHERE   Id     = 4
                                                              )
                                                       || '/'
                                             , 1
                                             , 1
                                             , NULL
                                             )     AS prev_id
                              FROM       all_paths
                              • 12. Re: Query to find previous Activity in STM
                                Cherif bh
                                Hi,

                                Try this one

                                with Activity as
                                (

                                select 1 Id, 'A' Node_Id FROM DUAL
                                union
                                select 2 Id, 'B' Node_Id FROM DUAL
                                union
                                select 3 Id, 'C' Node_Id FROM DUAL
                                union
                                select 4 Id, 'D' Node_Id FROM DUAL
                                )

                                select a.*,
                                lag(Node_Id, 1) over( order by id ) last_node
                                from Activity a
                                order by id desc ;


                                Thanks,
                                • 13. Re: Query to find previous Activity in STM
                                  popovitsj
                                  @jeneesh: unfortunately, this does not keep producing the right result when trying it with a more complex graph.
                                  • 14. Re: Query to find previous Activity in STM
                                    popovitsj
                                    @Cherif bh: this is not correct, because the Id of Activity is flagged as meaningless.
                                    1 2 Previous Next