On computer program being a whole

Who cares whether some computer program is a whole, how, and why? Turns out, more people than you may think—and so should you, since it can be costly depending on the answer. Consider the following two scenarios: 1) you download a ‘pirated’ version of MS Office or Adobe Photoshop (the most popular ones still) and 2) you take the source code of a popular open source program, such as Notepad++, add a little code for some additional function, and put it up for sale only as an executable app called ‘Notepad++ extreme (NEXT)’ so as to try to earn money quickly. Are these actions legal?

In both cases, you’d break the law, but how many infringements took place, of the one that you potentially could be fined for or face jail time? For the piracy case, is that once for the MS Office suite, or for each progam in the suite, or for each file created upon installing MS office, or for each source code file that went into making the suite during software development? For the open source case, was that violating its GNU GLP open source licence once for the zipped&downloaded or cloned source code or for each file in the source code, of which there are hundreds? It is possible to construct similar questions for trade secret violations and patent infringements for programs, as well as other software artefacts, like illegal downloads of TV series episodes (going strong during COVID-19 lockdowns indeed). Just in case you think this sort of issue is merely hypothetical: recently, Arista paid Cisco $400 million for copyright damages and just before that, Zenimax got $500 million from Oculus (yes, the VR software) for trade secret violations, and Google vs Oracle is ongoing with “billions of dollars at stake”.

Let’s consider some principles first. To be able to answer the number of infringements, we first need to know whether a computer program is a whole or not and why, and if so, what’s ‘in’ (i.e., a part of it) and what’s ‘out’ (i.e., definitely not part of it). Spoiler alert: a computer program is a functional whole.

To get to that conclusion, I had to combine insights from theories of parthood (mereology), granularity, modularity, unity, and function and add a little more into the mix. To provide less and more condensed versions of the argumentation, there is a longer technical report [1], of which I hope it is readable by a wider audience, and a condensed version for a specialist audience [2] that was published in the Proceedings of the 11th Conference on Formal Ontologies in Information Systems (FOIS’20) two weeks ago. Very briefly and informally, the state of affairs can be illustrated with the following picture:

(Source: adapted from [2])

This schematic representation shows, first, two levels of granularity: level 1 and level 2. At level 1, there’s some whole, like the a1 and a2 in the figure that could be referring to, say, a computer program, a module repository, an electorate, or a human body. At a more fine-grained level 2, there are different entities, which are in some way linked to the respective whole. This ‘link’ to the whole is indicated with the vertical dashed lines, and one can say that they are part of the whole. For the blue dots on the right residing at level 2, i.e., the parts of a1, there’s also a unifying relation among the parts, indicated with the solid lines with arrows, which makes a1 an integral whole. Moreover, for that sort of whole, it holds that if some object x (residing at level 2) is part of a1 then if there’s a y that is also part of a1, it participates in that unifying relation with x and vice versa (i.e., if y is in that unifying relation with x, then it must also be part of a1). For the computer program’s source code, that unifying relation can be the source tree graph.

There is some nitty gritty detail also involving the notion of function—a source code file contributes to doing something—and optional vs mandatory vs essential part that you can read about in the report or in the paper [1,2], covering the formalisation, more argumentation, and examples.

How would it pan out for the infringements? The Notepad++ exploitation scenario would simply be a case of one infringement in total for all the files needed to create the executable, not one for each source code file. This conclusion from the theory turns out remarkably in line with the GNU GPL’s explanation of their licence, albeit then providing a theoretical foundation for their intuition that there’s a difference between a mere aggregate where different things are bundled, loose coupling (e.g., sockets and pipes) and a single program (e.g., using function calls, being included in the same executable). The order of things perhaps should have been from there into the theory, but practically, I did the analysis and stumbled into a situation where I had to look up the GPL and its explanatory FAQ. On the bright side, in the other direction now then: just  in case someone wants to take on copyleft principles of open source software, here are some theoretical foundations to support that there’s probably much less money to be gained than you might think.

For the MS Office suite case mentioned at the start, I’d need a look under the hood to determine how it ties together and one may have to argue about the sameness of, or difference between, a suite and a program. The easier case for a self-standing app, like the 3^rd-place most pirated Windows app Internet Download Manager, is that it is one whole and so one infringement then.

It’s a pity that FOIS 2020 has been postponed to 2021, but at least I got to talk about some of this as expert witness for a litigation case and I managed to weave an exercise about the source tree with open source licences into the social issues and professional practice module I thought to some 750 students this past winter.

References

[1] Keet, C.M. Why a computer program is a functional whole. Technical report 2008.07273, arXiv. 21 July 2020. 25 pages.

