Polynomial encoding of ORM conceptual models in CF DI 8nc

Abstract

The use of conceptual models has long been con ned to the data analysis stage of software development. In recent years, this has been extended to use them at run-time as well, for, among others, querying large amounts of data. This brings afore the need to have tractable logicbased reconstructions of the conceptual models, i.e., in at most PTIME. We provide such a logic-based reconstruction for most of ORM using the Description Logic language CF DI8nc , which has several features important for conceptual models, notably n-ary relationships, complex identication constraints, and role subsumption. The encoding captures over 96% of the constructs used in practice in the set of 33 ORM diagrams analysed. The results are easily transferable to EER and UML Class diagrams, with an even greater coverage.

-

While for many years conceptual models were developed and then shelved upon implementation or used `o ine' for documentation purposes, recent years has seen an increase in using such precious resources computationally. One strand of investigation focuses on expressiveness and a logic foundation to compute satis ability and detect inconsistencies over the TBox only, among others [ 2, 5, 8, 16, 24 ], and several implementations exists using various technologies that are more or less scalable; e.g., using OCL [ 16 ], Alloy [ 8, 23 ], or a DL reasoner [ 19 ]. Another looks at usage during runtime for a range of purposes, such as using a conceptual model for scalable test data generation [35] and for designing [ 6 ] and executing [ 13 ] queries. Approximations of conceptual models are used also deeper into the machinery of querying databases, in particular during various stages of query compilation, e.g., when reasoning about duplicates [39]. The former purpose requires a logic foundation using a (very) expressive logic, whereas the latter requires computationally better behaved logics to keep the whole process feasible. What such a tractable logic language looks like that captures most, or all, important conceptual data modelling language features, has received little attention, however. To the best of our knowledge, there are only four e orts to capture a fragment of which concept or full satis ability checking is (or is claimed to be) in polynomial time (or less): one for ER [ 2 ], two for UML [ 1, 25 ], and one for ORM [35], with the rst one logic-driven and the last one implementationdriven, and they all di er substantially in coverage of features. The main general question, thus, is: what is a useful fragment for tractable runtime usage of a conceptual data model? Then, how to formalise it.

To answer this question, we choose to focus on ORM rst, for it is strictly more expressive than ER and UML class diagrams, and then facilitating transferability of the results. Given that there is a lot of insight in computational complexity of Description Logic (DL) languages and which ones are in P, we zoom in 8 on those for a logic-based reconstruction. It appears that the DL CF DInc [40] is a good t and can capture 96:5% of the ORM models in a dataset of 33 ORM models that are part of the dataset of 101 conceptual models (dataset available from [ 28 ]). This is chie y thanks to `trading' costly but lesser used covering constraints for the more often used arbitrary identi ers and n-ary relationships.

In the remainder of the paper, we rst provide background de nitions in Section 2. The main results are presented in Section 3, and are discussed and compared with related research in Section 4. We summarize our results and brie y outline future work in Section 5. 2

Preliminaries 8 The two preliminaries are the DL CF DInc and the ORM language, so as to keep the paper self-contained. 2.1 8

The Description Logic CF DInc All members of the CF D family of DLs are fragments of FOL with underlying signatures based on disjoint sets of unary predicate symbols called primitive concepts, constant symbols called individuals and unary function symbols called features.

De nition 1 (CF DInc Knowledge Bases) Let F, PC and IN be disjoint sets 8 of (names of) functional features, primitive concepts and individuals, respectively. A path function Pf is a word in F , and we denote the empty word by id 8 and concatenation by \:". Metadata and data in a CF DInc knowledge base K are respectively de ned by a TBox T and an ABox A. A TBox T consists of a nite set of inclusion dependencies of the form

A v B; A v :B; A v 8f:B; 8f:A v B; A v 9f 1;

or A v B : Pf1; : : : ; Pfk ! Pf where A; B 2 PC, f 2 F, and Pfi 2 F . A concept \B : Pf1; : : : ; Pfk ! Pf" that participates in the last dependency is called a path functional dependency (PFD). An ABox A consists of a nite set of facts in the form of concept assertions A(a), and function assertions f (a) = b where A 2 PC, f 2 F, and a; b 2 IN. Any PFD occurring in T must also satisfy a regularity condition by adhering to one of the following two forms:

C : Pf : Pf1; Pf2; : : : ; Pfk ! Pf or

C : Pf : Pf1; Pf2; : : : ; Pfk ! Pf :g: (1) A PFD is a key if it adheres to the rst of these forms.

