ISO/IEC JTC 1/SC34 N0403, 2003-04-03

ISO/IEC JTC 1/SC34

Information Technology —

Document Description and Processing Languages

Title:	AsTMa! Language Definition
Source:	Robert Barta, Bond University
Project:	ISO 18048
Project editor:	Lars Marius Garshol, H. Holger Rath
Status:	Individual contribution
Action:	For review and comment
Date:	2003-04-11
Summary:	Specification of the AsTMa! topic map constraint language
Distribution:	SC34 and Liaisons
Refer to:
Supercedes:
Reply to:	Dr. James David Mason (ISO/IEC JTC1/SC34 Chairman) Y-12 National Security Complex Information Technology Services Bldg. 9113 M.S. 8208 Oak Ridge, TN 37831-8208 U.S.A. Telephone: +1 865 574-6973 Facsimile: +1 865 574-1896 E-mail: mailto:mxm@y12.doe.gov http://www.y12.doe.gov/sgml/sc34/sc34oldhome.htm Mrs. Sara Desautels, ISO/IEC JTC 1/SC 34 Secretariat American National Standards Institute 25 West 43rd Street New York, NY 10036 Tel: +1 212 642-4937 Fax: +1 212 840-2298 E-mail: sdesaute@ansi.org

AsTMa! Language Definition

Robert Barta Bond University

rho@bond.edu.au

Constraining Topic Map (TM) instances is a necessary component of TM engineering. To make these constraints explicit we propose a Topic Map Constraint Language, AsTMa!. As such, AsTMa! is a part of the AsTMa language family which was designed to facilitate authoring, but also constraining and querying topic maps. This document provides a semi-formal definition of the language. Note that this is still an evolving project and that this document is a current snapshot only.

This document has no formal status. It is a technical report of Bond University.

Draft v0.6, 2003-04-07

1 Introduction
2 Conventions
3 Validation Relation
4 Maplets and Maplet Denotations
5 Unconditional Constraints
6 Maplet Patterns
7 Quantified Constraints
8 Constraints
9 Functions
10 Syntax Extensions
11 Moderators
12 Summary
13 Acknowledgements
A Appendix: Language Skins (Non-normative)
B Appendix: Predefined Functions (Normative)
C Appendix: Syntax (Normative)
D Appendix: External Functions (Non-normative)
E Appendix: Directives (Normative)
F Appendix: References (Non-normative)

1 Introduction

The objective of any TMCL (Topic Map Constraint Language) is to allow to formally specify rules for Topic Map documents.

In some respect a TMCL has a similar purpose as schema languages for relational databases and for XML applications. In all cases the constraint is supposed to characterize the possible values of the data (or the document). As Topic Map data may not only reside in documents containing Topic Map notated text but may also be generated from other data sources, we abstract away from documents and only regard Topic Map instances.

Constraints behave like type definitions: Given a constraint and a particular instance of a topic map it must be well-defined and computable in a reasonable time whether the instance validates against the constraint, or not. In the case of Topic Maps a constraint language must allow to specify

· a vocabulary, i.e. a set of topics,

· their respective types and relationships between them, and

· patterns which must, may or must not occur within a given topic map.

For our purposes we collectively use the term ontology to encompass all the above aspects of a particular knowledge domain. Accordingly, AsTMa! can be used as an ontology specification language.

As AsTMa! is making use of the authoring language AsTMa= it is mostly line oriented. It extends the authoring language by introducing variables which can be bound to text patterns similar to regular expressions and also variables which bind whole structures like in Prolog. We also peruse concepts of other languages e.g. the quantifiers 'forall' and 'exists' from logic-oriented languages and path expressions from XPath to add expressitivity or simplify the notation.

Following the general theme of the AsTMa* language family, AsTMa! was designed not so much as an orthogonal language, but more bias toward human authoring.

FIXME: Maybe make design goals more explicit?

2 Conventions

FIXME: use of regexp

FIXME: use of grammars (EBNF)

FIXME: use of relational algebra

3 Validation Relation

Given a particular map M, one may now ask whether M conforms to an ontology specified by a constraint O. Formally, we write O ||- M if M validates against the ontology O.

In practical settings, though, we will have to validate a map against several ontologies. Examples are situations where a customer has an ontology different from that of a vendor, or, when a company-wide ontology is refined and extended by a branch ontology. In these cases, topic map instances will have to comply with several such constraints. Technically this means that we will have to find ways to merge, i.e. combine constraints by logical operators having the following properties:

