Saturday, April 20, 2013

ERROL - from Amazon wiki


Copied from   http://www.amazon.com/wiki/ERROL

ERROL

ERROL (Entity Relationship Role Oriented Language; Markowitz and Raz 1983a) 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. With such characteristics it can be a foundation for future Data management languages, more convenient for humans to use than existing languages which may need complex expressions even for moderately complex NL expressions (e.g., SQL; see Example below).
ERROL is also applicable to newer applications like querying the Semantic web using ontologies. As well it is applicable to other than ERM semantic data models, e.g., Object-Role Modeling (ORM), which has many similarities to the ERM. ERROL has some similarities to the later Gellish (in particular to Gellish English), a formal language with a strong connection to natural languages, and can use its dictionaries.
Reshaped relational algebra (RRA; Markowitz and Raz 1983b, 1984; Raz 1986), 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.
ERROL and its RRA translation expose and exploit the connection between the way humans reason and talk about needed information, possibly very complex, and the database operations needed in order to compute this information from the database data. A sequence of such RRA operations is generated automatically from an ERROL expression by an ERROL-to-RRA compiler. The compiler output has been applied directly to a relational database, and also has a translation to SQL, the standard interface, for a straightforward, "regular" execution by SQL database systems, to take advantage of their query optimization.

Contents

[hide]

Introduction

While Natural language (NL) can be vague and ambiguous, ERROL (Markowitz and Raz 1983a) 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 sometimes vague and 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, and identical to it in most cases, ERROL eases these difficulties.
It is worthwhile noting that the English language utilization in ERROL is different in nature from its utilization in other computer languages like COBOL and SQL: While in the latter English-like language commands are utilized, in ERROL a predicate (in a query or other manipulation) is specified by an English-like expression.
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"; the emphasis is on navigation in an ER Diagram, versus any other data structure). 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 (within the ERROL System project; see the Brief history section below).
Reshaped relational algebra (RRA; Markowitz and Raz 1983b, 1984) 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 (Raz 1986) ). 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 a procedural language which specifies the way to compute it; for example, SQL comprises portions of each type). 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 (Raz 1987) 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 specification of a Hypertree, a computaion 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 with the correct intended meaning.

Structured English

Structured English (SE; Raz 1987; 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 (see examples in Raz 1987). A navigation hypertree 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 parentheses 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).
  • Assignment and Substitution: An ERROL subexpression can be named using assignment and be utilized in a long expression by its name (see example below). In particular entities and relationships can be defined and utilized.
  • Reserved words: Errol has a set of reserved words, for example, for commands (e.g., "get") and logic operators (e.g., "or").
  • Transitive closure. This feature enhances the expression and computing power of ERROL considerably. It is done by allowing to define (and name) relationships which are the transitive closure of existing reflexive relationships (i.e., between an entity to itself, e.g., EMPLOYEE MANAGES EMPLOYEE: A manager can be direct, or several levels above) either already appearing in the database, or defined by an ERROL expression.
  • 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.). Such component has not been implemented within the framework of the ERROL System project described below (see the Brief history section below).
  • 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. Such components have not been implemented within the framework of the ERROL System project described below (see the Brief history section below).
The linguistic aspect of the Entity relationship model, and the way it is utilized by ERROL for navigation in an ER Diagram is demonstrated 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:
  1. The equivalent ERROL examples above become unnecessarily more and more complex just to demonstrate ERROL's constructs, which allow to conveniently handle queries with very complex specifications.
  2. Many more equivalent query variations are possible.
  3. 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.
  4. Capital letters are used here for convenience only to emphasize entities, relationships, and certain reserved words; ERROL is not case sensitive.
  5. Compare expression complexity: write this query in SQL; All SQL expressions for this query are relatively complex and long.
See additional examples in a section below.

Reshaped relational algebra

Main article: Reshaped relational algebra
The Reshaped relational algebra (RRA; Markowitz and Raz 1983b, 1984; an alternative formulation can be found in Raz 1986 ) has been developed to support ERROL over relational databases. RRA is equivalent to the Relational Algebra (RA) in expression power (each one algebra's operator can be expressed by the other algebra's operators (Raz 1986) ), 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.

RRA operators and their relationship with Natural language constructs; from (Raz 1987)
An ERROL expression (or respective hypertree) can be translated in a straightforward way to an RRA expression. An RRA expression is a partial order (typically with several compatible sequences) 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 a single entity identifying temporary name for all that entity occurrences in the query that have the same reference symbol (for same entity occurrences with different reference symbols, different temporary names are given; for same entity occurrences with no reference symbol, different temporary names are given).
RRA expression simplification, and consistency checking together with subexpression contradiction and tautology identification, can be done using RRA axioms and theorems (Raz 1986). 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, with all needed for queries linguistic constructs, including implementation guidelines, have been developed by Victor M. Markowitz as the subject of his M.Sc. thesis (Markowitz 1983) at the Technion - Israel Institute of Technology (advisor: Yoav Raz). Further ERROL enhancements and implementation, including ERROL to RRA translation (M.Sc. project of Reuven Cohen; Cohen 1984), have been done by Yoav Raz together with graduate students. In 1984 Yoav Raz, Victor Markowitz, and Reuven Cohen won the Computer Science Award of ILA – The Israeli Information Technology Association.

ERROL System output example: ERROL query, compilation output (c+), and then execution output (x+). t - intermediate relations; x - (renamed) temporary attribute names; the left-side t operand in each RRA operation is the operation's result relation; from (Raz 1986)
The ERROL System (Raz et al. 1984) 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 (see output examples in Raz 1987).

ERROL (SE) examples

The examples below are given primarily in their skeleton representation, or close to that, rather than their more close-to-NL forms (e.g., set operations rather than quantifiers) to more clearly hint on their RRA translations.

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 (Raz 1987) )
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 parentheses 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.

See also

References

External links

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)