Complex SQL query I can't figure out

Question

I'm working on creating a report for the open source tool Validation Manager. I managed to pull out a report of all requirements covered after lots of work. I'm trying to make a report to list the ones not covered, but using not in gets the query into a never ending processing state.

Here's the DD diagram:

The involved tables are in the bottom right side of the diagram. Sample data can be obtained here. What would be the correct way to get uncovered requirements?

FYI: Uncovered requirements are those that doesn't have a related step and/or their children requirements are covered.

The main issue is that there are, in theory, infinite number of levels of requirement relationships and the SQL I have only works for 2 levels. Trying to figure out a way to look as deep as necessary.

As reference, see the query for the covered requirements below (which is the opposite of what I need):

select
    c.covered, t.total
from
    (SELECT DISTINCT
        count(distinct unique_id) as covered
    FROM
        requirement
    WHERE
        requirement.id IN (select
                requirement.id
            from
                `requirement` requirement
            INNER JOIN `step_has_requirement` step_has_requirement ON requirement.`id` = step_has_requirement.`requirement_id`
            INNER JOIN `step` step ON step_has_requirement.`step_id` = step.`id`
                AND step.`test_case_id` = step_has_requirement.`step_test_case_id`
                AND step.`test_case_test_id` = step_has_requirement.`step_test_case_test_id`
            INNER JOIN `test_case` test_case ON step.`test_case_id` = test_case.`id`
                AND test_case.`test_id` = step.`test_case_test_id`
            INNER JOIN `test` test ON test_case.`test_id` = test.`id`
            INNER JOIN `test_plan_has_test` test_plan_has_test ON test.`id` = test_plan_has_test.`test_id`
            INNER JOIN `test_plan` test_plan ON test_plan_has_test.`test_plan_id` = test_plan.`id`
                AND test_plan.`test_project_id` = test_plan_has_test.`test_plan_test_project_id`
            INNER JOIN `test_project` test_project ON test_plan.`test_project_id` = test_project.`id`
            INNER JOIN `requirement_status` requirement_status ON requirement.`requirement_status_id` = requirement_status.`id`
            INNER JOIN `requirement_spec_node` requirement_spec_node ON requirement.`requirement_spec_node_id` = requirement_spec_node.`id`
                AND requirement_spec_node.`requirement_spec_project_id` = requirement.`requirement_spec_node_requirement_spec_project_id`
                AND requirement_spec_node.`requirement_spec_spec_level_id` = requirement.`requirement_spec_node_requirement_spec_spec_level_id`
                AND requirement_spec_node.`requirement_spec_id` = requirement.`requirement_spec_node_requirement_spec_id`
            INNER JOIN `requirement_spec` requirement_spec ON requirement_spec_node.`requirement_spec_id` = requirement_spec.`id`
                AND requirement_spec.`project_id` = requirement_spec_node.`requirement_spec_project_id`
                AND requirement_spec.`spec_level_id` = requirement_spec_node.`requirement_spec_spec_level_id`
            INNER JOIN `project` project ON requirement_spec.`project_id` = project.`id`
            WHERE
                requirement_status.status = 'general.approved'
                    and (project.id = $P{target_project_id}
                    or project.parent_project_id = $P{target_project_id}))
        or requirement.id IN (select parent_requirement_id from requirement_has_requirement where parent_requirement_id = requirement.id
and requirement_id in (select
                requirement.id
            from
                `requirement` requirement
            INNER JOIN `step_has_requirement` step_has_requirement ON requirement.`id` = step_has_requirement.`requirement_id`
            INNER JOIN `step` step ON step_has_requirement.`step_id` = step.`id`
                AND step.`test_case_id` = step_has_requirement.`step_test_case_id`
                AND step.`test_case_test_id` = step_has_requirement.`step_test_case_test_id`
            INNER JOIN `test_case` test_case ON step.`test_case_id` = test_case.`id`
                AND test_case.`test_id` = step.`test_case_test_id`
            INNER JOIN `test` test ON test_case.`test_id` = test.`id`
            INNER JOIN `test_plan_has_test` test_plan_has_test ON test.`id` = test_plan_has_test.`test_id`
            INNER JOIN `test_plan` test_plan ON test_plan_has_test.`test_plan_id` = test_plan.`id`
                AND test_plan.`test_project_id` = test_plan_has_test.`test_plan_test_project_id`
            INNER JOIN `test_project` test_project ON test_plan.`test_project_id` = test_project.`id`
            INNER JOIN `requirement_status` requirement_status ON requirement.`requirement_status_id` = requirement_status.`id`
            INNER JOIN `requirement_spec_node` requirement_spec_node ON requirement.`requirement_spec_node_id` = requirement_spec_node.`id`
                AND requirement_spec_node.`requirement_spec_project_id` = requirement.`requirement_spec_node_requirement_spec_project_id`
                AND requirement_spec_node.`requirement_spec_spec_level_id` = requirement.`requirement_spec_node_requirement_spec_spec_level_id`
                AND requirement_spec_node.`requirement_spec_id` = requirement.`requirement_spec_node_requirement_spec_id`
            INNER JOIN `requirement_spec` requirement_spec ON requirement_spec_node.`requirement_spec_id` = requirement_spec.`id`
                AND requirement_spec.`project_id` = requirement_spec_node.`requirement_spec_project_id`
                AND requirement_spec.`spec_level_id` = requirement_spec_node.`requirement_spec_spec_level_id`
            INNER JOIN `project` project ON requirement_spec.`project_id` = project.`id`
            WHERE
                requirement_status.status = 'general.approved'
                    and (project.id = $P{target_project_id}
                    or project.parent_project_id = $P{target_project_id})))
    order by unique_id) c,
    (SELECT
        count(distinct unique_id) AS total
    FROM
        `requirement_status` requirement_status
    INNER JOIN `requirement` requirement ON requirement_status.`id` = requirement.`requirement_status_id`
    INNER JOIN `requirement_spec_node` requirement_spec_node ON requirement.`requirement_spec_node_id` = requirement_spec_node.`id`
        AND requirement_spec_node.`requirement_spec_id` = requirement.`requirement_spec_node_requirement_spec_id`
    INNER JOIN `requirement_spec` requirement_spec ON requirement_spec_node.`requirement_spec_id` = requirement_spec.`id`
        AND requirement_spec.`spec_level_id` = requirement_spec_node.`requirement_spec_spec_level_id`
        AND requirement_spec.`project_id` = requirement_spec_node.`requirement_spec_project_id`
    INNER JOIN `project` project ON requirement_spec.`project_id` = project.`id`
    INNER JOIN `spec_level` spec_level ON requirement_spec.`spec_level_id` = spec_level.`id`
    WHERE
        requirement_status.status = 'general.approved'
            and (project.id = $P{target_project_id}
            or project.parent_project_id = $P{target_project_id})) t

