Acknowledgements

1 Introduction

The query language of AMOS II, called AMOSQL, AMOSQL is similar to the OO parts of SQL:99 and based on the functional data model DAPLEX [Shi81] and OSQL [Lyn91]. The main new features of AMOSQL compared to OSQL are generalized foreign functions [LR92], optimization of overloaded functions with late binding, [FR95], functional active rules [Sko96][SR96] (being ported to AMOS II), and multi-database facilities [JR99a][JR99b]. AMOSQL furthermore has aggregation operators, nested subqueries, disjunctive queries, quantifiers, and is relationally complete. 

AMOS II is a distributed mediator system [Wie92] allowing several AMOS II mediator servers to communicate over the Internet. Applications can access data from several distributed data sources through a collection of distributed AMOS II servers. Each mediator server appears as a virtual OO database layer having OO data abstractions and an OO query language. OO views provide transparent access to data sources from clients and other mediator servers. Conflicts and overlaps between similar real-world entities being modeled differently in different data sources are reconciled through the mediation primitives [JR99a][JR99b] of AMOSQL. The mediation services allow transparent access to similar object structures represented differently in different data sources. AMOS II mediators are composable since a mediator server can regard other mediator servers as data sources. Different interconnecting topologies can be used to connect mediator servers depending on the integration requirements of the environment. 

In order to access data from external data sources AMOS II mediators contain one or several wrappers which process data from different kinds of external data sources, e.g. ODBC based access to relational databases [FR97][Bra98] or access to XML files. A wrapper is a program module in AMOS II having specialized facilities for query processing and translation of data from a particular class of external data sources. It contains both interfaces to external data sources and knowledge of how to efficiently translate and process queries involving accesses to a class of external data sources. In particular external AMOS II servers known to a mediator are also regarded as external data sources and there is a special wrapper for accessing other AMOS II servers. However, among the AMOS II servers special query optimization methods are used that take into account the distribution, capabilities, costs, etc. of the different servers [JR00][Jos99]. 

The declarative multi-database query language AMOSQL requires queries to be optimized before execution. The query compiler translates AMOSQL statements into object calculus and algebra expressions in an internal simple logic based language called ObjectLog [LR92], which is an OO dialect of Datalog [Ull88]. As part of the translation into object algebra programs, many optimizations are applied on AMOSQL expressions relying on its OO and multi-database properties. During the optimization steps, the object calculus expressions are re-written into equivalent but more efficient expressions. For distributed multi-database queries a multi-database query decomposer [JR00] distributes each object calculus query into local queries to be executed in the different distributed AMOS II servers and data sources. For better performance, the decomposed query plans are rebalanced over the distributed Amos II servers[JKR99]. A cost-based optimizer on each site translates the local queries into procedural execution plans in an OO algebra, based on statistical estimates of the cost to execute each generated query execution plan expressed in the OO algebra. A query interpreter finally interprets the optimized algebra to produce the (partial) result of a query. 

The query optimizer is extensible through a generalized foreign function mechanism, multi-directional foreign functions [LR92]. It gives transparent access from AMOSQL to special purpose data structures such as internal AMOS II meta-data representations or user defined storage structures. The mechanism allows the programmer to implement query language operators in an external language (Java, C or Lisp) and to associate costs and selectivity estimates with different user-define access paths. The architecture relies on extensible optimization of such foreign function calls [LR92]. They are important both for accessing external query processors [Bra98] and for integrating customized data representations from data sources. 

To achieve good performance we have carefully optimized the representation of critical system data structures, e.g. the storage manager, object representation, type information, and the representation of function definitions. We use tailored main memory data structure representations of system objects, rather than, e.g., storing them in relational tables represented as B-trees [GS92]. For example, our object identifiers are represented as variable length records with pointers to data structures representing type-information, function definitions, dependent objects, etc. It is crucial that system information is represented efficiently, since it is extensively looked up during both compilation and interpretation of AMOSQL functions. The storage manager relies on an incremental garbage collector for removing unused data. 