O₁ ^ O₂ ||- M <=> O₁ ||- M ^ O₂ ||- M

and, because of symmetry

O₁ v O₂ ||- M <=> O₁ ||- M v O₂ ||- M

With these requirements set, in the following we will specify the semantics of AsTMa!. For every map and for every AsTMa! expression this validation relation will be defined and can so be checked automatically.

We semi-formally define the relation ||- bottom-up. We start formalizing atomic parts of a map, maplets, and extend these to patterns which can be matched against topic map instances. Finally, we add quantifiers and boolean operators to allow the construction of rules.

4 Maplets and Maplet Denotations

To formally capture when exactly a topic map instance conforms to a constraint, we introduce maplets (Fig.1). A maplet is a part of a map, consisting of a single association and all topic characteristics of the topics mentioned in that association. This includes the association type, the association scope and all players and roles in the members.

Fig.1 Maplet connecting Topics

To also allow a single topic to be a maplet, we introduce a trivial association of type sum-ergo-sum and assume that any topic is a player in it:

(sum-ergo-sum)

topic: any-topic-here

4.1 Topic Characteristics

The topic characteristics are represented by a tuple (type, scope, value).

The type is indicated by a URI and specifies whether the characteristics is a baseName, an occurrence with a topic reference or inline data, etc. This is done using the predefined PSIs defined in [XTM].

The scope is another URI indicating the one topic which scopes the characteristic (We only use one scoping topic) in AsTMa*. For the unconstrained scope we will use the PSI defined in [XTM].

The value is a string comprising the value of the characteristics.

4.2 Maplet Merging

We will use maplets as atomic constructs. Obviously, any map can be constructed from these maplets or, conversely, can be fragmented into maplets.

Merging Maplet to build a Map

As operator + to combine maplets we simply use the merge operator as defined in the XTM standard[XTM00]. Consequently, any map M can be broken down into maplets m₁, ...,m_N:

M = + ^N_n=1 m_n

We call the set of maplets G_M = {m₁, ..., m_n} for a particular map M the generator of M. M is a submap of M', M << M', if G_M << G_M'. Obviously, the set of all submaps of M, 2^M, is a lattice.

5 Unconditional Constraints

We distinguish between maplets and maplet denotations which are text fragments in AsTMa= whereas maplets themselves are an abstraction of a representation an TM processor would use after having processed the maplet denotation (this is comparable to SAM[SAM03]). Thus, a maplet may be represented by a number of different maplet denotations.

We formalize the set of all maplet denotations as M₌.

Every maplet denotation is an unconditional constraint. Unconditional constraints only help to define the vocabulary aspect of an ontology. Per-se they do not impose any restrictions on a topic map structure and they only set the stage for more complex constraints. Nonwithstanding, an unconditional constraint is a constraint.

Any given map M satisfies any given unconditional constraint c₌ is element of M₌:

c₌ ||- M

It is straightforward to define a merge operator between unconditional constraints (we will later extend this to general constraints). If c₁ and c₂ are unconditional constraints, then c₁ + c₂ is also an unconditional constraint defined via

c₁ + c₂ ||- M <=> c₁ ||- M ^ c₂ ||- M

Again, as any map satisfies any unconditional constraint, that map also satisfies any merge of unconditional constraints. This also implies that any AsTMa= denotation A is an AsTMa! constraint, although all maps M will trivially conform to it:

A ||- M

6 Maplet Patterns

Maplet patterns themselves are no constraints but we will need them to build compound constraints later. Basically, maplet patterns are maplet denotations in AsTMa= with some of the text being replaced by variables and regular expressions.

Example:

$t (tutorial)

bn: /tutorial/i

oc: m|http://|

Here we simply reuse the matching semantics of regular expressions to define whether a particular maplet matches a maplet pattern. The maplet denotated by

astma (tutorial)

bn: AsTMa Tutorial

oc: http://astma.it.bond.edu.au/

matches the maplet pattern from above, whereas the maplet denotated by

astma (tutorial)

bn: AsTMa Tutorial

oc: no URL here

does not.

Before we define more expressive pattern matching we need variables which can be bound to values during the pattern matching process described below. After that we can define patterns for an open and closed expectation we could have on matching maplets.

