#  Implementing Software Resiliency in HPX for Extreme Scale Computing
Extended Abstract, SNL report number: SAND2020-3975 R

Nikunj Gupta14, Jackson R. Mayo2, Adrian S. Lemoine34, Hartmut Kaiser34
1Computer Science and EngineeringIIT Roorkee, Roorkee, India, Email:
<EMAIL_ADDRESS>2Sandia National Laboratories, Livermore, California,
USA, Email<EMAIL_ADDRESS>3Center for Computation Technology, Louisiana
State University, Baton Rouge, USA, Email<EMAIL_ADDRESS>4The
STE$||$AR Group, http://stellar-group.org

###### Index Terms:

software resilience, parallel and distributed computing, asynchronous many-
task systems, HPX

##  I Introduction

The DOE Office of Science Exascale Computing Project (ECP) [1] outlines the
next milestones in the supercomputing domain. The target computing systems
under the project will deliver 10x performance while keeping the power budget
under 30 megawatts. With such large machines, the need to make applications
resilient has become paramount. The benefits of adding resiliency to mission
critical and scientific applications, includes the reduced cost of restarting
the failed simulation both in terms of time and power.

Most of the current implementation of resiliency at the software level makes
use of a Coordinated Checkpoint and Restart (C/R) [2, 3, 4, 5, 6, 7]. This
technique of resiliency generates a consistent global snapshot, also called a
checkpoint. Generating snapshots involves global communication and
coordination and is achieved by synchronizing all running processes. The
generated checkpoint is then stored in some form of persistent storage. On
failure detection, the runtime initiates a global rollback to the most recent
previously saved checkpoint. This involves aborting all running processes,
rolling them back to the previous state and restarting them.

In its current form, the Coordinated C/R is excessively expensive on extreme-
scale systems. This is due to the high overhead costs of global rollback
followed by global restart. Adding to these overheads are the significant
overheads of global I/O access. In many cases, millions of processes have to
respond to a local process failure which leads to heavy loss of useful CPU
computation cycles and leads to a significant performance penalty. This was
observed when node level resiliency was implemented in a production
application running on Titan system at Oak Ridge National Laboratory [8]. The
overheads of resiliency had a significant impact on performance as the
overheads of C/R were 20-30% of the total execution time.

Emerging resilience techniques, such as Uncoordinated C/R [10] and Local
Failure Local Recovery (LFLR) [9] attempts to mitigate some of the overheads
of coordinated C/R by eliminating the requirement of aborting all running
processes and restarting. However, these techniques are based on assumptions
exclusive to Single Program Multiple Data (SPMD) model i.e. the same program
execution across all running processes. Asynchronous Many-Task (AMT) execution
models provide similar resilience techniques without any of these assumptions.

In this paper, we explore the implementation of resiliency techniques in
Asynchronous Many-Task (AMT) Runtime Systems. We have chosen to use HPX as a
model AMT as it exposes a standards conforming API which is easy to understand
and adopt. AMTs replace the bulk-synchronous MPI model with fine-grained tasks
and explicit task dependencies. They rely on a runtime system to schedule the
tasks and manage their synchronization. In an AMT model, a program can be seen
as a flow of data which is processed by tasks, each task executing a distinct
kernel. Failures within a program are nothing but a manifestation of a failed
task, which can be identified as a local point of failure. This significantly
simplifies the implementations of a resilient interface. The two intuitive
choices of resiliency in AMT are task replay and task replicate. Task replay
reschedules a failed task until it runs to completion or exhausts the number
of replay trials. Task replicate schedules a single task multiple times
(decided by the application developer) and, from the successfully completed
tasks, determines the appropriate result.

The section 2 talks about Related Work in AMT resilience. Section 3 discusses
about HPX and Resilience with HPX. Section 4 discusses about the
implementation details of implementing resilience. Section 5 describes the
benchmarks and Section 6 discusses the results.

##  II Related Work

Software based resilience for SPMD programs have been well studied and
explored including but not limited to coordinated checkpoint and restart
(C/R). Enabling resilience in AMT execution model has not been well studied
despite the fact that the AMT paradigm facilitates an easier implementation.
Subasi et al [11, 12, 13] have discussed a combination of task replay and
replicate with C/R for task-parallel runtime, OmpSs. For task repication, they
suggested to defer launch of the third replica until duplicated tasks report a
failure. This differs from our implementation, as we replicate the tasks and
do not defer the launch of any task for future. For task replay, they depend
on the errors triggered by the operating system. This approach, thus, assumes
a reliable failure detection support by the operating system, which is not
always available. We also found that automatic global checkpointing has been
explored within the Kokkos ecosystem as well [14].

Similar work has recently been explored in AMT with Habanero C [15]. The work,
however, is based on on node resiliency. We plan to extend our work to provide
distributed resiliency features. Furthermore, Our work implements the AMT
resliency APIs with different characteristics. We also provide more control
over the APIs by introducing multiple variants of a single resilience API.
Finally, HPX is standards C++ conforming, giving application developers the
least effort for the addition of resilience over their current non resilient
code.

##  III Background

###  III-A HPX

HPX [16, 17, 20, 18, 19] is a C++ standard library for distributed and
parallel programming built on top of an asynchronous many-task (AMT) runtime
system. Such AMT runtimes may provide a means for helping programming models
to fully exploit available parallelism on complex emerging HPC architectures.
The HPX programming model includes the following essential components: (1) an
ISO C++ standard conforming API that enables wait-free asynchronous parallel
programming, including futures, channels, and other asynchronization
primitives; (2) an active global address space (AGAS) that supports load
balancing via object migration; (3) an active-message networking layer that
ships functions to the objects they operate on; (4) work-stealing lightweight
task scheduler that enables finer-grained parallelization and synchronization.

###  III-B Resilience in HPX

In this work we assume that a “failure” is a manifestation of a failing task.
A task is considered “failing” if it either throws an exception or if
additional facilities (e.g. a user provided “validation function”) identifies
the computed result as being incorrect. This notion simplifies the
implementation of resilience and makes HPX a suitable platform to perform
experiments with resiliency APIs. We present two different ways to expose
resiliency capabilities to the user:

Task Replay is analogous to the Checkpoint/Restart mechanism found in
conventional execution models. The key difference being localized fault
detection. When the runtime detects an error it replays the failing task as
opposed to completely rolling back of the entire program to the previous
checkpoint.

Figure 1: Task Replay and Task Replicate

Task Replicate is designed to provide reliability enhancements by replicating
a set of tasks and evaluating their results to determine a consensus among
them. This technique is most effective in situations where there are few tasks
in the critical path of the DAG which leaves the system underutilized or where
hardware or software failures may result in an incorrect result instead of an
error. However, the drawback of this method is the additional computational
cost incurred by repeating a task multiple times.

##  IV Implementation Details

The two main resiliency APIs explored are described below. All new
functionalities are implemented as extensions of the existing HPX async and
dataflow API functions. This enables a seamless migration of existing HPX
codes to support the described resiliency features.

###  IV-A Task Replay

In this technique, a task is automatically replayed (re-run) up-to N times if
an error is detected (see Listing 1).

(1) Async and Dataflow Replay: This version of task replay will catch user
defined exceptions and automatically reschedule the task N times before re-
throwing theexception.

(2) Async and Dataflow Replay Validate: This version of replay adds a
validation function to the API that is used to validate the individual
results. It returns the first positively validated result. If the validation
fails or an exception is thrown, the task is replayed until no errors are
encountered or the number of specified retries has been exceeded.

⬇

1using namespace hpxr = hpx::resiliency;

2

3hpxr::async_replay(N, F, Args...);

4hpxr::dataflow_replay(N, F, Args...);

5

6hpxr::async_replay_validate(N, ValF, F, Args...);

7hpxr::dataflow_replay_validate(N, ValF, F, Args...);

Listing 1: Task Replay API calls with variations. N represents the number of
times the runtime system should attempt to reschedule the task, F is the
function (task) to execute, Args… are the arguments to pass to F, ValF is the
function to validate the results.

###  IV-B Task Replicate

This feature launches N instances of a task concurrently. The function will
take one of four code paths depending on the variation of the API (see Listing
2):

(1) Async and Dataflow Replicate: This API returns the first result that runs
without errors.

