Designing Low Level Application Fragments:  Selecting QSTR Calculi

Get Complete Project Material File(s) Now! »

Chapter5  Organising and Visualising QSTR Applications

Introduction

In Chapter 3 a theoretical foundation for QSTR applications was defined. Based on these underlying mathematical semantics a formal requirements methodology for QSTR applications was established in the previous chapter. However, while providing a sound formal basis for applying QSTR and characterising the problems that can be addressed, a methodology is still required that directly supports developers in the organisation and design of QSTR applications. In particular, it is natural for a designer to want to arrange relations into appropriate categories and conpartmentalise domain concepts in a process of information chunking; this provides a more cognitively manageable QSTR application, and hence directly improves the efficacy of the design process [40, 44]. On the other hand, structuring relations at this level is not required for the mechanical process of automated reasoning. Moreover, it is highly desirable that the underlying theory be kept as clean and simple as possible. Thus, methodologies for relation organisation are analogous to design patterns in software engineering [152], as they define a standard approach formodelling some structurethatiscommontoarangeofQSTRapplication domains as opposed to complicating the underlying semantics. This chapter presents a mapping between the concepts in object oriented software engineering and the QSTR application domain. This greatly enhances the accessibility of QSTR applications, as it allows the adoption of prominent software development tools such as the Unified Modelling Language (UML) for designing QSTR applications. Section 5.2 presents a methodology for organising relations in a model using the concept of fragments; furthermore an analysis of the case study QSTR applications is conducted with respect to the organisation of fragments. Section 5.3 presents the details of the mapping between object oriented (OO) domain concepts and the central concepts in QSTR applications. Section 5.4 adapts UML sequence diagrams to enable a developer to visualise the flow of information between components in a QSTR application.

Organising Relations and Constraints Into Model Fragments

Certain relations in QSTR application models can often be grouped together,because they refer toasimilaraspectofadomainatthesameabstractionlevel. Moreover,relationswithinagroup often share constraints such as mutual exclusivity, symmetry, having inverse pairs, and so on. In the area of qualitative reasoning (QR) about physical systems the termmodelfragment refers to modular, partial models composed of different components that can be reused and extended in other models [91]. The concept of fragments is ideal for structuring QSTR applications: a QSTR fragment is a cohesive group of relations and their constraints (expressed as theories, as definedinChapter3). Ingeneral,aQSTRcalculuscorrespondstoafragment. Howeveritisthe responsibility of the developer to determine the precise meaning of cohesive, according to the specific application context, when organising custom qualitative relations and their associated theories into fragments. Example 5.2.1. In the QtvLight application (refer to 2.8.1), Guesgen’s block algebra [2, 78] forms a natural fragment as it can be reused in a wide range of QSTR applications. The set of qualitative relations that define the subjective impressions of a lit environment also forms a natural fragment, which is distinct from the relations that pertain to varying qualitative degrees of ambient illumination [148].
Simple fragment metrics such as the number of fragments and the number of relations per fragment are highly effective in characterising QSTR applications. Specifically, fragment analysis can provide a heuristic measure of the overall relative application complexity, and can highlight important structural and operational properties. Table 5.1 presents a comparison of the QSTR application case studies, along with the SparQ library and the AmI Framework (developed by Bhatt, Dylla and Hois [37]; refer to Section 1.3) with respect to the number of fragments and the number of relations per fragment. It must be noted that multiple values or formulae for the relation count in Table 5.1 represent different variations of the associated calculus; for example, the oriented point calculus [8] supports variable granularity m. Table 5.2 presents the distribution of fragments and relations at high, intermediate, and low abstraction levels based on typical scenario in put (lowlevelfragments) and expected application out put (highlevel). Table5.3presents the distribution of custom application-specificfragmentsandrelations (i.e. excluding the application of existing QSTR calculi); the mean number of relations perfragmentis31(standarddeviation30)and the mean number offragmentsperapplicationis 6 (standard deviation 5). It can be observed from Tables 5.1, 5.2, and 5.3 that QtvLight is the most structurally complex application with respect to the range of abstraction levels and the number of potential fragment interactions, although many of the fragments contain very few relations. In contrast, Tree Sap GIS is very shallow with respect to the levelsofabstraction. Thequantityoffragments and the range of abstraction levels also highlights an operational distinction between TreeSap and QtvLight; in TreeSap the higher level relations which correspond to patterns on low level relations are dynamically defined by users during querying, whereas in QtvLight the higher level relations are built into the design of the application. It is also interesting to observe in the applications QtvLight, Image Retrieval, and SailAway that the low level QSTR calculi tend to contain more relations than higher level fragments by an order of magnitude. This suggests a more universal principle that higher level fragments tend to be significantly less expressive compared to low level relations. This is consistent with the definition of QSTR applications given in Section 3.2, specifically, that high level relations represent patterns in lower level relations. This demonstrates that the hierarchical nature of QSTR applications is reflected in the organisation of fragments and the distribution of relations. The QSTR fragment is a simple and powerful concept that provide sanintuitive mechanism for organising QSTR relations. Inthefollowingsectionsfragmentsformthebasisofamapping between object oriented concepts and the QSTR application domain. 5.3 Mapping Object Oriented Concepts to the QSTR ApplicationDomain The object oriented (OO) paradigm is one of the most popular approaches for organising and developing applications in the software engineering community [92, 141]. Many prominent softwaremodellinglanguages,suchastheUnifiedModellingLanguage(UML)unifiedprocess, are used for specifying and visualising primarily object oriented (OO) software systems [92, 141]. In particular, UML class diagrams visualise the static components of an OO software system, specifically focusing on the structure of objects and how their operations are organised [141].1 OO software design paradigms such as UML class diagrams can potentially provide a powerfulinterfaceforsoftwareengineerstodevelopandutiliseQSTRtechniques; thisrequires a mapping from OO concepts such as classes, object attributes, object operations and class relationships,totheQSTRapplicationdomain. The central challenge which prevents the direct employment of OO design tools for QSTR application development is that OO software is imperative whereas QSTR applications are rule-based systems. The key for associating QSTR applications with OO systems is to specify fragments as the analogue of OO classes. This establishes a fundamental mapping between OO software and QSTR applications, and forms a basis for adapting other prominent OO concepts. Thus, the analogue to class diagrams in the QSTR domain is the fragment structure of the qualitative model. Table 5.4 summarises the adaptation of OO class diagram notation for the QSTR domain. OO classes are analogous to fragments in a QSTR application model such as the Allen Interval Algebra.2 OO class attributes and operations correspond to fragment relations and constraints, such as neighbourhood graphs (refer to Section 2.7). Relationships between O classes are analogous to QSTR constraints between fragments. Two very common types of fragment constraints map directly to two types of OO relationships. These are presented as design patterns in the following sections.3 In both cases, relations in one fragment are tightly associated to relations ina collection of other fragments because theyrefer to the same concept in the domain, but at different levels of abstraction. Section 5.3.1 presents fragment definitions which are analogous to OO aggregation associations [141]. Section 5.3.2 presents fragment generalisations which are analogous to OO generalisations [141].

 DesignPattern: FragmentDefinitions

