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

constraint databases: Promising Technology or Just Intellectual Exercise?

constraints 1997年第1期2卷 35-44页

作者： Brodsky, Alexander Dept. Info. and Software Syst. Eng. Sch. of Info. Technol. and Eng. George Mason University Fairfax VA 22030-4444 United States

This paper describes the state of constraint databases (CDBs), a young discipline at the intersection of Database Management, constraint Programming, Computational Geometry and Operations Research. As in constraint Logic Programming, constraints in CDBs are a first class data type, and can play many modeling roles including spatial and temporal behavior, complex design requirements, and partial and incomplete information, for which existing databases have proven inadequate. We motivate the importance of CDBs, outline the work in the area that has been done, the current trends, and future directions and challenges. We briefly discuss (1) constraint modeling, canonical forms and algebras, (2) data models and query languages, (3) indexing and approximation-based filtering, (4) constraint algebra algorithms and global optimization, and (5) systems and case studies. We argue that CDBs are a promising technology that will impact many important application realms, and furthermore have the potential to be integrated into future database systems, and operations research and constraint programming tools.

关键词： constraint databases constraint programming constraints databases

来源：评论

学校读者我要写书评

暂无评论

Uniform generation in spatial constraint databases and applications

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2006年第4期72卷 576-591页

作者： Gross-Amblard, David de Rougemont, Michel Conservatoire Natl Arts & Metiers Equipe Vertigo Lab CEDRIC Special Informat CC 432 F-75141 Paris 03 France Univ Paris 02 F-91405 Orsay France Univ Paris 11 LRI F-91405 Orsay France

We study the efficient approximation of queries in linear constraint databases using sampling techniques. We define the notion of an almost uniform generator for a generalized relation and extend the classical generator of Dyer, Frieze and Karman for convex sets to the union and the projection of relations. For the intersection and the difference, we give sufficient conditions for the existence of such generators. We show how such generators give relative estimations of the volume and approximations of generalized relations as the composition of convex hulls obtained from the samples. (C) 2005 Elsevier Inc. All rights reserved.

关键词： constraint databases approximation estimator generator sampling volume dimension

来源：评论

学校读者我要写书评

暂无评论

Using constraint Programming in Selection Operators for constraint databases

引用

EXPERT SYSTEMS WITH APPLICATIONS 2014年第15期41卷 6773-6785页

作者： Teresa Gomez-Lopez, Maria Gasca, Rafael M. Univ Seville Dept Languages & Comp Syst Seville Spain

constraint databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). Commercial database management systems allow the storage and efficient retrieval of classic data, but for complex data a made-to-measure solution combined with expert systems for each type of problem are necessary. Therefore, in the same way as commercial solutions of relational databases permit storing and querying classic data, we propose an extension of the Selection Operator for complex data stored, and an extension of SQL language for the case where both classic and constraint data need to be managed. This extension shields the user from unnecessary details on how the information is stored and how the queries are evaluated, thereby enlarging the capacity of expressiveness for any commercial database management system. In order to minimize the selection time, a set of strategies have been proposed, which combine the advantages of relational algebra and constraint data representation. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Complex data Optimal query evaluation Selection Operator constraint databases constraint Programming

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient evaluation of specific queries in constraint databases

引用

INFORMATION PROCESSING LETTERS 2011年第19期111卷 941-944页

作者： Grimson, Rafael Heintz, Joos Kuijpers, Bart Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Comp RA-1428 Buenos Aires DF Argentina Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Matemat RA-1428 Buenos Aires DF Argentina Consejo Nacl Invest Cient & Tecn RA-1428 Buenos Aires DF Argentina Univ Cantabria Fac Ciencias Dept Matemat Estadist & Comp Santander 39071 Spain Hasselt Univ Database & Theoret Comp Sci Res Grp B-3590 Diepenbeek Belgium

