检索结果-内蒙古大学图书馆

First-order complete and computationally complete query languages for spatio-temporal databases

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2008年第2期9卷 1-51页

作者： Geerts, Floris Haesevoets, Sofie Kuijpers, Bart Univ Edinburgh Lab Fdn Comp Sci Edinburgh EH8 9LE Midlothian Scotland Hasselt Univ Theoret Comp Sci Grp B-3590 Diepenbeek Belgium

We address a fundamental question concerning spatio-temporal database systems: "What are exactly spatio-temporal queries?" We define spatio-temporal queries to be computable mappings that are also generic, meaning that the result of a query may only depend to a limited extent on the actual internal representation of the spatio-temporal data. Genericity is defined as invariance under groups of geometric transformations that preserve certain characteristics of spatio-temporal data (e. g., collinearity, distance, velocity, acceleration,...). These groups depend on the notions that are relevant in particular spatio-temporal database applications. These transformations also have the distinctive property that they respect the monotone and unidirectional nature of time. We investigate different genericity classes with respect to the constraint database model for spatio-temporal databases and we identify sound and complete languages for the first-order and the computable queries in these genericity classes. We distinguish between genericity determined by time-invariant transformations, genericity notions concerning physical quantities and genericity determined by time-dependent transformations.

关键词： design languages theory constraint databases moving objects query languages spatial databases spatio-temporal databases

来源：评论

学校读者我要写书评

暂无评论

constraint databases : First International Symposium, CDB 2004, Paris, France, June 12-13, 2004 : Proceedings 1

引用

丛书名： Lecture Notes in Computer Science 3074

2004年

作者： Kuijpers Bart. Revesz Peter

来源：评论

学校读者我要写书评

暂无评论

A representation independent language for planar spatial databases with Euclidean distance

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2007年第6期73卷 845-874页

作者： Kuper, Gabriel M. Su, Hanwen Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Univ Trent I-38050 Trento Italy

Linear constraint databases and query languages are appropriate for spatial database applications. Not only is the data model suitable for representing a large portion of spatial data such as in GIS systems, but there also exist efficient algorithms for the core operations in the query languages. An important limitation of linear constraints, however, is that they cannot model constructs such as Euclidean distance;extending such languages to include such constructs, without obtaining the full power of polynomial constraints has proven to be quite difficult. One approach to this problem, by Kuijpers, Kuper, Paredaens, and Vandeurzen, used the notion of Euclidean constructions with ruler and compass as the basis for a first order query language. While their language had the desired expressive power, the semantics are not really natural, due to its use of an ad hoc encoding. In this paper, we define a language over a similar class of databases, with more natural semantics. We show that this language captures a natural subclass, the representation independent queries of the first order language of Kuijpers, Kuper, Paredaens, and Vandeurzen. (c) 2006 Elsevier Inc. All rights reserved.

关键词： spatial databases constraint databases GIS database theory

来源：评论

学校读者我要写书评

暂无评论

First-order languages expressing constructible spatial database queries

引用

SIAM JOURNAL ON COMPUTING 2007年第6期36卷 1570-1599页

作者： Kuijpers, Bart Kuper, Gabriel Paredaens, Jan Vandeurzen, Luc Hasselt Univ Theoret Comp Sci Grp B-3590 Diepenbeek Belgium Trasnatl Univ Limburg B-3590 Diepenbeek Belgium Univ Trent Dipartimento Informat & Telecommunicaz I-38050 Trento Italy Univ Antwerp Dept Math & Comp Sci B-2020 Antwerp Belgium

The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints (FO + poly). For reasons of efficiency, this model is implemented with only linear polynomial constraints, but this limitation to linear polynomial constraints has severe implications on the expressive power of the query language. In particular, when used for modeling spatial data, important queries that involve Euclidean distance are not expressible. The aim of this paper is to identify a class of two-dimensional constraint databases and a query language within the constraint model that go beyond the linear model and allow the expression of queries concerning distance. We seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. We first present a programming language that captures exactly the first-order ruler-and-compass constructions that are expressible in a first-order language with real polynomial constraints. If this language is extended with a while operator, we obtain a language that is complete for all ruler-and-compass constructions in the plane. We then transform this language in a natural way into a query language on finite point databases, but this language turns out to have the same expressive power as FO + poly and is therefore too powerful for our purposes. We then consider a safe fragment of this language and use this to construct a query language that allows the expression of Euclidean distance without having the full power of FO + poly.

关键词： constraint databases real algebraic geometry first-order logic query languages ruler-and-compass constructions

来源：评论

学校读者我要写书评

暂无评论

Variable independence in constraint databases

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2003年第6期15卷 1422-1436页

作者： Chomicki, J Goldin, D Kuper, G Toman, D Univ Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA Univ Trent Dipartimento Informat & Telecomun Fac Sci I-38050 Trent Italy Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