[2] Keet, C.M. The computer program as a functional whole. Proc. of FOIS 2020. Brodaric, B. and Neuhaus, F. (Eds.). IOS Press. FAIA vol. 330, 216-230.

Advertisement

Orchestrating 28 logical theories of mereo(topo)logy

Parts and wholes, again. This time it’s about the logic-aspects of theories of parthood (cf. aligning different hierarchies of (part-whole) relations and make them compatible with foundational ontologies). I intended to write this post before the Ninth Conference on Knowledge Capture (K-CAP 2017), where the paper describing the new material would be presented by my co-author, Oliver Kutz. Now, afterwards, I can add that “Orchestrating a Network of Mereo(topo) logical Theories” [1] even won the Best Paper Award. The novelties, in broad strokes, are that we figured out and structured some hitherto messy and confusing state of affairs, showed that one can do more than generally assumed especially with a new logics orchestration framework, and we proposed first steps toward conflict resolution to sort out expressivity and logic limitations trade-offs. Constructing a tweet-size “tl;dr” version of the contents is not easy, and as I have as much space here on my blog as I like, it ended up to be three paragraphs here: scene-setting, solution, and a few examples to illustrate some of it.

 

Problems

As ontologists know, parthood is used widely in ontologies across most subject domains, such as biomedicine, geographic information systems, architecture, and so on. Ontology (the philosophers) offer a parthood relation that has a bunch of computationally unpleasant properties that are structured in a plethora of mereologicial and meretopological theories such that it has become hard to see the forest for the trees. This is then complicated in practice because there are multiple logics of varying expressivity (support more or less language features), with the result that only certain fragments of the mereo(topo)logical theories can be represented. However, it’s mostly not clear what can be used when, during the ontology authoring stage one may want to have all those features so as to check correctness, and it’s not easy to predict what will happen when one aligns ontologies with different fragments of mereo(topo)logy.

 

Solution

We solved these problems by specifying a structured network of theories formulated in multiple logics that are glued together by the various linking constructs of the Distributed Ontology, Model, and Specification Language (DOL). The ‘structured network of theories’-part concerns all the maximal expressible fragments of the KGEMT mereotopological theory and five of its most well-recognised sub-theories (like GEM and MT) in the seven Description Logics-based OWL species, first-order logic, and higher order logic. The ‘glued together’-part refers to relating the resultant 28 theories within DOL (in Ontohub), which is a non-trivial (understatement, unfortunately) metalanguage that has the constructors for the glue, such as enabling one to declare to merge two theories/modules represented in different logics, extending a theory (ontology) with axioms that go beyond that language without messing up the original (expressivity-restricted) ontology, and more. Further, because the annoying thing of merging two ontologies/modules can be that the merged ontology may be in a different language than the two original ones, which is very hard to predict, we have a cute proof-of-concept tool so that it assists with steps toward resolution of language feature conflicts by pinpointing profile violations.

 

Examples

The paper describes nine mechanisms with DOL and the mereotopological theories. Here I’ll start with a simple one: we have Minimal Topology (MT) partially represented in OWL 2 EL/QL in “theory8” where the connection relation (C) is just reflexive (among other axioms; see table in the paper for details). Now what if we add connection’s symmetry, which results in “theory4”? First, we do this by not harming theory8, in DOL syntax (see also the ESSLI’16 tutorial):

logic OWL2.QL
ontology theory4 =
theory8
then
ObjectProperty: C Characteristics: Symmetric %(t7)

What is the logic of theory4? Still in OWL, and if so, which species? The Owl classifier shows the result:

 

Another case is that OWL does not let one define an object property; at best, one can add domain and range axioms and the occasional ‘characteristic’ (like aforementioned symmetry), for allowing arbitrary full definitions pushes it out of the decidable fragment. One can add them, though, in a system that can handle first order logic, such as the Heterogeneous toolset (Hets); for instance, where in OWL one can add only “overlap” as a primitive relation (vocabulary element without definition), we can take such a theory and declare that definition:

logic CASL.FOL
ontology theory20 =
theory6_plus_antisym_and_WS
then %wdef
. forall x,y:Thing . O(x,y) <=> exists z:Thing (P(z,x) /\ P(z,y)) %(t21)
. forall x,y:Thing . EQ(x,y) <=> P(x,y) /\ P(y,x) %(t22)

As last example, let me illustrate the notion of the conflict resolution. Consider theory19—ground mereology, partially—that is within OWL 2 EL expressivity and theory18—also ground mereology, partially—that is within OWL 2 DL expressivity. So, they can’t be the same; the difference is that theory18 has parthood reflexive and transitive and proper parthood asymmetric and irreflexive, whereas theory19 has both parthood and proper parthood transitive. What happens if one aligns the ontologies that contain these theories, say, O1 (with theory18) and O2 (with theory19)? The Owl classifier provides easy pinpointing and tells you the profile: OWL 2 full (or: first order logic, or: beyond OWL 2 DL—top row) and why (bottom section):

