
%!psadobe 0

səhifə  1/3  tarix  26.09.2018  ölçüsü  134,5 Kb.   #70466 

JustInTime Databases and the WorldWide Web
Ellen Spertus
Mills College
5000 MacArthur Blvd.
Oakland, CA 94613 USA
+1 5104302011
spertus@mills.edu
Lynn Andrea Stein
MIT AI Lab
545 Technology Square
Cambridge, MA 02139 USA
+1 6172532663
las@ai.mit.edu
1.ABSTRACT It is not always possible or practical to store very large data sets in a relational database. For example, in a rapidly changing largescale environment with distributed control, such as the WorldWide Web, a strict relational approach is not feasible. Nevertheless, it is desirable for a user to be able to make SQL queries on the entire data set, because SQL is well known, supported, and understood. We introduce “JustInTime Databases”, which allow the user to query the entire data set as though it were in a relational database. The underlying engine brings data into the relational database only when it is required by user queries. We describe how “JustInTime Databases” are implemented, using the WorldWide Web as an example. 1.1Keywords
Semistructured information, Web, relational databases, SQL, federated databases, Internet
2.INTRODUCTION 2.1Motivation
With the rise of federated databases comes the need to query very large, heterogeneous, distributed sets of readonly documents. Relational databases provide a powerful abstraction for manipulating data. The division of data into relations helps users comprehend the data and allows them to specify queries in Structured Query Language (SQL). This need to structure information is greatest when a data set is very large; however, traditional database management systems require that the entire data set be stored in a relational database, which is not always possible.
Although not usually classified as such, the WorldWide Web can be seen as a federated database. Specifically, it is a very large distributed collection of documents, composed of a number of different types of semistructured information. Because of the Web’s size, dispersion, and flux, it would be impossible to store the entire Web in a relational database.
We introduce “JustInTime Databases”, which provide the user with the illusion that an entire massive data set is in a local relational database. In reality, data is retrieved or computed only as needed. This allows the benefits of the relational database model to be obtained even when it is impractical or impossible to actually store all the data in a relational database. We provide algorithms for implementing JustInTime Databases, using the Web as an example.
2.2Overview
A JustInTime Database specification consists of:

a relational database schema, which is first used to define tables in an underlying locallystored traditional relational database management system (RDBMS)

a set of functions for instantiating complete table rows, given values for a subset of columns
When the user issues a query on a JIT database, the JIT interpreter does the following:

Determines what data must be filled into the local database in order to answer the query, computing and inserting the data if it is not already present.

Passes the original query to the underlying RDBMS, returning the answer to the user.
The effect of the JIT interpreter is to provide the user with the illusion that the entire data set is stored in the relational database. In actuality, the relational database serves as a cache on the data set, containing only the data needed to answer queries that have been made.
The next section contains definitions useful for describing the behavior of the system more precisely, followed by the algorithms used to determine what information must be inserted into the actual relational database. We then discuss a JIT database for the Web. We then conclude with a discussion of the significance of this work and its relation to other research.
3.DEFINITIONS 3.1Defining columns
A table in a relational database consists of a set of columns. We call a column c a defining column if an executable function exists that maps any value of c to all sets of legal values for the other columns. This function may not refer to the table itself (e.g., do “select” queries).
For example, if a table squares contains two columns, base and square, representing an integer and its square, respectively, both columns would be defining columns. (Squares and other tables used in this section are shown in Figure 1. Throughout this paper, table names appear in small caps, column names in bold face, and function names in italics.) If the value of base is known, the legal value for square can be easily computed. If the value of square is known, the legal associated values for base can be computed. If square is zero, there will be precisely one legal value for base: zero. If square is the square of any other integer, there will be two legal values for base, the positive and negative square roots. If square is not the square of an integer, there will be no legal values for base. In any case, knowing the value of either column determines the legal values for the other column.
On the other hand, a table election (Figure 1) whose two columns voter or ballot would have no defining columns if it described a secret ballot. Knowing the identity of a voter or the contents of a ballot would not allow determination of the other column value.
3.2Fetch
We define an imperative operator fetch that, when given the values of one or more defining columns, augments a table by adding all legal relations having the given values. The syntax of the basic form of fetch is:
fetch tableName(col0=value0, … colN = valueN)
where tableName is the name of a table, cole0 through colN are defining columns, and value0 through valueN are, respectively, legal values. For example, consider the following instance:
fetch squares(base=4)
which would add the relation {base=4, square=16} to table squares, unless it was already present. It is permissible that, as a side effect, additional relations may be added to squares or other tables.

Squares



Election


Primes

base

square


voter

ballot


prime

0

0


Alice

yes


2

1

1


Bob

no


3

1

1


Carol

yes


5

2

4


David

yes


7

Figure 1: Tables squares, election, and primes, used as examples
fetchStatement

=

“fetch” “(” fetchList “)”



( “from ”



(“where ” logicExpression)?



(“group by ” columnList)?



(“having ” logicExpression)? )?




fetchList

=

namedArgument (“, ” namedArgument)*




namedArgument

=

“=” fetchExpression




fetchExpression

=



expression “” expression
expression “&” expression
expression

Figure 2: The grammar for fetch statements. Nonterminals tableList, logicExpression, columnList, orderList, and expression are defined elsewhere [15] and have the same meanings as the corresponding SQL nonterminals.
The full syntax for the fetch statement is shown in Figure 2. An optional “from” clause can be used to specify a set of values for a defining column. For example, if table Primes (Figure 1) has a column number containing the prime numbers less than 1000, the following statement would insert into Squares the primes between ten and fifty and their squares (unless they were already in the table):
fetch squares(base=p.number)
from primes p
where (p.number > 10 and p.number <50)
Within the fetch statement, a defined column can be assigned a single value, a conjunction, or a disjunction. For example, the following table would augment squares with the squares of the numbers from one to five:
fetch squares(base=12345)
The following statement would add no entries to squares:
fetch squares(base=1&2)
since no value for square is associated with base values of both one and two. A conjunction that could augment Squares is:
fetch squares(base=2&2)
since there is a value for square (4) that is associated with both base values.
Dostları ilə paylaş: 