Note: The SQL there is an example on how I managed to do the opposite, get the covered requirements. I would like to get the ones not covered. That SQl query is working properly.

What I am looking for is same for the parts which are not covered now(in the above)!

Answer 1

First thing's first

Your schema is your biggest enemy. I have attached an SQLFiddle with your step table. It is a very impressive table, but impressive isn't always workable in SQL. You would do very well to refactor your tables and make them normalized. There are very few cases where it makes sense to put multiple integers into one text file with commas separating them. If the only thing you are going to be putting in that column, ever, is integers separated by columns, you are failing to make your SQL schema even First Normal Form. While it may seem easier to design your schema this way, it is only on the face that you are doing so. In reality, you are creating a mess of epic proportions for yourself - as you may now be discovering. By failing to even meet First Normal Form, you are failing to take advantage of any of SQL's inherent relational power.

Edit This is a fairly large schema to take in. My reaction to being not 1NF was the text part of step. I don't really know what it is aiming to do so it is hard to say for sure, but it put up a big red flag when I saw multiple rows with the same integer columns in a text box separated by commas. That usually is a sign that several columns have been concatenated into one column. After examining other parts of the schema, it is clear that other parts are normalized. It doesn't appear to be an integral part of your schema, so, my mistake. That being said this is still a very complex application with a large number of cross referencing tables. Having both requirement_has_requirement and step_has_requirement as a table may have benefits but it also has serious drawbacks.

I question whether you need to differentiate steps from requirements in the way you currently are. Is a requirement not just another step? I understand you need different columns, but that could be solved by having a requirement_addendum and a step_addendum table, which can be called on at need and ignored at need as well. I note that you have versioning in requirement. Do you not anticipate that you will need versions in step? Do you anticipate that some of your requirements will be versioned at different times than others? Could a version table be created to cover the three version columns in order to have just one version_id in your requirement table and related tables?

In any case, assuming you can't do anything substantial to this table and you just need to pull a query...

My Suggestion

You have not actually defined what "as deep as necessary" is, so you need to determine what "as deep as necessary" means. If you have a formulaic way of discovering this, you can accomplish this relatively easily by creating a recursive procedure like @RandomSeed suggested. If you do not have a particularly formulaic way of determining what "as deep as necessary" is, are you going to determine by a client-defined number of levels? If so you can still rely on a stored procedure.

If you want to make these determinations on a more case-by-case basis, or if you suspect these requirements might change, you can also consider hard-coding the information into a MySQL table which stores metadata for your schema. This can allow you to determine how many steps by running an SQL SELECT query on this metadata table to receive your answer. You can easily assign each step or each scenario to have a number of recursions you want to accomplish. You would be able to use this information in a Stored Procedure.

If you can alter your table at all...

The benefit to altering your table even slightly is that you can create a terminal to step_has_requirement and requirement_has_requirement. Each record would then have a "yes" (1) or a "no" (0) to determine if there was a requirement involved. You could then run a query on any record which was a 1 or a 0 at your leisure.

requirement_has_requirement

id  | status | major_version | mid_version | minor_version
 .. |   0    |      NULL     |    NULL     |    NULL
 .. |   1    |        ..     |      ..     |     ..

