Domain ontologies that can solve various tasks using its concepts and determine fault reason for students' answers may serve as a good basis for creating for a testing system with extensive explanatory abilities. But capabilities of modern ontological reasoners may not be enough for this kind of task. In this study, we developed and tested an ontology able to build execution trace for the given algorithm containing sequences and alternatives and nd fault reasons for incorrect traces. The study also showed problems with the used reasoner that hinder the developed ontology from becoming fully e ective.
Ontology-based models and formal reasoning are used for knowledge
representation in di erent domains for a wide range of applications. Ontology Driven
Software Engineering (ODSE) approach [
The interesting and relevant topic within this aspect is algorithms' and
programs' analysis and synthesis using ontology-based models [
Copyright c 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
conceptual model of the developed software and is mapped to the entities in the
program code. This allows automating SRS detection and updating. The article
[
So ontology-based reasoning is a relevant approach for many tasks both in
software engineering as a professional activity and in software engineering
learning (e.g., to detect and explain the issues in the program code, to check the
conformity of the task and conceptual model with the program implementation,
etc). Ontologies are used in the learning process for di erent domains to generate
and grade questions [
According to [
Using complex questions targeting high cognitive levels also allows generating non-trivial feedback that is also an important problem in question generation. Explicitly de ning logical constraints for a correct answer to the given question allows detecting the broken constraints if a student's answer is incorrect, making possible showing explanations of the domain laws that the student violated in their answer.
In our research, we aim at creating a system for generating questions,
reasoning the correct answers to them using domain-dependent formal models like
ontologies, determine fault reasons in students' answers and explaining them to
correct misunderstandings of important domain concepts. One of the rst steps
requires studying whether modern ontological reasoners are capable of
performing the necessary tasks. When teaching introductory programming courses, one
of the complex tasks involving learning concepts of control structures is building
program trace [
An algorithm is represented as a tree of algorithmic structures: sequences, alternatives, and loops. Its trace is a sequence of acts of their execution in time; simple actions are represented as acts of their executions while complex algorithmic structures containing nested actions have di erent acts for the beginning and nishing of their execution. The trace also must contain the values of control conditions for alternatives and loops.
The input of the developed ontology includes: { An algorithm tree consisting of algorithmic structures and simple statements.
{ The set of unordered execution acts to be connected by the next_act to embody the correct trace. Acts executing expressions have expr_value datatype property holding the result.
{ The student's trace as student_next relations. Student's trace and correct trace share as many acts as possible.
The developed SWRL rules perform the following steps. First, the correct trace is built. The rules doing that are called positive. These rules look for a correct act in the partially built trace to connect the next act to. The connected act gets one of the subclasses of correct_act class, showing the reason why the act should be there (e.g., AltBranchBegin, SequenceEnd).
Second, the additional properties parent_of and corresponding_end are computed to easier navigating the correct trace (see g. 1). Similar properties are calculated for the student's trace. Indices for acts in both traces are calculated too.
Third, the negative rules determine student's mistakes and fault reasons. Fault reason detection is performed by rules that infer subclasses of Erroneous class showing the fault reason like CorrespondingEndMismatch, ExtraAct, DuplicateOfAct, MissingAct, DisplacedAct, BranchOfFalseCondition, NoBranchWhenConditionIsTrue, etc.
After the reasoning, the ontology is supplemented with the correct trace and facts about the types of student mistakes. This information can be extracted and shown to the students in a human-readable way using message templates for each fault-reason Fig. 1. Trace structure for two acclass, for example, "Act A can't be executed tions (1, 2) nested to a sequence after the end of Act B because sequence B (seq) contains act A and each act of a sequence execution include executing each its element once" or "Branch A can't be executed at this place because the condition B is false" or "Act A must be executed at this place because a do-while loop body must be executed at least once." 3
The current revision of the ontology1 includes: 74 SWRL rules (28 positive, 28 negative, 18 helper rules), 66 classes (24 representing algorithm elements, 7 1 https://github.com/den1s0v/c owl trace acts, 18 - mistakes, 27 - explanations for correct acts), and 30 properties.
The ontology supports sequences, alternatives, and loops of di erent types. It guarantees that at least one student's act is marked incorrect if there are any mistakes, even if all mistakes are omissions of correct acts: that makes providing detailed information about the mistakes' positions possible. Simultaneous reasoning over multiple traces injected into the same ontology is supported and can be used to improve the overall performance when processing multiple answers to the same question.
The developed SWRL rules require using SWRL built-ins like swrlb:add(), swrlb:notEqual(). Suitable reasoners include Pellet 2.3 and Pellet 3. Other popular reasoners like HermiT do not support these built-ins.
The ontology passed 33 tests consisting of short traces with annotated mistakes. A single run of the ontology with one trace takes about 1 second in Stanford Protege Editor invoking Pellet 2.3 plugin and about 5 seconds while running Pellet 2.3 as a standalone process. The same ontology using Stardog with Pellet 3 cannot complete the inference in minutes.
A few issues of SWRL implementation in Pellet 2 and 3 were found. { The problems with DifferentFrom: when no facts related to individuals distinction was provided a rule that uses DifferentFrom never res; in Pellet 2 it sometimes causes "Inconsistent Ontology" error or silently truncates some of the inference results. This problem e ectively stops the ontology from working. So it's better to avoid using DifferentFrom or SameAs unless you explicitly specify the information about the di erences of individuals.
{ In Stardog, using SameAs in the SWRL rule causes a parsing exception. { In Stardog, the uni cation of "scalar" variables works only for binding; when matching with an already bound variable, it allows any values. With rule (1), Stardog will connect all possible pairs of Product instances, regardless of whether their prices are equal, instead of selecting only instances that match at a price. This behavior was only observed when has_price is a DatatypeProperty.
P roduct(?a); P roduct(?b); has price(?a; ?p); has price(?b; ?p) ! ! has same price(?a; ?b) (1) { Including transitive properties has a signi cant impact on the reasoning time if they are inferred. Two of the determined mistakes - ExtraAct and MissingAct - require looking up any number of acts ahead that is impossible without using transitive properties. As a workaround, we created several duplicates of the rules, each with a xed length of the lookup (up to 6 acts).
The developed ontology di ers from the ontology-based program analysis
system [
Our work di ers from other ontologies used for question generation and solving in that it can be used in developing a question-generating system aimed at more complex questions targeting higher cognitive levels that makes reasoning the correct answer for the generated questions non-trivial as a question-solver and grading block. It also allows for generating explanatory feedback.
The proposed approach is limited to closed-ended questions because it
requires that every possible mistake in the answer can be a result of violating
a speci c domain law. The developed ontology solves and nds mistakes for
questions requiring ordering of a given set of program-trace strings. Open-ended
questions are limited to the lower-lever feedback for now [
During our research, we developed an ontology able to build correct traces for the given algorithm consisting of sequences, alternatives, and loops and nd mistakes in the given traces with enough information to generate explanatory feedback. This shows that developing an ontology-based system for generating and solving questions and providing explanatory feedback to students about their mistakes is possible. However, some problems of Pellet reasoner prevent e cient implementation of the rules and limit the number of mistakes that can be detected.
Future work will concern adding support for procedure calls, including recursive calls, and developing the tutor system using the created ontology and logical rules.