Reshaped relational algebra - From Amazon Wiki

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

Reshaped relational algebra

The reshaped relational algebra (RRA; Markowitz and Raz 1983b, 1984; reformulated in Raz 1986) is a modification of the relational algebra (RA) with enhanced operators. A major motivation for defining RRA has been providing a missing manipulative component to the entity-relationship model (ERM). The primary distinguishing feature of RRA operators is that they possess strong analogies to Natural language (NL) constructs. The main difference between RRA and RA is with natural join and projection operations embedded in various RRA operators. RRA is equivalent to RA in expressive power, in the sense that each algebra's operators can be expressed by the operators of the other (Raz 1986).
RRA has been utilized to support ERROL (Markowitz and Raz 1983a), an entity-relationship model (ERM) database language, over relational databases. It has been utilized both to define the semantics of ERROL, and to conveniently and effectively implement ERROL over relational databases.

Contents [hide] 1 Motivation 2 The linguistic aspect of the ERM 2.1 Straightforward examples 2.2 Simple NL surface sentences of an ERM scheme 2.3 Combining the simple NL sentences to NL logical predicates 2.4 NL queries 3 RRA operators and their linguistic counterparts 3.1 Notation and definitions 3.2 Renaming 3.3 Projection 3.4 Selection 3.5 Product (natural join, Cartesian product, intersection) 3.6 Bordered union 3.7 θ-join 3.8 Set-join 3.9 Negation/Complement 3.10 Aggregate functions 4 RRA example: The not (negation) operator 4.1 Basic properties 4.2 Negation and operators with comparison 4.3 De Morgan's laws 5 NL queries and their RRA expressions 5.1 Assumptions 5.2 RRA and its relational representation of the ERM 5.3 Constructing an RRA expression from an NL query 6 RRA development and utilization 7 See also 8 References 9 External links

 

Motivation

The motivation for RRA is explained in the Abstract part of (Markowitz and Raz 1984):

• "The entity-relationship model (ERM) has been defined without a manipulative part. Since a link between the ERM and the relational model may be established by choosing the relation to be the structural unit of the data-representational level of the ERM, this model could benefit by somehow inheriting the relational algebra. This paper proposes as manipulative part for the entity-relationship model a reshaped relational algebra (RRA). It is shown that just as the entity-relationship model concepts are based on the way people perceive information, the RRA operators bear analogies to the way people communicate, i.e., natural language, and are therefore convenient in describing the semantics of query languages within ERM."

 

The linguistic aspect of the ERM

Main articles: Entity-relationship model and ERROL
 

Entity Relationship Diagrams (ERDs) and Schemas can be described accurately by simple sentences of Natural languages (NLs). These simple sentences can be utilized to construct a complex sentence, or a compound sentence, or a combination, or a sequence of sentences which comprise a logic predicate. A predicate is either "true" or "false" depending on the substitution in it of the data (attribute) values (from some specific database described by the related ER diagram/schema). A database query is a combination of a set of attributes (the target set or the target list) and a logic predicate. A set of values that correspond to the target set is in the query's result if their corresponding values (from the same entity and relationship instances) substituted in the predicate (possibly of other attributes) results in the value "true" for the predicate.

Straightforward examples

These examples relate to a factory database. The portion of the database relevant to the examples 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(d_key, name, floor)

ITEM(i_key, name, color)

SUPPLIER(s_key, name)

The relationships are defined by the following relations:

REQUEST(d_key, i_key, s_key, quantity)

SUPPLY(d_key, i_key, s_key, quantity)

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

• NL: "Find key and name for items supplied to the Engineering department."

ERROL: Get i_key, name of item supplied to department with name="engineering"

• NL: "Find the names of suppliers from whom red or blue items are requested by the engineering department."

ERROL: Get names of suppliers requested items with color="red" or "blue" by department with name="engineering"

Each query has a target set (list) of attribute types to be retrieved, and a logic predicate. The predicate needs to assume a true value for related (same entity and relationship instances) attribute values substitution in order to extract the corresponding target set values.
For example, in the first query above, "id and name of an item" is the target list; "items supplied to the Engineering department" is the logic predicate.

Simple NL surface sentences of an ERM scheme

• A sentence describing a Relationship among Entities.
• A sentence connecting an Attribute to its Relationship.
• A sentence connecting an Attribute to its Entity.
• Is-a sentence – generalizing Entities.
•  

Combining the simple NL sentences to NL logical predicates

Utilizing linguistic constructs