FIXME unification-not: Maybe make a note that his is only about matching, not unification or reasoning. Unification would be necessary whenever two ontologies are going to be compared.

6.1 Variables

AsTMa! distinguishes between three different kinds of variables:

Reference Variables

Reference variables can only have topic identifiers as values and can match against topic identifiers.

Regular Expression Variables

These variables always appear as part of an Extended Regular Expression. They can only contain strings and can be matched against strings

Structural Variables

These variables are bound to whole submaps.

Since it is clear from the context what kind of variable is meant, there is no need to distinguish between them syntactically.

All variables are prefixed with the character $ or @. The name itself must follow the pattern \w[[:alnum:]-_]+. While variables of a different kind inhabit different namespaces, it is erroneous, though, to have within one scope two or more variables of different kinds but with the same name. This is mainly thought as a safety guard against casual errors.

6.1.1 Variable Scope

The scope of a variable is determined by the syntactic form of a constraint and will be defined later. Variables are implicitely declare by simply using them. In it's scope any further occurrence of a variable implies that all these occurrences must be bound to the same value during one match.

A notable deviation from the usual rules is that variables with different names must be bound to different values. This somewhat unorthodox interpretation helps to keep constraints concise and can be overridden if necessary by using the =~ operator, as in $a =~ $d.

6.1.2 Variable binding during Matching

During the matching process patterns will be matched against maplets. In this process variables within the patterns will be assigned values from the maplets (variable binding).

If - during such a match - an unbound variable is matched against a maplet value, that variable will be bound to that value for this match. This binding will remain the same for a single match; for such a match the variable will not change its value (immutable). Thus the set of variable bindings is characterizing a match.)

If - during a match - an already bound variable will be matched against a maplet value, the value of the variable and that in the maplet will have to be identical. Otherwise the match would not succeed.

6.1.3 Singular and Plural Variables

During the matching process variables are assigned values. In some cases we expect the variable to hold exactly one value. These variables are those which are prefixed with $. In other cases, though, we allow one variable to hold several values which are acquired during the matching process. This is indicated by the prefix @.

Example:

bn: $bn  # $bn will get one value during one match

some-role : @roles  # @roles will get several values during one match

Note that these variables are technically bags and not sets as they may contain a certain value more than once. Thus there is no inherent sequence. It also implies that two or more occurrences of a particular plural variable are compared as bags.

If a singular variable $v is to be matched against a particular constant, then the notation $v =~ value can be used. If $v should be matched against some other $w, then $v =~ $w can be used.

For a plural variable @v the value must be a bag for which we will use the notation @v =~ (value1, value2, ...). To make two bags be matched to the same values, we simply use @v =~ @w.

6.1.4 Reference Variables

Reference variables can appear anywhere in a maplet pattern where a topic reference can appear. During the matching process the variable will be bound to a topic reference (or to several topic references for plural variables).

Example:

$car (ferrari)

In cases where we do not care about the value to be matched we can also use the wildcard *. (Note, though, that this is no wildcard in the sense of regular expressions.)

6.1.5 Regular Expressions Variables

A regular expression (RE) can appear anywhere in a maplet pattern where arbitrary text is allowed, that is in occurrences, basenames and subject indicators. In the pattern matching process a corresponding maplet part of the map will be matched against regular expressions in a maplet pattern.

The regular expressions themselves follow the Perl syntax and are enclosed by the '/' character as in /.*/. As in Perl any other character can be used if the pattern starts with the character 'm' and the following character is the same as the last non-space character on this line.

Example:

bn: m|regexp pattern here|

In the above pattern we have introduced one regular expression using '|' as pattern terminator. This pattern will be matched against the string of a base name characteristic.

The use of Extended REs also allows to capture matched strings into variables. Here we make use of the facility to add a capture name for a text pattern using the notation (?var-name:pattern).

Example:

bn: /(?:b=.*)/

Here we introduced a variable b which will capture any basename string of a matched maplet.

For notational convenience text variables can also written without a pattern in the $ notation if that is simply /^\S.*\S$/ (any string except with no leading or trailing blanks). So, (?var-name:^\S.*\S$)) is equivalent to $var-name.

FIXME explicit-var-match: Is it necessary to add the syntax $v =~ /P/?

