Database design / normalization structure needs to contain ANDs, ORs, optional elements and their relationships

Question

I want to store the details of college courses in a (MySql) database but I'm not sure how to maintain the relationship between modules and selections.

Basically, a course can have mandatory section, group of optional modules, an options section and within each there can be selections which contain ANDs or ORs between modules.

---

Simple example:
A 60 credit course has a few mandatory modules which make up 40 credits. That leaves 20 credits to be selected from the group of optional modules. (Modules themselves can hold different amount of credits). Effectively; ('Mandatory module 1' AND 'Mandatory module 2'... AND'Mandatory module N') AND (40 credits from 'optional modules'),

ANDs & ORs:
When I say modules above, it could be a single module or it could be "Module x OR Module Y" i.e. in the mandatory section. (those modules would obviously have to have the same credit weight). Or in the optional section there might be single modules or even one of the choices could be something like "module x AND module y".

Options:
The students may have to take the mandatory modules plus one of n options which may or may not contain ANDs, ORs, and mandatory & optional sections; i.e. An 'Option' has all the attributes of the overall course modules selection. The Options section would be AND'd or OR'd with other sections like mandatory or optional; i.e. mandatory modules "plus one of the following options". Effectively the options section is just 'Option 1' OR 'Option 2'... OR 'Option N'.

---

The problem is how do I store all of the AND and OR relationships when the operand may be another AND/OR operation or a single module, and keep track of the amount of credits allowed for each selection; e.g. "20 credits from the following:" (group of optional modules).

Answer 1

A very simple, first approach would be using just 4 tables:

TABLE Course 
( CourseId 
, Title 
, TotalCredits 
, ... other stuff
, PRIMARY KEY (CourseId)
) ;

TABLE Module 
( ModuleId 
, Description 
, Hours
, Credits
, ... other stuff
, PRIMARY KEY (ModuleId)
) ;

and the combinations allowed through these 2:

TABLE Course_Module 
( CourseID                 --- for this course
, ModuleID                 --- this module is allowed (optional or mandatory)
, PRIMARY KEY (CourseID, ModuleId)
, FOREIGN KEY (CourseId) 
    REFERENCES Course (CourseId)
, FOREIGN KEY (ModuleId)
    REFERENCES Module (ModuleId)
) ;

TABLE Course_MandatoryModule 
( CourseID                  --- for this course
, ModuleID                  --- this module is mandatory
, PRIMARY KEY (CourseID, ModuleId)
, FOREIGN KEY (CourseID, ModuleId)
    REFERENCES Course_Module (CourseID, ModuleId)
) ;

---

Now, if your allowed combinations of modules and courses is more complicated, as your description suggests, instead of the Course_Module and the Course_MandatoryModule tables you could define a complex hierarchical model:

Courses:

TABLE Course                        --- same as previous model
( CourseId 
, Title 
, TotalCredits 
, ... other stuff
, PRIMARY KEY (CourseId)
) ;

Modules and groups of (modules):

TABLE ModuleEntity                  --- the supertype for both
( ModuleEntityId                    --- modules and group of modules
, PRIMARY KEY (ModuleEntityId)
) ;

TABLE Module                        --- subtype
( ModuleId 
, Description 
, Hours
, Credits
, ... other stuff
, PRIMARY KEY (ModuleId)
, FOREIGN KEY (ModuleId) 
    REFERENCES ModuleEntity (ModuleEntityId)
) ;

TABLE ModuleGroup                  --- group of modules
( ModuleGroupId                    --- subtype of the supertype (entity)
, GroupDescription        
, PRIMARY KEY (ModuleGroupId)
, FOREIGN KEY (ModuleGroupId) 
    REFERENCES ModuleEntity (ModuleEntityId)
) ;

and relationship (module belongs to group):

TABLE Module_in_Group  
( ModuleEntityId               --- this module or group
, ModuleGroupId                --- is in this group
, PRIMARY KEY (ModuleEntityId, ModuleGroupID)
, FOREIGN KEY (ModuleEntityId)
    REFERENCES ModuleEntity (ModuleEntityId)
, FOREIGN KEY (ModuleGroupId)
    REFERENCES ModuleGroup (ModuleGroupId)
) ;

and (finally) course can have group of modules:

TABLE Course_ModuleGroup
( CourseId                 --- for this course
, ModuleGroupId            --- this module group is allowed
, PRIMARY KEY (CourseID, ModuleGroupId)
, FOREIGN KEY (CourseId) 
    REFERENCES Course (CourseId)
, FOREIGN KEY (ModuleGroupId)
    REFERENCES ModuleGroup (ModuleGroupId)
) ;

Answer 2

The design is fairly straight-forward you just need a recursive "group" table with constraints.

Course
- ID
- Title
- Credits

Course_Group
- CourseID
- GroupID

Group
- ID
- GroupID
- Description
- AtLeastNSelections
- AtLeastNCredits

Group_Module
- GroupID
- ModuleID

Module
- ID
- Title
- Credits

An example structure would be