Now, what can one do? The conflict resolution cannot be fully automated, because it depends on what the modeller wants or needs, but there’s enough data generated already and there are known trade-offs so that it is possible to describe the consequences:

• Choose the O1 axioms (with irreflexivity and asymmetry on proper part of), which will make the ontology interoperable with other ontologies in OWL 2 DL, FOL or HOL.
• Choose O2’s axioms (with transitivity on part of and proper part of), which will facilitate linking to ontologies in OWL 2 RL, 2 EL, 2 DL, FOL, and HOL.
• Choose to keep both sets will result in an OWL 2 Full ontology that is undecidable, and it is then compatible only with FOL and HOL ontologies.

As serious final note: there’s still fun to be had on the logic side of things with countermodels and sub-networks and such, and with refining the conflict resolution to assist ontology engineers better. (or: TBC)

As less serious final note: the working title of early drafts of the paper was “DOLifying mereo(topo)logy”, but at some point we chickened out and let go of that frivolity.

 

References

[1] Keet, C.M., Kutz, O. Orchestrating a Network of Mereo(topo)logical Theories. Ninth International Conference on Knowledge Capture (K-CAP’17), Austin, Texas, USA, December 4-6, 2017. ACM Proceedings.

On generating isiZulu sentences with part-whole relations

It all sounded so easy… We have a pretty good and stable idea about part-whole relations and their properties (see, e.g., [1]), we know how to ‘verbalise’/generate a natural language sentence from basic description logic axioms with object properties that use simple verbs [2], like ‘each professor teaches at least one course’, and SNOMED CT is full of logically ‘simple’ axioms (it’s in OWL 2 EL, after all) and has lots of part-whole relations. So why not combine that? We did, but it took some more time than initially anticipated. The outcomes are described in the paper “On the verbalization patterns of part-whole relations in isiZulu”, which was recently accepted at the 9th International Natural Language Generation Conference (INLG’16) that will be held 6-8 September in Edinburgh, Scotland.

What it ended up to be, is that notions of ‘part’ in isiZulu are at times less precise and other times more precise compared to the taxonomy of part-whole relations. This interfered with devising the sentence generation patterns, it pushed the number of ‘elements’ to deal with in the language up to 13 constituents, and there was no way to avoid proper phonological conditioning. We already could handle quantitative, relative, and subject concords, the copulative, and conjunction, but what had to be added were, in particular, the possessive concord, locative affixes, a preposition (just the nga in this context), epenthetic, and the passive tense (with modified final vowel). As practically every element has to be ‘completed’ based on the context (notably the noun class), one can’t really speak of a template-based approach anymore, but a bunch of patterns and partial grammar engine instead. For instance, plain parthood, structural parthood, involvement, membership all have:

• (‘each whole has some part’) dwa
• (‘each part is part of some whole’) ingxenye dwa

There are a couple of noteworthy things here. First, the whole-part relation does not have one single string, like a ‘has part’ in English, but it is composed of the subject concord (SC) for the noun class (nc) of the noun that play the role of the whole ( W ) together with the phonologically conditioned conjunction na- ‘and’ (the “SC-CONJ”, above) and glued onto the noun of the entity that play the role of the part (P). Thus, the surface realisation of what is conceptually ‘has part’ is dependent on both the noun class of the whole (as the SC is) and on the first letter of the name of the part (e.g., na-+i-=ne-). The ‘is part of’ reading direction is made up of ingxenye ‘part’, which is a noun that is preceded with the copula (COP) y– and together then amounts to ‘is part’. The ‘of’ of the ‘is part of’ is handled by the possessive concord (PC) of ingxenye, and with ingxenye being in noun class 9, the PC is ya-. This ya- is then made into one word together with the noun for the object that plays the role of the whole, taking into account vowel coalescence (e.g., ya-+u-=yo-). Let’s illustrate this with heart (inhliziyo, nc9) standing in a part-whole relation to human (umuntu, NC1), with the ‘has part’ and ‘is part of’ underlined:

• bonke abantu banenhliziyo eyodwa ‘All humans have as part at least one heart’
  • The algorithm, in short, to get this sentence from, say : 1) it looks up the noun class of umuntu (nc1); 2) it pluralises umuntu into abantu (nc2); 3) it looks up the quantitative concord for universal quantification (QCall) for nc2 (bonke); 4) it looks up the SC for nc2 (ba); 5) then it uses the phonological conditioning rules to add na- to the part inhliziyo, resulting in nenhliziyo and strings it together with the subject concord to banenhliziyo; 6) and finally it looks up the noun class of inhliziyo, which is nc9, and from that it looks up the relative concord (RC) for nc9 (e-) and the quantitative concord for existential quantification (QC) for nc9 (being yo-), and strings it together with –dwa to eyodwa.