If we are not interested in the value itself and just need a placeholder, we can also use the wildcard character *. As now no name is associated with a matched value, such variables do not take part in the pattern matching process.

Example:

bn: *

6.2 Matching Rules

In the course of matching a maplet against a pattern various components of topics (such as baseNames, occurrences, etc.) and associations will have to be matched. This section contains the rules governing this process.

The individual components of a maplet pattern are:

instance-class patterns

With such a pattern an instance-class relationship is constrained, as, for example in $car (ferrari). This also includes instance-class constraints for associations.

(scoped) topic characteristics

Topic characteristics are constrained by using notations like bn: $basename or oc @ S ($type) : /http:/. Association roles are not regarded as characteristics here.

association role

Components like these constrain players and the roles in associations, eg. as in author: $a

For the following we assume that a given maplet should be matched against a component of a given maplet pattern. When a match is successful and how value bindings will occur is covered by this list.

· (topic instance-of:)

If a maplet pattern component is of the form

topic (type)

then a maplet set matches if there is a maplet of type instance-of where topic and type play the roles instance and class, respectively; or there is a maplet of type instance-of where topic plays the role instance and some other topic T plays the class, whereby T is a sub-type of type.

If topic is a variable and it is already bound to a value, the match will only succeed if that value plays an instance role in an instance-of association and the topic type matches like above. If it is not bound, it will be bound to any topic id in the maplet set.

FIXME: Not perfectly clear. And not overly elegant.

If the type is a variable and it is bound to a value there must be an association like outlined above between the type and the topic to make the match succeed. If the variable is not bound it will be bound to any value where such an association exists.

· (association instance-of:) If a maplet pattern component is of the form

(type)

then a maplet set matches if there is a maplet of type type. If type is a variable $v then it depends whether $v is already bound to a value or not. If it is then there must be a maplet in the set of exactly this type to make the match succeed. Otherwise, $v will be bound to a type of any maplet in the set.

FIXME: scoped association to be added.

· (basename constant:) If a maplet pattern component is of the form

bn: some-text

then a maplet matches if there is a topic characterstics of type 'baseName' which exactly matches the given text. All leading and trailing blanks are ignored, so is the scope.

· (basename pattern:)If a maplet pattern component is of the form

bn-or-oc-or-in: (?v=P)

with a variable v and a pattern P, then a maplet matches if a topic characteristic is of type 'baseName', 'occurrenceRef', or 'occurrenceData', respectively, and the according value matches the P. The scope value is ignored. If v is not yet bound to a value, it will be bound to the complete value of the characteristic (not only the part of the string which was matched). If v is already bound to a value, then that value must be identical to that of the base name string. The pattern P is ignored in this case.

· (characteristic scope:) If a maplet pattern component is of the form

bn-or-oc-or-in @ scope : ...

then additional to the rules for that particular topic characteristic type the scope is matched:

o If the scope is *, it will be ignored.

o If the scope is a constant S, then the topic characteristic in the maplet must have this as scope value.

o If the scope is a reference variable $s, then it depends whether $s is already bound to a value. If it is, then this value must be identical with the scope value in the topic characteristic. If not, then $s is bound to that value.

· (characteristic type:) If a maplet pattern component is of the form

bn-or-oc-or-in (type) : ...

then additional to the rules for that particular topic characteristic the type is matched:

o If the type is *, it will be ignored.

o If the type is a constant T, then the topic characteristic in the maplet must either have this as value or any other type which is a direct or indirect sub-type of T.

FIXME: match-global-view: need global view to other maplets here.

FIXME: Need somewhere definition of sub-type.

o If the type provided in the component is a reference variable $t, then it depends whether $t is already bound to a value. If it is, then this value must be identical with the type in the topic characteristic. If not, then $t is bound to that value.

FIXME: define-uris: need to define URIs for all of these types?

· (association role:) If a maplet pattern component is of the form

role : ...

then a maplet set will match if there is a maplet which contains the role given. If the role is not a constant, but a variable, then it depends whether this variable is already bound. If it is ... Otherwise the rule for matching the association player must be applied.

FIXME: this has to be factored out. Really.

· (association player:) If a maplet pattern component is of the form

... : player : ...

then a maplet set will match if there is a maplet which contains the role given. If the role is not a constant, but a variable, then it depends whether this variable is already bound.....

FIXME: this has to be factored out. Really.

Otherwise the rule for matching the association role must be applied.

