Abstract:
We consider the scheme of indefinite constraint databases proposed by
Koubarakis. This scheme can be used to represent indefinite information arising
in temporal, spatial and truly spatiotemporal applications. The main technical
problem that we address in this paper is the discovery of tractable classes of
databases and queries in this scheme. We start with the assumption that we have
a class of constraints C with satisfiability and variable elimination
problems that can be solved in PTIME. Under this assumption, we show that there
are several general classes of databases and queries for which query evaluation
can be done with PTIME data complexity. We then search for tractable instances
of C in the area of temporal and spatial constraints. Classes of
constraints with tractable satisfiability problems can be easily found in the
literature. The largest class that we consider is the class of Horn disjunctive
linear constraints over the rationals. Because variable elimination for Horn
disjunctive linear constraints cannot be done in PTIME, we try to discover
subclasses 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 the initial general results with C ranging
over the newly discovered tractable classes. Tractable query answering problems
for indefinite temporal and spatial constraint databases are identified in this
way.
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.