• zonke izinhliziyo ziyingxenye yomuntu oyedwa ‘All hearts are part of at least one human’
  • The algorithm, in short, to get this sentence from : 1) it looks up the noun class of inhliziyo (nc9); 2) it pluralises inhliziyo to izinhliziyo (nc10); 3) it looks up the QCall for nc10 (zonke); 4) it looks up the SC for nc10 (zi-), takes y- (the COP) and adds them to ingxenye to form ziyingxenye; 5) then it uses the phonological conditioning rules to add ya- to the whole umuntu, resulting in yomuntu; 6) and finally it looks up the noun class of umuntu, which is nc1, and from that the RC for nc10 (o-) and the QC for nc10 (being ye-), and strings it together with –dwa to oyedwa.

For subquantities, we end up with three variants: one for stuff-parts (as in ‘urine has part water’, still with ingxenye for ‘part’), one for portions of solid objects (as in ‘tissue sample is a subquantity of tissue’ or a slice of the cake) that uses umunxa instead of ingxenye, and one ‘spatial’ notion of portion, like that an operating theatre is a portion of a hospital, or the area of the kitchen where the kitchen utensils are is a portion of the kitchen, which uses isiqephu instead of ingxenye. Umunxa is in nc3, so the PC is wa- so that with, e.g., isbhedlela ‘hospital’ it becomes wesibhedlela ‘of the hospital’, and the COP is ng- instead of y-, because umunxa starts with an u. And yet again part-whole relations use locatives (like the containment type of part-whole relation). The paper has all those sentence generation patterns, examples for each, and explanations for them.

The meronymic part-whole relations participation and constitution have added aspects for the verb, such as generating the passive for ‘constituted of’: –akha is ‘to build’ for objects that are made/constituted of some matter in some structural sense, else –enza is used. They are both ‘irregular’ in the sense that it is uncommon that a verb stem starts with a vowel, so this means additional vowel processing (called hiatus resolution in this case) to put the SC together with the verb stem. Then, for instance za+akhiwe=zakhiwe but u+akhiwe=yakhiwe (see rules in paper).

Finally, this was not just a theoretical exercise, but it also has been implemented. I’ll readily admit that the Python code isn’t beautiful and can do with some refactoring, but it does the job. We gave it 42 test cases, of which 38 were answered correctly; the remaining errors were due to an ‘incomplete’ (and unresolvable case for any?) pluraliser and that we don’t know how to systematically encode when to pick akha and when enza, for that requires some more semantics of the nouns. Here is a screenshot with some examples:

The ‘wp’ ones are that a whole has some part, and the ‘pw’ ones that the part is part of the whole and, in terms of the type of axiom that each function verbalises, they are of the so-called ‘all some’ pattern.

The source code, additional files, and the (slightly annotated) test sentences are available from the GENI project’s website. If you want to test it with other nouns, please check whether the noun is already in nncPairs.txt; if not, you can add it, and then invoke the function again. (This remains this ‘clumsily’ until we make a softcopy of all isiZulu nouns with their noun classes. Without the noun class explicitly given, the automatic detection of the noun class is not, and cannot be, more than about 50%, but with noun class information, we can get it up to 90-100% correct in the pluralisation step of the sentence generation [4].)

 

References

[1] Keet, C.M., Artale, A. Representing and Reasoning over a Taxonomy of Part-Whole Relations. Applied Ontology, 2008, 3(1-2):91-110.

[2] Keet, C.M., Khumalo, L. Basics for a grammar engine to verbalize logical theories in isiZulu. 8th International Web Rule Symposium (RuleML’14), A. Bikakis et al. (Eds.). Springer LNCS vol. 8620, 216-225. August 18-20, 2014, Prague, Czech Republic.

[3] Keet, C.M., Khumalo, L. On the verbalization patterns of part-whole relations in isiZulu. 9th International Natural Language Generation conference (INLG’16), September 5-8, 2016, Edinburgh, UK. (in print)

[4] Byamugisha, J., Keet, C.M., Khumalo, L. Pluralising Nouns in isiZulu and Related Languages. 17th International Conference on Intelligent Text Processing and Computational Linguistics (CICLing’16), Springer LNCS. April 3-9, 2016, Konya, Turkey. (in print)

New OWL files for the (extended) taxonomy of part-whole relations