· (subject indicator:) If a maplet pattern component is of the form

sin : value

then a set of maplets match if there is a topic characteristics of type 'subjectIndicator' and the value matches.

6.3 Open Maplet Patterns

If p is a maplet pattern, then [ p ] is a open maplet pattern. A maplet set S matches [ p ] if it satifies all of the following:

· all topic characteristic components in p can be matched to one and the same set of topic characteristics in one maplet m is element of S.

· all topic identifiers in an topic instance-of component of p match the player which is characterized by exactly the same topic characteristic set.

· All topic identifier in a association instance-of within p match the topic in that map.

FIXME: Need MUCH MUCH MUCH MORE formalism for this!!!

· All association role components in p match.

· All association player components in p match.

The maplet set can contain additional information which has no counterparts in p.

Example: Consider the open maplet pattern

[ * (tutorial)

  bn: /tutorial/i

  oc: /http:/ ]

The maplet denoted via

astma (tutorial)

bn: AsTMa Tutorial

bn @ de : AsTMa Einfuehrung

oc: http://astma.it.bond.edu.au/tutorial1

oc: http://astma.it.bond.edu.au/tutorial2

would match as it has a matching id, the type (instanceOf) matches and all characteristics (basename and occurrence) in the pattern have a matching counterpart in the maplet. Any additional characteristics (the basename with a different scope and the second additional occurrence) has no influence on the matching outcome.

6.4 Closed Maplet Patterns