The lower level relations represent properties or attributes, and specific combinations of these properties realise some particular higher level concepts. Therefore: Design a tethe higher level fragment as the abstraction domain,and the lower level fragment as the reference domain. For each abstraction domain relation, select a subset of reference domain relations that together describe or define the higher level relation ;this subsetis a definition of the higher level relation. Therecanbemorethanonedefinitionforeachhigherlevelconcept. The developer should define each subset as a minimal subset; if any of the lower level relations are removed from the definition then the subset no longer accurately describes the higher level concept. This encourages the developer to create multiple precise definitions that can overlap, rather than a smaller number of fuzzy definitions. For each definition, specify a constraint of the form:
<conjunction of reference domain relations in the definition> implies <the higher level relation>.
Example 5.3.1. In the Image Retrieval application (refer to Section 2.8.4) a mountain image can be defined as an image with more mountains than sky, and more sky than grass. To express this, the designer can define two fragments, one for qualitative image categories, including the relation mountain, and another for qualitative differences in features of an image, including “mountain > sky” and “sky > grass”. The conjunction between fragments is then implemented with the constraint x∈R+mountain>sky∧x∈R+ sky>grass →x∈R+mountain

DesignPattern: FragmentGeneralisation

The difference between two fragments is granularity, so that relations in one fragment are a coarse, incomplete, ambiguous, or generalised representation of relations in another, more fine grained fragment. Therefore: Design ate the higher level fragment as the abstraction domain,and the lower level fragment as the reference domain. For each abstraction domain relation, select a subset of reference domain relations that individually represent the same concept as the abstraction domain relation, but to a more precise degree ;this subsetisa specialisation. There is always exactly one specialisation subset for each higher level relation. Furthermore, two specialisations for two different high level relations can overlap. The developer should define each subset as a maximal subset; if any lower level relations are not included in the subset then in no way do they refine the higher level relation. This ensures that a specialisation represents all possible refinements of a highlevelconcept,andtendstopreventthedeveloperrulingoutpotential,albeitim probable,refinements, which would compromise reason in gsoundness. Following this strategy, adeveloper can clearly identify when a high level relation is too coarse or general (i.e. the specialisation subset is too large), and may decide to either partition the overly general relation into different relations within the abstraction domain, or introduce an entirely new intermediate abstraction layer fragment. For each specialisation, specify a constraint of the form: <disjunction of reference domain relations in the specialisation> implies <the higher level relation>.
Example5.3.2. Considertheincompletetemporalinformationthat“MozartisolderthanBeethoven”. In Freka’s semi-interval calculus [66], a time interval t1 is older than time interval t2 if t1 started before t2. This semi-interval knowledge says nothing about the relationship between the endings of the two time intervals. Thus, the high level semi-interval relation older than can potentiallyberefinedtooneofthefollowingintervalrelations: before,meets,overlaps,finished by, or contains. The disjunction of relations is implemented with the constraint (t1,t2)∈before+∨…∨(t1,t2)∈contains+→(t1,t2)∈olderThan+.

