Methods and apparatus for generating and using safe...

Details Methods and apparatus for generating and using safe... Methods and apparatus for generating and using safe...

1999-05-28

2001-03-13

Alam, Hosain T. (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06202063

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to database management systems and, more particularly, to methods and apparatus for generating and using safe constraint queries in accordance with relational and spatial database management systems.
BACKGROUND OF THE INVENTION
The power of classical query languages is linked to the fact that they express a restricted class of declarative programs. The class of semantic objects expressible through queries in the relational calculus is limited in a number of helpful ways, for example, each such query is polynomial-time computable. Although relational calculus queries may not return finite results, a natural subclass of the relational calculus does, namely, the class of range-restricted queries. This class gives guarantees of finite output and is complete in that it captures all relational calculus queries whose outputs are always finite, i.e., safe queries. The class of range-restricted queries provides an effective syntax for safe queries, as every safe query is equivalent to a range-restricted one. However, the question of whether a relational calculus query is safe or not is known to be undecidable in conventional database systems.
The relational theory on which these results are based deals only with pure relational queries, that is, those containing no interpreted predicates. Practical query languages, in contrast, contain interpreted functions such as + and *. The resulting queries, then, make use of the domain semantics, rather than being independent of them as are pure relational queries. For example, if the underlying structure is the field of real numbers
, +, *, 0,1, <
, the extension of relational calculus is achieved by using polynomial (in)equalities. For example, the query &phgr;(x, y)≡∃z·R (x, z)
R(z, y)
x
2
+y
2
=z defines a subset of the self-join operation with the condition that in joinable tuples (x, z) and (z, y), z must be the sum of squares of x and y. A natural question, then, is what sort of restrictions still apply to queries given with interpreted structure.
A problem related to safety is that of state-safety, that is, for a query and a database, determine if the output is finite. Unlike the safety problem, which are undecidable, the state-safety problem is decidable for some domains, such as natural numbers with the order relation. However, there are interpreted structures (even with decidable first-order theory) for which this problem is undecidable and for which the class of safe queries cannot be described syntactically.
Accordingly, there is a need for methods and apparatus for generating relational calculus queries in the context of certain types of database systems that are considered safe and thus solve the issues of undecidability and the lack of effective syntax.
SUMMARY OF THE INVENTION
The present invention provides for methods and apparatus for ensuring that queries presented to a database are safe thus providing solutions to both the undecidability and lack of effective syntax issues mentioned above. In a broad aspect of the invention, a method for use in a database system includes obtaining an original query entered by a user. The invention then provides for pre-processing the query before submittal to a database engine associated with the database system wherein a result of the pre-processing operation is to ensure that a query provided to the engine is safe. As mentioned above, safety has a different meaning depending on the application. For example, safety may include ensuring that a query will return an output with finite results or it may include ensuring that certain geometric properties in the query are preserved in the output.
In a first embodiment of the invention, the pre-processing step includes automatically modifying the original query to ensure a return of finite results from the database by inserting at least one range-restriction in the original query. The range-restriction specifies an upper bound on the results to be returned by the database as a set of roots of polynomials with coefficients coming from an active domain of the database and a finite set of constants. Preferably, the range-restriction is inserted regardless of whether the original query would have returned a finite result.
In a second embodiment, the original query is a conjunctive query and the pre-processing step includes analyzing the original conjunctive query to determine if the original conjunctive query would return finite results from the database. Further, the pre-processing step includes prompting the user to restrict the original conjunctive query, if the original query would not return finite results, by inserting at least one range-restriction in the original query. Again, the range-restriction specifies an upper bound on the results to be returned by the database as a set of roots of polynomials with coefficients coming from an active domain of the database and a finite set of constants.
In a third embodiment, the original query contains at least one geometric property and the pre-processing step includes coding the original query with effective syntax to ensure preservation of the at least one geometric property in results returned from the database. Thus, whenever a query includes a certain type of geometric object, the result returned by the database engine will include only that type of geometric object.
The invention applies to the standard relational calculus with interpreted functions on finite structures; we then applied these results to get structural restrictions on the behavior of queries in the constraint database model of Kanellakis, Kuper and Revesz, “Constraint Query Languages,” Journal of Computer and System sciences, 51 (1995), 26-52 (extended abstract in PODS'90, pp. 299-313). This model is motivated by new applications involving spatial and temporal data, which require storing and querying infinite collections. It extends the relational model by means of “generalized relations.” These are possibly infinite sets defined by quantifier-free first-order formulae in the language of some underlying infinite structure M=
U,&OHgr;
. Here U is a set (assumed to be infinite), and &OHgr; is a signature that consists of a number of interpreted functions and predicates over U. For example, in spatial applications, M is usually the real field
, +, *, 0,1, <
, and generalized relations describe sets in
n
.
A database given by a quantifier-free formula &agr;(x
1
, . . . ,x
n
) in the language of &OHgr; defines a (possibly infinite) subset of U
n
given by D
&agr;
={{right arrow over (&agr;)} ∈ U
n
| M
&agr; ({right arrow over (&agr;)})}. Such databases are called finitely representable, as the formula &agr; provides a finitary means fox representing an infinite set. For example, if &agr;(x, y)≡(x
2
+y
2
≦1), then D
&agr;
is the circle of radius
1
with the center in (0, 0).
Relational calculus can be extended in a straightforward manner to this model, by incorporating atomic formulas which are &OHgr;-constraints, that is, atomic &OHgr;-formulae. For example, &phgr;(x, y)≡(D (x, z)
y=x
2
) is a first-order query which, on D
&agr;
defined above, returns the intersection of the circle with the graph of the function y=x
2
.
For the constraint model, the invention enforces safety in the sense of the preservation of restricted geometric classes of databases within powerful constraint query languages. In particular, we deal with enforcing that polynomial constraint queries preserve linear constraint databases and subclasses thereof. Linear constraints are used to represent spatial data in many applications. Linear constraints have several advantages over polynomial: the quantifier-elimination procedure is less costly, and numerous algorithms have been developed to deal with figures represented by linear constraints. At the same time, the extension of relational calculus with linear constraints has severely limited power as a query language. Thus, it is natural to use a mo

Affiliated with

Also associated with

Rating

Methods and apparatus for generating and using safe... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for generating and using safe..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for generating and using safe... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2503193