If p is a maplet pattern, then ] p [ is a closed maplet pattern. A maplet set S matches ] p [ if it satisfies all of matching rules of a open maplet pattern, but all topics are minimal in the sense that they do not contain additional roles and topic characteristics which are explicitely not matched.

FIXME: well could be clearer.

Example: Flipping the [] brackets in the earlier example gives us such an closed maplet pattern:

] * (tutorial)

  bn: /tutorial/i

  oc: /http:/ [

Now the maplet above will not match anymore as the additional basename and the occurrence violate the maplet pattern which allows only one basename and only one occurrence.

7 Quantified Constraints

Quantified constraints build the core of the AsTMa! language. They finally allow to define rules which a conforming map must, may, or must not follow. To cater for that we have to introduce quantifiers and with them structural variables.

In contrast to regular expression variables and reference variables, structural variables are bound to whole submaps (maplet sets) when these are successfully matched against a maplet pattern. Otherwise the same rules for variables apply for them.

7.1 Syntax

Syntactically, AsTMa! follows the line-oriented paradigm and introduces also indentation to structure expressions syntactically:

· A constraint is not interrupted by an empty line or a line containing a comment.

· Constraints on the same logical level must be indented to the same column. Inconsistent indentation must be flagged by an AsTMa! parser.

Examples of valid constraints are:

# Example 1

exist $t [ * (person) ]

# Example 2, means the same, but with confusing line breaks

exists

    $t [

* (person)

# Example 3

forall [ $t (person) ]

   => exists [ (is-employed-at)

               employee : $t ]   # indentation not enforced

# Example 4

forall [ $t (person) ]

   => exists [ (is-employed-at)

               employee : $t ]   # indentation not enforced

      and                        # indentation important

      exists [ (is-married-with)

               partner : $t ]    # indentation not enforced

Examples of invalid indentations are:

# Example 5

forall [ $t (person) ]

   => exists [ (is-employed-at)

               employee : $t ]

   and                           # indentation invalid

    exists [ (is-married-with)   # indentation invalid

               partner : $t ]

7.2 Existence Quantified Constraints

If p is an open or closed maplet pattern and $v is a structural variable, then exists $v p is a (quantified) constraint.

If a variable is not needed as it is not necessary to refer to the matched submap in other parts of the constraint, then the variable can also be omitted as in exists p. In this case an internally generated variable will be used.

If c is such a constraint, then var(c) is the set of variables mentioned in that constraint. The scope of these variables starts with their first appearance and reaches until the end of the maplet pattern.

Informally, a map M conforms to th constraint exists $v p, if there is at least one submap m << M matching p.

More formally, we define a function b which computes all variable assignments for the successful matches. In this process only the smallest submaps of M are regarded which can satisfy p.

If var(c) is the set of variables involved and we introduce an arbitrary order on these variables (e.g. using alphanumeric sorting), then every single binding is an ordered tuple with one value for each variable. For $v the matched submap will be used. Technically, b (exists $v p, M) returns thus a relation. In the following this allows us to base the semantics on relational algebra.

7.3 Conditional Quantified Constraints

Some constraints only should apply to specific submaps of the map under consideration. To specify such constraints we have to first select these submaps and check then the rest of the constraint with each of them.

For variables this means that all variables mentioned in the condition are visible also in the rest of the constraint. This defines the scope of variables.

Quantified constraints can also be combined using the usual boolean operators AND, OR and NOT although some restrictions apply to reduce the expressiveness of the language.

Example: The following is a valid quantified constraint:

forall $t [ $p (person) ]

   => exists $t [ bn @ unconstrained-scope: * ]

and

      exists [ (is-employed-by)

               employee : $p ]

whereas the following is not:

forall $t [ $p (person) ]

   => not forall $t [ bn @ unconstrained-scope: * ] # invalid

      => exists [ (is-employed-by)

                  employee : $p ]

7.3.1 Positive Quantified Constraints

If c is a quantified constraint, p is an open or closed maplet pattern and $v is a structural variable, then forall $v p => c is a (conditional) quantified constraint. As with existence quantified constraints, the structural variable can be omitted if it is not needed. In that case an internally generated variable will be used.

Example X: Let us consider

forall [ $c (car) ]

   => exists [ $c

               bn: /ferrari/i ]

Such a conditional constraint would enforce that all submaps of the map under consideration which include a (direct or indirect) instance of a car also include the some topic such that it has base name characteristic which's value matches the word ferrari.

More formally, b is a function computing the assignment of values to variables. b (forall $v p, M) is computed as all tuples which have values for their corresponding variables in such a way, that p is successfully matched with a submap of M. In this case only the biggest submaps which match are considered.

For conditional constraints the bindings are computed as

b (f => g, M) = b (f, M) |><|r b (g, M)

whereby |><|r is the natural right join as known from the relational algebra.

Example X: In the following example we first try to match cars. For all of these matched maplets there must exist another maplet in the map matching the is-property-of association.

forall [ $t (car)

         bn: /ferrari/i ]

      => exists [ (is-property-of)

                   owner : millionaire

                   object: $t ]

In these cases we will often have to refer to topics, associations or parts thereof. This can be done with variables as above. For every topic of type car which we find in our map, its topic identifier will be bound to the variable $t. Our expectation is that the same topic plays the role of the object in an is-property-of association.

7.3.2 Negative Quantified Constraints

If c is a quantified constraint, p is an open or closed maplet pattern and $v is a structural variable, then forall $v p => not c is a (conditional) quantified constraint.

Intuitively, we check first all submaps matching the pattern and then have to ensure that none of these submaps match successfully with c. More formally, we define b to be:

b (f => not g, M) = b (f, M) - pi_var(f) b (f => g, M)

by simply deducting those bindings from b (f, M) which follow f => g.

7.3.3 Conjuction Quantified Constraints

If c and d are quantified constraints, p is an open or closed maplet pattern and $v is a structural variable, then forall $v p => c and d is a (conditional) quantified constraint.

The and takes not only care that both constraints c and d have to be matched by every submap matching p. In this case all variables are within one scope coercing appearences in c and d to have the same values. This is formalized by using the natural join on the individual bindings:

b (f => c and d, M) = b (f => c, M) |><| ₌ b (f => d, M)

7.3.4 Disjunction Quantified Constraints

If c and d are quantified constraints, p is an open or closed maplet pattern and $v is a structural variable, then forall $v p => c or d is a (conditional) quantified constraint.

In constrast to the conjunction variables in c and d are completely independent. The individual branches can be evaluated separately:

b (f => c or d, M) = b (f => c, M) union b (f => d, M)

8 Constraints

Finally, we can build constraints. First we define that any quantified constraint is already a constraint. The validity of such constraints is defined as

exists $v p ||- M <=> b (exists $v p, M) is not empty

and if c = forall $v p then

c => d ||- M <=> b (c, M) = pi_var(c) (b (c => d, M))

In the first case a map M is valid if there is at least one binding for the variables in b. In the second case all the bindings which forall $v p has in M must also be bindings for forall $v p => d whereby the projection operator pi only filters out those parts of the tuples which are relevant for c.

To build more complex constraints, we introduce boolean constants and operators to combine constraints.

8.1 True and False

For formal reasons we define true and false as constraints. All maps satisfy true, no map satisfies false:

true ||- M for all maps M

false ||- M for all maps M

8.2 Negation

In a next step we define the not operator. It allows to cover situations in which we are interested not to occur in conforming maps. If c is a constraint, then not c is defined via:

( not c ) ||- M <=> not ( c ||- M )

8.3 Conjunction

If c₁ and c₂ are constraints then c₁ and c₂ is a constraint, whereby we define

c₁ and c₂ ||- M <=> b (c₁, M) |><| ₌ b (c₂, M) is non-empty

Obviously, we use the natural join to define the conjunction of tuple sets. This implies that all variables have to be shared.

8.4 Disjunction

Also c₁ or c₂ is a constraint defined by

c₁ or c₂ ||- M <=> c₁ ||- M v c₂ ||- M

Here all variables are independent from each other; the clauses can be evaluated separately.

9 Functions

AsTMa! also offers language constructs to define new (boolean) functions. Their primary purpose is to keep constraints concise and to reuse particular domain knowledge.

Functions can be declared at any place within an AsTMa! instance and can be referenced via their name. The names follow the pattern /\w[[:alnum:]-_]+/.

function-definition -> 'function' function-name '(' [ formal-param-list ]')' 'returns' constraint

param-list        -> < ',', parameter-name [ ':' value ] >

Functions can have parameters. Formal parameters are listed within a () pair in a comma separated list and their names also follow the pattern /\w[[:alnum:]-_]+/. If for a parameter there exists a default value it is specified after the name following a colon (:). Optionally these values can be enclosed by "" to avoid ambiguity.

A function is referenced via its name followed by a list of actual parameters. The assignment of actual parameters to formal parameters is processed positional. If the actual parameter list is shorter than the formal parameter list, the defaults will be used. If there are no defaults, an error will be flagged.

FIXME: no recursion, this is more macro expansion.

Example: The following defines a function to control whether a particular topic T is used as a topic or association type:

function is-used-as-type (T)

  returns

     exists [ * (T) ]

OR

     exists [ (T) ]

Outside the function it can be referenced like in the following:

is-used-as-type (elephant)

FIXME: Should functions only be for top-level constraints?

An AsTMa! processor must understand the predefined functions listed in Appendix ?.

10 Syntax Extensions

In this section we extend the AsTMa! syntax without adding more expressiveness. The added constructs serve as convenience and help to keep real-world constraints concise.

10.1 Implicit AND

When using the exists operator often individual situations are requested as in

exists [ $c (car)

         bn: /ferrari/i ]

AND

exists [ (is-owned-by)

         owner : rho

         property : $c ]

If the exists keyword is not followed by a structural variable, the individual patterns can be combined into one:

exists [ $c (car)

         bn: /ferrari/i

         (is-owned-by)

         owner : rho

         property : $c ]

FIXME: does this work for forall? What about variables?

10.2 Negating Topic Characteristics

In some case it is necessary to constrain that topics should not have particular characteristic. Following the AsTMa! core language this can be done by not allowing the topic to exhibit that characteristic:

not exists $t [ bn @ de : * ]

Effectively, we disallowed all topics to contain base names scoped to the german language. The same can also be achieved with the following abridged syntax:

forall [ ! bn @ de : * ]

The internal ! operator works for occurrences (oc), inline text occurrences (in) and basenames (bn).

If two or more negations are used then the not conditions are ANDed:

forall [ ! bn : /stopword/

         ! oc : m|http://www.stop.com/| ]

# is equivalent with

NOT exists $t [ bn : /stopword/ ]

AND

NOT exists $t [ oc : m|http://www.stop.com/| ]

Conversely, if we would want to constrain that a particular basename does not occur in some topics we notate:

exists [ ! bn @ de : * ]

which is equivalent with

not forall [ bn @ de : * ]

FIXME: This only can work at the outest level? Allow it?

FIXME: should we allow bn @ ! de : /..../ or oc (!tutorial) : ....?

10.3 Negated Regular expressions

Also regular expressions within maplet patterns can be negated as the following example shows:

forall [ bn : !/ferrari/ ]

Here we specified that all topics must never have a basename matching the brand above. As such, this is equivalent to

not exists [ bn : /ferrari/ ]

# is equivalent with