The semantics is de ned in the standard way with respect to an interpretation I = (4; ( )I ), where 4 is a domain of \objects" and ( )I an interpretation function that xes the interpretation of primitive concepts A to be subsets of 4, features f to be total functions on 4, and individuals a to be elements of 4. The interpretation function is extended to path expressions by interpreting id , the empty word, as the identity function x:x, concatenation as function composition, and to derived concept descriptions as follows:

(:A)I =4 n AI (8f:A)I =fx j f I (x) 2 AI g (9f 1)I =fx j 9y 2 4 : f I (y) = xg (C : Pf1; : : : ; Pfk ! Pf)I =fx j 8y 2 CI : (Vik=1 PfiI (x) = PfiI (y)) ) PfI (x) = PfI (y)g An interpretation I satis es an inclusion dependency C v D if CI DI , a concept assertion A(a) if aI 2 AI , and a function assertion f (a) = b if f I (aI ) = bI . I satis es a knowledge base K if it satis es each inclusion dependency and asser8 tion in K. In addition, every CF DInc knowledge base must satisfy the following two conditions. 1. (inverse feature and value restriction interaction) If fA v 9f 1; 8f:A0 v

Bg T then (a) A v A0 2 T , (b) A0 v A 2 T or (c) A v :A0 2 T . 2. (inverse feature and PFD interaction) Any non-key PFD occurring in T that involves features used in the 9f 1 concept in T must also satisfy a stronger regularity condition by adhering to the following form:

C : Pf :f; Pf2; : : : ; Pfk ! Pf :g: (2) 8 Proposition 1 ([40]). Consistency of CF DInc knowledge bases is complete for PTIME.