Contents
1 Introduction
1.1 The Application of Qualitative Spatial and Temporal Reasoning
1.2 Objectives of this Thesis
1.3 State of the Art in Applying QSTR Calculi
1.4 Contributions of this Thesis
1.5 Organisation of this Thesis
2 Qualitative Spatial and Temporal Reasoning
2.1 Introduction
2.2 Early QSTR Calculi
2.3 Unifying, Generalising and Augmenting QSTR Calculi
2.4 Algebraic Formulation of QSTR Calculi
2.5 Underlying Domains of Interpretation
2.6 Reasoning using Qualitative Spatial and Temporal Calculi
2.7 Conceptual Neighbourhoods
2.8 Case Studies of QSTR Applications
2.9 Summary
3 Theoretical Foundations of QSTR Applications
3.1 Introduction
3.2 Formal Definition of QSTR Applications
3.3 Actors and Roles
3.4 Ambiguity
3.5 Fundamental Operations on Scenarios
3.6 Characteristics of QSTR Applications
3.7 Summary
4 Formal Software Requirements for QSTR Applications
4.1 Introduction
4.2 External Interface Requirements
4.3 Specifying Functional Requirements with an Idealised Application
4.4 A Complete Enumeration of QSTR Tasks
4.5 Characterising QSTR Application Execution Behaviour
4.6 Performance Requirements
4.7 Summary
5 Organising and Visualising QSTR Applications
5.1 Introduction
5.2 Organising Relations and Constraints Into Model Fragments
5.3 Mapping Object Oriented Concepts to the QSTR Application Domain
5.4 Adapting UML Sequence Diagrams to Visualise QSTR Application Behaviour
5.5 Summary
6 Designing Low Level Application Fragments:  Selecting QSTR Calculi
6.1 Introduction
6.2 Defining Functional Consistency
6.3 Determining Functional Consistency in Consistent Unambiguous Scenarios
6.4 Determining Functional Consistency in Consistent Ambiguous Scenarios
6.5 Determining Functional Consistency in Inconsistent Scenarios
6.6 Functional Consistency Analysis Methodology
6.7 Generating the Strongest QSTR Theory from the Idealised Application
6.8 Summary
7 Designing High Level Application Fragments: Utilising Data-Based Metrics and DerivingHighLevelNeighbourhoodGraphs
7.1 Introduction
7.2 Analysing Fragment Interaction using Coupling and Cohesion
7.3 Generating High Level Neighbourhoods using Decision Tree Learning
7.4 Designing Consistent High Level Neighbourhood Graphs
7.5 Summary
8 ImplementingQSTRApplications
8.1 Introduction
8.2 Languages and Architecture
8.3 Encoding Relations and Scenarios
8.4 Implementing General Reasoning
8.5 Resource Constraints
8.6 Summary
9 Tes tClasses and Test Quality Metrics for Validating QSTR Applications
9.1 Introduction
9.2 Overview of QSTR Validation Methodologies
9.3 Unit Testing
9.4 Integration Testing
9.5 Test Coverage for Test Set Evaluation
9.6 Fault Seeding for Test Set Evaluation
9.7 Summary
10 H-Complexity for Analysing and Validating QSTR Applications
10.1 Introduction
10.2 H-Complexity Theory
10.3 Using H-complexity to Analyse QSTR Applications
10.4 Using H-complexity to Quantify Test Coverage
10.5 Summary
11 EvaluatingValidationTechniques
11.1 Introduction
11.2 Evaluation Methodology
11.3 Generating Random Subject QSTR Applications
11.4 An Experiment for Evaluating the Presented QSTR Validation Techniques
11.5 Summary
12 Conclusions
12.1 Future Research
12.2 QSTR Application Development using Functional Consistency Analysis and Future Research
12.3 Discussion of Limitations and Future QSTR Meta-Validation Research
References

GET THE COMPLETE PROJECT
Methodologies for the Development of Qualitative Spatial and Temporal Reasoning Applications