Information Systems Group

Despoina Magka

Research Student

Biography

I am a final year doctoral student and member of the Information Systems Group led by Prof. Ian Horrocks. During my DPhil, I worked on knowledge representation and reasoning formalisms modelling non-tree structures, such as complex biochemical objects. Specifically, I built a theoretical and practical logic-based framework for the classification of graph-shaped objects based on their structural properties. In the context of this framework, I researched extensions of datalog rules with existentials in the head and nonmonotonic negation in the body and their application to automatically building taxonomies of manually curated knowledge bases.

Prior to that, I completed an MSc Computer Science degree in the Department of Computer Science, University of Oxford; for my MSc project and under the supervision of Dr. Yevgeny Kazakov and Prof. Ian Horrocks I outlined polynomiality conditions for the lightweight description logic EL when extended with numerical datatypes.

For my first degree, I studied electrical and computer engineering in National Technical University of Athens. In my undergrad project and under the supervision of Dr. Giorgos Stamou, I explored methods for connecting databases and ontological knowledge under the presence of uncertainty. In particular, I developed a java tool to convert database tuples into fuzzy OWL assertions according to user-defined membership functions.

Conference Publications

Despoina Magka, Markus Krötzsch, Ian Horrocks
Computing Stable Models for Nonmonotonic Existential Rules.
In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, (IJCAI 2013), AAAI press, 2013.
[Pdf   |  BibTeX-Entry  |  Experiments ]

In this work, we consider function-free existential rules extended with nonmonotonic negation under a stable model semantics. We present new acyclic- ity and stratification conditions that identify a large class of rule sets having finite, unique stable mod- els, and we show how the addition of constraints on the input facts can further extend this class. Check- ing these conditions is computationally feasible, and we provide tight complexity bounds. Finally, we demonstrate how these new methods allowed us to solve relevant reasoning problems over a real- world knowledge base from biochemistry using an off-the-shelf answer set programming engine.

Markus Krötzsch, Despoina Magka, Ian Horrocks
Concrete Results on Abstract Rules.
In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2013) , Springer, 2013.
[Pdf   |  BibTeX-Entry ]

There are many different notions of "rule" in the literature. A key feature and main intuition of any such notion is that rules can be "applied" to derive conclusions from certain premises. More formally, a rule is viewed as a function that, when invoked on a set of known facts, can produce new facts. In this paper, we show that this extreme simplification is still sufficient to obtain a number of useful results in concrete cases. We define abstract rules as a certain kind of functions, provide them with a semantics in terms of (abstract) stable models, and explain how concrete normal logic programming rules can be viewed as abstract rules in a variety of ways. We further analyse dependencies between abstract rules to recognise classes of logic programs for which stable models are guaranteed to be unique.

Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik and Zhe Wang.
Acyclicity Conditions and their Application to Query Answering in Description Logics.
In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), AAAI Press, 2012.
[Pdf   |  BibTeX-Entry ]

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a key problem in knowledge representation and databases. This problem can be solved using the chase (aka materialisation) algorithm; however, CQ answering is undecidable for general existential rules, so the chase is not guaranteed to terminate. Several acyclicity conditions provide sufficient conditions for chase termination. In this paper, we present two novel such conditions—modelfaithful acyclicity (MFA) and model-summarising acyclicity (MSA)—that generalise many of the acyclicity conditions known so far in the literature. Materialisation provides the basis for several widely-used OWL 2 DL reasoners. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2 DL; furthermore, some systems go beyond OWL 2 RL, but they provide no termination guarantees. In this paper we investigate whether various acyclicity conditions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 DL ontologies are MSA, and that the facts obtained via materialisation are not too large. Thus, our results suggest that principled extensions to materialisationbased OWL 2 DL reasoners may be practically feasible.

Despoina Magka, Boris Motik and Ian Horrocks
Modelling Structured Domains Using Description Graphs and Logic Programming.
In Proceedings of the 9th Extended Semantic Web Conference (ESWC 2012), Vol. 7295, Pages 330-344, Springer, 2012.
[Pdf   |  BibTeX-Entry  |  Experiments ]