• Restriction (by a constant or variable)
• Relativization
• Coordination (OR and AND)
• Quantifiers
• Aggregation
• Referencing

 

NL queries

Navigating in the ER Diagram
Combining a target data type set (of the query; what is being retrieved) with a logical predicate to produce a query.

RRA operators and their linguistic counterparts

For major syntactic natural language (NL) constructs needed for queries in most common NLs, each has a matching RRA operator. The relationships between these NL constructs and RRA operators are summarized in the following table:

RRA operators and their relationship with Natural language constructs; from (Raz 1987)

The RRA operators are defined as follows:

Notation and definitions

RRA definitions; from (Raz 1987)

Renaming

RRA definitions; from (Raz 1987)

Projection

RRA definitions; from (Raz 1987)

Selection

RRA definitions; from (Raz 1987)

Restriction by a constant.

Product (natural join, Cartesian product, intersection)

RRA definitions; from (Raz 1987)

NL: Both Relativization and AND coordination (Conjunction).

Bordered union

RRA definitions; from (Raz 1987)

NL: OR coordination (Disjunction).

θ-join

Attribute join

RRA definitions; from (Raz 1987)

Restriction by a variable.

Set-join

Generalized division

RRA definitions; from (Raz 1987)

Set comparison; Universal quantification.

Negation/Complement

Not

RRA definitions; from (Raz 1987)  Negation.

The not operator is defined in (Raz 1986) and replaces the subtruction/difference operator originally used for RRA in (Markowitz and Raz 1983b, 1984). not allows a simpler representation of NL negation (e.g., the English "not").

Aggregate functions

RRA definitions; from (Raz 1987)

Sum, Count, Minimum, Maximum, Average, etc.

RRA example: The not (negation) operator

Basic properties

RRA – The not operator 1; from (Raz 1986) page 36

RRA – The not operator 2; from (Raz 1986) page 37

Negation and operators with comparison

The operators with comparison are select, θ-join (attribute join), and set-join.
By applying negation (not) to the comparison they all obey the following formula (within the defined semantics):

not(operator_{parameter1 comparison parameter2}) = operator_{parameter1 not(comparison) parameter2}

Specifically,

• select operator with comparison θ from { =, <, > }:

not(select_{attribute θ constant} R) = select_{attribute not(θ) constant} R

Related NL (and ERROL) example:

NOT AN ITEM with COLOR = RED

is equivalent to:

AN ITEM WITH COLOR not= RED

• attribute-join operator with comparison θ from { =, <, > }:

not(R1 attribute-join_{attribute1 θ attribute2} R2) = R1 attribute-join_{attribute1 not(θ) attribute2} R2

NL (and ERROL) example:

DEPARTMENT THAT REQUESTS ITEMS FROM A SUPPLIER IN QUANTITY THAT IS SMALLER THAN (<) THE QUANTITY IT (reference; the same department) IS SUPPLIED WITH BY THE SAME (reference) SUPPLIER

is the negation of:

DEPARTMENT THAT REQUESTS ITEMS FROM A SUPPLIER IN QUANTITY THAT IS NOT-SMALLER THAN (not <) THE QUANTITY THAT IT (reference; the same department) IS SUPPLIED WITH BY THE SAME (reference) SUPPLIER.

• set-join operator with comparison δ from { =, contains, contained-in }:

not(R1 set-join_{set1 δ set2} R2) = R1 set-join_{set1 not(δ) set2} R2

NL (and ERROL) example:

SET OF ITEMS (or "all the items"; universal quantifier) SUPPLIED TO DEPARTMENT IS CONTAINED-IN ("are included in") SET OF ITEMS REQUESTED BY THAT (reference; the same) DEPARTMENT

is the negation of

SET OF ITEMS (or "all the items") SUPPLIED TO A DEPARTMENT IS NOT-CONTAINED-IN ("are not included in") THE SET OF ITEMS REQUESTED BY THAT (reference; the same) DEPARTMENT.

Comments:

• For database context for the English expressions in the examples above see the Straightforward examples section above.
• These English examples can be used by the respective application to check consistency between REQUEST and SUPPLY (what is not requested should not be supplied; a hidden aggregation on suppliers exists in the set containment example since SUPPLIER does not appear explicitly, which makes it "by all relevant suppliers").

 

De Morgan's laws

Main article: De Morgan's laws

De Morgan's laws are demonstrated below for RRA and English sentences:

RRA – De-Morgan's Laws; from (Raz 1986) page 39

