DATABASES

RA Relational Algebra Interpreter

noreply@blogger.com (Ron Tinnel) — Wed, 30 Nov 2011 05:37:00 +0000

RA RELATIONAL ALGEBRA INTERPRETER

REVISED: Sunday, March 3, 2013

You will learn the basic fundamentals of RA.

I. INTRODUCTION

RA is a relational algebra interpreter that translates relational algebra queries into SQL queries, then executes the SQL on a standard relational database system. RA was developed by Prof. Jun Yang at Duke University. RA runs on the SQLite open-source relational database system.

The simplest relational algebra expression is one that returns the contents of a single relation.

Relation and attribute names are case-insensitive; for example, pizzeria is the same as PIZZERIA.

Every operator starts with a backslash (\).

The following is an example of a complex query; it finds all pizzas eaten by at least one person who does not frequent the 'Dominos' pizzeria.

\project_{pizza} ( ((\project_{name} Person) // all people

\diff (\project_{name} // people who frequent Dominos

\select_{pizzeria='Dominos'} Frequents) \join Eats)) // join with Eats to find pizzas

The syntax is insensitive to whitespace, and queries may span multiple lines.

II. OPERATORS

RA supports the following relational algebra operators:

A. \select_{cond}

\select_{cond} is the relational selection operator. For example, to select people with name Amy or Ben, we write "\select_{name='Amy' or name='Ben'} Person". The syntax for cond follows SQL: string literals can be enclosed in single or double quotes, and boolean operators and, or, and not may be used. Comparison operators <=, <, =, >, >=, and <> work on both string and numeric types.

B. \project_{attr_list}

\project_{attr_list} is the relational projection operator, where attr_list is a comma-separated list of attribute names. For example, to find the pizzas served by Applewood (but without the price information), we would write

"\project_{pizza} (\select_{pizzeria='Applewood'} Serves)".

C. \cross

\cross is the relational cross-product operator. For example, to compute the cross-product of Person and Frequents, we write "Person \cross Frequents".

D. \join

\join is the relational natural join operator. For example, to join Person(name,age,gender) and Frequents(name,pizzeria) enforcing equality on the shared name attribute, we simply write "Person \join Frequents". Natural join automatically equates all pairs of identically named attributes from its inputs (in this case, name), and outputs only one attribute per matching pair. The schema of the result in our example is (name,age,gender,pizzeria).

E. \join_{cond}

\join_{cond} is the relational theta-join operator. For example, to join the two relations Person(name,age,gender) and Serves(pizzeria,pizza,price) enforcing that the pizza price is lower than the person's age, we write "Person \join_{age>price} Serves". Syntax for cond follows SQL; see above for \select.

F. \union, \diff, And \intersect

\union, \diff, and \intersect are the relational union, difference, and intersection operators, respectively. For example, to compute the union between Person and itself, we write "Person \union Person;", which returns the original Person relation. To compute the difference between Person and itself, we write "Person \diff Person;", which returns the empty relation. To compute the intersection between Person and itself, we write "Person \intersect Person;", which returns the original Person relation.

RA allows these operators to be applied to any two subexpressions that produce an equal number of attributes, even if the corresponding attribute names do not match. This allowance is typical of most SQL implementations but violates the requirements of pure relational algebra. As good practice, and for unambiguous attribute names in the result, we suggest using the \rename operator (next) as needed to enforce matching schemas whenever \union, \diff, or \intersect is used.

G. \rename_{new_attr_name_list}

\rename_{new_attr_name_list} is the relational renaming operator, where new_attr_name_list is a comma-separated list of new names, one for each attribute of the input relation. For example, to rename the attributes of relation Person and compute the cross-product of Person with itself, we write "\rename_{name1,age1,gender1} Person \cross \rename_{name2,age2,gender2} Person;".

III. LIMITATIONS

Currently, RA has the following limitations:

A. \rename

\rename only supports renaming of attributes; it does not support renaming of relations.

B. RA Expressions

RA expressions may yield multiple attributes with the same name, but only in the outermost experssion. An error may occur if you try to refer to or even rename such attributes later in the same expression. If a subexpression will yield multiple attributes with the same name, you should use the \rename operator within the subexpression to make the names unique.

C. relName.attrName

The standard relName.attrName notation for referencing an attribute is neither needed nor supported. Using the \rename operator, attribute name names can always be made unambiguous.

D. Attribute Order

As in most SQL implementations, attribute order is relevant in relations and in the result of expressions. This property is significant primarily for set operators, which as mentioned above do not consider attribute names. For example, if we take the \union of relations R(A,B) and S(B,A), the result contains two columns:

(1) The union of the A values in R and the B values in S.

(2) The union of the B values in R and the A values in S.

A good practice is to use the \rename operator to enforce matching schemas on R and S before applying the \union.

E. Error Messages