Let F(1),...,F(s) is an element of R[X(1),...,X(n)] be polynomials of degree at most d, and suppose that F(1),...,F(s) are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of R(n) defined by F(1),...,F(s). For any point x is an element of R(n), we consider the task of determining the signs of the values F(1)(x),...,F(s)(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F1,...,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size s(O(L+n)) which allows the evaluation of the sign condition query using only (Ln)(O(1)) log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal. By the way, we show that the point location query can be evaluated using d(O(n)) log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F(1),...,F(s) belong to Z[X(1),...,X(n)] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F(1),...,F(s). (C) 2011 Elsevier B.V. All rights reserved.

关键词： constraint databases Query evaluation Computational complexity

来源：评论

学校读者我要写书评

暂无评论

On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases

引用

THEORETICAL COMPUTER SCIENCE 2005年第1期336卷 125-151页

作者： Geerts, F Kuijpers, B Limburgs Univ Ctr Dept WNI Dept Math Phys & Comp Sci B-3590 Diepenbeek Belgium Helsinki Inst Informat Technol Basic Res Unit Helsinki Finland

The formalism of constraint databases, in which possibly infinite data sets are described by Boolean combinations of polynomial inequality and equality constraints, has its main application area in spatial databases. The standard query language for polynomial constraint databases is first-order logic over the reals. Because of the limited expressive power of this logic with respect to queries that are important in spatial data base applications, various extensions have been introduced. We study extensions of first-order logic with different types of transitive-closure operators and we are in particular interested in deciding the termination of the evaluation of queries expressible in these transitive-closure logics. lt turns out that termination is undecidable in general. However, we show that the termination of the transitive closure of a continuous function graph in the two-dimensional plane, viewed as a binary relation over the reals, is decidable, and even expressible in first-order logic over the reals. Based on this result, we identify a particular transitive-closure logic for which termination of query evaluation is decidable and which is more expressive than first-order logic over the reals. Furthermore, we can define a guarded fragment in which exactly the terminating queries of this language are expressible. (c) 2004 Elsevier B.V. All rights reserved.

关键词： data base theory constraint databases query languages query evaluation dynamical systems theory fixed points

来源：评论

学校读者我要写书评

暂无评论

On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases

On the decidability of termination of query evaluation in tr...

引用

9th International Conference on Database Theory (ICDT)

作者： Geerts, F Kuijpers, B Limburgs Univ Ctr Dept WNI Dept Math Phys & Comp Sci B-3590 Diepenbeek Belgium Helsinki Inst Informat Technol Basic Res Unit Helsinki Finland

关键词： data base theory constraint databases query languages query evaluation dynamical systems theory fixed points

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

IMPROVING THE DETERMINATION OF MINIMAL HITTING SETS IN MODEL-BASED DIAGNOSIS USING constraint databases

引用

IFAC Proceedings Volumes 2006年第13期39卷 1509-1514页

作者： M.T. Gómez-López R.M. Gasca C. del Valle Escuela Técnica y Superior de Ingeniería Informática de Sevilla Spain

In model-based diagnosis, minimal hitting sets are usually used to identify which components may fail in a system. This work presents a set of algorithms to improve the determination of all Minimal Hitting Sets. Our proposal uses the minimal conflict sets to obtain, in an efficient way, the diagnosis of a system. The improvement consists of three algorithms which analyse only the relevant options. This proposal builds an equivalent system in order to obtain all minimal hitting sets depending on the location of the sensors. At the same time, all the information of the process is stored in a constraint Database, keeping the information persistent and recoverable. Some empirical results are presented in order to show how the proposal improves the process in order to obtain all minimal hitting sets.

关键词： Model-based Diagnosis constraint databases minimal hitting sets

来源：评论

学校读者我要写书评

暂无评论

On the expressiveness of linear-constraint query languages for spatial databases

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期254卷 423-463页

作者： Vandeurzen, L Gyssens, M Van Gucht, D Limburgs Univ Ctr Dept WNI B-3590 Diepenbeek Belgium Indiana Univ Dept Comp Sci Bloomington IN 47405 USA

The linear database model, in which semi-linear sets are the only geometric objects, has been identified as suitable for spatial database applications from both modeling expressiveness as query efficiency considerations. For querying linear databases, the language FO + linear has been proposed. In this paper, we examine the expressiveness of this language. First, we present a list of general queries expressible in FO + linear. In particular, we mention the dimension query, which in turn allows us to express several other interesting linear queries. Next, we show the non-expressibility in FO + linear of a whole class of linear queries that are related to sets not definable by linear formulae, a result which demonstrates the need for more expressive linear query languages. We present a method to extend FO + linear with operators in a sound way with respect to the linear queries expressible in FO + poly, and argue its validity by comparing it to another paradigm for enriching FO + linear. Whether any of the proposed extensions is complete for the linear queries definable in FO + poly remains open. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： spatial databases constraint databases linear constraints query languages expressiveness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：