Although OWL 2 is widely used to describe complex objects such as chemical molecules, it cannot represent ‘structural’ features of chemical entities (e.g., having a ring). A combination of rules and description graphs (DGs) has been proposed as a possible solution, but it still exhibits several drawbacks. In this paper we present a radically different approach that we call Description Graph Logic Programs. Syntactically, our approach combines DGs, rules, and OWL 2 RL axioms, but its semantics is defined via a translation into logic programs under stable model semantics. The result is an expressive OWL 2 RL-compatible formalism that is well suited for modelling objects with complex structure.

Despoina Magka, Yevgeny Kazakov and Ian Horrocks
Tractable Extensions of the Description Logic EL with Numerical Datatypes.
In Proceedings of the Int. Joint Conf. on Automated Reasoning (IJCAR 2010), Vol. 6173, Pages 61--75, LNAI, 2010.
[Pdf (277K)  |  BibTeX-Entry ]

We consider extensions of the lightweight description logic (DL) EL with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decid- able in polynomial time provided that the datatypes enjoy the so-called convexity property. Unfortunately many combinations of the numerical relations violate convexity, which makes the usage of these datatypes rather limited in practice. In this paper, we make a more fine-grained complexity analysis of these DLs by considering restrictions not only on the kinds of relations that can be used in ontologies but also on their occurrences, such as allowing certain relations to appear only on the left- hand side of the axioms. To this end, we introduce a notion of safety for a numerical datatype with restrictions (NDR) which guarantees tractabil- ity, extend the EL reasoning algorithm to these cases, and provide a complete classification of safe NDRs for natural numbers, integers, ra- tionals and reals.

Journal Publications

Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik and Zhe Wang
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies.
In Journal of Artificial Intelligence Research (JAIR), Vol.47:781-808.
[Pdf   |  BibTeX-Entry ]

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions. Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.

Janna Hastings, Despoina Magka, Colin Batchelor, Lian Duan, Robert Stevens, Marcus Ennis and Christoph Steinbeck
Structure-based classification and ontology in chemistry.
In Journal of Cheminformatics, 4:8, 2012.
[Pdf   |  BibTeX-Entry  |   Paper at Chemistry Central ]

Background
Recent years have seen an explosion in the availability of data in the chemistry domain. With this information explosion, however, retrieving relevant results from the available information, and organising those results, become even harder problems. Computational processing is essential to filter and organise the available resources so as to better facilitate the work of scientists. Ontologies encode expert domain knowledge in a hierarchically organised machine-processable format. One such ontology for the chemical domain is ChEBI. ChEBI provides a classification of chemicals based on their structural features and a role or activity-based classification. An example of a structure-based class is ‘pentacyclic compound’ (compounds containing five-ring structures), while an example of a role-based class is ‘analgesic’, since many different chemicals can act as analgesics without sharing structural features. Structure-based classification in chemistry exploits elegant regularities and symmetries in the underlying chemical domain. As yet, there has been neither a systematic analysis of the types of structural classification in use in chemistry nor a comparison to the capabilities of available technologies.
Results
We analyze the different categories of structural classes in chemistry, presenting a list of patterns for features found in class definitions. We compare these patterns of class definition to tools which allow for automation of hierarchy construction within cheminformatics and within logic-based ontology technology, going into detail in the latter case with respect to the expressive capabilities of the Web Ontology Language and recent extensions for modelling structured objects. Finally we discuss the relationships and interactions between cheminformatics approaches and logic-based approaches.
Conclusion
Systems that perform intelligent reasoning tasks on chemistry data require a diverse set of underlying computational utilities including algorithmic, statistical and logic-based tools. For the task of automatic structure-based classification of chemical entities, essential to managing the vast swathes of chemical data being brought online, systems which are capable of hybrid reasoning combining several different approaches are crucial. We provide a thorough review of the available tools and methodologies, and identify areas of open research.

