| CS-1990-45 | ||||
|---|---|---|---|---|
| Title | Reasoning About Equations and Functional Dependencies on Complex Objects | |||
| Authors | M.F. van Bommel and G.E. Weddell | |||
| Abstract |
Virtually
all
semantic
or
object-oriented
data
models
assume
objects
have
an
identity
separate
from
any
of
their
parts,
and
allow
users
to
define
complex
object
types
in
which
part
values
may
be
any
other
objects.
This
often
results
in
a
choice
of
query
language
in
which
a
user
can
express
navigating
from
one
object
to
another
by
following
a
property
value
path.
In this paper, we consider a constraint language in which one may express equations and functional dependencies over complex object types. The language is novel in the sense that component attributes of individual constraints may correspond to property paths. The kind of equations we consider are also important since they are a natural abstraction of the class of conjunctive queries for query languages which support property value navigation. In our introductory comments, we give an example of such a query, and outline two applications of the constraint theory to problems relating to a choice of access plan for the query. We present a sound and complete axiomatization of the constraint language for the case in which interpretations are permitted to be infinite, where interpretations themselves correspond to a form of directed labeled graph. Although the implication problem for our form of equational constraint alone over arbitrary schema is undecidable, we present decision procedures for the implication problem for both kinds of constraints when the problem schema satisfies a stratification condition, and when all input functional dependencies are keys. | |||
| Report | Reasoning About Equations and Functional Dependencies on Complex Objects (DVI) | Reasoning About Equations and Functional Dependencies on Complex Objects (PDF) | ||