Course: 1, "Math Major", 60
Group: 1, NULL, "Core Modules", 2, 40
Course_Group: 1, 1
    Group: 2, 1, "Required (5) Core Modules", 5, 25
    Course_Group: 1, 1
    Group_Module: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)
        Module: 1, "Calculus I", 5
        Module: 2, "Calculus II", 5
        Module: 3, "Calculus III", 5
        Module: 4, "Stats I", 5
        Module: 5, "Stats II", 5
    Group: 3, 1, "Required (3) Of (N) Modules", 3, 15
    Course_Group: 1, 3
    Group_Module: (3, 6), (3, 7), (3, 8), (3, 9), (3, 10)
        Module: 6, "Number Theory", 5
        Module: 7, "Bridge Adv. Math", 5
        Module: 8, "Calculus IV", 5
        Module: 9, "Stats III", 5
        Module: 10, "Finite Math", 5
Group: 4, NULL, "Secondary Modules", 1, 20
Course_Group: 1, 4
    Group: 5, 4, "Comp. Sci.", 2, 0
    Course_Group: 1, 5
    Group_Module: (5, 11), (5, 12), (5, 13), (5, 14), (5, 15), (5, 16)
        Module: 11, "Math in Hardware", 4
        Module: 12, "Math in Software", 4
        Module: 13, "Programming 101", 4
        Module: 14, "Algorithms 101", 4
        Module: 15, "Programming I", 5
        Module: 16, "Programming II", 5
    Group: 6, 4, "Physics", 0, 8
    Course_Group: 1, 6
    Group_Module: (6, 17), (6, 18), (6, 19), (6, 20)
        Module: 17, "Physics Mechanics", 4
        Module: 18, "Physics Thermodynamics", 4
        Module: 19, "Physics Magnetism", 5
        Module: 20, "Physics Theoretical", 5
    Group: 7, 4, "Gen. Ed.", 0, 0
    Course_Group: 1, 7
    Group_Module: (7, 21), (7, 22), (7, 23), (7, 24)
        Module: 21, "Business Writing", 3
        Module: 22, "Ethics", 3
        Module: 23, "Aesthetics", 3
        Module: 24, "Graphic Design", 3

A quick walk through... the course "Math Major" has two groups under it "Core Modules" and "Secondary Modules". "Core Modules" requires AT LEAST 2 children AND AT LEAST 40 credits. "Secondary Modules" requires AT LEAST 1 child AND AT LEAST 20 credits.

You can see that the constraints of the groups under "Core Modules" are more restrictive than the constraints of the groups under "Secondary Modules".

To output the example structure above would be something like.

SELECT c.Title, g.Description, m.Title FROM Course c
 INNER JOIN Course_Group cg ON c.ID = cg.CourseID
 INNER JOIN Group g ON cg.GroupID = g.ID
 INNER JOIN Group_Module gm ON g.ID = gm.GroupID
 INNER JOIN Module m ON gm.ModuleID = m.ID
WHERE c.ID = 1
ORDER BY g.GroupID, g.ID, m.Title  

So if you have a course and modules you can get all the groups for the course from the Course_Group table and get which group the modules belong to from the Group_Module table. Once you have the modules in their group(s) you can check the group's constraints AtLeastNSelections AND AtLeastNCredits walking up the Group.GroupID parentage chain until you get to Group.GroupID = NULL.

Answer 3

You can create a recursive table structure here, wherein Options reference their parent options.

• The "main" options can then be identified by querying this table for all options with "null" parents.

• The "and-or" relationships can be implemented by a separate "option-set" table, where the primary key is to an "option". The option-set table's with null self-references are the "root" point for defining a course's options. From that point, you will select option-set records with parent = root. This will be the first "level" of options. Some will be mandatory, some won't. To express that, you will have to have a boolean attribute on the option-set table as a flag. Thus each option-set is defined in terms of smaller option-sets. Of course, ultimately, once you get to the bottom, your option-set's will define an actual class at some point.

I would suggest that this can much more effectively be modelled in JSON or XML, since those data structures support hierarchies in a much more expressive manner.

Answer 4

You can probably do something like this:

TABLE course_definition (
    ID int,
    num_mandatory_sections int,
    mandatory_hours int,
    num_optional_modules int,
    optional_hours int,
);

TABLE modules (
    ID int,
    Description varchar(max),
    hours int,
    ....
);

TABLE course (
    Course_ID int FOREIGN KEY (course_definition.id),
    module_id int FOREIGN KEY (modules.id)
);

TABLE course_module_relationship (
     Course_ID int FOREIGN KEY (course_definition.id),
     module_ID int foreign key (modules.id),
     Requirement_flag ENUM ("MANDATORY", "OPTIONAL")
);

TABLE Student_to_course (
     Student_ID int,
     Course_ID int foreign key (course_definition.id)
);

TABLE Student_to_module (
     Student_ID int,
     Module_ID int FOREIGN KEY (module.id)
);

If you really need to be able to create group modules aka single module created from the multiple other modules then table module will need to have a flag field:

group_module boolean

and the following table should be added:

TABLE module_groupings (
    group_module_ID int foreign key (module.id)
    dependant_module_id int foreign key (module.id)
);

This is more of pseudo code but you get the idea. The table course and course_module_relationship will have no keys and store your relationships as they can be many to many as I understand the problem. So basically the code that will read process the selections will have to check whether or not this meets the criteria for the course_definition.

If the Mandatory section to Course is a 1-to-1 relationship you can separate your mandatory section into a separate table but you will have to analyze your data more thoroughly.