Once upon a time (surely >6 years ago) I made an OWL file of the taxonomy of part-whole relations [1], which contains several parthood relations and a few meronyic-only ones that in natural language are considered ‘part’ but are not so according to mereology (like participation, membership). Some of these relations were defined with a specific domain and range that was a DOLCE category (it could just as well have been, say, GFO). Looking at it recently, I noticed it was actually a bit scruffy (but I’ll leave it here nonetheless), and more has happened in this area over the years. So, it was time for an update on contents and on design.

For the record on how it’s done and to serve, perhaps, as a comparison exercise on modeling, here’s what I did. First of all, I started over, so as to properly type the relations to DOLCE categories, with the DOLCE IRIs rather than duplicated as DOLCE-category-with-my-IRI. As DOLCE is way too big and slows down reasoning, I made a module of DOLCE, called DOLCEmini, mainly by removing the irrelevant object properties, though re-adding the SOB, APO and NAPO that’s in D18 but not in DOLCE-lite from DLP3791. This reduced the file from DOLCE-lite’s 534 axioms, 37 classes, 70 OPs, in SHI to DOLCEmini’s 388 axioms, 40 classes, 43 OPs, also in SHI, and I changed the ontology IRI to where DOLCEmini will be put online.

Then I created a new ontology, PW.owl, imported DOLCEmini, added the taxonomy of part-whole relations from [1] right under owl:topObjectProperty, with domain and range axioms using the DOLCE categories as in the definitions, under part-whole. This was then extended with the respective inverses under whole-part, all the relevant proper part versions of them (with inverses), transitivity added for all (as the reasoner isn’t doing it [2]) annotations added, and then aligned to some DOLCE properties with equivalences. This makes it to 524 axioms and 79 object properties.

I deprecated subquantityOf (annotated with ‘deprecated’ and subsumed by a new property ‘deprecated’). Several new stuff relations and their inverses were added (such as portions), and annotated them. This made it to the PW ontology of 574 axioms (356 logical axioms) and 92 object properties (effectively, for part-whole relations: 92 – 40 from dolce – 3 for deprecated = 49).

As we made an extension with mereotopology [3] (and also that file wasn’t great, though did the job nevertheless [4]), but one that not everybody may want to put up with, yet a new file was created, PWMT. PWMT imports PW (and thus also DOLCEmini) and was extended with the main mereotopological relations from [3], and relevant annotations were added. I skipped property disjointness axioms, because they don’t go well with transitivity, which I assumed to be more important. This makes PWMT into one of 605 (380 logical) axioms and 103 object properties, with, effectively, for parts: 103 – 40 from dolce – 3 for deprecated – 1 connection = 59 object properties.

That’s a lot of part-whole relations, but fear not. The ‘Foundational Ontology and Reasoner enhanced axiomatiZAtion’ (FORZA) and its tool that incorporates with the Guided ENtity reuse and class Expression geneRATOR (GENERATOR) method [4] describes a usable approach how that can work out well and has a tool for the earlier version of the owl file. FORZA uses an optional decision diagram for the DOLCE categories as well as the automated reasoner so that it can select and propose to you those relations that, if used in an axiom, is guaranteed not to lead to an inconsistency that would be due to the object property hierarchy or its domain and range axioms. (I’ll write more about it in the next post.)

Ah well, even if the OWL files are not used, it was still a useful exercise in design, and at least I’ll have a sample case for next year’s ontology engineering course on ‘before’ and ‘after’ about questionable implementation and (relatively) good implementation without the need to resorting to criticizing other owl files… (hey, even the good and widely used ontologies have a bunch of pitfalls, whose amount is not statistically significantly different from ontologies made by novices [5]).

 

References

[1] Keet, C.M., Artale, A. Representing and Reasoning over a Taxonomy of Part-Whole Relations. Applied Ontology, 2008, 3(1-2):91-110.

[2] Keet, C.M. Detecting and Revising Flaws in OWL Object Property Expressions. 18th International Conference on Knowledge Engineering and Knowledge Management (EKAW’12), Oct 8-12, Galway, Ireland. Springer, LNAI 7603, 252-266.

[3] Keet, C.M., Fernandez-Reyes, F.C., Morales-Gonzalez, A. Representing mereotopological relations in OWL ontologies with OntoPartS. 9th Extended Semantic Web Conference (ESWC’12), Simperl et al. (eds.), 27-31 May 2012, Heraklion, Crete, Greece. Springer, LNCS 7295, 240-254.

[4] Keet, C.M., Khan, M.T., Ghidini, C. Ontology Authoring with FORZA. 22nd ACM International Conference on Information and Knowledge Management (CIKM’13). ACM proceedings, pp569-578. Oct. 27 – Nov. 1, 2013, San Francisco, USA.

