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.

We investigate a generalization of the notion of XML security view introduced by Stoica and Farkas [17] and later refined by Fan et al. [8]. The model consists of access control policies specified over DTDs with XPath expression for data-dependent access control policies. We provide the notion of security views for characterizing information accessible to authorized users. This is a transformed (sanitized) DTD schema that can be used by users for query formulation and optimization. Then we show an algorithm to materialize "authorized" version of the document from the view and an algorithm to construct the view from an access control specification. We also propose a number of generalizations for security policies.

The rapid growth of IP centric communication in worldwide networks and the parallel mass deployment of fiber based WDM networks have propelled IP over WDM being considered as an eventual solution for bandwidth on demand to customers. Contemporary optical networks are, however, based on lightpath communication and a lightpath represents end-to-end optical circuits from source to destination. Light-trails are a generalization of lightpaths, such that multiple nodes along a trail can participate in time differentiated communication over the same established trail. Managing and setting up of light-trails in order to cater to IP centric traffic is a key to the success of IP centric communication at the optical layer. A light-trail represents an open optical path that allows multiple users to communicate without the need for switch reconfiguration at any user node, the light-trail itself being static. IP communication on the other hand represents a bursty traffic flow often characterized by spurts or bursts of data. The goal of this paper is to show how to create efficient light-trails based virtual topology for a given network traffic flow. We first describe a tree-shaped variant of light-trail, called the clustered light-trail (CLT) and then present optimization techniques for satisfying the given IP centric communication requirements, using the light-trails framework that is very flexible, despite being basically a static mechanism.

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.

Integrity constraints are an essential part of modern schema denition languages. They are useful for semantic specication, update consistency control, query optimization, information preservation, etc. In this paper, we propose UCM, a model of integrity constraints for XML that is both simple and expressive. Because it relies on a single notion of keys and foreign keys, the UCM model is easy to use and makes formal reasoning possible. Becauseitreliesonapowerful type system, the UCM model is expressive, capturing in a single framework the constraints found in relational databases, objectoriented schemas and XML DTDs. We study the problem of consistency of UCM constraints, the interaction between constraints and subtyping, and algorithms for implementing these constraints. Keywords XML, XML Schema, Integrity Constraints, Keys, Object Identity, Subtyping, Constraint Reasoning 1.

No abstract available.

We discuss the issue of adding aggregation to constraint databases. Previous work has shown that, in general, adding aggregates to constraint databases results in languages that are not closed. We show that by imposing a natural restriction, called variable independence (which is a generalization of the assumptions underlying the classical relational model of data) on the schema, we can guarantee that a restricted version of the language with aggregation is closed. We illustrate our approach in the context of linear constraint databases. 1 Introduction Constraint databases [KKR90] are a natural generalization of the relational model of data by allowing infinite relations that are finitely representable using constraints. Constraint databases find numerous applications in spatial [BJM93, BK95, BLLM95, PVdBVG94, VGVG95] and temporal databases [Cho94]. Generalizing aggregation operators to constraint databases has been identified as one of the most important open research issues in this...

We define a new aggregation operator P. for constraint databases that makesit possible tomeasure infinite subsets of the n-dimensional space defined by constraints.We show that it is well defined for real linear arithmetic constraints and integer linear arithmetic constraints together with periodicity constraints.We also show that relational algebra augmented with .LL. is closed in the real case and, under certain restrictions, in the integer case as well.

We propose an object-oriented data model that generalizes the relational, hierarchical, and network models. A database scheme in this model is a directed graph, whose leaves represent data and whose internal nodes represent connections among the data. Instances are constructed from objects, which have separate names and values. We define a logic for the model, and describe a nonprocedural query language that is based on the logic. We also describe an algebraic query language and show that it is equivalent to the logical language.

We discuss the relationship between constraint programming and database query languages. We show that bottom-up, efficient, declarative database programming can be combined with efficient constraint solving. The key intuition is that the generalization of a ground fact, or tuple, is a conjunction of constraints. We describe the basic Constraint Query Language design principles, and illustrate them with four different classes of constraints: Polynomial, rational order, equality, and Boolean constraints.

Parallel algorithms and computational complexity results are given for two problems; computing the relative complement of terms and antiunification. The concepts of antiunification and relative complement are useful for theorem proving, logic programming, and machine learning. The relative complement problem is shown to be NP-complete.>

Article Free Access Share on On the expressive power of logic programming languages with sets Author: Gabriel M. Kuper IBM T.J. Watson Research Laboratory, Yorktown Heights, New York IBM T.J. Watson Research Laboratory, Yorktown Heights, New YorkView Profile Authors Info & Claims PODS '88: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMarch 1988Pages 10–14https://doi.org/10.1145/308386.308397Published:01 March 1988Publication History 20citation217DownloadsMetricsTotal Citations20Total Downloads217Last 12 Months27Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Logic programming with sets Author: G. M. Kuper IBM T J Watson Research Laboratory, Yorktown Herghts, New York IBM T J Watson Research Laboratory, Yorktown Herghts, New YorkView Profile Authors Info & Claims PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsJune 1987 Pages 11–20https://doi.org/10.1145/28659.28661Online:01 June 1987Publication History 60citation282DownloadsMetricsTotal Citations60Total Downloads282Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on On the expressive power of the logical data model: prelimiary report Authors: Gabriel M. Kuper Department of Computer Science, Stanford University, Stanford, California Department of Computer Science, Stanford University, Stanford, CaliforniaView Profile , Moshe Y. Vardi Center for Study of Language and Information, Stanford University, Stanford, California Center for Study of Language and Information, Stanford University, Stanford, CaliforniaView Profile Authors Info & Claims SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of dataMay 1985 Pages 180–187https://doi.org/10.1145/318898.318915Published:01 May 1985Publication History 15citation293DownloadsMetricsTotal Citations15Total Downloads293Last 12 Months27Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We suggest a new approach to database updates, in which a database is treated as a collection of theories. We investigate two issues: a) equivalence of databases under update operations, b) simultaneous multiple update operations.

We propose here a data model that generalizes the relational, hierarchical, and network models. A database scheme in this model is a directed graph, where leaves represent data and internal nodes represent connections between the data. Instances are constructed from r-values, which constitute the data space, and l-values, which constitute the address space. We define a logic for the model, and describe a non-procedural quary language that is based on the logic. Finally, we describe an algebraic query language and show that it is equivalent to the logical language.

System/U is a universal relation database system under development at Standford University which uses the language C on UNIX. The system is intended to test the use of the universal view, in which the entire database is seen as one relation. This paper describes the theory behind System/U, in particular the theory of maximal objects and the connection between a set of attributes. We also describe the implementation of the DDL (Data Description Language) and the DML (Data Manipulation Language), and discuss in detail how the DDL finds maximal objects and how the DML determines the connection between the attributes that appear in a query.