Despoina Magka, Yevgeny Kazakov and Ian Horrocks
Tractable Extensions of the Description Logic EL with Numerical Datatypes.
In Journal of Automated Reasoning, 47(4):427-450, 2011.
[Pdf   |  BibTeX-Entry  |  Paper at Springer ]

We consider extensions of the lightweight description logic (DL) EL with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decidable in polynomial time provided that the datatypes enjoy the so-called convexity property. Unfortunately many combinations of the numerical relations violate convexity, which makes the usage of these datatypes rather limited in practice. In this paper, we make a more fine-grained complexity analysis of these DLs by considering restrictions not only on the kinds of relations that can be used in ontologies but also on their occurrences, such as allowing certain relations to appear only on the left-hand side of the axioms. To this end, we introduce a notion of safety for a numerical datatype with restrictions (NDR) which guarantees tractability, extend the EL reasoning algorithm to these cases, and provide a complete classification of safe NDRs for natural numbers, integers, rationals and reals.

Workshop Publications

Despoina Magka, Markus Krötzsch, Ian Horrocks
Nonmonotonic Existential Rules for Non-Tree-Shaped Ontological Modelling.
In Proceedings of the The 26th International Workshop on Description Logics (DL 2013) , CEUR, 2013.
[Pdf   |  BibTeX-Entry  |  Experiments ]

In this work, we consider function-free existential rules extended with nonmonotonic negation under a stable model semantics. We present new acyclic- ity and stratification conditions that identify a large class of rule sets having finite, unique stable mod- els, and we show how the addition of constraints on the input facts can further extend this class. Check- ing these conditions is computationally feasible, and we provide tight complexity bounds. Finally, we demonstrate how these new methods allowed us to solve relevant reasoning problems over a real- world knowledge base from biochemistry using an off-the-shelf answer set programming engine.

Despoina Magka
Ontology-Based Classification of Molecules: a Logic Programming Approach.
In Proceedings of the 5th International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS 2012), Best paper prize.
[Pdf   |  BibTeX-Entry  |  Experiments ]

We describe a prototype that performs structure-based classification of molecular structures. The software we present implements a sound and complete reasoning procedure of a formalism that extends logic programming and builds upon the DLV deductive databases system. We capture a wide range of chemical classes that are not expressible with OWL-based formalisms such as cyclic molecules, saturated molecules and alkanes. In terms of performance, a noticeable improvement is observed in comparison with previous approaches. Our evaluation has discovered subsumptions that are missing from the the manually curated ChEBI ontology as well as discrepancies with respect to existing subclass relations. We illustrate thus the potential of an ontology language which is suitable for the Life Sciences domain and exhibits an encouraging balance between expressive power and practical feasibility.

Despoina Magka, Boris Motik and Ian Horrocks
Modelling Structured Domains Using Description Graphs and Logic Programming. .
In Proceedings of the The 25th International Workshop on Description Logics (DL 2012) , Vol. 846, CEUR, 2012. [Pdf   |  BibTeX-Entry  |  Experiments ]