(2) Async and Dataflow Replicate Validate: This API additionally takes a
function that validates the idnividual results. It returns the first result
that is positively validated.

(3) Async and Dataflow Replicate Vote: This API adds a voting function to the
basic replicate function. Many hardware or software failures are silent errors
that do not interrupt the program flow. The API determines the “correct”
result by using the voting function allowing to build a consensus.

(4) Async and Dataflow Replicate Vote Validate: This combines the features of
the previously discussed replicate APIs. Replicate vote validate allows a user
to provide a validation function and a voting function to filter results. Any
exceptions thrown during execution of the task are handled and are treated as
if the task failed. If all of the replicated tasks encounter an error, the
last exception encountered while computing the task is re-thrown. If finite
results are computed but fail the validation check, an exception is re-thrown.

⬇

1using namespace hpxr = hpx::resiliency;

2

3hpxr::async_replicate(N, F, Args...);

4hpxr::dataflow_replicate(N, F, Args...);

5

6hpxr::async_replicate_validate(N, ValF, F, Args...);

7hpxr::dataflow_replicate_validate(N, ValF, F, Args...);

8

9hpxr::async_replicate_vote(N, VoteF, F, Args...);

10hpxr::dataflow_replicate_vote(N, VoteF, F, Args...);

11

12hpxr::async_replicate_vote_validate(N, VoteF, ValF, F, Args...);

13hpxr::dataflow_replicate_vote_validate(N, VoteF, ValF, F, Args...);

Listing 2: Task Replicate API calls with variations. N is the number of
replicate tasks to be launched concurrently, F is the function (task) to
execute, Args… are the arguments to pass to F, ValF is the function to
validate the results, and VoteF is the function to use to select the correct
result.

##  V Benchmarks

This section discusses the benchmark examples, the machine architecture and
the HPX configuration.

Machine: All our benchmarks were run on a single node of NERSC’s Supercomputer
Cori. Each node has two sockets, each with Haswell Xeon E5-2698 v3 CPUs at
2.30GHz. While hyperthreading is enabled on the node, we have always run not
more than one kernel thread per core (32 CPU threads). Each physical core has
a dedicated L1 cache of 32KB and L2 cache of 256KB. Each socket has an L3
cache of 40MB shared between thirty two physical cores.

HPX configuration: We use Boost version 1.70.0, binutils version 2.32 and
jemalloc version 5.2.0 for the HPX builds. Boost and HPX were built with gcc
8.3 and all the benchmarks use gcc 8.3 as well [21].

Benchmarks: We ran our experiments with two benchmarks. The first benchmark
was written to allow us to easily vary an artificial workload. The second
benchmark application is a 1D stencil application that was adapted from a
preexisting HPX example.

To ensure statistically relevant results, we ran all of the benchmarks 10
times and report the average timing as the benchmark’s execution time. We did
not include the initialization and shutdown costs in the measured execution
time.

###  V-A Artificial work loads

This benchmark was written in order for the user to precisely control the task
grain size and therefore correctly compute the overheads of the resiliency
implementation. The benchmark calls a function 1,000,000 times and measures
the execution time. The function takes several arguments including the task
grain size and the error rate. The task grain size argument enables the user
to change the amount of “work” contained in each task. In order to model
random failures in the computation, the function uses an error rate to adjust
the percentage of tasks which will “fail”.

Within the function (see Listing 3), we added a timer to accurately measure
the user specified task grain size and an atomic counter to count the total
number of failed tasks. Furthermore, the task may throw an exception to
simulate “failure” based on a probabilistic criterion. In the case of the
validate API, we compare the final computed result with our expected result.
The benchmark measures the resilience capabilities of the system and the
robustness of the APIs themselves.

⬇

1int universal_ans(uint64_t delay_ns, double error)

2{

3 std::exponential_distribution<> dist(error);

4 double num = dist(gen);

5 bool error_flag = false;

6 if (num > 1.0)

7 {

8 error_flag = true;

9 ++counter;

10 }

11 uint64_t start = high_resolution_clock::now();

12 while (true)

13 {

14 uint64_t now = high_resolution_clock::now();

15 if (now - start >= delay_ns)

16 {

17 if (error_flag) throw std::exception();

18 break;

19 }

20 }

21 return 42;

22}

Listing 3: Function body of a task run in the artificial benchmark

###  V-B 1D Stencil

For this benchmark, we ported the 1D stencil code from HPX to enable
resilience while adding multiple time advancing steps per iteration on a
stencil. This benchmark accurately measures the overheads that one can observe
while using dataflow resilient variants. The overheads encountered with
dataflow arise from two factors. First, the overheads introduced from the
creation of the dataflow object, and second the sequence in which the futures
passed to the dataflow become ready. A dataflow waits for all provided futures
to become ready, and then executes the specified function.

This benchmark solves a linear advection equation. The task decomposition,
Lax-Wendroff stencil, and checksum operations are as described in previous
work [15]. Each task has three dependencies, the subdomain the current task
works on and the left and right neighboring subdomains. The stencil is
advanced through multiple time steps in each task by reading an extended
“ghost region” of data values from each neighbor, which helps reducing
overheads and latency effects.

We run the benchmark with two cases that we call 1D stencil case A and 1D
stencil case B. The case A uses 128 subdomains each with 16,000 data points,
it runs for 8,192 iterations with 128 time steps per iteration. The case B
uses 256 subdomains each with 8,000 data points, it runs for 8,192 iterations
with 128 time steps per iteration. The performance depends upon the task grain
size, i.e. the subdomain size, the number of time steps advanced per
iteration, and the number of dataflow operations involved, i.e. number of
subdomains and iterations. The performance overhead of resilience depends upon
the number of tasks. Case A invokes a total of 1,048,576 tasks while Case B
involves 2,097,152 tasks.

###  V-C Injecting errors

Errors injected within the applications are artificial and not a reflection of
any computational or memory errors. We use an exponential distribution
function to generate an exponential curve signature such that the probability
of errors is equal to $e^{-x}$, where x is the error rate factor. For example,
an error rate of 1 will have the probability of introducing an error within a
task equal to $e^{-1}$ or 0.36.

##  VI Results

This section discusses the empirical results for the benchmarks described in
Section 5.

###  VI-A Async Replay and Replicate

Resilient variants of async were measured with the artificial benchmarks to
compute the overheads. The overheads introduced by our implementation are
listed in Table I. The observed implementation overheads are very small and
are often comparable to the measurement accuracy.

| No. of
---
Cores
| Async Replay and
---
Replay Validate
(in $\mu$s)
| Async Replicate, Replicate Validate,
---
Replicate Vote and Replicate Vote
Validate (in $\mu$s)
1 | 0.792 | 0.774 | 0.985 | 0.986 | 0.987 | 1.023
4 | 0.251 | 0.263 | 0.161 | 0.165 | 0.161 | 0.163
8 | 0.145 | 0.150 | 0.078 | 0.078 | 0.078 | 0.082
16 | 0.080 | 0.085 | 0.034 | 0.034 | 0.034 | 0.036
32 | 0.057 | 0.058 | 0.017 | 0.017 | 0.017 | 0.016
TABLE I: Amortized overheads per task of resilient async variants with a task
grain size of 200$\mu$s

Replicate variants of async behave similarly. The overheads for replicate
depends upon the number of replications. Other minor overheads such as vector
memory allocation and the number of push back function calls are also
dependent on the number of replicates requested. With sufficient compute
resources available, one can expect these overheads to be within the margin of
error. For a task of 200$\mu$s making three replicates, there is thrice the
number of tasks involved compared to its replay counterpart (see also Figure
2(b)). Because these extra tasks are independent of each other, the overheads
are quickly amortized when there are available resources than its replay
counterpart, which will not be able to take advantage of the added parallelism
as efficiently. The minor differences in overheads between resilient variants
arises from the underlying implementation, some requiring more boilerplate
code to be executed than others.

(a) Async Replay: Extra execution time per task vs. Probability of error
occurrence.

(b) Async Replicate: Extra execution time per task vs. Probability of error
occurrence

Figure 2: Extra execution time per task for task grain size of 200$\mu$s.