AMOS II runs under Windows NT. The system uses around 350KB of code and 1500KB of meta data. The system has client-server and inter-database communication primitives whereby AMOS II servers can communicate over TCP/IP. 

A graphical browser for AMOS II, Goovi [CR01], is also available. It is implemented in Java and has facilities for multi-database browsing and integration. 

The predecessor of AMOS II, Amos [FRS93], was built on top of WS-Iris [LR92], the workstation version of the Iris system[Fis89], running on Unix platforms. AMOS II has a completely new kernel developed for Windows NT/95/98 that is now also ported to Unix platforms. AMOS II provides OO multi-database queries and reconciliation of heterogeneous data not present in Amos. Furthermore, AMOS II is designed for multi-layered distribution of mediator servers where distributed query optimization allows queries to be passed through many layers of mediators without any performance degradation.

The rest of this document gives an overview of the facilities of the AMOS II, including its OO data modeling primitives, its OO query language constructs, and its distributed multi-database facilities. The document AMOS II User's Manual describes the details of how to run  AMOS II, the AMOSQL language, etc.

2 The AMOS II Data Model

2.1 Objects

The literal objects are self-described system maintained objects which do not have explicit OIDs. Examples of literal objects are numbers and strings. Literal objects can also be collections, representing collections of other objects. The system-supported collections are vectors (1-dimensional arrays of objects) and bags (unordered sets with duplicates). 

Objects persist in the database until they are no longer referenced from any other object or from external systems. The removal of unreferenced objects is done through an automatic garbage collector. 

Surrogate objects are created by the create stament, e.g.: 

   create person instances :a;

2.2 Types

Regular user-defined types are created by the create type statement, e.g. 

   create type person;
   create type student under person;
   create type teacher under person;
   create type TA under student, teacher;

Every object has an associated type set which is the set of those types that the object is an instance of. Every object also has one most specific type which is the type specified when the object is created. For example, objects of type TA have the most specific type named TA. The full type set includes the most specific type and all types above the type in the type hierarchy. For example, objects of type TA have the type set {TA, teacher, student, person, userobject, object}. Notice that user-defined objects always have the meta-type userobject in their type set and that the extent of type userobject contains all user-defined objects in the database. 

The type set of an object can dynamically change during the lifetime of the object through AMOSQL statements that change the most specific type of an object. The reason for such facilities is because the role of an object may change during the lifetime of the database. For example, a TA might become a student for a while and then a teacher. 

All objects in the database are typed, including meta-objects such as those representing the types themselves. The meta-objects representing types are instances of the meta-type named type. In the example the extent of the type named type is the meta-objects representing the types named TA, teacher, student, and person. 

The following picture shows parts of the system type hierarchy: 
 
 

The type number is a supertype covering both integer and real numbers. 

A collection are literals holding collections of other values. 

Functions definitions are instances of the meta-type function. 

The meta-database type datasource represents decriptions of other AMOS II databases and datasources known to this database. This will be explained in Mediation Primitives. 

2.3 Functions

A function consists of two parts, the signature and the implementation: 

The signature defines the types, and optional names, of the argument(s) and the result of a function. For example, the signature of the function modeling the attribute name of type person could have the signature 

   name(person p)->charstring nm

    plus(number,number)->number

The implementation of a function is normally non-procedural, i.e. a function only computes values and does not have any side effects. The exception is database procedures which are special functions having side effects. 

AMOS II functions are, furthermore, often multi-directional meaning that the system is able to inversely compute one or several argument values if (some part of) the expected result value is known[LR92]. Inverses of multi-directional functions can be used in database queries and are important for specifying general queries with function calls over the database. For example, the following query, which finds the age of the person named 'Tore', uses the inverse of function name: 

   select age(p) from person p where name(p)='Tore';