OWL 2 is widely used to describe complex objects such as chemical molecules; however, OWL 2 axioms cannot represent `structural' features of chemical entities such as having a ring. A combination of OWL 2, rules and \emph{description graphs} (DGs) has been suggested as a possible solution, but an attempt to apply this formalism in a chemical Semantic Web application has revealed several drawbacks. Based on this experience, we present a radically different approach to modelling complex objects via a novel formalism that we call Description Graph Logic Programs. At the syntactic level, our approach combines DGs, rules, and OWL 2 RL axioms, but we give semantics to our formalism via a translation into logic programs interpreted under stable model semantics. The result is an expressive formalism that is well suited for modelling objects with complex structure, that captures the OWL 2 RL profile, and that thus fits naturally into the Semantic Web landscape. Additionally, we test the practical feasibility of our approach by means of a prototypical implementation which provides encouraging results.

Despoina Magka, Boris Motik and Ian Horrocks
Classifying Chemicals Using Description Graphs and Logic Programming.
In Proceedings of the 9th OWL: Experiences and Directions Workshop (OWLED 2012), Vol.849, 2012.
[Pdf   |  BibTeX-Entry  |  Experiments ]

OWL 2 is widely used to describe complex objects such as chemical molecules; however, OWL 2 axioms cannot represent `structural' features of chemical entities such as having a ring. A combination of OWL 2, rules and \emph{description graphs} (DGs) has been suggested as a possible solution, but an attempt to apply this formalism in a chemical Semantic Web application has revealed several drawbacks. Based on this experience, we present a radically different approach to modelling complex objects via a novel formalism that we call Description Graph Logic Programs. At the syntactic level, our approach combines DGs, rules, and OWL 2 RL axioms, but we give semantics to our formalism via a translation into logic programs interpreted under stable model semantics. The result is an expressive formalism that is well suited for modelling objects with complex structure, that captures the OWL 2 RL profile, and that thus fits naturally into the Semantic Web landscape. Additionally, we test the practical feasibility of our approach by means of a prototypical implementation which provides encouraging results.

Despoina Magka, Boris Motik and Ian Horrocks
Chemical Knowledge Representation with Description Graphs and Logic Programming.
In Proceedings of the 4th International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS 2011), Pages 74-75, ACM, 2011.
Highlight poster .
[Pdf   |  BibTeX-Entry  |  Experiments ]

OWL 2 is widely used to describe complex objects such as chemical molecules; however, OWL 2 axioms cannot represent `structural' features of chemical entities such as having a ring. A combination of OWL 2, rules and \emph{description graphs} (DGs) has been suggested as a possible solution, but an attempt to apply this formalism in a chemical Semantic Web application has revealed several drawbacks. Based on this experience, we present a radically different approach to modelling complex objects via a novel formalism that we call Description Graph Logic Programs. At the syntactic level, our approach combines DGs, rules, and OWL 2 RL axioms, but we give semantics to our formalism via a translation into logic programs interpreted under stable model semantics. The result is an expressive formalism that is well suited for modelling objects with complex structure, that captures the OWL 2 RL profile, and that thus fits naturally into the Semantic Web landscape. Additionally, we test the practical feasibility of our approach by means of a prototypical implementation which provides encouraging results.

Despoina Magka, Yevgeny Kazakov and Ian Horrocks
Tractable Extensions of the Description Logic EL with Numerical Datatypes.
In Proceedings of the 2010 Description Logic Workshop (DL 2010), Vol. 573, Pages 79-90, CEUR, 2010.
[Pdf (163K)  |  BibTeX-Entry ]

We consider extensions of the lightweight description logic (DL) EL with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decid- able in polynomial time provided that the datatypes enjoy the so-called convexity property. Unfortunately many combinations of the numerical relations violate convexity, which makes the usage of these datatypes rather limited in practice. In this paper, we make a more fine-grained complexity analysis of these DLs by considering restrictions not only on the kinds of relations that can be used in ontologies but also on their occurrences, such as allowing certain relations to appear only on the left- hand side of the axioms. To this end, we introduce a notion of safety for a numerical datatype with restrictions (NDR) which guarantees tractabil- ity, extend the EL reasoning algorithm to these cases, and provide a complete classification of safe NDRs for natural numbers, integers, ra- tionals and reals.

Technical Reports

Despoina Magka, Markus Krötzsch, Ian Horrocks
Stable Models for Nonmonotonic Existential Rules.
Technical report, University of Oxford, 2013.
[Pdf   |  BibTeX-Entry  |  Experiments ]

In this work, we consider function-free existential rules extended with nonmonotonic negation under a stable model semantics. We present new acyclic- ity and stratification conditions that identify a large class of rule sets having finite, unique stable mod- els, and we show how the addition of constraints on the input facts can further extend this class. Check- ing these conditions is computationally feasible, and we provide tight complexity bounds. Finally, we demonstrate how these new methods allowed us to solve relevant reasoning problems over a real- world knowledge base from biochemistry using an off-the-shelf answer set programming engine.

Despoina Magka, Boris Motik and Ian Horrocks
Modelling Structured Domains Using Description Graphs and Logic Programming.
Technical report, University of Oxford, 2011.
[Pdf  |  BibTeX-Entry  |  Experiments ]

OWL 2 is widely used to describe complex objects such as chemical molecules, but cannot represent `structural' features of chemical entities such as having a ring. Adding rules, and description graphs (DGs) has been suggested as a possible solution, but still exhibits several drawbacks. We present a radically different approach that we call Description Graph Logic Programs. Syntactically, our approach combines DGs, rules, and OWL 2 RL axioms, but the semantics is via a translation into logic programs interpreted under stable model semantics. The result is an expressive OWL 2 RL-compatible formalism that is well suited for modelling objects with complex structure.