The trend is similar when the applications are injected with artificial
errors. When errors are encountered, the resilient logic is activated and
behaves as specified. For cases with low probability of failures, we see that
amortized overheads of async replay and variants are still small enough to be
hidden by system noise (see also Figure 2(a)). For instance, the overheads, in
the worst case scenario for an error rate of 5%, is about 0.54$\mu$s or 0.27%
of the total overhead per task. Given that the probability of failure within a
machine will not be more than a percent in most cases, it is safe to assume
that async replay introduces no measurable overheads for applications
utilizing the feature. Taken together, the presented results indicate that
these resilient features will not incur any meaningful execution time costs.

For cases that use async replicate and variants, we observe that the amortized
overhead per task stand at 6.4% for task size of 200$\mu$s, which is
significantly larger. This is expected as the overheads include running more
duplicate tasks. A minor implementation overhead is also present, though
dwarfed by the time it takes to repeatedly run a task itself. The graph is a
straight line, as expected, since every task is replicated three times
irrespective of any encountered errors (see Figure 2(b)). With these costly
overheads, this resiliency feature is only recommended in portions of code
which are starved for work (i.e. there are sufficient computational resources
available) or for critical portions of code, where computed results have to be
guaranteed to be correct.

###  VI-B 1D stencil

1D stencil example was designed to check the dataflow resiliency capabilities.
The aim of this benchmark was to observe the extra execution time for
different stencil parameters. Table II summarizes the measured results for the
case of no failures, comparing the new API variations with a base-line version
that is based on basic HPX dataflow facilities.

| 1D
---
stencil
| Pure
---
Dataflow
(in s)
| Replay
---
without
checksums
(in s)
| Replay
---
with
checksums
(in s)
| Replicate
---
without
checksums
(in s)
Case A | 46.564 | 47.315 | 46.869 | 135.871
Case B | 47.267 | 49.756 | 49.268 | 139.242
TABLE II: 1D stencil: Execution time in case of no failures for case A and
case B, where case A utilizes 128 subdomains each with 16000 data points and
case B utilizes 256 subdomains each with 8000 data points, each case iterating
8192 times with 128 times steps per iteration.

Implementing resiliency using the dataflow variations with 1D stencil case A
introduces 1.5% and 0.4% overheads for replay without and with checksums
respectively. Similarly, with case B we observe 5% and 4.1% overheads for
replay without and with checksums respectively. These numbers are certainly
higher than its async variants. This is expected given that dataflow waits for
all futures to become ready before executing the function. We currently cannot
explain why the benchmarks with checksums runs (slightly) faster. The time
difference in execution might arise due to lower overheads of synchronization
within dataflow. Resiliency with replication are low as expected as well,
which can be attributed owing to efficient parallelism and cache effects.

When we inject errors within the code, we see similar trends as those we
observed in the case of its async counterpart. For low failure rates, we
observe that the overheads are about the same as the implementation overheads.
As expected we see a spike in overheads as the probability of failure
increases with 5.9% and 6.9% overheads for Case A and 8.5% and 9.6% for Case
B.

(a) 1D stencil case A: Percentage extra execution time vs. Probability of
error occurrence.

(b) 1D stencil case B: Percentage extra execution time vs. Probability of
error occurrence.

Figure 3: 1D stencil case A and case B: case A utilizes 128 subdomains each
with 16000 doubles and case B utilizes 256 subdomains each with 8000 doubles,
and each case iterates 8192 times with 128 times steps periteration.

## Conclusion

In this paper, we implemented two resiliency APIs in HPX: task replay and task
replication. Task replay reschedules a task up to n-times until a valid output
is returned. Task replication runs a task n-times concurrently. We demonstrate
that only minimal overheads are incurred when utilizing these resiliency
features for work loads where the task size is greater than 200 $\mu$s. We
also show that most of the added execution time arises from the replay or
replication of the tasks themselves and not from the implementation of the
APIs.

Furthermore, as the new APIs are designed as extensions to the existing HPX
async facilities that are fully conforming to the C++ standard, these features
will be easy enough to embrace and enable a seamless migration of existing
code. Porting a non resilient application to its resilient counterpart will
require minimal changes, along with the implementation of validation/vote
functions, wherever necessary. This removes the necessity of costly code re-
writes as well as time spent learning new APIs.

Finally, we developed multiple resilient APIs that are designed to cater to
the specific needs of an application. This allows developers the option to
choose the optimal resilient function with the least disruption to efficiency.

## Future Work

The current implementation of resiliency is limited to intra node parallelism.
We plan to extend the presented resiliency facitities to the distributed case
while maintaining the straightforward API. We expect that both – task replay
and task replicate – can be seamlessly extended to the distributed use case by
introducing special executors that will manage the aspects of resiliency and
task distribution across nodes.

The current implementation enables to have both task replay and task replicate
within the code independently. Task replicate can be made more robust by
adding task replay within its implementation allowing any failed replicated
task to replay until its computed without error detection. This will allow for
finer consensus in case of soft failures within the system.

## Acknowledgment

Sandia National Laboratories is a multimission laboratory managed and operated
by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned
subsidiary of Honeywell International Inc., for the U.S. Department of
Energy’s National Nuclear Security Administration (NNSA) under contract DE-
NA0003525. This work was funded by NNSA’s Advanced Simulation and Computing
(ASC) Program. This paper describes objective technical results and analysis.
Any subjective views or opinions that might be expressed in the paper do not
necessarily represent the views of the U.S. Department of Energy or the United
States Government.

## References

  * [1] P. Kogge et al., ExaScale Computing Study: Technology Challenges in Achieving Exascale Systems, tech. report TR-2008-13, Dept. of Computer Science and Eng., Univ. of Notre Dame, 2008
  * [2] J. T. Daly, “A higher order estimate of the optimum checkpoint interval for restart dumps,” Future Gener. Comput. Syst., vol. 22, no. 3, pp. 303–312, Feb. 2006.
  * [3] J. Duell, P. Hargrove, and E. Roman, “The design and implementation of berkeley lab’s linux checkpoint/restart,” Lawrence Berkeley National Laboratory, Tech. Rep. LBNL-54941, 2002.
  * [4] K. Li, J. Naughton, and J. Plank, “Low-latency, concurrent checkpointing for parallel programs,” Parallel and Distributed Systems, IEEE Transactions on, vol. 5, no. 8, pp. 874–879, Aug 1994.
  * [5] A. Moody, G. Bronevetsky, K. Mohror, and B. de Supinski, “Design, modeling, and evaluation of a scalable multi-level checkpointing system,” in High Performance Computing, Networking, Storage and Analysis (SC), 2010 International Conference for, 2010, pp. 1–11.
  * [6] J. S. Plank, K. Li, and M. A. Puening, “Diskless checkpointing,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 10, pp. 972–986, October 1998.
  * [7] E. Roman, “Survey of checkpoint/restart implementations,” Lawrence Berkeley National Laboratory, Tech. Rep. LBNL-54942, 2002.
  * [8] M. Gamell, D. S. Katz, H. Kolla, J. Chen, S. Klasky, and M. Parashar, “Exploring automatic, online failure recovery for scientific applications at extreme scales,” in Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, ser. SC ’14, 2014.
  * [9] K. Teranishi and M. A. Heroux, “Toward local failure local recovery resilience model using MPI-ULFM,” in Proceedings of EuroMPI/Asia’14, the 21st European MPI User Group Meeting, 2014.
  * [10] A. Guermouche, T. Ropars, E. Brunet, M. Snir, and F. Cappello, “Uncoordinated checkpointing without domino effect for send-deterministic mpi applications,” in Parallel Distributed Processing Symposium (IPDPS), 2011 IEEE International, 2011, pp. 989–1000.
  * [11] O. Subasi et al., “Nanocheckpoints: A task-based asynchronous datafow framework for efficient and scalable checkpoint/restart,” in 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, pp. 99–102, March 2015.
  * [12] O. Subasi et al., “A runtime heuristic to selectively replicate tasks for application-specific reliability targets,” in 2016 IEEE International Conference on Cluster Computing (CLUSTER), pp. 498–505, Sept 2016.
  * [13] O. Subasi et al., “Designing and modelling selective replication for fault-tolerant hpc applications,” in 2017 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID), pp. 452–457, May 2017.
  * [14] H. Carter Edwards et.al., “Kokkos: Enabling Manycore Performance Portability through Polymorphic Memory Access Patterns”, Journal of Parallel and Distributed Computing, 2014, vol. 74, num. 12, pp. 3202-3216.
  * [15] K. Teranishi et al., “ASC CSSE level 2 milestone #6362: Resilient asynchronous many-task programming model,” Sandia National Laboratories, Tech. Rep. SAND2018-9672, 2018.
  * [16] Thomas Heller et.al., “Application of the ParalleX Execution Model to Stencil-Based Problems”, in Computer Science - Research and Development, 2012, vol. 28, num. 2-3, pp. 253-261.
  * [17] Thomas Heller et.al., “Using HPX and LibGeoDecomp for Scaling HPC Applications on Heterogeneous Supercomputers”, ScalA 2013, SC Workshop.
  * [18] Hartmut Kaiser et.al., “Higher-level Parallelization for Local and Distributed Asynchronous Task-based Programming”, ESPM 2015, SC Workshop.
  * [19] Thomas Heller et.al., “Closing the Performance Gap with Modern C++”, E-MuCoCoS 2016, ISC Workshop.
  * [20] H.Kaiser et.al., “HPX: A Task Based Programming Model in a Global Address Space”, International Conference on Partitioned Global Address Space Programming Models (PGAS), 2014, art. id 6.
  * [21] HPX GitHub repository, STE$||$AR Group, https://github.com/STEllAR-GROUP/hpx, 2019, Available under the Boost Software License 1.0.