• Stored functions represent properties of objects (attributes) stored in the database. Stored functions correspond to attributes in OO databases and tables in relational databases.
• Derived functions are functions defined in terms of OO queries over other AMOSQL functions. Derived functions cannot have side effects and the query optimizer is applied when they are defined. Derived functions correspond to side-effect free methods in OO models and views in relational databases. AMOSQL has an SQL-like select statement for defining derived functions. It can also be used for ad hoc queries. 
• Foreign functions are implemented through an external programming language (Java, Lisp or C). Multi-directional foreign functions correspond to methods in OO databases and provide access to external storage structures similar to data 'blades', 'cartridges', or 'extenders' in object-relational databases. To help the query processor, a multidirectional foreign function can have several associated access path implementations with cost and selectivity functions. 
• Proxy functions represent functions in other databases. They are further explained in Mediation Primitives.
• Database procedures are functions defined using a procedural sublanguage of AMOSQL. They correspond to methods with side effects in OO models.

The extent of a function is a mapping between its arguments and its results. For example, the extent of the function defined as 

   create function name(person p)-> charstring as stored;

   select name(p) from person p;
   select name(:v);

   select x+1 from number x;

3 Database manipulation 

3.1 Schema manipulation

   create type Person;
   create type Teacher under Person;
   create type Student under Person;
   create type TA under Teacher, Student;
   create type Course;

   create function name(Person) -> Charstring as stored;
   create function birthyear(Person) -> Integer as stored;
   create function hobbies(Person) -> bag of Charstring as stored;
   create function name(Course) -> Charstring as stored;
   create function teaches(Teacher) -> bag of Course as stored;
   create function enrolled(Student) -> bag of Course as stored;
   create function instructors(Course c) -> Teacher t as
        select t
        where teaches(t) = c; /* Inverse of teaches */

The types and their attributes can be defined together using the properties clause. For example, the above definition of types Person and Teacher with their attribute functions can also be defined by: 

  create type Person properties
        (name Charstring,
         birthyear Integer,
         hobbies bag of Charstring);
   create type Teacher under Person properties
         (teaches bag of Course);

   create function phone(Person) -> Charstring as stored; 

The following figure illustrates an AMOS II schema through a Daplex diagram [Shi81], where ovals are types (entities), thick arrows indicate inheritance relationships, and thin arrows indicate functions (directed relationships). 
 
 

Types are deleted with the delete type statement, e.g.: 

    delete type Person;

Functions are deleted with the delete function statement, e.g.: 

   delete function teaches;

3.2 Database updates

   create person(name, birhtyear, hobbies) instances
     :bill ("Bill", 1962, "Sailing"), :bob ("Bob", 1970, "Tennis");

The attribute assignments can be done separately too. The set command updates an instance of the extent of a function. For example, the create statement above is equivalent to: 

   create person instances :bill, :bob;
   set name(:bill) = "Bill";
   set birthyear(:bill) = 1962;
   set hobbies(:bill) = "Sailing";
   set name(:bob) = "Bob";
   set birthyear(:bob) = 1970;
   set hobbies(:bob) = "Tennis";

   add hobbies(:bill) = "Stamps";

 
   hobbies(:bill);

   "Sailing"
   "Stamps"

   remove hobbies(:bill) = "Sailing";

   set hobbies(:bill) = nil;

  set income(p) = pi
  from Person p, Integer pi
  where pi = sumagg(income(parents(p)))
    and income(p) > pi;

Instances of objects are deleted with the delete statement, for example: 

   delete :bill;
   delete :bob;

3.3 Queries 

3.3.1 Function calls

   hobbies(:tore);

Function calls can also be nested which can be seen as traversals of the function diagram, for example: 

   name(teaches(:math));

Another example of Daplex semantics is: 

   sqrt(sqrt(16.0));

For nested function calls the query optimizer will be applied to produce an execution plan for the call, which is then immediately executed. Therefore nested function calls are significantly slower than unnested ones, and, if the calls are to be executed more than once, the user is recommended to avoid nested function calls by defining suitable derived functions. In the example above, define: 

   create function teacher_name(Course p) -> Charstring
          as select name(teaches(p)); /* Optimizer invoked here
                                        and execution plan saved in db */

   teacher_name(:math); /* Optimizer NOT invoked here */

3.3.2 The select statement

   select result
   from   type extents
   where  condition

   select name(p), birthyear(p)
   from   Person p
   where  birthyear(p) > 1970;