[5] Keet, C.M., Suarez-Figueroa, M.C., Poveda-Villalon, M. Pitfalls in Ontologies and TIPS to Prevent Them. In: Knowledge Discovery, Knowledge Engineering and Knowledge Management: IC3K 2013 Selected papers. Fred, A., Dietz, J.L.G., Liu, K., Filipe, J. (Eds.). Springer, CCIS 454, pp. 115-131. 2015.

Part-whole relations, mereotopology and the OntoPartS tool

Part-whole relations are considered essential in knowledge representation and reasoning and, more practically, in ontology development and conceptual data modelling, especially in the subject domains of biology, medicine, geographic information systems, and manufacturing. In contrast to Ontology that sticks to one type of part-of, the modellers and subject domain experts have come up with a plethora of part-whole relations, some of which are considered real parthood relations and others only meronymic (or: due to imprecise natural language use). For instance, the Foundational Model of Anatomy has 8 basic locative part-whole relations [1], GALEN has come up with 26 part-whole relations [2], and in cognitive science and conceptual data modelling, it hovers around about 6 types [3,4]. They have been structured in a taxonomy of part-whole relations that makes a distinction between mereology and meronomy, transitivity and in- or non-transitivity, and the domain and range of the relationship [5], and some initial usage guidelines were proposed in [6].

But that’s not enough for the complex subject domains and demands on the representation and reasoning over the ontologies. This holds in particular when one has to represent that some things are contained in or located in something else. For instance, the way how Paris and France relate is somehow different from how the euro coin in your wallet relate to each other—the latter being an example of  (spatial) containment, but not structural part of—whereas in other case, the spatial containment of regions of space and the structural parthood of the objects occupying those regions do coincide, e.g., your heart in your body. Or consider representing that Alto Adige/Südtirol is a border province of Italy (bordering Austria), where we have to handle both the notion of administrative entities and connecting geographical regions. That is, handling regions and ‘things’ that occupy those regions (mereotopology).

Being more precise about how the things relate provides nice inferences. Take, e.g., NTPLI as ‘non-tangential proper located in’—a part is located in the whole but not at the boundary of it—and , with the following instances in our knowledge base , , and , then it deduces correctly that , whereas with a mere ‘part-of’, we would not have been able to obtain this result.

Besides these examples, there are actual system requirements for, among others, annotating and querying multimedia documents and cartographic maps, such as annotating a photo of a beach where the area of the photo that depicts the sand touches the area that depicts the seawater so that, together with the knowledge that Varadero is a tangential proper part of Cuba, the semantically enhanced system can infer possible locations where the photo has been taken, or, vv., it can propose that the photo may depict a beach scene.

But how to cater for such things?

Let me summarise the three main basic problems that have to be resolved first:

1. There is lack of oversight on plethora of part-whole relations, that include real parthood (mereology) parts with their locations (mereotopology), and other part-whole relations (from meronymy);
2. The challenge to figure out which one to use when;
3. The underspecified representation and reasoning consequences when one has to put up with less expressive languages for which technological infrastructure exists.

We propose to solve that in the following way, which is described in detail in [7] that recently got accepted at the 9th Extended Semantic Web Conference (ESWC’12).

The short answer for the reader who is not interested in all the theory, design, and evaluation, but just wants to model quickly: the OntoPartS tool guides you to choose the most appropriate relation and saves the selection into your OWL file.

Now for a slightly longer answer. First, we extend the taxonomy of part-whole relations of [5] with the novel addition of a taxonomy of formally defined mereotopological relations, which is driven by the KGEMT mereotoplogical theory of Varzi [8], resulting in a taxonomy of 23 part-whole relations—mereological, mereotopological, and meronymic ones—therewith ensuring a solid ontological and logic-based foundation.

Second, some things have to be simplified from the KGEMT theory to make it implementable in OWL, and we describe the design rationale and trade-offs so that OntoPartS can load OWL/OWL2-formalised ontologies, and, if desired, modify the OWL file with the chosen relation. Which OWL species is best suited obviously depends on your individual requirements, but from a representation & reasoning and mereotopology viewpoint, OWL 2 DL and OWL 2 RL seem to fit better than the other ones. (Note: there are papers on DL and representing spatial relations and on DL and parthood, and alternative representation choices are discussed in the paper, yet, as far as we are aware of, none deals with mereotopological relations in OWL or, more generally, in DL.)