Other reasoning tasks, such as logical implication and concept consistency reduce (linearly) to knowledge base consistency. Relaxing either of the aforementioned conditions leads to EXPTIME and PSPACE completeness, respectively [40]. Note also, that condition (2) imposed on PFDs applies only to non-key PFDs. Overall, however, the restrictions do not seem to impact the modeling utility 8 of CF DInc in relation to keys and functional constraints. Indeed, arbitrary functional dependencies in relational schema are easily captured. Finally and 8 for convenience CF DInc supports additional syntax, e.g., subsumptions of the form 9f 1 v A. This additional syntax is mere syntactic sugar and can be 8 equivalently expressed in CF DInc as de ned above [40]. Object-Role Modelling as a general term is also known as Fact-Based Modeling and comprises several notational variants with varying language features, ranging from its predecessor NIAM and its recent notation in the proprietary CogNIAM tool of PNA, to the FCO-IM avour [ 4 ], to ORM as in [ 21 ] popularised with VisioModeler 3.1 and ORM2 [ 22 ] popularised with the NORMA tool [ 15 ] as plugin for MS Visio, among others. We use Halpin's notation [ 22 ] in the remainder of the paper for its compactness. As we are interested in the static, structural components, we ignore deontic constraints5|they did not occur in any of the evaluated ORM models anyway [ 28 ]|and derived constraints (ORM's version of methods). ORM2 has four di erent kinds of named entities: { entity type, which is like an EER entity type and UML class and may be objecti ed, and is denoted with a blue rectangle with round corners; { value type, which is an entity type that has a binary fact type (relationship) to a data type, denoted with a blue dashed rectangle with round corners; { role that each entity/value type plays in a fact type, denoted with a small rectangle and connected to the object type or value type; { n-ary fact type (n 1) that relates entity types to each other or entity types to value types and they have to be elementary (uniqueness constraint spanning n or n 1 roles), denoted with a rectangle composed of the roles. Typically, roles and fact types are named automatically, but this can be added, as indicated with the user-named role [DE] in Fig. 1; note that the text next to the fact types are `readings' for model verbalisations, not fact type names. 5 Refer to [36] for a treatment of deontic constraints in the context of DLs and SBVR

ORM has many constraint types (some of which are used rarely [ 28 ]); a nonexhaustive example is shown in Fig. 1. The ones used in the gure are mandatory (small blob), uniqueness (line over rectangle), reference schemes (simple identiers, e.g., .empNr), and external identi ers (circle with double horizontal line), subtype (arrow) and subset (over roles, fact types, paths), disjointness (encircled cross); others include coverage, constraints on values, and 11 relationship constraints (a.o., transitive, irre exive).

As transformations exist from one ORM model to UML and to ER [ 22 ], ORM is `more conceptual' than the other models for one does not have to commit to an implementation paradigm upfront. Moreover, the notation is also used for business rules speci cations [ 32 ]. 3

ORM2cfd fragment into CF DI nc 8 8 While we primarily focus on ORM to CF DInc mapping here, we also aim for an easy extension to EER and UML Class diagrams, the ability to use it for inter-model assertions across models represented in di erent languages [ 17 ], and for uni cation of the conceptual modelling language families for a widely used subset of features. To this end, we rst de ne the syntax and semantics of a `generic' conceptual data modelling language, which we name CMcom, as it is, essentially, a proper fragment of CMcom|used as common conceptual data modelling language for EER, UML, and ORM [ 30 ]|without covering and disjunctive mandatory constraints, and with limited cardinalities and a more precise de nition of relationship subsumption and disjointness. CMcom contains those 8 features mappable into CF DInc (as described in Section 3.3) and captures a subset of features of ORM, named ORM2cfd . Thus, within the scope of this paper, one can equate CMcom and ORM2cfd . 3.1

Syntax

The syntax is introduced rst, and subsequently illustrated with an example. We assume a transformation where an ORM value type is encoded in CMcom as an attribute, and note that recursive relationships are allowed such that a class can participate more than once in a relationship.

De nition 2 (Conceptual Data Model CMcom syntax) A CMcom conceptual data model is a tuple = (L; rel; att; cardR; cardA; isaC ; isaR; isaU ; disjC ; disjR; id; extid; fd; obj; rex) such that: 1. L is a nite alphabet partitioned into the sets: C (object type symbols), A (attribute symbols), R (relationship symbols), U (role symbols), and D (domain symbols); the tuple (C; A; R; U ; D) is the signature of . 2. att is a function that maps a class symbol in C to an A-labeled tuple over D, so that att(C) = fA1 : D1; : : : ; Ah : Dhg where h is a non-negative integer. 3. rel is a function that maps a relationship symbol in R to an U -labeled tuple over C, rel(R) = fUi : Cigih=1; h 1, Ui 6= Uj if i 6= j, h is called the arity of R, and if (Ui; Ci) 2 rel(R) then player(R; Ui) = Ci and role(R; Ci) = Ui.

The signature of the relation is R = fUigin=1.

To link this syntax to ORM's icons, value types are transformed into attributes, any unary relationship is translated into a class and a binary relationship with a Boolean datatype, and a suitable naming scheme for the roles and fact types is in place.

Example 1 Let us consider a mapping between this CMcom syntax and some of the mappable ORM icons of the ORM2cfd fragment, using the diagram in Fig. 1. The fact type verbalised with works for can be represented with the relationship rel(works) = fDE : Department; ED : Employeeg Identi cation (single attribute, resp. external) of the Employee and Room with id(Employee) = fempNrg and extid(Room) = fflocBuildingName; roomNrgg. Subsumption of ORM entity types and fact types is straightforward as:

Academic isaC Employee and supports isaR works and mandatory participation of Department in works as cardR(works; DE) = (1; 1). } 3.2

Semantics

The model-theoretic semantics of CMcom in the light of ORM2cfd is as follows. 6 We assume that the compatibility is enforced explicitly by additional isaC pairs of the classes linked to the matching roles in the relationships, e.g., for U : C 2 rel(R1) and U : D 2 rel(R2) we have C isaC D. { for each U; Ui 2 U ; 1 i h, R 2 R: if fd(R) = (fUigih=1; U ), then exists C; Ci 2 C such that C : U 2 rel(R), Ci : Ui 2 rel(R) and #fo 2 CI such that fU : og [ fUi : oi; g 2 RIg 1 for any oi 2 CiI; 1 i h. { for each R 2 R, C 2 C: if obj(R) = C, then exist Ri 2 R with rel(Ri) = fUi1 : C; Ui2 : Cig, for all 1 i n, and the following statements are also satis ed: extid(C) = f(Ri; Ui2) j 0 < i ng, cardR(Ri; Ui1) = (1; 1), and cardR(Ri; Ui2) = (0; 1). { for each Ui 2 U ; 1 i h: if fUigih=1 2 rex, then exists Ri 2 R with arity m, such that Ui : Ci 2 rel(Ri). Then for each o 2 CiI the following condition is true #fk such that fUk : og 2 RkI; 1 k hg 1.

is said to be globally consistent if it admits at least one legal state. We formalize how CF DI8nc can capture ORM2cfd conceptual models. Let = (L; rel; att; cardR; cardA; isaC ; isaR; isaU ; disjC ; disjR; id; extid; fd; obj; rex) be a CMcom conceptual data model corresponding to ORM2cfd . We map to a CF DI8nc TBox T in the vocabulary PC, F using the following rules: { Include in the vocabulary one concept name for each ORM2cfd object type and datatype, i.e., for each C 2 C, D 2 D we have C 2 PC, D 2 PC. { To map attributes, there are two cases to consider: if the attribute is functional then it is mapped as a function symbol and two concepts that reify each of the roles; otherwise it is rei ed as a new concept, with the corresponding cardinality constraints. For each C 2 C such that att(C) = fAi : Digin=1, and for each i: if cardA(C; Ai) = (1; 1), then we introduce two new concepts U1Ai ; UAi 2 2 PC, a new function symbol ai 2 F, and fC v 8ai:Di; C v U1Ai ; U1Ai v C; U2Ai v 9ai 1; 9ai 1 v U2Ai g 2 T . otherwise we introduce new concept symbols Ai; UiA;1; UiA;2 2 PC, and two new function symbols ai;1; ai;2 2 F, with fAi v 8ai;1:UiA;1; Ai v 8ai;2:UiA;2; UiA;1 v C; UiA;2 v Di; UiA;1 v 9ai;1 1; UiA;2 v 9ai;2 1; 8ai;1:UiA;1 v Ai; 8ai;2:UiA;2 v Ai; Ai v Ai : ai;1; ai;2 ! idg T . If cmin(C; Ai) = 1, then also C v UiA;1 2 T ; if if cmax(C; Ai) = 1, then Ai v Ai : ai;1 ! id 2 T . { The mapping of relationships (ORM2cfd fact types) is similar as the mapping of attributes. If the relationship is binary and one of its roles has a (1; 1) constraint, then it is mapped as an attribute; in the other cases the relationship and its roles are rei ed as a new concepts, with new attributes from the rei ed relationship to the rei ed roles. The rei ed roles are then subconcepts of the concepts originally participating in the relationship. For n each R 2 R such that rel(R) = fUi : Cigi=1 then if n = 2 and cardR(R; U1) = (1; 1), then we introduce a new function symbol u1 2 F, and fC1 v 8u1:C2; C1 v C1 : u1 ! idg 2 T . Similarly if cardR(R; U2) = (1; 1) then we introduce function symbol u2 2 F and fC2 v 8u2:C1; C2 v C2 : u2 ! idg 2 T . otherwise we add new concept symbols R; UiR 2 PC; 1 i n , new function symbols uiR 2 F; 1 i n, and then fR v 8uiR:UiR; UiR v Ci; UiR v 9uiR 1; 8uiR:UiR v Rgin=1 [ fR : u1R; : : : ; unR ! idg T . Additionally for each i; 1 i n if cmin(R; Ui) = 1 then also Ci v UiR 2 T ; and if cmax(R; Ui) = 1, then R v R : uiR ! id 2 T . { for each C1; C2 2 C such that C1 isaC C2, then C1 v C2 2 T . { for each R1; R2 2 R such that R1 isaR R2, then R1 v R2 2 T . In order to de ne relationship inheritance in ORM2cfd , the types of the participating concepts must be compatible, therewith adhering to the syntax restriction of ORM (as aside: without this condition, the reconstruction in a PTIME language is not possible). { for each U1; U2 2 U such that U1 isaU U2 then U1 v U2 2 T . { for each Ci; C 2 C such that fCigin=1 disjC C, then fCi v Cgin=1 [ fCi v { f:oCrjegain6=chj;i;Rj=i 12 RT s,uscthattihnagtthfeRicgoinn=c1ep2tsdairsejRp,aitrhweinsefdRisijovint:.Rj; Ri v Rj :

Rj ! idgin6=j;i;j=1 T . Again, ORM has the condition that relationship exclusion must be de ned over compatible types for the participating concepts (which also happens to be a necessary condition for the e ciency of the translation). { for each C 2 C, Ai 2 A such that id(C) = fAigin=1, then C v C : a1; : : : ; an ! id 2 T . In this case since the attributes are keys then they must be in (1; 1) constraint with C, so they are mapped as features in T by the rst point of the respective rule, described above. { for each C 2 C, Ri 2 R, Ui 2 U , Aj 2 A such that f(Ri; Ui)gih=1 [ fAjgjk=1 2 extid(C), then C v C : u1R; : : : ; uhR; a1; : : : ; ak ! id 2 T . Here the only possibility is that Ui and Aj belonging to the external identi er have a (1; 1) constraint, so they are mapped with features. { for each U; Ui 2 U , R 2 R: if fd(R) = (fUigih=1; U ), then CR v CR : u1R; : : : ; uhR ! uR. This case is similar as the previous one: we ensure the roles and attributes belonging to the external identi er are mapped as features in T because the are (1; 1) to C. { for each R 2 R, C 2 C: if obj(R) = C, then we have the mappings for extid(C), cardR(Ri; Ui1) = (1; 1), and cardR(Ri; Ui2) = (0; 1). { for each Ui 2 U : if fUigih=1 2 rex, then exists Ri 2 R; Ci 2 C with arity m, such that (Ui : Ci) 2 rel(Ri); 1 i h. Then fUiR v :UjRgih6=j;i;j=1 T . Note that rex requires optional participation in the role, and therewith uses the second case of the relationship mapping above.

Case analysis of the translation combined with Proposition 1 yields the following: Theorem 1. Let be an ORM2cfd conceptual data model. A class C is consistent in if and only if the knowledge base (T ; fC(aC )g) is consistent. is globally consistent if and only if T is consistent with A = fC(aC ) j C 2 Cg. Example 2 Consider again the running example with Fig. 1 and the illustration 8 of the syntax (Example 1), the corresponding CF DInc knowledge base contains, among others: the translation where empNr is an attribute of Employee with 8 cardA(empNr; Employee) = (1; 1), the following CF DInc axioms: f Works v 8deworks:DEworks; DEworks v Department; DEworks v 9deworks 1; 8deworks:DEworks v Works; Works v Works : deworks; edworks ! id; Department v DEworks; Works v 8edworks:EDworks; EDworks v Employee; EDworks v 9edworks 1; 8edworks:EDworks v Works and likewise for the remainder of the diagram in Figure 1. g; } 4

Discussion There are many papers with logic-based reconstructions of ORM, EER, and UML; we discuss a subset relevant to the scope of this paper.

Comparison with other ORM2 Encodings. Fairly expressive logic-based reconstructions of ORM fragments exist, including ORM 2zero in the EXPTIMEcomplete ALCQI [ 20 ], ORM2 [ 30 ] in the EXPTIME-complete DLRifd [ 11 ], an ORM2 fragment (e.g., [41]) in SROIQ that is N2EXPTIME-Complete [ 27 ], and ORM in the undecidable FOL [ 21 ]. An Alloy encoding and a numeric model as encoding for ORM are proposed in [ 23 ], which are experimentally compared to unsatis ability pattern checks, showing that the latter two far outperform the Alloy approach (seconds vs. hours and timeouts), but complexity results are not provided. Their ORM fragment of the number encoding does include `costly' features, such as covering constraints, disjunctive mandatory, arbitrary frequency (with uniqueness check), external identi ers, and value constraints, but it is unclear what was used in the test ORM diagrams. The only ORM fragment claimed in PTIME is Smaragdakis et al.'s ORM [35] that also uses a number model. It includes non-overlapping uniqueness constraints over n-ary relationships, simple mandatory, non-overlapping frequency constraints (cardinalities > 1), value constraints, and subtype constraints. Arbitrary frequency constraints (like arbitrary projections in a relational table) cause undecidability, but, though not speci ed in [35], one could assume it always occurs in conjunction with a suitable uniqueness constraint in order to regain decidability, as discussed in [ 23, 29 ]. Their value constraints are not constrained either, i.e., value ranges of integers, oats, and enumerations are allowed, and have no constraints, such as so-called \safe" data types [ 3 ]. Most problematic, however, is the integer bound propagation in step 2 of Algorithm 2 in [35], which has recently shown to be NP-Complete [ 7 ], hence, Smaragdakis et al.'s solution seems to be at least NP-Hard. To the best of our knowledge, the here provided logic-based reconstruction of the ORM2cfd ORM fragment in the PTIME CF DI8nc is the rst tractable encoding of ORM, yet still capturing most of the entities encountered in extant ORM models. Extensibility to EER and UML Class Diagrams. As ORM is more expressive than UML Class Diagrams and EER, and an ORM diagram can be translated into UML and into ER [ 22 ], the results obtained should be at least as good for those. A quick matching thanks to availing of the unifying metamodel 8 [ 31, 18 ] reveals that that is the case, where CF DInc can encode over 97% of the 34 UML models and over 99% of the 34 (E)ER models in our dataset. This can be of use here as well, as also most UML Class Diagram encodings focus on expressiveness, using, among others, DLRifd [ 5 ] as well, or an OCL-lite encoding matching ALCI [34], which is still EXPTIME-complete. Kaneiwa and Satoh claim to have some fragments of UML Class Diagrams in P and PSpace for full satis ability checking (all classes must be satis able) [ 25, 26 ], but this has been proven otherwise by Artale et al. [ 1 ]. Focusing on coverage of features, the smallest restricted fragment is shown to be NLogSpace [ 1 ] when disallowing isa on associations and completeness on subclasses, using approximations of rei ed binaries (i.e., missing extid, and thus also no quali ed associations). An initial analysis shows that this might still capture almost 96% of the UML models in our dataset, and might thus also be a worthwhile fragment of UML. Such high coverage can be obtained partially due to the changes to UML v2.4.1 [ 33 ] where relational properties (asymmetry and transitivity) for aggregation have been dropped, with aggregation taking up about a quarter of all associations, and not all UML features in the standard are implemented in modelling tools.

The story is similar for (E)ER. Various encodings exist [ 14, 37, 38 ], (partially due to the absence of a standard), which either use a language in the EXPTIMEcomplete DLR family [9{11] or DL-Lite family [ 12 ] with di erent computational complexities for di erent EER fragments [ 2 ]. Trading functionality for gaining a little in computational complexity [ 2 ], however, is certainly not an option if coverage is also an aim, especially due to all the identi ers in EER and ORM (which can be represented in CF DI8nc ). 5

Conclusions A logic-based reconstruction for most of ORM using the PTIME Description 8 Logic language CF DInc has been presented, covering 96.5% of a set of extant ORM models. This is the rst tractable encoding of ORM, which includes features important for conceptual models, notably n-ary relationships and complex identi cation constraints. Future work includes working toward implementations of the scenarios alluded to in the introduction, and we also expect to apply this encoding to facilitate inter-model interoperability [ 17 ] as the results are easily transferable to EER and UML Class diagrams.

Acknowledgments. This work is based upon research supported by the National Research Foundation of South Africa (Project UID: 90041), the Argentinian Ministry of Science and Technology (PRF and CMK), and NSERC (DT). 34. Queralt, A., Artale, A., Calvanese, D., Teniente, E.: OCL-Lite: Finite reasoning on

UML/OCL conceptual schemas. Data & Knowledge Engineering 73, 1{22 (2012) 35. Smaragdakis, Y., Csallner, C., Subramanian, R.: Scalable satis ability checking and test data generation from modeling diagrams. Automation in Software Engineering 16, 73{99 (2009) 36. Solomakhin, D., Franconi, E., Mosca, A.: Logic-based reasoning support for SBVR.

Fundamenta Informaticae 124(4), 543{560 (2013) 37. Song, I.Y., Chen, P.P.: Entity relationship model. In: Liu, L., Ozsu, M.T. (eds.)

Encyclopedia of Database Systems, vol. 1, pp. 1003{1009. Springer (2009) 38. Thalheim, B.: Extended entity relationship model. In: Liu, L., Ozsu, M.T. (eds.)

Encyclopedia of Database Systems, vol. 1, pp. 1083{1091. Springer (2009) 39. Toman, D., Weddell, G.E.: Fundamentals of Physical Design and Query Compilation. Synthesis Lectures on Data Management, Morgan & Claypool Publishers (2011) 40. Toman, D., Weddell, G.E.: On adding inverse features to the description logic CFD8nc. In: PRICAI 2014: Trends in Arti cial Intelligence - 13th Paci c Rim International Conference on Arti cial Intelligence, Gold Coast, QLD, Australia, December 1-5, 2014. pp. 587{599 (2014) 41. Wagih, H.M., Zanfaly, D.S.E., Kouta, M.M.: Mapping Object Role Modeling 2 schemes into SROIQ(D) Description Logic. International Journal of Computer Theory and Engineering 5(2), 232{237 (2013)

References

1. Artale , A. , Calvanese , D. , Iban~ez-Garc a , Y.: Full satis ability of UML class diagrams . In: Parsons, J. , et al. (eds.) Proceedings of the 29th International Conference on Conceptual Modeling (ER'10) . LNCS, vol. 6412 , pp. 317 { 331 . Springer ( 2010 )

2. Artale , A. , Calvanese , D. , Kontchakov , R. , Ryzhikov , V. , Zakharyaschev , M. : Reasoning over extended ER models . In: Parent, C. , Schewe , K.D. , Storey , V.C. , Thalheim , B . (eds.) Proceedings of the 26th International Conference on Conceptual Modeling (ER'07) . LNCS, vol. 4801 , pp. 277 { 292 . Springer ( 2007 ), auckland, New Zealand, November 5- 9 , 2007

3. Artale , A. , Ryzhikov , V. , Kontchakov , R. : DL-Lite with attributes and datatypes . In: Proceeding of the 20th European Conference on Arti cial Intelligence (ECAI'12) . pp. 61 { 66 . IOS Press ( 2012 )

4. Bakema , G. , Zwart , J.P. , van der Lek, H.: Volledig Communicatiegeorienteerde Informatiemodellering FCO-IM. Academic Service ( 2005 )

5. Berardi , D. , Calvanese , D. , De Giacomo , G.: Reasoning on UML class diagrams . Arti cial Intelligence 168 ( 1-2 ), 70 { 118 ( 2005 )

6. Bloesch , A.C. , Halpin , T.A. : Conceptual Queries using ConQuer-II . In: Proceedings of ER'97: 16th International Conference on Conceptual Modeling. LNCS , vol. 1331 , pp. 113 { 126 . Springer ( 1997 )

7. Bordeaux , L. , Katsirelos , G. , Narodytska , N. , Vardi , M.Y.: The complexity of integer bound propagation . Journal of Arti cial Intelligence Research 40 , 657 { 676 ( 2011 )

8. Braga , B.F.B. , Almeida , J.P.A. , Guizzardi , G. , Benevides , A.B. : Transforming OntoUML into Alloy: towards conceptual model validation using a lightweight formal methods . Innovations in Systems and Software Engineering 6 ( 1-2 ), 55 { 63 ( 2010 )

9. Calvanese , D. , De Giacomo , G. , Lenzerini , M. : On the decidability of query containment under constraints . In: Proc. of the 17th ACM SIGACT SIGMOD SIGART Sym. on Principles of Database Systems (PODS'98) . pp. 149 { 158 ( 1998 )

10. Calvanese , D. , De Giacomo , G. , Lenzerini , M.: Reasoning in expressive description logics with xpoints based on automata on in nite trees . In: Proc. of the 16th Int. Joint Conf. on Arti cial Intelligence (IJCAI'99) . pp. 84 { 89 ( 1999 )

11. Calvanese , D. , De Giacomo , G. , Lenzerini , M. : Identi cation constraints and functional dependencies in description logics . In: Nebel, B. (ed.) Proc. of the 17th Int. Joint Conf. on Arti cial Intelligence (IJCAI 2001 ). pp. 155 { 160 . Morgan Kaufmann ( 2001 ), seattle, Washington, USA, August 4- 10 , 2001

12. Calvanese , D. , Giacomo , G.D. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and e cient query answering in description logics: The DL-Lite family . Journal of Automated Reasoning 39 ( 3 ), 385 { 429 ( 2007 )

13. Calvanese , D. , Keet , C.M. , Nutt , W. , Rodr guez-Muro, M. , Stefanoni , G.: Webbased graphical querying of databases through an ontology: the WONDER system . In: Shin, S.Y. , Ossowski , S. , Schumacher , M. , Palakal , M.J. , Hung , C.C. (eds.) Proceedings of ACM Symposium on Applied Computing (ACM SAC'10) . pp. 1389 { 1396 . ACM ( 2010 ), 22 - 26 March , 2010 , Sierre, Switzerland

14. Chen , P.P.: The entity-relationship model|toward a uni ed view of data . ACM Transactions on Database Systems 1 ( 1 ), 9 { 36 ( 1976 )

15. Curland , M. , Halpin , T. : Model driven development with NORMA . In: Proceedings of the 40th International Conference on System Sciences (HICSS-40) . pp. 286a{ 286a. IEEE Computer Society ( 2007 ), los Alamitos, Hawaii

16. Farre , C. , Queralt , A. , Rull , G. , Teniente , E. , Urp , T. : Automated reasoning on UML conceptual schemas with derived information and queries . Information and Software Technology 55 ( 9 ), 1529 { 1550 ( 2013 )

17. Fillottrani , P.R. , Keet , C.M. : Conceptual model interoperability: a metamodeldriven approach . In: Bikakis, A. , et al. (eds.) Proceedings of the 8th International Web Rule Symposium (RuleML'14) . LNCS, vol. 8620 , pp. 52 { 66 . Springer ( 2014 ), august 18- 20 , 2014 , Prague, Czech Republic

18. Fillottrani , P.R. , Keet , C.M.: KF metamodel formalisation . Technical report 1412.6545v1 (September 2014 ), arxiv.org

19. Fillottrani , P.R. , Franconi , E. , Tessaris , S. : The ICOM 3 . 0 intelligent conceptual modelling tool and methodology . Semantic Web Journal 3 ( 3 ), 293 { 306 ( 2012 )

20. Franconi , E. , Mosca , A. : The formalisation of ORM2 and its encoding in OWL2 . Technical Report KRDB12-2 , KRDB Research Centre, Faculty of Computer Science, Free University of Bozen-Bolzano, Italy (March 2012 ), http://www.inf.unibz.it/krdb/pub/TR/KRDB12-2.pdf

21. Halpin , T.: A logical analysis of information systems: static aspects of the dataoriented perspective . Ph.D. thesis , University of Queensland, Australia ( 1989 )

22. Halpin , T. , Morgan, T.: Information modeling and relational databases . Morgan Kaufmann, 2nd edn. ( 2008 )

23. Jahangard-Rafsanjani , A. , Mirian-Hosseinabadi , S.H. : Lightweight formalization and validation of ORM models . Journal of Logical and Algebraic Methods in Programming p. http ://dx.doi.org/10.1016/j.jlamp. 2015 . 03 .001 ( 2015 )

24. Jahangard Rafsanjani , A. , Mirian-Hosseinabadi , S.H. : A Z approach to formalization and validation of ORM models . In: Ariwa, E. , El-Qawasmeh , E. (eds.) Digital Enterprise and Information Systems, Communications in Computer and Information Science , vol. 194 , pp. 513 { 526 . Springer ( 2011 )

25. Kaneiwa , K. , Satoh , K. : Consistency checking algorithms for restricted UML class diagrams . In: Proceedings of the 4th International Symposium on Foundations of Information and Knowledge Systems (FoIKS'06) . Springer Verlag ( 2006 )

26. Kaneiwa , K. , Satoh , K. : On the complexities of consistency checking for restricted UML class diagrams . Theoretical Computer Science 411 , 301 { 323 ( 2010 )

27. Kazakov , Y. : RIQ and SROIQ Are Harder than SHOIQ . In: Brewka, G. , Lang , J . (eds.) 11th International Conference on Principles of Knowledge Representation and Reasoning (KR'08) . pp. 274 { 284 . AAAI Press ( 2008 ), 16 - 19 September, 2008 , Sydney, Australia

28. Keet , C.M. , Fillottrani , P.R. : Dataset of publicly available conceptual models and its analysis ( 2015 ), http://www.meteck.org/SAAR.html

29. Keet , C.M. : Prospects for and issues with mapping the Object-Role Modeling language into DLRifd . In: 20th International Workshop on Description Logics (DL'07) . CEUR-WS , vol. 250 , pp. 331 { 338 ( 2007 ), 8 - 10 June 2007, Bressanone, Italy

30. Keet , C.M. : Ontology-driven formal conceptual data modeling for biological data analysis . In: Elloumi, M. , Zomaya , A.Y. (eds.) Biological Knowledge Discovery Handbook: Preprocessing, Mining and Postprocessing of Biological Data , chap. 6 , pp. 129 { 154 . Wiley ( 2013 )

31. Keet , C.M. , Fillottrani , P.R. : Toward an ontology-driven unifying metamodel for UML class diagrams, EER, and ORM2 . In: Ng, W. , Storey , V.C. , Trujillo , J . (eds.) 32nd International Conference on Conceptual Modeling (ER'13) . LNCS, vol. 8217 , pp. 313 { 326 . Springer ( 2013 ), 11 - 13 November, 2013 , Hong Kong

32. Object Management Group: Semantics of Business Vocabulary and Rules (SBVR) { OMG released versions of SBVR , formal/2008-01-02 ( January 2008 ), http://www.omg.org/spec/SBVR/1.0

33. Object Management Group: Superstructure speci cation . Standard 2.4 .1, Object Management Group ( 2012 ), http://www.omg.org/spec/UML/2.4.1/