Loading...
Please wait, while we are loading the content...
Similar Documents
Dense-order constraint databases (extended abstract) (1995).
| Content Provider | CiteSeerX |
|---|---|
| Author | Grumbach, Stéphane Su, Jianwen |
| Abstract | We consider infinite databases which admit a finite representation in terms of dense-order constraints. We study the complexity and the expressive power of various query languages over dense order constraint databases, allowing order, addition, recursion, or nested sets. We provide in particular an exact characterization of the class of dense order queries computable in PTIME (data complexity). We also prove that region and graph connectivity queries are not definable with linear constraints. We then investigate complex object models for constraint databases. Complex objects are fundamental to deal with pointsets as first-class citizens. We introduce an active domain semantics, and show that in terms of complexity and expressive power, the characterizations of the calculus for constraint complex objects are similar to the case of the classical complex object calculus. |
| File Format | |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dense-order Constraint Database Extended Abstract Expressive Power Exact Characterization Constraint Database Dense-order Constraint Finite Representation First-class Citizen Active Domain Semantics Nested Set Complex Object Model Data Complexity Linear Constraint Dense Order Constraint Database Graph Connectivity Query Constraint Complex Object Infinite Database Dense Order Query Classical Complex Object Calculus Various Query Complex Object |
| Content Type | Text |