Despoina Magka, Yevgeny Kazakov and Ian Horrocks.
Tractable Extensions of the Description Logic EL with Numerical Datatypes.
Technical report, University of Oxford, 2010.
[Pdf (268K)  |  BibTeX-Entry ]

We consider extensions of the lightweight description logic (DL) EL with numerical datatypes such as naturals, integers, rationals and reals equipped with relations such as equality and inequalities. It is well-known that the main reasoning problems for such DLs are decid- able in polynomial time provided that the datatypes enjoy the so-called convexity property. Unfortunately many combinations of the numerical relations violate convexity, which makes the usage of these datatypes rather limited in practice. In this paper, we make a more fine-grained complexity analysis of these DLs by considering restrictions not only on the kinds of relations that can be used in ontologies but also on their occurrences, such as allowing certain relations to appear only on the left- hand side of the axioms. To this end, we introduce a notion of safety for a numerical datatype with restrictions (NDR) which guarantees tractabil- ity, extend the EL reasoning algorithm to these cases, and provide a complete classification of safe NDRs for natural numbers, integers, ra- tionals and reals.

Dissertations

Despoina Magka
Consequence-based Datatype Reasoning in EL: Identifying the Tractable Fragments.
MSc Project, Oxford University Computing Laboratory, September 2009.
[Pdf (568K)  |  BibTeX-Entry ]

The current dissertation suggests a consequence-based reasoning approach for the EL? description logic with numerical datatypes. It provides a set of saturation rules which are used in the formulation of a polynomial classification algorithm. Furthermore, it introduces the notion of safety which is a property that numerical datatypes exhibit and guarantees the preservation of polynomiality. The proposed algorithm is proved to be complete only for the safe datatypes. Additionally, the corresponding reasoning problem for non-safe datatypes is proved to be EXPTIME-hard. Apart from that, a classification of specific instances of datatypes is attempted. Finally, the present work, based on the results it produces, suggest a modification of the EL Profile in OWL 2 in order to add datatype features, which are currently available only in OWL 2.

Despoina Magka
Database and ontology integration under uncertainty.
Diploma Thesis (in Greek), National Technical University of Athens, July 2008.
[Pdf (6.01M)  |  BibTeX-Entry ]

The main objective of this diploma thesis is the study of methods, which connect databases and ontological knowledge under the presence of uncertainty. The aim is to give to the knowledge engineer the possibility to convert database content into a set of fuzzy assertions, as a part of an ontological knowledge. This way, the process of representing databases’ content via fuzzy assertions is being automatized. A system was developed for the purposes of the present diploma thesis. This system, initially, permits the user to correspond the attributes and tables of a database to the classes and properties of a TBox. Τhis mapping is used by the system during the creation of the assertions (ABox). The user defines a set of membership functions in order to determine with accuracy how fuzziness will be inserted into the assertions. After the above interaction between the user and the system, the system expresses the information of the database content using assertions, which are based on the terminologies found in the ontology. The produced fuzzy assertions are presented to the user via system’s interface. Moreover, the user can access a file where the produced assertions are stored.