In general the semantics of an AMOSQL query is as follows: 

• Form the cartesian product of the type extents. 
• Restrict the cartesian product by the condition. 
• For each possible variable binding to tuple elements in the restricted cartesian product, evaluate the result expressions to form a result tuple. 
• Result tuples containing NIL are not included in the result set; queries are null intolerant. 

   select nm, by
   from Person P, Charstring nm, Integer by
   where by = birthyear(p) and
         nm = name(p) and
         by > 1970;

3.3.3 Defining derived functions

   create type person;
   create type student under person;
   create function income(Person) -> Number as stored; 
   create function taxes(Person) -> Number as stored; 
   create function parents(Person) -> bag of Person as stored; 
   create function netincome(Person p) -> Number as 
        select income(p)-taxes(p);
   create function sparents(Person c) -> Student as 
        select parents(c); /* Parent if parent is student; 
                              bag of implicit for derived functions */ 
   create function grandsparentsnetincomes(Person c) -> Number as 
        select netincome(sparents(parents(c)));

The function grandsparentsnetincomes illustrates the power of traversing the function diagram through the Daplex semantics, where each arc traversal become a function application. The function computes the net incomes of the studying grandparents of a person. Notice that derived functions, such as grandsparentnetincomes implicitly return bags (multisets) of values and therefore always have the result implicitly declared as bag of. In this case there will be more than one number returned when several grandparents study. 

Given these function definitions one can formulate advanced queries, such as: 

  select name(c) 
         from Person c
         where grandsparentsnetincomes(c) > 100000 and
         income(c) < 10000;