##  VII Artifact Description: Implementing Software Resiliency in HPX
forExtreme Scale Computing

###  VII-A Abstract

In this section we describe the configuration and environment needed to run
our experiments. The experiments are run on a single node of NERSC Cori
supercomputer. We present the steps to build the software on Cori and repeat
our experiments and how to gather the performance results.

###  VII-B Description

####  VII-B1 Check-list (artifact meta information)

  * •

Program: HPX

  * •

Compilation: GCC 8..3

  * •

Hardware: Cori

  * •

Run-time state:

  * •

Output: Benchmark results in text

  * •

Publicly available?: Yes

####  VII-B2 How software can be obtained (if available)

HPX can be obtained from https://github.com/STEllAR-GROUP/hpx. Resiliency
features are available as an HPX module within HPX itself.

####  VII-B3 Hardware dependencies

Access to Cori can be requested through NERSC.

####  VII-B4 Software dependencies

The following modules need to be loaded to build HPX:

  * •

gcc/8.3.0

  * •

boost/1.70.0

  * •

cmake/3.10.2

The following software need to be built from their source since they are not
available on Cori:

  * •

jemalloc. The latest version of CMake can be downloaded from
https://github.com/jemalloc/jemalloc.

###  VII-C Installation

  * •

HPX

⬇

1cmake

2 -H<PATH_TO_HPX_CODE>

3 -B<PATH_TO_HPX_BUILD>

4 -DCMAKE_BUILD_TYPE=Release

5 -DCMAKE_C_COMPILER=gcc

6 -DCMAKE_CXX_COMPILER=g++

7 -DBOOST_ROOT=<PATH_TO_BOOST>

8 -DBoost_NO_SYSTEM_PATHS=True

9 -DHPX_WITH_EXAMPLES=False

10cmake \--build <PATH_TO_HPX_BUILD>

###  VII-D Running Benchmarks

  * •

Get a job from Cori for a single node haswell and ensure all required modules
listed in section VII-B4 are loaded.

  * •

Copy the script files provided at https://github.com/STEllAR-
GROUP/hpxr_data/tree/master/benchmark_scripts to the binary directory. Execute
the scripts to generate the results.

  * •

Repeat the same for all the shell scripts

###  VII-E Evaluation and expected result

Scripts to generate graphs on the returned results are provided at
https://github.com/STEllAR-
GROUP/hpxr_data/tree/master/benchmark_results/graphs. Copy them to the binary
directory and run the python files. To successfully generate the graphs make
sure that the following are available:

  * •

python 2.7

  * •

matplotlib

  * •

Tkinter

The emperical results that we achieved running the scripts described above are
provided at https://github.com/STEllAR-
GROUP/hpxr_data/tree/master/benchmark_results/benchmarks. Running the python
scripts on them will result in the graphs used in the paper.


# Interactive Query Formulation using Spider Queries
Asymetrix Report 94-2

H.A. Proper
Asymetrix Research Laboratory
Department of Computer Science
University of Queensland
Australia 4072
<EMAIL_ADDRESS>
(Version of at 23:14)

###### Abstract

Effective information disclosure in the context of databases with a large
conceptual schema is known to be a non-trivial problem. In particular the
formulation of ad-hoc queries is a major problem in such contexts. Existing
approaches for tackling this problem include graphical query interfaces, query
by navigation, query by construction, and point to point queries. In this
article we propose the spider query mechanism as a final corner stone for an
easy to use computer supported query formulation mechanism for InfoAssisant.

The basic idea behind a spider query is to build a (partial) query of all
information considered to be relevant with respect to a given object type. The
result of this process is always a tree that fans out over existing conceptual
schema (a spider).

We also provide a brief discussion on the integration of the spider quer
mechanism with the existing query by navigation, query by construction, and
point to point query mechanisms.

Published as:

> H.A. (Erik) Proper. Interactive Query Formulation using Spider Queries.
> Technical report, Asymetrix Research Laboratory, University of Queensland,
> Brisbane, Queensland, Australia, 1994.

##  1 Introduction

Most present day organisations make use of some automated information system.
This usually means that a large body of vital corporate information is stored
in these information systems. As a result an essential function of information
systems is the support of disclosure of this information. Without a set of
adequate information disclosure avenues an information system becomes
worthless since there is no use in storing information that will never be
retrieved. An adequate support for information disclosure, however, is far
from a trivial problem. Most query languages do not provide any support for
the users in their quest for information. Furthermore, the conceptual schemata
of real-life applications tend to be quite large and complicated. As a result,
the users may easily become lost in conceptual space and they will end up
retrieving irrelevant (or even wrong) objects and may miss out on relevant
objects. Retrieving irrelevant objects leads to a low precision, missing
relevant objects has a negative impact on the recall ([SM83]).

The disclosure of information stored in an information system has some clear
parallels to the disclosure problems encountered in document retrieval
systems. To draw this parallel in more detail, we quote the information
retrieval paradigm as introduced in [BW92]. The paradigm starts with an
individual or company having an information need they wish to fulfil. This
need is typically a vague notion and needs to be made more concrete in terms
of an information request (the query) in some (formal) language. The
information request should be as good as possible a description of the
information need. The information request is then passed on to an automated
system, or a human intermediary, who will then try to fulfil the information
request using the information stored in the system. This is illustrated in the
information disclosure, or information retrieval paradigm, presented in
LABEL:Type.sq01irpd 1 which is taken from [BW92].

We now briefly discuss why the information retrieval paradigm for document
retrieval systems is also applicable for information systems. For a more
elaborate discussion on the relation between information systems and document
(information) retrieval systems in the context of the information retrieval
paradigm, refer to [Pro94a]. In the paradigm, the retrievable information is
modelled as a set ${\cal K}$ of information objects constituting the
information base (or population).

In a document retrieval system the information base will be a set of documents
([SM83]), while in the case of an information system the information base will
contain a set of facts conforming to a conceptual schema. Each information
object $o\in\mbox{${\cal K}$}$ is characterised by a set of descriptors
$\mbox{${\cal X}$}(o)$ that facilitates its disclosure. The characterisation
of information objects is carried out by a process referred to as indexing. In
an information system, the stored objects (the population or information base)
can always be identified by a set of (denotable) values, the identification of
the object. For example, an address may be identified as a city name, street
name, and house number. The characterisation of objects in an information
system is directly provided by the reference schemes of the object types.

The actual information disclosure is driven by a process referred to as
matching. In document retrieval applications this matching process tends to be
rather complex. The characterisation of documents is known to be a hard
problem ([Mar77], [Cra86]), although newly developed approaches turn out to be
quite successful ([Sal89]). In information systems the matching process is
less complex as the objects in the information base have a more clear
characterisation (the identification). In this case, the identification of the
objects (facts) is simply related to the query formulation $q$ by some
(formal) query language.

Figure 1: The information retrieval paradigm

The remaining problem is the query formulation process itself. An easy and
intuitive way to formulate queries is absolutely essential for an adequate
information disclosure. Quite often, the quest from users to fulfil their
information need can be aptly described by ([Bru93]):

