Organisational policies express constraints on generation and processing of resources. However, application domains rely on transformation processes, which are in principle orthogonal to policy speci cations and domain rules and policies may evolve in a non-synchronised way. In previous papers, we have proposed annotations as a exible way to model aspects of some policy, and showed how they could be used to impose constraints on domain con gurations, how to derive application conditions on transformations, and how to annotate complex patterns. We extend the approach by: allowing domain model elements to be annotated with collections of elements, which can be collectively applied to individual resources or collections thereof; proposing an original construction to solve the problem of annotations remaining orphan, when annotated resources are consumed; introducing a notion of contract, by which a policy imposes additional pre-conditions and post-conditions on rules for deriving new resources. We discuss a concrete case study of linguistic resources, annotated with information on the licenses under which they can be used. The annotation framework allows forms of reasoning such as identifying con icts among licenses, enforcing the presence of licenses, or ruling out some modi cations of a licence con guration.
Organisational policies express constraints on generation and processing of resources which are accepted by agents subject to, or anyway acknowledging, the authority of such organisations. However, agents retain the ability to operate on such resources according to their own strategies, as long as the results of these operations conform to the policy, or are used in areas not subject to it.
A typical example is that of licenses, which de ne ways in which software
resources can be manipulated and made available for usage by third parties.
The di usion of open data [
In [
In this paper we extend the notion of annotation in four directions: rst we propose an original construction for transformations of annotated models, which solves the problem of orphan annotations, which remain dangling when annotated resources are consumed. Second, we allow domain model elements to be annotated with collections of elements from the annotations domain, which can be collectively applied to individual elements or collections thereof. Third, we consider violations of constraints induced by the creation of elements for which an annotation must be provided and de ne constraint repair actions to solve such situations. Finally, we introduce a notion of contract, by which a policy imposes additional pre- and post-conditions on rules for deriving new resources. Again, the use of contracts leads to an original notion of transformation under contracts. In all the considered cases, the de nition of transformations relies on the speci c features of annotations and classical categorial constructions. Paper organisation. After discussing related work in Section 2 and recalling fundamental notions in Section 3, we provide a construction for avoiding orphan annotations in Section 4 and introduce a motivational case study concerning linguistic resources annotated with licenses in Section 5. The model for rewriting under annotation constraints and contracts, illustrated via the case study, is presented in Section 6. Section 7 concludes the paper. 2
A number of approaches have considered the management of inconsistencies in
the eld of graph transformations. In particular, mechanisms for ensuring that
invariants are maintained throughout transformations have lead to the identi
cation of mechanisms for the generation of pre- or post-application conditions to
be associated with rules, or for manipulation of the left-hand or right-hand side
of a rule. This topic was started in [
Another line of research involves the identi cation of inconsistencies of a
model with respect to some desired (or undesired) property established at the
metamodel level. For example, conformance to a pattern can be imposed by
completing the missing required parts of the pattern by a co-limit construction [
Contracts were introduced in the form of pairs of graphs indicating pre- and
post-conditions of operations [
The need for a formalisation of licenses has been addressed for services, where
service composition has to take into account that di erent services may run
under di erent licenses, as part of service level agreement, focusing mostly on
service behaviour [
Graphs and morphisms. We introduce classical notions from graph
transformation theory (see [
De nition 1. A graph is a tuple G = (VG; EG; s; t), where VG is a set of nodes, EG is a set of edges, s : EG ! VG and t : EG ! VG are the source and target functions, i.e. graphs are considered to be directed.
De nition 2. Given two graphs G1 and G2 a morphism : G1 ! G2 is a pair of functions V : VG1 ! VG2 , E : EG1 ! EG2 such that E preserves the images of sources and targets, i.e. for e 2 E we have: s2( E (e)) = V (s1(e)) and t2( E (e)) = V (t1(e)).
We use morphisms for a number of purposes, some of which exempli ed through Figure 1.
Typing. For G1 a graph, and GT a type graph, : G1 ! GT is a typing morphism if is total. Typed graphs are extended to attributed typed graphs de ning speci c sets of attributes for them. A node of a certain type will be associated with a value for each of the attributes de ned by the type.
Transformation rule. One (as in the Single Pushout Approach, SPO, see Figure 1 (c)) or two (as in the Double Pushout Approach, DPO, see Figure 1 (a)) m G3 o
P O (a) G6 r / G2 P O m / G4 , G3 type-preserving morphisms are used to de ne rules. Regardless of the form, a rule p identi es a graph G1 and the applicability of p to a graph G3 depends on the existence of a total type-preserving morphism m : G1 ! G3. If a rule p is applied to a graph G3 to produce graph G4, we write (G3; G4) 2=)p. Constraint. : G1 ! G2 de nes a constraint together with a satisfaction relation, j=: for any graph G3, G3 j= i for each morphism 3 : G1 ! G3, there exist a morphism 4 : G2 ! G3 such that the triangle of Figure 1(b) commutes1. A negative constraint, denoted by : : G1 ! G2, is satis ed by G3 if no such morphism 4 exists for some 3. The particular case : : G1 ! G1, de nes a forbidden graph and is represented by the single graph G1. Application condition. Given a (DPO or SPO) rule p with identi ed graph G1, 1 : G7 ! G8 is an application condition (AC) for p if it restricts the relation =)p to pairs (G3; G4) for which there exist morphisms 3 : G1 ! G7, 4 : G7 ! G3 and 5 : G8 ! G3 such that the triangles in the diagram of Figure 1(c) commute (in the SPO approach the square in it is a pushout, analogously for the two squares in Figure 1(a)). The requirement that no such 4 exist is called a negative application condition (NAC).
All of the above is naturally extended to sets of rules and to attributed type
graphs, so that constraints and application conditions can refer to prescribed
values that attributes of the matched nodes must have. Rules can require updates
on the values associated with preserved nodes, or assignment of values for the
created nodes. In all these cases,we follow the approach of symbolic attributed
graphs [
De nition 3 from [
A type B-graph includes a set of box types BT which are sources or targets
for edge types. Moreover, a function cntT : BT ! }(V T [ BT ) associates each
type of box with the set of types of elements it can contain. Similarly, a (total)
morphism on B-graphs was de ned in [
V [B(x) 2 cnt2( B(b)), with V [B the (disjoint) union of V and B. In [
Based on these notions, annotation nodes can be used not just with reference
to individual nodes in T G1 and values in T G2, but also to collections in either
domain, i.e. a collection of annotation values can be used in an atomic way to
annotate some resource or collection thereof. However, in the original
formulation of rewriting with boxes in [
L o l K r / R m
P O
P O
m > G_ o G0 o
D
/ H P B P O h g0 D0 h0 / H0 Proposition 1. For G0 2 L a (T G) and a rule L K ! R, the graph H0 generated as in Construction 1 is in L a (T G). Moreover, Ann(H0) Ann(G0), where Ann(X) denotes the set of annotation nodes in a graph X. Proof. We rst observe that Ann(H0) = Ann(D0), so that Ann(H0) Ann(G0), since H, which is typed on T G1, does not present any new annotation. Since D0 is well-formed, none of its annotation nodes is an orphan. 5
A license speci es admissible forms of access, usage and redistribution of resources and of the results of manipulating them. While individual resources can be associated with speci c licenses, the licenses connected to a resource usually depend on some policy associated with the repository from which it is extracted. Moreover, such repositories often publish resources under a number of licenses, which must be all simultaneously respected, and which are normally transferred to the extracted resources. As this imposes some form of compatibility among licenses, deciding whether a certain usage is admitted may become complex. As an example, elements published under a Creative Commons, CC, scheme can be associated with combinations of the following licenses: NC for NonCommercial (the resource cannot be used for commercial purposes), BY for Attribution (credit to the author is acknowledged), SA for ShareAlike (derived resources must be redistributed preserving the original licenses), and ND for NoDerivatives (remixing, transforming, or building upon the resource may not grant redistribution). Each element is considered to be of PublicDomain (PD).
BabelNet3 [
BabelNet itself is obtained as the result of the automatic mapping (which is in
turn considered a kind of resource unique to BabelNet) and integration of several,
publicly available, knowledge repositories. However, each repository provides
resources (e.g. synsets and senses) under di erent licenses. For example, WordNet
[
However, the opposite is not possible, as no-one can modify a SA license. As a result, some licenses, such as CC-BY-NC-SA and CC-BY-SA, are inherently and mutually incompatible. To solve this problem, BabelNet is viewed as a collection of knowledge resources with heterogeneous licenses. For instance, it is possible to consider a subset of resources which can be used commercially, e.g. Wikipedia, WordNet and others. However, the resources with NC license (e.g. the Basque wordnet and the BabelNet mapping) cannot be used commercially. As the mapping is the enabling technology for interconnecting the various resources into a whole uni ed, multilingual network, any commercial use is subject to obtaining a commercial license from the BabelNet's authors.
To represent the management of licenses and languages in BabelNet, we model synsets, senses, etc. as nodes (or boxes) of speci c types from a domain, R, of Resources. Similarly, licenses are modeled as nodes of type License, from the domain of Licenses, L, with an attribute name ranging over strings identifying the di erent kinds of license, and languages are modeled as nodes of type Language, from the domain of Languages, K, with name ranging over the available languages. We consider R as the application domain, and L and K as contextual domains, typing the annotation edges accordingly. Thus, for xxx a type in R, edges of types xxxLicAnnotation and xxxLangAnnotation allow its annotation with elements of L and K, through edges of type annotatesWith.
Figure 4 presents the type graph T G for BabelNet. Stereotypes indicate whether an element is of the Node or Box sort, and if it comes from the domain R, L or K, or is an AnnotationTypeNode. In the domain R, a Sense is characterised by an attribute content, with values in the sort of strings. Moreover, the three types of box, Synset, Collection and LicenseBundle, can contain only elements of suitable types, namely Sense, Synset and License, respectively. The attribute concept for Synset indicates the concept represented by that collection of senses. The type LicenseBundleAnn, of the Node sort and derived from AnnotationTypeNode, can be used to relate resources with LicenseBundle. However, as it inherits from LicenseAnn, one can annotate any element in the resource domain with single licenses or with license bundles. A Request to obtain a Collection can be annotated with both license and language information (not indicated to avoid cluttering) and activates a Service producing the collection.
<<Node>> <<Resources>>
Service <<Node>> <<Resources>>
Mapping activates produces
<<Box>> <<Resources>>
Collection servLicAnnotation in
<<Box>> <<Resources>>
Synset -concept : string <<Node>> <<Resources>> origin
Sense -content : string puts -id : Identifier <<Box>> annotatesWith <<Licenses>>
LicenseBundle annotatesWith annotatesWith <<Node>> <<Licenses>>
License -name : string <<Node>> <<Languages>>
Language -name : string
We rst model the basic working of BabelNet services via increasing rules in the Resources domain. Rule createCollection in Figure 5 (top) creates an initially empty collection for the synsets to be served in response to a query to de ne the concepts in a set Z. Two rules allow the inclusion in the collection of a synset for a concept in the request. Rule addSynset in Figure 5 (middle) is used to add an already available synset in the collection if it is not already there, as indicated by the NAC. The other one, not shown, creates and adds a synset for a concept, if it does not exist already. Rule createMapping in Figure 5 (bottom) is used to populate synsets with senses representing the concept, according to a mapping, with a NAC to avoid including a sense twice.
obtains collLicAnnotation synsetLicAnnotation
<<Node>> <<Resources>>
Request -concepts : string[]
<<Node>> <<Annotation>>
LicenseBundleAnn <<Node>> <<Resources>>
Repository reposLicAnnotation
<<Node>> <<Annotation>>
LicenseAnn senseLangAnnotation
<<Node>> <<Annotation>>
LanguageAnn 5: offers 1 : Service name = "MAP" 2: activates 3 : Request
concepts = Z 4 : Repository name = "BABELNET"
name = "MAP" : produces
cnt(6)=
R 2: activates 3 : Request concepts = Z 5: offers
name = "BABELNET" 1 : Service name = MAP
4 : produces 5 : Collection
NAC 2: activates cnt(5) {6} 3 : Request concept = Z 6 : Synset concept = Y L=H 1 : Service name = MAP 4 : produces 2: activates
cnt(5) = H, YZ
concepts = Z
concept = Y
R 1 : Service 3 : Request name = MAP concepts = W 4 : produces 2: activates
concept = Y cnt(5)= H{6}, W=Z\{Y} NAC
5 : Synset : in concept = Y : Mapping : puts 2 : Sense content = X
L=H 5 : Synset concept = Y isRepr(Y,X), cnt(5)=H 2 : Sense content = X
R 5 : Synset : in concept = Y : Mapping cnt(5)=H{2} : puts 2 : Sense content = X
In all these cases, the bundle of licenses associated with the invoked
service must be associated with the produced collection, as will be discussed in
Section 6.2. Moreover, requests can be further characterised, for example by
annotating them with particular licenses or languages, so that only senses
annotated with those licenses or languages are included in the obtained collection,
as per suitable application conditions, following the constructions in [
While the result of applying a rule is guaranteed to produce a correctly typed graph, it might be the case that such a graph does not conform to further conditions imposed on the model at hand. We identify two dimensions along which conditions can be distinguished: one pertaining to the identi cation of the domain for which the condition is de ned (whether the application domain or the domain resulting from the annotation process) and one relative to the scope of the condition (whether global to the domain or local to speci c transformations).
Concerning the latter dimension, we use constraints, as introduced in Section 3, to impose well-formedness conditions for a domain. We assume that the host graph to which a rule is applied is well-formed, and we identify mechanisms to ensure that the transformation process produces another well-formed graph.
In [
In this section we focus on situations in which the addition of application conditions is not su cient, since the required context cannot already exist, in particular if a newly created element must be annotated in speci c ways. This would require the right-hand side of a rule to be enriched with the appropriate annotation, but then the rule would no longer be de ned only on the application domain. To approach this problem, we consider separately situations violating global constraints, and situations violating conditions on speci c rules, that we model as contracts. Since we are interested in rules which add new elements, i.e. L = K for a DPO rule, we present them as simple morphisms. 6.1
As shown in Table 1, licenses can require or forbid the presence of one another. While the rst case can be modelled by a positive constraint5, we model the second via forbidden graphs. Figure 6 (left) shows the forbidden graph expressing that no resource can be annotated with both licenses SA and ND. An analogous graph will forbid the presence of both licenses in the same bundle. The constraint on the right requires that each resource be PD, where we use the generic type name Resource to refer to any of the types from the Resource domain.
FG
: Resource : LicenseAnnotation : LicenseAnnotation
: License name="ND" : License name="SA"
P 1 : Resource
C 1 : Resource : resLicAnnotation : LicenseAnn : annotatesWith
: License name="PD"
The application of a rule may disrupt a constraint, typically by not creating the proper annotations. Hence, given a constraint , constraint repair actions are automatically inferred and applied, which modify the derivation relation so that the result satis es . 5 This would be a constraint with annotations both in P and C, not considered here. De nition 4 (Constraint repair action). Let 1 : G1 ! G2 be a rule and 2 : G3 ! G4 an annotation constraint. We de ne the relation =) 1; 2 with reference to Figure 7. For any two graphs G5 and G6 such that (G5; G6) 2=) 1 as witnessed by the leftmost square, and G6 6j= 2 (i.e. there exists a morphism i5 : G3 ! G6 but no morphism 6 : G4 ! G6 for which the triangle formed by 2, i5 and 6 commutes), we have (G5; G7) 2=) 1; 2 , where G7 is constructed as the colimit of all the diagrams constructed by taking the pushout of i5 and 2 along G3 for each i5 via the morphisms i7 : G4 ! Gi7 and i4 : G4 ! Gi7. The set of all the i4 is called a constraint repair action.
m G1 G5
1 / G2 P O m
i5 }}}}= ~}}}} / G6 S i 4 G3
2 / G4
Following Proposition 2 a repair action produces a graph compliant with 2. Proposition 2. Given G7 and 2 as in De nition 4 we have G7 j=
Proof. We know that G3 has a match in G5, so that the constraint is violated by the presence of some element without proper annotation, which is added in each Gi7 as an e ect of the pushout. Since we only deal with annotation constraints, each Gi7 does not present violations of 2 which were not in G4, but actually presents one less violation. By taking the colimit, no violation appears in G7.
Proposition 3 allows the cumulative application of repair actions. Proposition 3. Let G6 be as in De nition 4 and M2 = f j2 : Gj3 ! Gj4 j G6 6j= j2g. Then, let G07 the colimit of all the graphs G7 constructed as in De nition 4 for each j2 2 M2. Then G07 j= j2 for each j2 2 M2.
Proof. Since the premise of each j2 does not contain annotation elements, no G7 constructed for one constraint can add new violations of any other constraint. The result then follows by the associativity of colimits. 6.2
Contracts de ne situations in which the application of a rule requires the production of some annotation, but only in situations in which elements in its left-hand side are associated with speci c annotations.
De nition 5 (Contract). Given a rule 2 : G3 ! G4, a contract on 2, , is given by a morphism 1 : G1 ! G2 (G1 and G2 typed on T G) together with spans G1 3 G5 !4 G3, G4 5 G6 !6 G2 (formed by total injective morphisms) and a morphism 7 : G5 ! G6, (G5 and G6 typed on T G1), such that all the closed paths in the upper part of Figure 8 commute.
As an example, the top contract in Figure 9 describes the overall policy for license assignment: each collection is generated with the same collection of licenses of the generating service. Here, numbers are used to identify the nodes common to the rule and the contract, and letters for identifying elements related by the contract morphism.
1 : Service
3 : Request 2: activates
b : LicenseBundleAnn f : servLicAnnotation g : annotatesWith
a: LicenseBundle d: License 1 : Resource name="SA" f : resLicAnnotation dcnta), b : LicenseBundleAnn ccnt(a) c : License name=X g : annotatesWith a: LicenseBundle
2: activates 1 : Service 3 : Request 7 : produces f : servLicAnnotation b : LicenseBundleAnn 6 : Collection g : annotatesWith : annotatesWith a: LicenseBundle : LicenseBundleAnn
: collLicAnnotation d: License 1 : Resource name="SA" f : collLicAnnotation dcnt(e), b : LicenseBundleAnn ccnt(e) c : License name=X : Resource g : annotatesWith a: LicenseBundle : collLicAnnotation : LicenseBundleAnn e: LicenseBundle : annotatesWith
We can now model the asymmetry in license extension described in Section 5 with reference to the contract in Figure 9 (bottom): if a copy of a resource annotated with a bundle including the SA license is generated, the bundle annotating the new resource must preserve all the original licenses. This forbids the possibility of contracts which remove some license when SA is present, while it allows adding more licenses to the bundle, if not in contrast with others already present. Analogous contracts can be devised for multiple annotations with single licenses, rather than with a bundle of licenses. It is important to note that the directionality inherent to this contract would not be expressible via constraints, which would either impose or forbid the presence of annotations in the bundles both before and after rule application.
The application of a domain rule creating new elements typically violates contracts requiring that they be annotated in certain ways. Hence, actions must be taken, as speci ed in De nition 6 De nition 6 (Contract enforcement action). Let 2 : G3 ! G4 and be as in De nition 5. A derivation (G7; G8) 2=) 1 ful lls the contract i for each morphism 10 : G1 ! G7 such that the leftmost square in the diagram of Figure 8 commutes, and for each morphism 5i : G6 ! G4 there exists at least one morphism 8i : G2 ! G8 so that the triangle m 5i 7 : G5 ! G8, 1 3 : G5 ! G2 and 8i : G2 ! G8 commutes.
If the above does not hold, the pair (G7; G8) is said to breach the contract 1. A breach can be repaired by a contract enforcement action 11 for 1; 2 on G7 m by constructing G8 !11 G9 9 G2 as the pushout of the span G8 5i G6 !11 G2. We denote the derivation thus obtained by (G7; G9) 2=) 2; 1 . Note that if no 10 exists, then (G7; G8) also ful lls the contract.
Whenever multiple contracts apply to 2, the nal graph to be obtained for its application is represented by the colimit of all the diagrams thus formed, noting that in all such diagrams the pushout formed by G7 G3 ! G4 and G7 ! G8 G4 remains the same. Notice also that by a straightforward application of the associativity and commutativity of colimits, the same result can be obtained by successively applying the above construction to individual contracts, regardless of the order. The proof of Proposition 4 is then straightforward.
2 and a contract 1 on it, each derivation in =) 2; 1 ful lls 1.
Theorem 1 states that applying the enforcement action is equivalent to applying a rule resulting from the composition of 2 and 1. (G7; G9) 2=) 02 .
Theorem 1. Given a rule 2 : G3 ! G4 and a contract 1 : G1 ! G2 on 2, there exists a rule 02 such that for each pair (G7; G9) 2=) 2; 1 , we have Proof (Sketch.). Referring back to the diagram in Figure 8, the new left-hand side is constructed as the pushout of the span G1 3 G5 !4 G3, while the righthand side as the colimit of the collection of spans G4 5i G6 !6 G2. Shown in Figure 10 are the induced matching morphism G03 ! G7, the new rule 02 : G03 ! G04, and the result G9 of applying 02 to G07 via the induced matching. Since G04 already "contains" G2, there is no need for a subsequent enforcement action. (G5; G6) 2=) 1; 2 only if G6 6j= 1, of other contracts of the form
We can also de ne negative contracts, indicated as 1 : G1 !: G2 such that 2. This prevents the application, to the same 01 : G01!G02 with G01 ,! G1 and G2 ,! G02.
1 7 G1 BoBBBB3BB1B3? _PGO5 ~|1|4||4||||/G3m
G03 10 9! 02(9!) 2 m/ G4 BoB1B5BB5BiBP O
B / G04 ?* _G6
The constructions above can be adapted to general, i.e. not only increasing, DPO rules G3 G10 ! G4 by considering contracts in the form of spans G1 G11 ! G2 and identifying the spans G5 G12 ! G6 and G10 G13 ! G11.
In all these cases, we consider morphisms which are injective in the restrictions to D1 of the involved graphs, as well as in the immersion of D1 into D, while they can be non-injective in the restriction to D2. 7
We have extended the theory of annotation from [
With respect to the theory, future research will involve considering
constraints with annotations also in the premise, and to study dependencies and
con icts [
As concerns the application domain considered in the paper, we plan to extend this work towards a generic framework for managing licenses, taking into consideration also other licensing schemes, by which declarative speci cations of resource usages could be checked for veri cation of conformance to licenses. Moreover, the mentioned analysis tools in the eld of graph transformations can be applied to verify the internal consistency of license bundles.