3.3.4 Aggregation operators

   count(parents(parents(:adam));

   bag of p

   count(bag of object b) -> integer

  select name(c) 
         from Person c
         where sumagg(grandsparentsnetincomes(c)) > 100000;

  select sumagg(select netincome(p) from Person p);

3.3.5 Quantifiers

   some(bag of object o) -> boolean
   notany(bag of object o) -> boolean

For example, the following queries find those persons having some grandparent, and having no grandparent, respectively: 

   select name(p)
   from Person p
   where some(parents(parents(p)));

   select name(p)
   from Person p
   where notany(parents(parents(p))); 

   select name(p)
   from Person p
   where notany(select gp from Person gp
                          where gp = parents(parents(p))
                            and netincome(gp)<100000);

3.3.6 Disjunctive Queries

Example: 

create function father(person) -> person as stored;
create function mother(person) -> person as stored; 
create function parent(person p) -> person q 
        as select q where q=father(p) or q=mother(p);

3.3.7 Transitive closures

tclose(function f,object o,integer maxdepth)-> <object r,integer depth>

tclose is overloaded so that, as an alternative, the name of the traversal function can be specified as a string. 

Example: 

create function ancestors(person o)-> bag of person a
        as select a from integer d
        where  tclose("person.parents->person",o,200) = <a,d> 
                                and a != o;

ancestors(:kain);
select p from person p where ancestors(p) = :eve;

An alternative definition of ancestors would be as a recursive function. This is, however, NOT supported in AMOS II! 

4 Multi-database Architecture

4.1 Distribution

• It can be a single-user, a server or an embedded system, where a single-user AMOS II system is a private database, a server is servicing several other AMOS II systems, and an embedded system is linked to some application. 
• It can be a stand-alone, or a mediator system, where a stand-alone system is an isolated database and a mediator access data from some mediator(s) or data source(s). 

• (A) is an embedded AMOS II mediator linked to an application program. The small footprint of an embedded AMOS II system makes it easy to link it to applications. The system has interfaces to application programs in Java, C, and Lisp. Applications always access meditator servers by AMOSQL commands that are passed through an embedded AMOS II mediator. 
• (B) is a single-user mediator which imports and integrates data from AMOS II servers through the multi-database facilities, but which is not servicing other systems.
• (C) is a single user stand-alone database where the user can enter AMOSQL commands to populate, search, and update a private database. 
• (D) is a mediator server which services inter-database requests from other AMOS II systems and defines mediating OO views that integrate data from other servers.
• (E) is a mediator server which translates data from a relational database. It has knowledge of how to translate AMOSQL queries to SQL [FR97] and interfaces to call SQL through ODBC [Bra98]. It can use the facilities of AMOSQL for semantic mediation of data from its data source and its local database into views presented to other systems. 
• (F) is a stand-alone database server which is accessed from mediator (D) by TCP/IP. It is also a nameserver. It keeps track of the mediator servers and clients in this group of mediators, as indicated by the dotted arrows. Every AMOS II mediator belongs to a group of mediators and must be given a unique name within the group. The nameserver is an ordinary AMOS II mediator server having the special task to store information about names, locations, and other meta-properties of the mediators in a group. A nameserver thus identifies a group of mediators and all mediators in the group will access meta-data about the federation of mediators from the nameserver (dotted lines in the figure above).
• (G) is a stand-alone embedded AMOS II system which provides database facilities for an application, e.g. for FEA analysis [OR96]. 

4.1.1 The nameserver

Every mediator must has a name registered with a nameserver and the nameserver is also its own nameserver. So the first thing to do when setting up a group of AMOS II mediators on the net is to start nameserver as follows: 

1. Start a stand-alone AMOS II database. 

2. Call the AMOSQL function 
   nameserver("<server name>");
for example 
   nameserver("MyServer");
This call will register the stand-alone AMOS II database as a mediator server named <server name> in the nameserver, i.e. in itself. 

3. Start running the nameserver by calling 
   listen();
After this call the system will no longer prompt for AMOSQL commands but will start listening for inter-database requests from other AMOS II systems. 

You can interrupt the listening loop by typing CTRL-C. After that the server is not active and you can type AMOSQL commands as usual. Resume the server listening loop again by calling listen();. 

An unnamed AMOS II system is not a mediator but can be a stand-alone (C) or an embedded stand-alone (G) database. It can also be an embedded AMOS II system (A) through which an application communicates with mediator servers. Before an AMOS II database has become a named client mediator it is NOT allowed to import or integrate data from mediators to store in the local database. 

4.1.2 Mediator clients

Once a mediator client is registered it may send multi-database requests to the mediator servers registered in its name server. The most primitive way to communicate with mediator servers is through the system function 
   ship("<mediator server>","<AMOSQL command>");
For example 
   ship("MyServer","select t from type t;");
It executes an AMOSQL command in a mediator server and ships the result back to the issuing mediator. Section 9.2 describes sophisticated multi-database query facilities in AMOS II through which data can be retrieved and combined from several mediator servers. 

4.1.3 Mediator servers

4.2 Mediation

• A mechanism to access external data sources from AMOS II. The meta-type datasource describes properties of each data source and provides the basic mechanisms for multi-database queries to each kind of external data source. The wrappers for each class of data sources are defined as subtypes to the virtual type datasource. 
• Some special kinds of types and functions that are used for importing OO schemas from other AMOS II servers and for combining and transforming heterogeneous type hierarchies. 

4.2.1 Mediation types

• Stored types are the regular types whose instances are explicitly stored in the the local database and created by the user. The supertypes of a stored type must also be stored types.
• Derived types (DTs) are defined in terms of other types through queries, i.e. DTs define types as views. Derived types are important for data mediation but can also be used for modeling OO views. The extent of a DT is a subset of the extents of one or more constituent supertypes specified through a query over the supertypes. Its extent is a subset of the intersection of the extents of the constituent types. The principles of the DTs are described in detail in [JR99a].
• Proxy types represent external objects stored in other AMOS II servers or in some of the supported types of data sources, e.g. ODBC data sources [Bra98].
• Integration union types (IUTs) provide a mechanism for defining OO views capable of resolving semantic heterogeneity among meta-data and data from multiple data sources. Informally, while the DTs represent restrictions and intersections of extents of other types, the IUTs represent reconciled unions of data in one or more mediators or data sources.

4.2.2 External data access

References

[CR01]K.Cassel, T.Risch: An Object-Oriented Multi-Mediator Browser. Presented at 2nd International Workshop on User Interfaces to Data Intensive Systems, Zürich, Switzerland, May 31 - June 1, 2001

[FRS93] G. Fahl, T. Risch, M. Sköld: AMOS - An Architecture for Active Mediators. Workshop on Next Generation Information Technologies and Systems (NGITS'93), Haifa, Israel, June 1993. 

[FR97] G. Fahl, T. Risch: Query Processing over Object Views of Relational Data. VLDB Journal, November 1997 ( http://www.dis.uu.se/~udbl/publ/vldbj97.pdf). 

[Fis89] D.Fishman et al.: Overview of the IRIS DBMS, in W.Kim, F.H.Lochovsky (eds.): Object-Oriented Concepts, Databases, and Applications, ACM Press, Addison-Wesley, 1989. 

[FR95] S. Flodin, T. Risch, Processing Object-Oriented Queries with Invertible Late Bound Functions, Proc. VLDB Conf., Zürich, Switzerland, 1995. 

[GS92] H.Garcia-Molina and K.Salem: Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, Vol. 4, No. 6, Dec. 1992. 

[JKR99] V.Josifovski, T.Katchaounov, T.Risch: Optimizing queries in distributed and composable mediators, Presented at 4th Conference on Cooperative Information Systems, CoopIS'99, Edinburgh, Scotland, September 1999.

[Jos99] V.Josifovski: Design, Implementation and Evaluation of a distributed Mediator System for Data Integration, PhD Thesis No 582, Linköping University, 1999 (http://www.dis.uu.se/~udbl/publ/vanjaphd.pdf). 

[JR99a] V.Josifovski, T.Risch: Functional Query Optimization over Object-Oriented Views for Data Integration. Journal of Intelligent Information Systems (JIIS), Vol. 12, No. 2-3, 1999.

[JR99b] V.Josifovski, T.Risch: Integrating Heterogeneous Overlapping Databases through Object-Oriented Transformations, Proc. 25th Intl. Conf. On Very Large Databases, Edinburgh, Scotland, September 1999 ( http://www.dis.uu.se/~udbl/publ/vldb99.pdf).

[JR00] V.Josifovski, T.Risch: Query Decomposition for a Distributed Object-Oriented Mediator System , To be published in Distributed and Parallel Databases J., Kluwer, 2000.

[LR92] W.Litwin, T.Risch: Main Memory Oriented Optimization of OO Queries Using Typed Datalog with Foreign Predicates, IEEE Transactions on Knowledge and Data Engineering, Vol. 4, No. 6, December 1992 ( http://www.dis.uu.se/~udbl/publ/tkde92.pdf). 

[Lyn91] P. Lyngbaek et al: OSQL: A Language for Object Databases, Tech. Report, HP Labs, HPL-DTD-91-4, 1991 

[OR96] K.Orsborn, T.Risch: Next Generation of O-O Database Techniques in Finite Element Analysis. The Third International Conference on Computational Structures Technology, Budapest, Hungary, August 21-23, 1996. 

[RJ00]T.Risch, V.Josifovski: Distributed Data Integration through Object-Orinented Mediator Servers, to be published in Theory and Practice of Object Systems J., John Wiley & Sons, 2000.

[Shi81] D.Shipman: The Functional Data Model and the Data Language DAPLEX, ACM Transactions on Database Systems, 6(1), 1981. 

[Sko96] M. Sköld, Active Rules based on Object Relational Queries - Efficient Change Monitoring Techniques, PhD Thesis No 494, Linköping University, 1996 (http://www.ida.liu.se/~edslab/publications.html). 

[SR96] M. Sköld, T. Risch: Using Partial Differencing for Efficient Monitoring of Deferred Complex Rule Conditions. 12th International Conf. on Data Engineering (ICDE'96), (IEEE), New Orleans, Louisiana, Feb. 1996. 

[Ull88] J.D.Ullman: Principles of Database and Knowledge-Base Systems, Volume I and II, Computer Science Press, 1988 and 1989. 

[Wie92] G Wiederhold: Mediators in the Architecture of Future Information Systems, IEEE Computer, 1992.