Comment: For database context for the English expressions in the examples above see the Straightforward examples section above.

NL queries and their RRA expressions

Assumptions

An RRA expression allows one to compute the result of respective NL (or ERROL) query from a relational database. For this purpose two condition should be met:

1. Entities and Relationships as defined by the entity-relationship model (ERM) are represented by relations as define by the relational model (RM) in a certain general, natural, normalized form (see below; applicability to other representations of ERM and other data models is established by proper mapping from the normal form).
2. The NL sentence can unambiguously be parsed to extract certain syntactic structures (see table above). Most major NL languages are based on these structures and can be translated to RRA. From these structures and their order the RRA expression is constructed. NLs are vague and ambiguous in nature, and sometime several iterations by a user are needed to produce the intended unambiguous NL sentence (or a sequence of sentences). In contrast, ERROL which is a super-set (with added parentheses for disambiguation) of a subset of the English language, is unambiguous and can be parsed and translated to RRA immediately, if phrased correctly (by its own syntax rules; this has been the motivation for defining ERROL).

(see Straightforward examples at section 2 above)

RRA and its relational representation of the ERM

The ER normal form (of a relational scheme).

Constructing an RRA expression from an NL query

The attribute type set to be retrieved by the query and the NL-based logical predicate in the query (which together comprise the query) produce a Hyper-tree (acyclic Hypergraph) of RRA operators by navigating in the ER Diagram according to the predicate. The hyper-tree has a straightforward translation to the intended RRA expression for the query (Cohen 1984, Raz 1987).

RRA development and utilization

RRA has been developed by Victor M. Markowitz (together with an initial version of ERROL) as his M.Sc. thesis (Markowitz 1983) at the Technion – Israel Institute of Technology (advisor: Yoav Raz). RRA has been developed to support all needed (for queries) basic linguistic constructs in a Natural language (NL), with an RRA operator for each such construct. The thesis also includes RRA expressions implementation guidelines. RRA has been utilized both to describe the semantics of ERROL, and to effectively implement ERROL over relational databases. ERROL to RRA Compiler has been constructed in the M.Sc. project of Reuven Cohen (Cohen 1984; Advisor: Yoav Raz). This compiler has been utilized in the ERROL system, an entity-relationship model (ERD) based database system prototype developed during the years 1982–1988 by Yoav Raz together with graduate students at the Technion, Israel and later enhancements at UCSD, United states (Raz et al. 1984, Raz 1987). RRA has been reformulated in (Raz 1986) with a proof of equivalence to relational algebra (RA): Each of one algebra's operators can be expressed with the other algebra's operators.

See also

• Relational algebra
• Entity-relationship model
• Natural language
• ERROL 

 

References

• Victor M. Markowitz, Yoav Raz (1983a): "ERROL – An Entity Relationship Role Oriented Query Language", In Entity Relationship Approach to Software Engineering (ER 1983), October 5–9, Anaheim, California. Davis, G.C. et al. (eds.), pp. 329–345, North-Holland.

• Victor M. Markowitz, Yoav Raz (1983b): "A Modified Relational Algebra and Its Use in an Entity Relationship Environment", In Entity Relationship Approach to Software Engineering (ER 1983), October 5–9, Anaheim, California. Davis, G. C. et al. (eds.), pp. 315–328, North-Holland, 1983.

• Victor M. Markowitz, Yoav Raz (1984): "An entity-relationship algebra and its semantic description capabilities", Journal of Systems and Software, Volume 4, Issues 2–3, pp. 147–162, Elsevier Science Inc., July 1984.

• 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 ILA award in Computer Science for The ERROL System).

• Victor M. Markowitz (1983): ERROL – An Entity Relationship Role Oriented Query Language, M.Sc. Thesis, Dept. of Computer Science, Technion – Israel Institute of Technology, Haifa, January 1983.

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

• Yoav Raz (1986): A Precise Definition of RRA – a Reshaped Relational Algebra which Follows Natural Language Constructs (pdf), Technical Report TR #405, Computer Science Dept., Technion, Israel, March 1986.

• Yoav Raz (1987): Supporting Structured English Interfaces for Relational Databases Using RRA (pdf), Technical Report TR CS-093, EECS Dept., UCSD (ERROL, RRA, ERROL translation to RRA, and The ERROL System examples). Earlier version appeared as Supporting Natural Language Interfaces for Relational Databases Using RRA, TR #410, Computer Science Dept., Technion, Israel, May 1986.

 

External links

• ERROL page in Yoav Raz's site