In this paper, we study constraint databases with variable independence conditions (vics). Such databases occur naturally in the context of temporal and spatiotemporal database applications. Using computational geometry techniques, we show that variable independence is decidable for linear constraint databases, We also present a set of rules for inferring vics in relational algebra expressions. Using vics, we define a subset of relational algebra that is closed under restricted aggregation.

关键词： constraint databases aggregation closure integrity constraints spatiotemporal databases

来源：评论

学校读者我要写书评

暂无评论

Linearization and completeness results for terminating transitive closure queries on spatial databases

引用

SIAM JOURNAL ON COMPUTING 2006年第6期35卷 1386-1439页

作者： Geerts, F Kuijpers, B Van Den Bussche, J Hasselt Univ Theoret Comp Sci Grp B-3590 Diepenbeek Belgium Transnatl Univ Limburg B-3590 Diepenbeek Belgium

We study queries to spatial databases, where spatial data are modeled as semialgebraic sets, using the relational calculus with polynomial inequalities as a basic query language. We work with the extension of the relational calculus with terminating transitive closures. The main result is that this language can express the linearization of semialgebraic databases. We also show that the sublanguage with linear inequalities only can express all computable queries on semilinear databases. As a consequence of these results, we obtain a completeness result for topological queries on semialgebraic databases.

关键词： constraint databases real algebraic geometry transitive closure logics query languages

来源：评论

学校读者我要写书评

暂无评论

Generating queries with cardinality constraints for DBMS testing

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2006年第12期18卷 1721-1725页

作者： Bruno, Nicolas Chaudhuri, Surajit Thomas, Dilys Microsoft Corp Redmond WA 98052 USA Stanford Univ Stanford CA 94305 USA

Good testing coverage of novel database techniques, such as multidimensional histograms or changes in the execution engine, is a complex problem. In this work, we argue that this task requires generating query instances, not randomly, but based on a given set of constraints. Specifically, obtaining query instances that satisfy cardinality constraints on their subexpressions is an important challenge. We show that this problem is inherently hard, and develop heuristics that effectively find approximate solutions.

关键词： QUERYING (Computer science) constraint databases DATABASE management MULTIDIMENSIONAL databases HEURISTIC databases QUEUING theory DATABASE searching ELECTRONIC data processing

来源：评论

学校读者我要写书评

暂无评论

Paying down design debt with strategic refactoring

引用

COMPUTER 2006年第12期39卷 131-134页

作者： Neill, Colin J. Laplante, Phillip A. Penn State Univ Div Engn University Pk PA 16802 USA Penn State Univ Sch Grad Profess Studies University Pk PA 16802 USA

Our studies indicate that strategic refactoring using design patterns is the most effective way to repair decaying code for object-oriented (OO) systems. However, applying a pattern-based approach to legacy system rep... 详细信息

关键词： SOFTWARE refactoring ARCHITECTURAL design PATTERN recognition systems SOFTWARE patterns SYSTEMS software constraint databases constraint programming (Computer science) COMPUTER software

来源：评论

学校读者我要写书评

暂无评论

Tractable fragments of Presburger Arithmetic

引用

THEORY OF COMPUTING SYSTEMS 2005年第5期38卷 647-668页

作者： Subramani, K W Virginia Univ LDCSEE Morgantown WV 26506 USA

In this paper we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP) the program variables can assume arbitrary integral values, as opposed to the boolean values that are assumed by the variables of an instance of QSAT. QIPs naturally represent two-person integer matrix games. The Quantified Integer Programming problem is PSPACE-hard in general, since the QSAT problem is PSPACE-complete. Quantified Integer Programming can be thought of as a restriction of Presburger Arithmetic, in that we allow only conjunctions of linear inequalities. We focus on analyzing various special cases of the general problem, with a view to discovering subclasses that are tractable. Subclasses of the general QIP problem are obtained by restricting either the constraint matrix or quantifier specification or both. We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time. We also establish the computational complexities of Oblivious strategy games and Clairvoyant strategy games.

关键词： COMPUTATIONAL-COMPLEXITY constraint databases DATALOG QUERIES FASTALGORITHMS TIME ALGORITHM 2 VARIABLES PROGRAMS FLOW

来源：评论

学校读者我要写书评

暂无评论

An incremental algorithm for DLO quantifier elimination via constraint propagation

引用

ARTIFICIAL INTELLIGENCE 2004年第1-2期160卷 173-190页

作者： Nykänen, M Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland

The first-order logical theory of dense linear order has long been known to admit quantifier elimination. This paper develops an explicit algorithm that yields an equivalent quantifier free form of its input formula. This algorithm performs existential quantifier elimination via constraint propagation. The result is computed incrementally using functional programming techniques. This approach may be of interest in implementing query languages for constraint databases. (C) 2004 Elsevier B.V. All rights reserved.

关键词： quantifier elimination constraint propagation constraint databases

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：