> I don’t know what I’m looking for, but I’ll know when I find it.

In document retrieval systems this problem is attacked by using query by
navigation ([BW92], [Bru93]) and relevance feedback mechanisms ([Rij89]). The
query by navigation interaction mechanism between a searcher and the system is
well-known from the Information Retrieval field, and has proven to be useful.
It shall come as no surprise that these mechanisms also apply to the query
formulation problem for information systems. In [BPW93], [BPW94], [HPW94b],
[Pro94a] such applications of the query by navigation and relevance feedback
mechanisms have been described before. When combining the query by navigation
and manipulation mechanisms with the ideas behind visual interfaces for query
formulation as described in e.g. [ADD+92] and [Ros94] powerfull and intuitive
tools for computer supported query formulation become feasible. Such tools
will also heavily rely on the ideas of direct manipulation interfaces
([Sch83]) as used in present day computer interfaces.

One important step in the improvement of the information disclosure of
information systems, is the introduction of query languages on a conceptual
level. Examples of such conceptual query languages are RIDL ([Mee82]), LISA-D
([HPW93], [HPW94a]), and FORML ([HHO92]). By letting users formulate queries
on a conceptual level, users are safeguarded from having to know the exact
mapping to internal representations (e.g. a set of tables which conform to the
relational model) to be able to formulate queries in a non conceptual language
such as SQL. The next step is to introduce ways to support users in the
formulation of queries in such conceptual query languages (CQL).

In line with the above discussed information retrieval paradigm and the notion
of relevance feedback, a query formulation process (both for a document
retrieval system, and an information system) can be said to roughly consist of
the following four phases:

  1. 1.

The explorative phase. What information is there, and what does it mean?

  2. 2.

The constructive phase. Using the results of phase 1, the actual query is
formulated.

  3. 3.

The feedback phase. The result from the query formulated in phase 2 may not be
completely satisfactory. In this case, phases 1 and 2 need to be re-done and
the result refined.

  4. 4.

The presentation phase. In most cases, the result of a query needs to be
incorporated into a report or some other document. This means that the results
must be grouped or aggregated in some form.

Depending on the user’s knowledge of the system, the importance of the
respective phases may change. For instance, a user who has a good working
knowledge of the structure of the stored information may not require an
elaborate first phase and would like to proceed with the second phase as soon
as possible.

In this report, we discuss an additional mechanism to support automated
disclosure of information stored in information systems, the spider query
mechanism. As stated before, the related notions of query by navigation and
query by construction have already been discussed in [BPW93], [PW95],
[Pro94a]. The point to point query mechanism was already discussed in
[Pro94b].

The idea behind spider queries is to start out from one object type, and to
associate all information that is relevant to this object type. The essential
part of a spider query is selecting the object types in the direct suroundings
of the initial object type that are considered to be relevant. This style of
querying corresponds to a situation where users only know about the existance
of some object types in the conceptual schema about which they would like to
be informed.

The structure of this report is as follows. In LABEL:Type.SampleSession 2, we
discuss an example spider query session, and elaborate briefly on the
integration with the existing query by navigation, query by construction, and
point to point querie mechanisms. Section 3 deals with the representation of
conceptual schema as a graph. Building a spider query (essentailly also a
graph) is covered in LABEL:Type.SpiderQuery 4. Before concluding, section
LABEL:Type.SpiderPath 5 discusses the representation of a spider query as a
path expression. For the reader who is unfamiliar with the notation style used
in this report, it is advisable to first read [Pro94c].

##  2 An Example Spider Query Session

In this section we discuss a sample session involving a spider query, and also
discuss briefly the relationship to the existing query by navigation, query by
construction and point to point queries. The discussed example operates on a
conceptual schema for the administration of the election of American
presidents. The example schema itself is not shown; the structure of the
domain will become clear from the sample session. Note that the quality of the
verbalisations of the paths in the examples used in this section should be
improved, however, this is subject of further research. In LABEL:Type.sq02sqst
2 a possible screen is depicted for building queries using a point to point
query mechanism. No special window is needed for a spider query (see also
[Pro94b]).

Figure 2: Start of a spider query

We start out from an existing query in a query by construction window. Note
that this could also be single object type, e.g. politician. The spider query
mechanism adds one important aspect to the query by construction window, the
spider button:  . When a user presses this button, the system calculates the
spider query of the object type directly to the right of the button. This is
illustrated in LABEL:Type.sq02sqrs 3. The system allows for the removal of
parts of the resulting spider query that are not considered to be relevant by
the user. Suppose the user is not interested in administration is headed by
and election won by, then these paths can be deleted, which leads to the
screen depicted in LABEL:Type.sq02sqpr 4.

Figure 3: Result of a Spider Query

Figure 4: Pruning the Spider Query

It is now interesting to see that a query essentially is a double tree with a
shared root (politician in the example). Furthermore, the leaves on the tree
resulting from the spider query can be extended further if desired by
commencing new spider queries. Finally, since the result of a spider query is
constructed from path expressions as well, these expressions have the
associated that can be used to select alternative paths between the head and
tail object types. Furthermore, the paths can also be used as a starting point
of a query by navigation session. This latter posibility is illustrated in
LABEL:Type.sq02sqbn 5.

Figure 5: Switching to query by navigation

As stated before in [Pro94b], the query by construction window is basically a
syntax directed editor. In the left part of the window all possible constructs
from the query language are listed. In our examples we have used the
constructs defined in LISA-D. Once the FORML and LISA-D languages have been
merged, a more complete language for the query by construction part will
result.

##  3 A Conceptual Schema as a Graph

For the purpose of finding a path between object types in a conceptual schema,
the schema first needs to be translated to a graph. This translation is
exactly the same as provided in [Pro94b], but for reasons of completeness we
provide it again. We start out from a formalisation of ORM based on the one
used in ([HP95]). However, since only a very limited part of the formalisation
is needed, we do not cover the formalisation in full detail.

A conceptual schema is presumed to consist of a set of types ${\cal T\\!P}$.
Within this set of types two subsets can be distinguished: the relationship
types ${\cal R\\!L}$, and the object types ${\cal O\\!B}$. Furthermore, let
${\cal R\\!O}$ be the set of roles in the conceptual schema. The fabric of the
conceptual schema is then captured by two functions and two predicates. The
set of roles associated to a relationship type are provided by the partition:
$\mathop{\mbox{\normalsize$\mbox{\tenasf Roles}$}}\nolimits:\mbox{${\cal
R\\!L}$}\mathop{\mbox{\normalsize$\rightarrow$}}\nolimits\mathop{\mbox{\normalsize$\mbox{\Large$\wp$}$}}\nolimits(\mbox{${\cal
R\\!O}$})$. Using this partition, we can define the function
$\mathop{\mbox{\normalsize$\mbox{\tenasf Rel}$}}\nolimits$ which returns for
each role the relationship type in which it is involved:
$\mathop{\mbox{\normalsize$\mbox{\tenasf Rel}$}}\nolimits(r)=f\iff
r\in\mathop{\mbox{\normalsize$\mbox{\tenasf Roles}$}}\nolimits(f)$. Every role
has an object type at its base called the player of the role, which is
provided by the function: $\mathop{\mbox{\normalsize$\mbox{\tenasf
Player}$}}\nolimits:\mbox{${\cal
R\\!O}$}\mathop{\mbox{\normalsize$\rightarrow$}}\nolimits\mbox{${\cal
T\\!P}$}$. Subtyping and polymorphy of object types are captured by the
predicates $\mathop{\mbox{\normalsize$\mbox{\tenasf
SpecOf}$}}\nolimits\subseteq\mbox{${\cal O\\!B}$}\times\mbox{${\cal O\\!B}$}$
and $\mathop{\mbox{\normalsize$\mbox{\tenasf
HasMorph}$}}\nolimits\subseteq\mbox{${\cal O\\!B}$}\times\mbox{${\cal
O\\!B}$}$ respectively. For any ORM conceptual schema the following
(undirected) labelled graph $G=\left\langle N,E\right\rangle$ can then be
defined:

$\displaystyle N$ $\displaystyle\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits$ ${\cal T\\!P}$ (1) $\displaystyle E$
$\displaystyle\mathop{\mbox{\normalsize$\mathchar 13356\relax$}}\nolimits$
$\left\\{\begin{array}[]{c}\left\langle\mbox{\normalsize$\\{\mathop{\mbox{\normalsize$\mbox{\tenasf
Player}$}}\nolimits(r),\mathop{\mbox{\normalsize$\mbox{\tenasf
Rel}$}}\nolimits(r)\\}$},r\right\rangle\>\left|\>\begin{array}[]{c}r\in\mbox{${\cal
R\\!O}$}\end{array}\right.\end{array}\right\\}$ (4)
$\displaystyle\mathop{\mbox{\normalsize$\bigcup$}}\nolimits\limits$
$\left\\{\begin{array}[]{c}\left\langle\mbox{\normalsize$\\{x,y\\}$},\mathop{\mbox{\normalsize$\mbox{\tenasf
SpecOf}$}}\nolimits\right\rangle\>\left|\>\begin{array}[]{c}x\mathop{\mbox{\normalsize$\mbox{\tenasf
SpecOf}$}}\nolimits y\end{array}\right.\end{array}\right\\}$ (7)
$\displaystyle\mathop{\mbox{\normalsize$\bigcup$}}\nolimits\limits$
$\left\\{\begin{array}[]{c}\left\langle\mbox{\normalsize$\\{x,y\\}$},\mathop{\mbox{\normalsize$\mbox{\tenasf
HasMorph}$}}\nolimits\right\rangle\>\left|\>\begin{array}[]{c}x\mathop{\mbox{\normalsize$\mbox{\tenasf
HasMorph}$}}\nolimits y\end{array}\right.\end{array}\right\\}$ (10)

The edges in the resulting graph have the format
$\left\langle\mbox{\normalsize$\\{x,y\\}$},l\right\rangle$, where $x$ and $y$
are the source/destination (no order) of the edge, and $l$ is the label of the
edge. The labels on the edges either result from the roles in the relationship
types (2), or they result from specialisation or polymorphism (3,4). In the
remainder, the graph $G$ will be used as an implicit parameter for all
introduced functions and operations. As a convention, the nodes of graph $G$
are accessed by $G.N$, and the edges by $G.E$.

Figure 6: Example Conceptual Schema

As an example, consider the conceptual schema depicted in LABEL:Type.sq03excs
6. For this schema we have:

$\begin{array}[]{ll}\mbox{${\cal
T\\!P}$}=\mbox{\normalsize$\\{A,B,C,D,f,g\\}$}&\mathop{\mbox{\normalsize$\mbox{\tenasf
Roles}$}}\nolimits(f)=\mbox{\normalsize$\\{r,s\\}$},\mathop{\mbox{\normalsize$\mbox{\tenasf
Roles}$}}\nolimits(g)=\mbox{\normalsize$\\{t,u\\}$}\\\\[2.84544pt]
\mbox{${\cal
R\\!L}$}=\mbox{\normalsize$\\{f,g\\}$}&\mathop{\mbox{\normalsize$\mbox{\tenasf
Player}$}}\nolimits(r)=A,\mathop{\mbox{\normalsize$\mbox{\tenasf
Player}$}}\nolimits(s)=B,\mathop{\mbox{\normalsize$\mbox{\tenasf
Player}$}}\nolimits(t)=C,\mathop{\mbox{\normalsize$\mbox{\tenasf
Player}$}}\nolimits(u)=A\\\\[2.84544pt] \mbox{${\cal
O\\!B}$}=\mbox{\normalsize$\\{A,B,C,D\\}$}&A\mathop{\mbox{\normalsize$\mbox{\tenasf
HasMorph}$}}\nolimits C,A\mathop{\mbox{\normalsize$\mbox{\tenasf
HasMorph}$}}\nolimits g\\\\[2.84544pt] \mbox{${\cal
R\\!O}$}=\mbox{\normalsize$\\{r,s,t,u\\}$}&D\mathop{\mbox{\normalsize$\mbox{\tenasf
SpecOf}$}}\nolimits B\end{array}$

From this schema the graph as depicted in LABEL:Type.sq03exgr 7 can be
derived.

Figure 7: Example Graph

Note that for spider queries, it might be usefull to limit the edges resulting
from roles to those roles which are not used in the reference schemas of other
object types. We cannot yet decide on this until we have finallised the path
expression language, but it is simply a matter of filtering the proper edges.

##  4 Building a Spider Query

The construction of a spider query corresponds to the construction of a graph.
The nodes and edges in this graph are based on the nodes (object types) and
edges from the original conceptual schema graph. A spider query graph is a
labelled tree (connected directed acyclic graph). It is not just a subgraph of
the conceptual schema graph, since one object type can be visited more than
once on different branches of the graph (legs of the spider query graph). Let
ℕ be the set of all nodes that can occur in a spider query, and let
$\mbox{\tenmsy L}\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits\mbox{${\cal
R\\!O}$}\mathop{\mbox{\normalsize$\cup$}}\nolimits\mbox{\normalsize$\\{\mathop{\mbox{\normalsize$\mbox{\tenasf
SpecOf}$}}\nolimits,\mathop{\mbox{\normalsize$\mbox{\tenasf
HasMorph}$}}\nolimits\\}$}$ be the set of labels that can occur in a spider
query graph. The spider query graph itself is now constructed by the function:

$\mathop{\mbox{\normalsize$\mbox{\tenasf
SpiderQuery}$}}\nolimits:\mbox{\tenmsy
N}~{}\mathop{\mbox{\normalsize$\rightarrow$}}\nolimits~{}(\mbox{\tenmsy
N}\mathop{\mbox{\normalsize$\mathchar 13338\relax$}}\nolimits\mbox{${\cal
T\\!P}$})\times\mathop{\mbox{\normalsize$\mbox{\Large$\wp$}$}}\nolimits(\mbox{\tenmsy
N}\times\mbox{\tenmsy N}\times\mbox{\tenmsy L})$

The result of a spider query $\mathop{\mbox{\normalsize$\mbox{\tenasf
SpiderQuery}$}}\nolimits(x)$ is a tuple $\left\langle O,S\right\rangle$, where
$O:\mbox{\tenmsy N}\mathop{\mbox{\normalsize$\mathchar
13338\relax$}}\nolimits\mbox{${\cal T\\!P}$}$ provides the relation between
the spider query graph and the conceptual schema, and the spider query graph
itself is defined by the (directed!) edges in
$S\subseteq\mathop{\mbox{\normalsize$\mbox{\Large$\wp$}$}}\nolimits(\mbox{\tenmsy
N}\times\mbox{\tenmsy N}\times\mbox{\tenmsy L})$.

The construction process itself is driven by a recursive function $\sigma$,
which is activated as follows:

$\mathop{\mbox{\normalsize$\mbox{\tenasf
SpiderQuery}$}}\nolimits(x)~{}\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits~{}\sigma(\mbox{\normalsize$\\{\left\langle\mbox{\tenasf
NewNode}(x),x\right\rangle\\}$},\mathchar
1343\relax,\mbox{\normalsize$\\{x\\}$})$

where NewNode is a function returning a new node each time it is called. The
$\sigma$ function is the actual engine of the construction process. This
function tries to extend the spider query graph in a number of steps. In each
step the possible extensions of the existing graph at that moment are
calculated by the $\varepsilon$ function. The $\varepsilon$ function takes as
parameters the current spider query graph: $O$, $S$, and the nodes which are
allowed to be extended: $T$. It returns a number of tuples of the form
$\left\langle n,t,l\right\rangle$, where $n$ is an extendable node in the
existing spider query graph, and $t$ is a type in the conceptual schema that
is reachable in (the conceptual schema graph) from object type $O(n)$. A
restriction on the returned tuples is that no cycles may be formed, i.e. no
revisiting of object types on one path in the spider query graph. The formal
definition is given by:

$\varepsilon(O,S,T)~{}\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits~{}\mbox{\normalsize$\left\\{\begin{array}[]{c}\left\langle
n,t,l\right\rangle\>\left|\>\begin{array}[]{c}\left\langle\mbox{\normalsize$\\{O(n),t\\}$},l\right\rangle\in
G^{\prime}.E\land n\in T\land t\not\in\mathop{\mbox{\normalsize$\mbox{\tenasf
Top}$}}\nolimits(n)\end{array}\right.\end{array}\right\\}$}$