Error messages in response to ill-formed RA expressions may not be especially meaningful. Recall that RA translates relational algebra expressions into SQL queries. Often an incorrect RA expression simply results in incorrect SQL queries. In these cases, RA just passes back the error messages from the underlying DBMS, without attempting to create RA-specific messages.

You have learned the fundamentals of RA.

Elcric Otto Circle

--> --> -->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"

XML DTD Overview

noreply@blogger.com (Ron Tinnel) — Sun, 30 Oct 2011 23:30:00 +0000

XML DTD OVERVIEW

REVISED: Sunday, March 3, 2013

You will receive an introduction to XML DTD.

I. XML DTD OVERVIEW

XML "document type definition" (DTD). The DTD defines the elements that may be included in your document, what attributes these elements have, and the ordering and nesting of the elements. There are two ways to connect a DTD with the content of an XML file:

External DTD: You can put the DTD in a separate file from the XML file, and refer to it using a line at the beginning of the XML file. The advantage of this method is that many XML files can all refer to the same DTD.

Internal DTD: You can put the DTD inside the declaration at the front of the XML file. The advantage of an internal DTD is that the file can be validated by itself, without reference to any external files.

A. RULES FOR WELL FORMED XML

1. There must be exactly one top level element.

2. All opening tags bust be closed.

3. All elements are properly nested; i.e., there are no interleaved elements.

4. Attribute values must be enclosed in single or double quotes.

B. DTD

Here is a DTD:

<!DOCTYPE A [
<!ELEMENT A (B+, C)>
<!ELEMENT B (#PCDATA)>
<!ELEMENT C (B?, D)>
<!ELEMENT D (#PCDATA)>
]>

According to the DTD, an A element has within it one or more B subelements, and then a C element.

Within the C element is zero or one B elements followed by exactly one D element.

In terms of regular expressions, the tag sequences we can see are:

A (B /B)(B /B)* C (D /D | B /B D /D) /C /A.

Some text may appear between each B-/B pair and each D-/D pair, but text may not appear elsewhere.

C. XML

An XML document contains the following portion:

<EMP name = "Kermit">

    <ADDR>123 Sesame St.</ADDR>
    <PHONE type = "cell">555-1212</PHONE>
</EMP>

The XML must follow two rules:

1. A #REQUIRED attribute must appear in every element.

2. An attribute can have types CDATA, ID, or IDREF(S), but not #PCDATA.

D.  XML DTD

Here is an XML DTD:

<!DOCTYPE meal [

    <!ELEMENT meal (person*,food*,eats*)>
    <!ELEMENT person EMPTY>
    <!ELEMENT food EMPTY>
    <!ELEMENT eats EMPTY>
    <!ATTLIST person name ID #REQUIRED>
    <!ATTLIST food name ID #REQUIRED>
    <!ATTLIST eats diner IDREF #REQUIRED dish IDREF #REQUIRED>
]>

Focus on the ID and IDREF attributes.

A valid document needs to have unique values across ID attributes.

An IDREF attribute can refer to any existing ID attribute value.

E.  XML

An XML document contains the following portion:

<INFO>

         <ADDR>101 Maple St.</ADDR>
         <PHONE>555-1212</PHONE>
         <PHONE>555-4567</PHONE>
</INFO>

In the XML snippet, the info element has one address subelement and two phone subelements, in that order.

In the DTD the list of components for INFO must include ADDR, ADDR*, ADDR+,or ADDR? followed by PHONE* or PHONE+.

Interspersed with these may be any elements that are not required to appear-- that is, any components with a ? or *.

We might also have components like NAME* or MANAGER? at any point in the list.

F.  XML SCHEMA SPECIFICATION

Study the following XML Schema specification:

<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">

  <xs:element name="person">
    <xs:complexType>
      <xs:sequence>
        <xs:element name="fname" type="xs:string"/>
        <xs:element name="initial" type="xs:string"
            minOccurs="0"/>
        <xs:element name="lname" type="xs:string"/>
        <xs:element name="address" type="xs:string"
            maxOccurs="2"/>
        <xs:choice>
          <xs:element name="major" type="xs:string"/>
          <xs:element name="minor" type="xs:string"
              minOccurs="2" maxOccurs="2"/>
        </xs:choice>
      </xs:sequence>
    </xs:complexType>
  </xs:element>
</xs:schema>

This question deals with the xs:element, xs:sequence, and xs:choice elements in XML Schema.

In order for XML to be valid according to the specified schema:

The elements contained in a sequence must appear in exactly the same order as specified in the xs:sequence.

Exactly one of the elements contained in an xs:choice must appear.

If an element specifies a minOccurs attribute, the XML must contain at least thatmany instances of the element.

If an element specifies a maxOccurs attribute, the XML must not contain more thanthat many instances of the element.

If minOccurs and maxOccurs are not specified, their default value is 1.

Elements not defined as a part of a sequence or choice cannot occur inside the corresponding xs:sequence and xs:choice.

The given schema specifies the following constraints:

The "fname", "initial", "lname", and "address" elements must occur in that sequennce.

The "initial" element is optional due to its minOccurs value being 0.

The "address" element can occur either 1 or 2 times due to its maxOccurs value being 2.

After the "address" element, either exactly one "major" element or exactly 2 "minor" elements can occur, but not both.

Elements not defined as a part of this schema specification are not allowed to occur as a part of the "person" element.

Here is an example of valid XML for this schema:

<person>

<fname>John</fname>

    <initial>Q</initial>
    <lname>Public</lname>
    <address>123 Public Avenue</address>
    <address>Seattle, WA 98001</address>
    <major>Computer Science</major>
 </person>

You will have received an introduction to XML DTD, enjoy!

Elcric Otto Circle

-->

-->

-->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"

XML SCHEMA

noreply@blogger.com (Ron Tinnel) — Wed, 19 Oct 2011 22:51:00 +0000

XML SCHEMA

REVISED: Sunday, March 3, 2013

You will learn the fundamentals of XML Schema.

I. INTRODUCTION TO XML SCHEMA (XSD)

XML Schemas are themselves XML documents. XML Schemas provide an "Object Oriented" approach to defining the format of an XML document.

XML Schemas provide us with a way to give content specific specifications to our XML data.

Validating XML Parser checks to see if the data specifications are met.

Like "Document Type Definitions" (DTD's) XML Schema can specify elements, attributes, nesting, ordering, and #occurrences.

In addition we can specify data types, keys, (typed) pointers, and much more.

XSD is written in XML.

XSD's are in a separate file.

We work with a data file and a Schema file.

Four things in Schema are not present in DTD's:

1. Typed values.

2. Key declarations.

3. References.

4. Occurrence constraints.

You have learned the fundamentals of XML Schema.

Elcric Otto Circle

-->

-->

-->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"

XML

noreply@blogger.com (Ron Tinnel) — Wed, 19 Oct 2011 22:44:00 +0000

XML

REVISED: Sunday, March 3, 2013

You will learn the fundamentals of XML.

I. WELL FORMED XML

The Extensible Markup Language (XML), is well formed when it has:

A. Single root elements.

B. Properly nested matched tags.

C. Unique attributes within elements.

You have more flexibility and ease of change with well formed XML.

II. VALID XML

Adheres to basic structural requirements and content-specific specifications.

Two languages, Document Type Descriptors (DTDs) and XML Schema Descriptions (XSDs) are used to type the XML data and make it valid XML.

It is possible for the specifications to become larger than the document itself.

III. DTDs and XSDs

A. BENEFITS OF USING

Describes the structure of the data.

Provide the benefits of strongly typed data.

Grammar type language for specifying elements, attributes, nesting, ordering, and # occurrences.

Programs that use them, and CSS/XSL, can assume structure.

Specification language for data exchanges.

Documentation for data exchange.

B. BENEFITS OF NOT USING

Provide the benefits of no typing of data.

Flexibility

Ease of change

DTDs can be messy if the documents are irregular.

Specifications can become larger then the document itself.

IV. IDs & IDREFs

IDs and IDREFs help you establish pointers within a document.

You have learned the basic fundamentals of XML.

Elcric Otto Circle

-->

-->

-->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"

INTRODUCTION TO DATABASES

noreply@blogger.com (Ron Tinnel) — Wed, 19 Oct 2011 20:53:00 +0000

INTRODUCTION TO DATABASES

REVISED: Sunday, March 3, 2013

You will receive an introduction to databases.

I. INTRODUCTION TO DATABASES

A database is a set of named relations or tables. Each relation has a set of named attributes or columns. Each tupple or row has a value for each attribute. Each attribute has a type or domain.

A. TERMINOLOGY

1. Schema

Schema is the structural description of the relations in a database.

2. Instance

Instance is the actual contents of a database at a given point in time.

3. Relations

Relations are tables.

4. Attributes

Attributes are columns.

5. Tuples

Tuples are rows.

6. Types

Types are domains.

7. Null

Null is a special value for unknown or undefined.

8. Key

Key is a unique attribute in each tuple or set of attributes whose combined values are unique.

9. Ad-hoc queries

Ad-hoc queries are questions you did not think of in advance.

10. Queries

Queries return relations.

11. Compositionality

Compositionality is the ability to run a query over the results of a previous query.

12. Query languages

Query languages include SQL and Relational Algebra.

13. XML

XML is the Extensible Markup Language (XML) was designed originally for exchanging data on the Internet. XML basic construct consists of nested tagged elements, attributes, and text. Data can be stored in relational databases or XML. A parser can be used to determine if the XML is well formed.

Well formed XML has:

a. Single root elements.

b. Properly nested matched tags.

c. Unique attributes within elements.

Parsed XML can be accessed by Document Object Model (DOM) and in streams by SAX.

Rule based languages such as Cascading Style Sheets (CSS) and Extensible Stylesheet Language (XSL) can be used to display XML as HTML.

You have received an introduction to databases, enjoy!

Elcric Otto Circle

-->

-->

-->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"