|
|
Technical Report TR530:
Adding a Path Connectedness Operator to FO + poly (linear)
Chris Giannella and Dirk Van Gucht
Unknown Date, 31 pages
[Revised December, 2000]
- Abstract:
-
In the constraint database community, FO+poly and FO+linear have been proposed as foundations for spatial database query languages. One of the strengths of this approach is that these languages are a clean and natural generalization of Codd's relational model to a spatial setting. As a result, rigorous mathematical study of their expressiveness and complexity can be carried out.
Along this line, important geometric queries involving connectivity have been shown to be inexpressible in FO+poly and FO+linear. To address this problem, we extend both languages with a parameterized path-connectivity predicate, Pconn. We show that: FO+linear+Pconn and FO+poly+Pconn-3D are closed and have PTIME data complexity. We also examine the expressiveness of FO+poly+Pconn and FO+linear+Pconn and show that parity and transitive closure are expressible in each.
- Available as:
-
There is help available
if you want further information about the available file formats and
software to display and print these files. Return to the Technical Report Index
|