step_has_requirement

id  | status | ...

Etc.

Query now becomes as simple as toggling between status 0 and status 1 to find your records. You can query all elements of your hierarchy at the same time.

Please note that this becomes much easier and contains less repetition if step and requirement are in one table with additional columns on separate tables based on whether it was a requirement or a step. There are no doubt drawbacks to this but there are also benefits. If you have the ability to make these changes prior to Volume 1 it could be beneficial.

Conclusion

You clearly have a very sophisticated application in development. Unfortunately the sophistication is outgrowing your schema. There is no "best" way to accomplish what you are looking for without making some minor changes to your schema. If changing your schema is not currently an option then I strongly advise you to make a quick hack so as not to waste more time and make a request to adapt the schema soon, before this becomes an even larger headache for you.

Answer 2

It's a mess, but I took a crack at it. By breaking it up into chunks with CTEs, you can troubleshoot smaller pieces.

;WITH 

cteRequirement (id) AS
(   SELECT      distinct requirement.id
    FROM        requirement
    INNER JOIN  step_has_requirement 
        ON      requirement.id                  = step_has_requirement.requirement_id
    INNER JOIN  step 
        ON      step.id                         = step_has_requirement.step_id
        AND     step.test_case_id               = step_has_requirement.step_test_case_id
        AND     step.test_case_test_id          = step_has_requirement.step_test_case_test_id
    INNER JOIN  test_case 
        ON      test_case.id                    = step.test_case_id
        AND     test_case.test_id               = step.test_case_test_id
    INNER JOIN  test 
        ON      test.id = test_case.test_id
    INNER JOIN  test_plan_has_test 
        ON      test_plan_has_test.test_id      = test.id
    INNER JOIN  test_plan 
        ON      test_plan.id                    = test_plan_has_test.test_plan_id
        AND     test_plan.test_project_id       = test_plan_has_test.test_plan_test_project_id
    INNER JOIN  test_project 
        ON      test_project.id                 = test_plan.test_project_id
    INNER JOIN  requirement_status 
        ON      requirement_status.id           = requirement.requirement_status_id
    INNER JOIN  requirement_spec_node 
        ON      requirement_spec_node.id                                = requirement.requirement_spec_node_id
        AND     requirement_spec_node.requirement_spec_project_id       = requirement.requirement_spec_node_requirement_spec_project_id
        AND     requirement_spec_node.requirement_spec_spec_level_id    = requirement.requirement_spec_node_requirement_spec_spec_level_id
        AND     requirement_spec_node.requirement_spec_id               = requirement.requirement_spec_node_requirement_spec_id
    INNER JOIN  requirement_spec 
        ON      requirement_spec.id             = requirement_spec_node.requirement_spec_id
        AND     requirement_spec.project_id     = requirement_spec_node.requirement_spec_project_id
        AND     requirement_spec.spec_level_id  = requirement_spec_node.requirement_spec_spec_level_id
    INNER JOIN  project 
        ON      project.id                  = requirement_spec.project_id
    WHERE       requirement_status.[status] = 'general.approved'
        and     (project.id = $P{target_project_id} or project.parent_project_id = $P{target_project_id})
),

cteParent (id) AS
(   SELECT      DISTINCT parent_requirement_id
    FROM        requirement_has_requirement
    INNER JOIN  cteRequirement
        ON      cteRequirement.id = requirement_has_requirement.requirement_id
    WHERE       parent_requirement_id = requirement.id
),

ListOfRequirementIDs (requirement_id) AS
(   SELECT id FROM cteRequirement UNION
    SELECT id FROM cteParents
),

ListOfUniqueIDs (unique_id) AS
(   SELECT      DISTINCT unique_id
    FROM        requirement_status
    INNER JOIN  requirement 
        ON      requirement.requirement_status_id           = requirement_status.id
    INNER JOIN  requirement_spec_node 
        ON      requirement_spec_node.id                    = requirement.requirement_spec_node_id
        AND     requirement_spec_node.requirement_spec_id   = requirement.requirement_spec_node_requirement_spec_id
    INNER JOIN  requirement_spec 
        ON      requirement_spec_node.requirement_spec_id   = requirement_spec.id
        AND     requirement_spec.spec_level_id              = requirement_spec_node.requirement_spec_spec_level_id
        AND     requirement_spec.project_id                 = requirement_spec_node.requirement_spec_project_id
    INNER JOIN  project 
        ON      project.id                                  = requirement_spec.project_id
    INNER JOIN  spec_level 
        ON      spec_level.id                               = requirement_spec.spec_level_id
    WHERE       requirement_status.status = 'general.approved'
        and     (project.id = $P{target_project_id} or project.parent_project_id = $P{target_project_id})
)

SELECT      'Covered' AS [Type], COUNT(ListOfRequirementIDs.requirement_id) AS Cnt
FROM        ListOfRequirementIDs
UNION ALL
SELECT      'Total' AS [Type],   COUNT(ListOfUniqueIDs.unique_id) AS Cnt
FROM        ListOfUniqueIDs