ERROL

ERROL (an acronym for Entity Relationship Role Oriented Language) is a declarative database query and manipulation language for the Entity-relationship model (ERM). It is applicable to any data model on which ERM can be mapped, virtually any general purpose database data model. It is based on the capability of ER diagrams to be described accurately by simple Natural language (NL) sentences. A specification of a complex operation upon an ERM database can be described accurately by a complex and/or compound NL sentence constructed from the simple sentences describing the respective ER diagram. An ERROL expression mimics such NL sentence with one-to-one correspondence between ERROL subexpressions and NL subsentences: An ERROL expression can look like the corresponding NL sentence, or at least like a similar, equivalent one. This allows to write in ERROL very complex queries by simple conversion from their NL specifications. It also allows a straightforward checking of an ERROL expression meeting a complex NL specification.

ERROL is also applicable to newer applications like querying the Semantic web using ontologies.

Reshaped Relational Algebra (RRA), with operators that follow the semantics of respective major NL constructs, has been developed to support ERROL over relational databases. It is used both to specify ERROL's semantics concisely and accurately, and to implement ERROL effectively over relational databases.

Introduction

While "Natural language" (NL) can be vague and ambiguous, ERROL is accurate with well defined semantics, and thus provides a check for NL queries. With these properties ERROL is a good compromise between NL as a query language and other database languages: Long experience with database languages shows that simple queries are easy to phrase with both NL and most database languages. However, some complicated queries may be hard to phrase accurately in most languages, including NL. In most cases NL is the natural query tool for humans, but being vague and sometimes ambiguous, often a complex NL query's meaning is not accurately defined, and a dialogue that involves a well defined formal language feedback is needed to verify the intended meaning when NL is used. In practice a query specification is typically initially thought of, formulated, in NL, and then translated by an expert to the desired database language. Validating translation correctness (semantic equivalence) is usually difficult for complex queries and relies completely on the expert's understanding of the NL specification. Wrong interpretation can be very costly, both in execution time and implications. Being very close to NL, ERROL eases these difficulties.

Though originally motivated by the linguistic aspect of ERM, ERROL has been found to provide a powerful paradigm beyond this aspect: Specification of a complex query predicate by Navigation in an ER Diagram ("query by navigation"). Even without exploiting many NL elements, the navigation itself together with basic schema elements provides accurate specification. As a matter of fact the navigation is independent of any specific NL, and presents the semantic relations (Relationships and comparisons) between objects of interest (Entities and attributes, and resulting objects by arithmetic operations, aggregations, and logic derivations), where the ER diagram provides a limited form of semantic network. All the needed information for a complete specification over a given schema exists in a skeleton ERROL specification which includes only ER Diagram elements, and may include constants, aggregate functions, logical connectives, arithmetic operations and comparison operators. Using such language-independent representation, a specification can be easily machine-translated accurately among different natural languages, using small numbers of each language's syntactic constructs, and having an ER diagram described by respective simple sentences in different languages. Specification reconstruction in English (that can be re-processed correctly by the ERROL compiler) from the language-independent representation has been done successfully.