Third, there is the ‘how to select’ from the 23 relations. To enable a quick selection of the appropriate relation, we avail of a simplified OWL-ized DOLCE ontology—well, just the taxonomy of categories—for the domain and range restrictions imposed on the part-whole relations and with that, we can let the user take shortcuts compared to a lengthy decision procedure. In this way, we reduced the selection procedure to 0-4 options based on just 2-3 inputs. All of this has been structured neatly in implementation-independent activity diagrams, and subsequently has been implemented; see also the demos, the tool, and the OWL version of the taxonomy of the 23 relations.

Last, we have tested OntoPartS with modellers in controlled experiments and it was shown to improve efficiency and accuracy in modeling of part-whole relations.

As mentioned, further details can be found in [7], Representing mereotopological relations in OWL ontologies with OntoPartS, which I co-authored with Francis Fernández-Reyes, with the Instituto Superior Politécnico “José Antonio Echeverría” (CUJAE), and Annette Morales-González, with the Advanced Technologies Application Center (CENATAV), both located in Cuba (the example on semantic annotation of multimedia with spatial relations comes straight from the image processing research being done at CENATAV). A tidbit of non-scientific information: the first version of the OntoPartS tool was developed as part of the mini-project that Francis, Annette (and Alexis, who is into fish fulltime now) had chosen to carry out for the ontology engineering course I taught at the University of Havana in 2010 (mentioned earlier here and here). For the paper, we added some more theory, minor refinements to the tool, and a user evaluation with several CUJAE and UKZN students and a few FUB colleagues (thanks again for their cooperation and interest). We’ve started work on additional features, so if you have any particular request, drop me a line.

References

1. Mejino, J.L.V., Agoncillo, A.V., Rickard, K.L., Rosse, C.: Representing complexity in part-whole relationships within the foundational model of anatomy. In: Proc. of the AMIA Fall Symposium. pp. 450–454 (2003)
2. http://www.opengalen.org/tutorials/crm/tutorial9.html up to http://www.opengalen.org/tutorials/crm/tutorial16.html/.
3. Winston, M., Chaffin, R., Herrmann, D.: A taxonomy of part-whole relations. Cognitive Science 11(4), 417–444 (1987)
4. Odell, J.: Advanced Object-Oriented Analysis & Design using UML. Cambridge: Cambridge University Press (1998)
5. Keet, C.M., Artale, A.: Representing and reasoning over a taxonomy of part-whole relations. Applied Ontology 3(1-2), 91–110 (2008)
6. Keet, C.M.: Part-whole relations in object-role models. In: Proc. of ORM’06, OTM Workshops 2006. LNCS, vol. 4278, pp. 1116–1127. Springer (2006)
7. Keet, C.M., Fernández Reyes, F.C., Morales-González, A.: Representing mereotopological relations in OWL ontologies with OntoPartS. In Simperl, et al., eds.: Proc. of ESWC’12. LNCS, Springer (2012) 27-31 May 2012, Heraklion, Greece.
8. Varzi, A.: Handbook of Spatial Logics, chap. Spatial reasoning and ontology: parts, wholes, and locations, pp. 945–1038. Berlin Heidelberg: Springer Verlag (2007)

72010 SemWebTech lecture 6: Parts and temporal aspects

The previous three lectures covered the core topics in ontology engineering. There are many ontology engineering topics that zoom in on one specific aspect of the whole endeavour, such as modularization, the semantic desktop, ontology integration, combining data mining and clustering with ontologies, and controlled natural language interfaces to OWL. In the next two lectures on Dec 1 and Dec 14, we will look at three such advanced topics in modelling and language and tool development, being the (ever recurring) issues with part-whole relations, temporalizations and its workarounds, and languages and tools for dealing with vagueness and uncertainty.

Part-whole relations

On the one hand, there is a SemWeb best practices document about part-whole relations and further confusion by OWL developers [1, 2] that was mentioned in a previous lecture.  On the other hand, part-whole relations are deemed essential by the most active adopters of ontologies—i.e., bio- and medical scientist—while its full potential is yet to be discovered by, among others, manufacturing. A few obvious examples are how to represent plant or animal anatomy, geographic information data, and components of devices. And then the need to reason over it. When we can deduce which part of the device is broken, then only that part has to be replaced instead of the whole it is part of (saving a company money). One may want to deduce that when I have an injury in my ankle, I have an injury in my limb, but not deduce that if you have an amputation of your toe, you also have an amputation of your foot that the toe is (well, was) part of. If a toddler swallowed a Lego brick, it is spatially contained in his stomach, but one does not deduce it is structurally part of his stomach (normally it will leave the body unchanged through the usual channel). This toddler-with-lego-brick gives a clue why, from an ontological perspective, equation 23 in [2] is incorrect.