where $\mathop{\mbox{\normalsize$\mbox{\tenasf
Top}$}}\nolimits(n)\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits\mathop{\mbox{\normalsize$\bigcup$}}\nolimits\limits_{\scriptstyle
m:\left\langle m,n,l\right\rangle\in
S}(\mathop{\mbox{\normalsize$\mbox{\tenasf
Top}$}}\nolimits(m)\mathop{\mbox{\normalsize$\cup$}}\nolimits\mbox{\normalsize$\\{m\\}$})$
is the set of types on the path in the spider query graph leading from the
root to $n$.

The actual driver function $\sigma$ evolves around three parameters. These
parameters are updated in every step of the function. In the definition we use
$O$, $S$ and $T$ as variable names, where $T$ contains the nodes in the spider
query graph that may be used for further extensions, and $O$ and $S$ represent
the spider query graph so-far. The $\sigma$ function is identified by:

$\sigma(O,S,T)~{}\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits~{}\left\\{\begin{array}[]{ll}\sigma(O^{\prime},S^{\prime},T^{\prime})&\mbox{\normalsize
if~{}}\varepsilon(O,S,T)\neq\mathchar 1343\relax\\\ \left\langle
O,S\right\rangle&\mbox{\normalsize otherwise}\end{array}\right.$

where:

$\displaystyle O^{\prime}$ $\displaystyle=$ $\displaystyle
O\mathop{\mbox{\normalsize$\cup$}}\nolimits\mbox{\normalsize$\left\\{\begin{array}[]{c}\left\langle\mbox{\tenasf
NewNode}(t),t\right\rangle\>\left|\>\begin{array}[]{c}t\in\pi_{2}~{}\varepsilon(O,S,T)\end{array}\right.\end{array}\right\\}$}$
(13) $\displaystyle S^{\prime}$ $\displaystyle=$ $\displaystyle
S\mathop{\mbox{\normalsize$\cup$}}\nolimits\mbox{\normalsize$\left\\{\begin{array}[]{c}\left\langle
n,m,l\right\rangle\>\left|\>\begin{array}[]{c}\left\langle
n,t,l\right\rangle\in\varepsilon(O,S,T)\land
O^{\prime}(m)=t\end{array}\right.\end{array}\right\\}$}$ (16) $\displaystyle
T^{\prime}$ $\displaystyle=$
$\left\\{\begin{array}[]{c}m\>\left|\>\begin{array}[]{c}\left\langle
n,m,l\right\rangle\in\varepsilon(O,S,T)\land\mathop{\mbox{\normalsize$\mbox{\tenasf
CWeight}$}}\nolimits(O^{\prime}(m))\leq\mathop{\mbox{\normalsize$\mbox{\tenasf
CWeight}$}}\nolimits(O^{\prime}(n))\end{array}\right.\end{array}\right\\}$
(19)

In 4, the newly found object types in $\varepsilon(O,S,T)$ are assigned a new
node so that they can be added to the existing spider query graph. The set of
edges of the spider query graph is updated in 5. The new set of nodes that
will be considered for further extensions in the next step of $\sigma$ are
determined by 6. In this definition, the conceptual weight function
$\mathop{\mbox{\normalsize$\mbox{\tenasf CWeight}$}}\nolimits$ is the same
function as used in [Pro94b], and should provide the conceptual importance of
each object type. This importance could for instance be based on the
abstraction level at which the object type occurs ([CH94]). The rationale
behind the use of the $\mathop{\mbox{\normalsize$\mbox{\tenasf
CWeight}$}}\nolimits$ function is that as soon as the conceptual importance
increases, any new neigbouring object type from the last added object type
(the one with the increased $\mathop{\mbox{\normalsize$\mbox{\tenasf
CWeight}$}}\nolimits$) is not relevant for the root of the current spider
query graph, i.e. we have left the relevance scope of the current root. Note,
however, the neighbours of the last added object type could quite well be
relevant for a spider query starting out from this latter object type. These
nodes will be added if the user presses the spider query button that will be
associated to this node.

Figure 8: Example graph for a spider query

As an example of the operation of the $\mathop{\mbox{\normalsize$\mbox{\tenasf
SpiderQuery}$}}\nolimits$ function, consider the graph depicted in
LABEL:Type.sq04exgr 8. Each edge in this graph is labelled, and each node has
associated its name (object type), and the conceptual weight. In
LABEL:Type.sq04spq1 9 the tree is depicted with which the $\sigma$ function is
started. The double circle around node B is used to indicate that node B is in
the set of extendible nodes $T$.

Figure 9: Initial spider query graph

Figure 10 depicts the spider query graph after one incremental step of
$\sigma$. All neighbours of B are added to the graph, and since they do not
have a higher conceptual weight than B, they can be used for further
extensions.

Figure 10: First step in building the spider query graph

The next step of the algorithm is illustrated in LABEL:Type.sq04spq3 11. Node
A has two neigbours: B and F. However, since adding B to the spider query
graph would lead to a repetition of an existing node on the path to the root
of the spider query graph, B is not added. Similarly, B is not added as a
neighbour of C and F. Nodes D and E are not marked as points of further
extensions since they both have a higher conceptual weight then node C. As a
resuolt, node H is not part of node B’s scope of rellevance. However, node B
would be part of a spider query starting from H. Note that nodes D and E will
both have associated a spider query button when the result is presented to the
user, so a user can always explicitly decide to further ‘climb the conceptual
importance mountain’.

Figure 11: Second step in building the spider query graph

The result of the last step of $\sigma$ is shown in LABEL:Type.sq04spq4 12.
The second node A, and node G, do not lead to further extensions. All
neighbours of these two nodes are already present on the paths to the root of
the graph. Only the leftmost node F leads to a further extension with a G.
After this extension no further extensions are possible.

Figure 12: Last step in building the spider query graph

Finally, it is good to realise that the $\sigma$ function always terminates:

Lemma 4.1

The $\sigma$ function always terminates.

Proof:

This corresponds to saying that the resulting graph is finite.

The number of object types in an ORM schema is (presumed to be) finite, and
the paths of the spider query will not contain cycles (follows from the
definition of $\varepsilon$).

As a result, each node only has a finite number of outgoing arcs, and each
path from the root to a leaf is finite. Hence the resulting graph is finite.
$\Box$

##  5 The Resulting Path Expressions

In this section we discuss how to transfer a spider query graph into a path
expression. We use the spider query graph $O$, $S$ as an implicit parameter
for all definitions in this section.

Given a node $x$ in the spider query graph, then the following path expression
can be associated to this node:

$\mbox{\tenasf NodeExpr}(x)~{}\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits~{}\left\\{\begin{array}[]{ll}[a_{1}:\mbox{\tenasf
PathSeg}(y_{1},l_{1},x),\ldots,a_{n}:\mbox{\tenasf
PathSeg}(y_{n},l_{n},x);O(x)]&\mbox{\normalsize if~{}}S\neq\mathchar
1343\relax\\\\[2.84544pt] O(x)&\mbox{\normalsize otherwise}\end{array}\right.$

where $S=\mbox{\normalsize$\\{\left\langle
y_{1},l_{1}\right\rangle,\ldots,\left\langle y_{n},l_{n}\right\rangle\\}$}$ is
a set such that $S=\mbox{\normalsize$\left\\{\begin{array}[]{c}\left\langle
y,l\right\rangle\>\left|\>\begin{array}[]{c}\left\langle x,y,l\right\rangle\in
S\end{array}\right.\end{array}\right\\}$}$, and $a_{1},\ldots,a_{n}$ is a set
of fresh attribute names. A good choice for these latter names are the names
of the object types where the PathSegs end (suffixed with a number to make the
name unique if needed). The $\mathop{\mbox{\normalsize$\circ$}}\nolimits$
operation is the concatenation operation for path expressions, and the
$[X_{1},\ldots,X_{n}]$ construct is the path confluence operation. It allows
us to combine a variety of path expressions. For more details about the path
expression operators, refer to [HPW93] and the forthcomming Asymetrix report
on path expressions. One single edge from the spider query graph is converted
to a path expression as follows:

$\mbox{\tenasf PathSeg}(y,l,x)~{}\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits~{}\mbox{\tenasf NodeExpr}(y)~{}\mbox{\tenasf
Connector}(l,x)~{}O(x)$

where

$\mbox{\tenasf Connector}(l,x)~{}\mathop{\mbox{\normalsize$\mathchar
13356\relax$}}\nolimits~{}\left\\{\begin{array}[]{ll}\mathop{\mbox{\normalsize$\circ$}}\nolimits&\mbox{\normalsize
if~{}}l\in\mbox{\normalsize$\\{\mathop{\mbox{\normalsize$\mbox{\tenasf
HasMorph}$}}\nolimits,\mathop{\mbox{\normalsize$\mbox{\tenasf
SpecOf}$}}\nolimits\\}$}\\\\[2.84544pt]
\mathop{\mbox{\normalsize$\circ$}}\nolimits
l\mathop{\mbox{\normalsize$\circ$}}\nolimits&\mbox{\normalsize
if~{}}x\in\mbox{${\cal R\\!L}$}\land
l\in\mathop{\mbox{\normalsize$\mbox{\tenasf
Roles}$}}\nolimits(x)\\\\[2.84544pt]
\mathop{\mbox{\normalsize$\circ$}}\nolimits{l}^{\leftarrow}\mathop{\mbox{\normalsize$\circ$}}\nolimits&\mbox{\normalsize
otherwise}\end{array}\right.$

The linear path expressions are for internal use only. They can be mapped to
proper SQL queries on the one hand, and verbalised as semi-natural language
sentences using the verbalisation information as provided in the conceptual
schema on the other hand. As stated before, the verbalisation of path
expressions is subject of further research.

Finally, the (unique) root of a spider query graph is determined as follows:

$\mbox{\tenasf
IsRoot}(r)\iff\mathop{\mbox{\normalsize$O\\!\\!\downarrow\\!\\!r$}}\nolimits\land\lnot\exists_{\scriptstyle
x,l}\left[\left\langle x,r,l\right\rangle\in S\right]$

If $r$ is the (unique) root of a spider query graph, then $\mbox{\tenasf
NodeExpr}(r)$ results in the complete path expression for this spider query
graph.

##  6 Conclusions

In this article we introduced a novel way to computer supported query
formulation called spider queries. We provided a sample session with a
provisional tool supporting spider queries, and briefly discussed the
relationship to query by navigation, query by construction, and point to point
queries. Together with these existing mechanisms a powerfull query formulation
tool can now indeed be build.

As a next step, the path expressions should be further developed to suit our
needs. Furthermore, elegant verbalisations of the path expressions should be
catered for.

asy

## References

  * [ADD+92] A. Auddino, Y. Dennebouy, Y. Dupont, E. Fontana, S. Spaccapietra, and Z. Tari.  SUPER – Visual Interaction with an Object–based ER Model.  In G. Pernul and A.M. Tjoa, editors, 11th International Conference on the Entity–Relationship Approach, volume 340-356 of Lecture Notes in Computer Science, pages 423–439, Berlin, Germany, EU, 1992\. Springer.
  * [BPW93] C.A.J. Burgers, H.A. (Erik) Proper, and Th.P. van der Weide.  Organising an Information System as Stratified Hypermedia.  In H.A. Wijshoff, editor, Proceedings of the Computing Science in the Netherlands Conference, pages 109–120, November 1993.
  * [BPW94] C.A.J. Burgers, H.A. (Erik) Proper, and Th.P. van der Weide.  An Information System organized as Stratified Hypermedia.  In N. Prakash, editor, CISMOD94, International Conference on Information Systems and Management of Data, pages 159–183, October 1994.
  * [Bru93] P.D. Bruza.  Stratified Information Disclosure: A Synthesis between Information Retrieval and Hypermedia.  PhD thesis, University of Nijmegen, Nijmegen, The Netherlands, EU, 1993\.
  * [BW92] P.D. Bruza and Th.P. van der Weide.  Stratified Hypermedia Structures for Information Disclosure.  The Computer Journal, 35(3):208–220, 1992.
  * [CH94] L.J. Campbell and T.A. Halpin.  Abstraction Techniques for Conceptual Schemas.  In R. Sacks–Davis, editor, Proceedings of the 5th Australasian Database Conference, volume 16, pages 374–388, Christchurch, New Zealand, January 1994. Global Publications Services.
  * [Cra86] T.C. Craven.  String Indexing.  Academic Press, New York, New York, USA, 1986.
  * [HHO92] T.A. Halpin, J. Harding, and C-H. Oh.  Automated Support for Subtyping.  In B. Theodoulidis and A.G. Sutcliffe, editors, Proceedings of the Third Workshop on the Next Generation of CASE Tools, pages 99–113, May 1992.
  * [HP95] T.A. Halpin and H.A. (Erik) Proper.  Subtyping and Polymorphism in Object–Role Modelling.  Data & Knowledge Engineering, 15:251–281, 1995.
  * [HPW93] A.H.M. ter Hofstede, H.A. (Erik) Proper, and Th.P. van der Weide.  Formal definition of a conceptual language for the description and manipulation of information models.  Information Systems, 18(7):489–523, October 1993.
  * [HPW94a] A.H.M. ter Hofstede, H.A. (Erik) Proper, and Th.P. van der Weide.  A Conceptual Language for the Description and Manipulation of Complex Information Models.  In G. Gupta, editor, Seventeenth Annual Computer Science Conference, volume 16 of Australian Computer Science Communications, pages 157–167, Christchurch, New Zealand, January 1994. University of Canterbury. ISBN 047302313
  * [HPW94b] A.H.M. ter Hofstede, H.A. (Erik) Proper, and Th.P. van der Weide.  Supporting Information Disclosure in an Evolving Environment.  In D. Karagiannis, editor, Proceedings of the 5th International Conference DEXA‘94 on Database and Expert Systems Applications, Athens, Greece, EU, volume 856 of Lecture Notes in Computer Science, pages 433–444, Berlin, Germany, EU, September 1994. Springer. ISBN 3540584358
  * [Mar77] M.E. Maron.  On Indexing, Retrieval and the Meaning of About.  Journal of the American Society for Information Science, 28(1):38–43, 1977.
  * [Mee82] R. Meersman.  The RIDL Conceptual Language.  Technical report, International Centre for Information Analysis Services, Control Data Belgium, Inc., Brussels, Belgium, EU, 1982.
  * [Pro94a] H.A. (Erik) Proper.  A Theory for Conceptual Modelling of Evolving Application Domains.  PhD thesis, University of Nijmegen, Nijmegen, The Netherlands, EU, 1994\. ISBN 909006849X
  * [Pro94b] H.A. (Erik) Proper.  Interactive Query Formulation using Point to Point Queries.  Technical report, Asymetrix Research Laboratory, University of Queensland, Brisbane, Queensland, Australia, 1994.
  * [Pro94c] H.A. (Erik) Proper.  Introduction to Formal Notations.  Technical report, Asymetrix Research Laboratory, University of Queensland, Brisbane, Queensland, Australia, 1994.
  * [PW95] H.A. (Erik) Proper and Th.P. van der Weide.  Information Disclosure in Evolving Information Systems: Taking a shot at a moving target.  Data & Knowledge Engineering, 15:135–168, 1995.
  * [Rij89] C.J. van Rijsbergen.  Towards an information logic.  In Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, Cambridge, Massachusetts, USA, pages 77–86, New York, New York, USA, June 1989. ACM.
  * [Ros94] P. Rosengren.  Using Visual ER Query Systems in Real World Applications.  In G.M. Wijers, S. Brinkkemper, and T. Wasserman, editors, Proceedings of the Sixth International Conference CAiSE‘94 on Advanced Information Systems Engineering, Utrecht, The Netherlands, EU, volume 811 of Lecture Notes in Computer Science, pages 394–405, Berlin, Germany, EU, June 1994. Springer.
  * [Sal89] G.E Salton.  Automatic Text Processing–The Transformation, Analysis, and Retrieval of Information by Computer.  Addison Wesley, Reading, Massachusetts, USA, 1989.
  * [Sch83] B. Schneiderman.  Direct Manipulation: A Step Beyond Programming Languages.  IEEE Computer, 16(8):57–69, 1983.
  * [SM83] G.E Salton and M.J. McGill.  Introduction to Modern Information Retrieval.  McGraw–Hill, New York, New York, USA, 1983.