Reshaped Relational Algebra (RRA) has been developed to support ERROL over relational databases. RRA is equivalent to Relational algebra (RA) in expression power (each one algebra's operator can be expressed by the other algebra's operators). A strong correlation exists between ERROL constructs (and corresponding NL's) and RRA operators. This is used both to specify ERROL's semantics concisely and accurately, and to implement ERROL effectively over relational databases. For any ERROL specification (expression; query or other manipulation) a corresponding RRA expression is derived in a straightforward way. This RRA expresstion computes the specification over any relational database with schema that is semantically relevant to the specification (possibly through schema transformation for ERM compatibility with the specification, when needed; the computation result is a relation).

Language overview

ERROL is a declarative language (a specification of what is requested is given, rather than the way to compute it). An ERROL expression describes a "navigation hypertree" (hypertree is an acyclic hypergraph), generated by navigating in the ER diagram. Names and constants are nodes. Entities and Relationships define one types of edges, sets of attribute names. A connecting ERROL construct defines a second type of edge, a "regular" tree (dual node) edge. (See last reference below for more detail.) The navigation may include jumps in the diagram (in case of comparisons) or repetitions over same sections in the diagrams (if the query specification requires repeated utilization of same diagram elements). A complex operation specification by a long NL sentence may suffer from ambiguities due to unclear connection between sentence parts. ERROL solves this problem by inserted parantheses (primarily parentheses) when needed, to uniquely define an expression's hypertree.

Structured English (SE; not to be confused with Structured English used for pseudocode) is an extension of a subset of the English language and an enhancement of the initial ERROL. In SE several "syntactic sugar" elements of ERROL have been made more flexible, and further flexibility with word usage and sentence structure has been introduced, to get it closer to NL. However, the original correspondence between NL and respective ERROL basic constructs has been preserved. In what follows no distinction is made between ERROL and SE.

Highlights:
*The navigation hypertree with correct RRA interpretation (respective RRA operator substitution for any ERROL construct type) provides all the semantics needed to define accurately an ERROL (SE) expression. A navigation hypertree (see last reference below) has one-to-one correspondence with a "skeleton expression" of ERROL, a canonical form that describes the navigation hypertree only by Entitys, Relationships, and Attributes, together with Constants, Aggregate functions, Logical connectives, Arithmetic operations, and Comparison operators.
*An ERROL expression has one navigation hypertree, but typically several navigation hypertrees exist (for different ways of NL phrasing) that provide the same result, by navigating in the ER Diagram through same elements in different ways (e.g., in different directions, in different orders).
*Scope of an aggregate function is determined by parantheses when the intended scope is not properly determined by the defaults. Any ERROL subexpression can be aggregated by inserting aggregation function name and parantheses in the right place.
*Decomposition: A long NL specification can be broken into several simpler sentences. Correspondingly a respective ERROL expression can be replaced by a set of respective simple expressions separated by "delimiters", (e.g., " ; "), which is equivalent to the original expression (see example below).
*Reference or correlation: Often it is required that entities can be referenced properly in a sentence or across sentences. In NL it is done by using expressions like "his", "the above", "the second above", etc. In ERROL it is done as well, primarily by reference (correlation) symbols like (x), attached to entity name repetitions in an expression, and by some supported, or ad-hoc defined per a given schema, English constructs. All entity name repetitions marked with (x) are the same entity occurrence in the database for any instance for which the query predicate is true (see examples below).
*Substitution: An ERROL subexpression can be named using assignment and be utilized in a long expression by its name (see example below).
*Reserved words: Errol has a set of reserved words, for example, for "commands" (e.g., "get") and "logic operators" (e.g., "or").
*ERROL has been enhanced with Transitive closure.
*An interactive graphical interface (Graphical ERROL) can be built in a straightforward way to construct the navigation hypertree (and corresponding ERROL expression; the ERROL system can already reconstruct an NL expression from an RRA expression using the system's dictionary) by picking up elements from the ER Diagram, and other needed elements (logical, comparison, constants, etc.).
*SE can be replaced by a respective subset of any other Natural language (e.g., French, Hebrew, etc.) with basic syntactic constructs that have semantics similar to the English constructs used for SE. Skeleton expression translations require only names' translations, and language fonts replacement when needed.

The liguistic aspect of the Entity relationship model, and the way it is utilized by ERROL for navigation in an ER Diagram is demonstareted by the following example:

Example

:Assume an ER diagram for a relational database of employees, with EMPLOYEE "entity" (as defined in ERM) and MANAGE "relationship" between two employees.

::EMPLOYEE(id, salary) is the database relation for the entity EMPLOYEE ::MANAGE(id1, id2) is the relation for the relationship MANAGE: employee with id1 manages employee with id2.

:Consider the following query:

:*"Find the employees that earn more than their manager."

:The following equivalent (in result; some also in navigation hypertree) ERROL queries provide a correct solution:

:*Get employees that earn more than their manager:*Get employee that earns more than his manager:*Get EMPLOYEE that EARNS more than his MANAGER:*Get id of EMPLOYEE that has salary greater than that of his MANAGING EMPLOYEE:*Get EMPLOYEE(x) having salary > salary of EMPLOYEE that MANAGES EMPLOYEE(x):*Get id of EMPLOYEE(x) MANAGED by EMPLOYEE having salary < salary of EMPLOYEE(x):*Get id EMPLOYEE(x) salary > salary EMPLOYEE MANAGE EMPLOYEE(x) ("Skeleton query"):*Get EMPLOYEE(x) WHERE EMPLOYEE(x) is MANAGED by EMPLOYEE(y) AND has salary> salary of EMPLOYEE(y):*Get EMPLOYEE(x); EMPLOYEE(y) MANAGE EMPLOYEE(x); salary EMPLOYEE(x)>salary EMPLOYEE(y) (delimited expressions are connected by logical conjunction (AND) ):* E1:= salary of EMPLOYEE(x) > salary of EMPLOYEE(y); Get EMPLOYEE(x) WHERE E1 AND E2; E2:= EMPLOYEE(x) is MANAGED by EMPLOYEE(y) (substitution; assignment location in expression does not matter)

:Comments::- The symbols x, y in the examples above are used for reference, correlation: All entity name repetitions marked with (x) are the same entity occurrence in the database for any instance for which the query predicate is true. :- Many more equivalent query variations are possible. :- Capital letters are used here for convenience only to emphasize entities, relationships, and certain reserved words; ERROL is not case sensitive.:- The equivalent ERROL examples above become unnecessarily more and more complex just to demonstrate its constructs that allow conveniently handling queries with very complex specifications.

:Compare expression complexity: write this query in SQL.

See additional examples in a section below.

Reshaped Relational Algebra

The Reshaped Relational Algebra (RRA) has been developed to support ERROL over relational databases. RRA is equivalent to the Relational Algebra (RA), and has strong analogies to some basic NL constructs. As such it is ideal for describing the semantics of ERROL, as well as for implementing ERROL over relational databases. For any ERROL specification (expression; query or other manipulation) a crresponding RRA expression computes the specification over a relational database. The main difference between RRA and RA is with "natural join" and "projection" operations embedded in various RRA operators.

An ERROL expression (or respective hypertree) can be translated in a straightforward way to an RRA expression. An RRA expression is a sequence of RRA operations, which provides a procedure for computing the value of the ERROL expression over a relational database (i.e., computing the query or data manipulation resulting relation) by manipulating its relations. Each ERROL subexpression type has a corresponding RRA operator. The subexpression variables (entity, relationship, and attribute names) and constants comprise the operator's parameters. The operators' order is determined by the hypertree structure of the (possibly paranthesized) ERROL expression. By proper "renaming", the join operation embedded in RRA operators automatically connects between corresponding attributes in entities and relationships, and resolves references by using one entity identifying name per reference symbol.

RRA expression simplification, and consistency checking together with subexpression contradiction and tautology identification, can be done using RRA axioms and theorems. RRA expression computation optimization can be done similarly to the ways it is done for Relational algebra (RA).

Brief history

Both RRA and initial version of ERROL, including implementation guidelines, have been developed by Victor M. Markowitz as the subject of his M.Sc. thesis at the Technion, Israel (completed in 1983; Advisor: Yoav Raz). Further ERROL enhancements and implementation, including ERROL to RRA translation, have been done by Yoav Raz together with graduate students.

The ERROL System implements database queries and manipulations over a relational database using SE and RRA. During the years 1982-1988 it has been developed at the Technion, Israel, using UNIX, Lex, YACC, and Ingres, and further enhanced at UCSD.

ERROL (SE) examples

Example 1

This example relates to a factory database. The portion of the database relevant to this example (and other examples below) has departments, items in stock, and suppliers of these items as "entities". Departments REQUEST (order) items from suppliers. Suppliers SUPPLY items to departments. Both last sentences above define ternary (three-way) "relationships".

:Entities are defined by the following relations:

::DEPARTMENT(did, name, floor)::ITEM(iid, name, color)::SUPPLIER(sid, name)

:The relationships are defined by the following relations:

::REQUEST(did, iid, sid, quantity)::SUPPLY(did, iid, sid, quantity)

:Possible simple ERROL queries over this schema for respective Natural language (NL) specifications are as follows:

*NL: "Find id and name for items supplied to the Engineering department."::Get id, name of ITEM SUPPLIED to DEPARTMENT with name="Engineering", or::Get id, name of ITEMS SUPPLIED to the Engineering DEPARTMENT - (additional dictionary definition is required for using this ERROL expression)

*NL: "Find the names of suppliers from whom red or blue items are requested by the Engineering department."::Get names of SUPLIERS REQUESTED ITEMS with color="Red" OR "Blue" by DEPARTMENT with name="Engineering"

Example 2

(from example 2 in the last reference below)

Using the schema in Example 1 above consider the following imaginary complex query:

*"Find departments such that each ( is located in floor lower than the floor of a department requesting number of items greater than 20) or ( (not supplied by supplier named "Tom") and has the name "Engineering" )."

A possible straightforward skeleton ERROL expression for this query is the following:

*Get DEPARTMENT (floor < floor DEPARTMENT REQUEST COUNT ITEM > 20) OR (NOT SUPPLY SUPPLIER name = "Tom") AND name = "Engineering"

or the following:

*Get DEPARTMENT(x) WHERE (E1 AND E2) OR ((NOT E3) AND E4); E1:=floor DEPARTMENT(x)< floor DEPARTMENT(y); E2:=DEPARTMENT(y) REQUEST COUNT ITEM>20; E3:=DEPARTMENT(x) SUPPLY SUPPLIER name = "Tom"; E4:=DEPARTMENT(x) name="Engineering" (comment: the parantheses in the first subexpression are unnecessary due to common defaults)

::Comment: Judging by the ERROL compiler output in example 2 of the last reference below, it seems that some parantheses in the input expression there have been lost, probably due to a (paper) "cut and paste" error, that had also propagated to the example 2 text there.

Example 3

Using the schema in Example 1 above:

*"Find pairs of supplier, department, such that the supplier supplies to the department more than half the number of all the "Red" items requested by all the departments."

ERROL query:

*Get SUPPLIER(x), DEPARTMENT SUPPLIED by SUPPLIER(x) COUNT ITEMS > 0.5*COUNT ITEMS (REQUESTED AND have color="Red")

If half the number of "Red" items requested by any single department is considered, the NL sentence is slightly changed:

*"Find pairs of supplier, department, such that the supplier supplies to the department more than half the number of "Red" items requested by any department."

A possible ERROL query is the following:

*Get SUPPLIER(x), DEPARTMENT SUPPLIED by SUPPLIER(x) COUNT ITEMS > 0.5*COUNT ITEMS (REQUESTED AND have color="Red") by DEPARTMENT::Here in the second COUNT operator the aggregation is done separately for each DEPARTMENT.

::The symbol x is for a reference.

Example 4

Using the schema Example 1 above:

*"Find pairs of supplier, department such that the supplier supplies to the department all the items that this department requests from that supplier."

ERROL query:

*Get SUPPLIER(x), DEPARTMENT(y) SUPPLIED by SUPPLIER(x) SET ITEMS = SET ITEMS REQUESTED by DEPARTMENT(y) from SUPPLIER(x)."

::The symbols x, y are for references.

Example 5

Using the schema in Example 1 above:

*"Find the departments that get all the quantity of Red Bolts they order."

ERROL query:

*Get DEPARTMENT(x) SUPPLIED with SUM quantity of ITEMS with color="RED" AND name="Bolt" = SUM quantity of REQUESTED ITEMS with color="RED" AND name="Bolt" by DEPARTMENT(x)

::The symbol x is for reference.

References

*Victor M. Markowitz, Yoav Raz (1983): [http://www.informatik.uni-trier.de/~ley/db/conf/er/MarkowitzR83a.html "ERROL - An Entity Relationship Role Oriented Query Language"] , In "Entity Relationship Approach to Software Engineering", October 5-9, Anaheim, California. Davis, G.C. et al. (eds.), pp. 329-345, North- Holland.

*Victor M. Markowitz, Yoav Raz (1983): [http://www.informatik.uni-trier.de/~ley/db/conf/er/MarkowitzR83.html "A Modified Relational Algebra and Its Use in an Entity Relationship Environment"] , In "Entity Relationship Approach to Software Engineering", October 5-9, Anaheim, California. Davis, G. C. et al. (eds.), pp. 315-328, North-Holland, 1983.

*Yoav Raz, Reuven Cohen, Victor M. Markowitz (1984): "ERROL - An Entity Relationship, Role Oriented Query and Data Manipulation Language" (Extended abstract), "The 9th National Conference on Information Processing" together with "The 4th Jerusalem Conference on Information Technology" (JCIT4), May 21-25, Jerusalem, Israel (1984 [http://www.ila.org.il/Index.asp?CategoryID=134&ArticleID=92 ILA] award in Computer Science for "The ERROL System").

*Victor M. Markowitz: "ERROL - An Entity Relationship Role Oriented Query Language", M.Sc. Thesis, Dept. of Computer Science, Technion, Haifa, Israel (January 1983).

*Reuven Cohen: "The Translation of ERROL to RRA - A Reshaped Relational Algebra", M.Sc. Thesis, Dept. of Computer Science, Technion, Haifa, Israel (July 1984).

*Yoav Raz (1987): [http://yoavraz.googlepages.com/SupportingNL.pdf "Supporting Structured English Interfaces to Relational Databases Using RRA" (PDF)] , Technical Report, TR CS-093, EECS Dept., UCSD (ERROL, RRA, ERROL translation to RRA, and "The ERROL System" examples).