Abstract:
We start with the assumption that temporal and spatial knowledge
usually captured by constraint networks
can be represented and queried more effectively by using
the scheme of indefinite constraint databases.
Because query evaluation in this scheme is in general a hard
computational problem, we seek tractable instances of query evaluation.
We assume that we have a class of constraints
C with some reasonable computational and closure properties
(the computational properties of interest are that the satisfiability
problem and an appropriate version of the variable elimination problem for
C should be solvable in PTIME).
Under this assumption, we exhibit general classes
of indefinite constraint databases and first-order
modal queries for which query evaluation
can be done with PTIME data complexity.
We then search for tractable instances of C among the subclasses
of Horn disjunctive linear constraints over the rationals. From
previous research we know that the
satisfiability problem for Horn disjunctive linear constraints is
solvable in PTIME, but not the variable elimination problem.
Thus we try to discover subclasses of Horn disjunctive linear
constraints with tractable variable elimination problems.
The class of UTVPI^{\ne} constraints
is the largest class that we show to have this property.
Finally, we restate our general tractability results with C ranging
over the newly discovered tractable classes. Interesting
tractable query answering problems for indefinite temporal and spatial
constraint databases are identified in this way. We close our complexity
analysis by precisely outlining the frontier between tractable and possibly intractable
query answering problems
Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.