To shed light on part-whole relations and sort out such modelling problems, we will look first at mereology (the Ontology take on part-whole relations), and to a lesser extent meronymy (from linguistics), and subsequently structure the different terms that are perceived to have something to do with part-whole relations into a taxonomy of part-whole relations [3]. This, in turn, is to be put to use, be it with manual or software-supported guidelines to choose the most appropriate part-whole relation for the problem, and subsequently to make sure that is indeed represented correctly in an ontology. The latter can be done by availing of the so-called RBox Reasoning Service [3]. All this will not solve each modelling problem of part-whole relations, but at least provide you with a sound basis.

Temporal knowledge representation and reasoning

Compared to part-whole relations, there are fewer loud and vocal requests for including a temporal dimension in OWL, even though it is needed. For instance, you can check the annotations in the OWL files of BFO and DOLCE (or, more conveniently, search for “time” in the pdf) where they mention temporality that cannot be represented in OWL, or SNOMED CT’s concepts like “Biopsy, planned” and “Concussion with loss of consciousness for less than one hour” where the loss of consciousness still can be before or after the concussion, or a business rule alike ‘RentalCar must be returned before Deposit is reimbursed’ or the symptom HairLoss during the treatment Chemotherapy, and Butterfly is a transformation of Caterpillar.

Unfortunately, there is no single (computational) solution to address all these examples at once. Thus far, it is a bit of a patchwork, with, among many aspects, the Allen’s interval algebra (qualitative temporal relations, such as before, during, etc.), Linear Temporal Logics (LTL), and Computational Tree Logics (CTL, with branching time), and a W3C Working draft of a time ontology.

If one assumes that recent advances in temporal Description Logics may have the highest chance of making it into a temporal OWL (tOWL)—although there are no proof-of-concept temporal DL modelling tools or reasoners yet—then the following is ‘on offer’. A very expressive (undecidable) DL language is DLRus (with the until and since operators), which already has been used for temporal conceptual data modelling [4] and for representing essential and immutable parts and wholes [5]. A much simpler language is TDL-Lite [6], which is a member of the DL-Lite family of DL languages of which one is the basis for OWL 2 QL; but these first results are theoretical, hence no “lite tOWL” yet. It is already known that EL++ (the basis for OWL 2 EL) does not keep the nice computational properties when extended with LTL, and results with EL++ with CTL are not out yet. If you are really interested in the topic, you may want to have a look at a recent survey [7] or take a broader scope with any of the four chapters in [8] (that cover temporal KR&R, situation calculus, event calculus, and temporal action logics), and several people with the KRDB Research Centre work on temporal knowledge representation & reasoning.  Depending on the remaining time during the lecture, more or less about time and temporal ontologies will pass the revue.

References

[1] I. Horrocks, O. Kutz, and U. Sattler. The Even More Irresistible SROIQ. In Proc. of the 10th International Conference of Knowledge Representation and Reasoning (KR-2006), Lake District UK, 2006.

[2] B. Cuenca Grau, I. Horrocks, B. Motik, B. Parsia, P. Patel-Schneider, and U. Sattler. OWL 2: The next step for OWL. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 6(4):309-322, 2008

[3] Keet, C.M. and Artale, A. Representing and Reasoning over a Taxonomy of Part-Whole Relations. Applied Ontology, IOS Press, 2008, 3(1-2): 91-110.

[4] Alessandro Artale, Christine Parent, and Stefano Spaccapietra. Evolving objects in temporal information systems. Annals of Mathematics and Artificial Intelligence (AMAI), 50:5-38, 2007, Springer.

[5] Artale, A., Guarino, N., and Keet, C.M. Formalising temporal constraints on part-whole relations. 11th International Conference on Principles of Knowledge Representation and Reasoning (KR’08). Gerhard Brewka, Jerome Lang (Eds.) AAAI Press, pp 673-683. Sydney, Australia, September 16-19, 2008

[6] Alessandro Artale, Roman Kontchakov, Carsten Lutz, Frank Wolter and Michael Zakharyaschev. Temporalising Tractable Description Logics. Proc. of the 14^th International Symposium on Temporal Representation and Reasoning (TIME-07), Alicante, June 2007.

[7] Carsten Lutz, Frank Wolter, and Michael Zakharyaschev.  Temporal Description Logics: A Survey. In  Proceedings of the Fifteenth International Symposium on Temporal Representation and Reasoning. IEEE Computer Society Press, 2008.

[8] Frank van Harmelen, Vladimir Lifschitz and Bruce Porter (Eds.). Handbook of Knowledge Representation. Elsevier, 2008, 1034p. (also available from the uni library)

Note: reference 3 is mandatory reading, 4 optional reading, 2 was mandatory and 1 recommended for an earlier lecture, and 5-8 are optional.

Lecture notes: lecture 6 – Parts and temporal issues

Course webpage