5th International Conference Prague, Czech Republic, January 11–13, 1995 Proceedings
Mobile and Wireless Computing is a new emerging computing paradigm posing many challenging data management problems. We provide a brief introduction to wireless technology, identify new research challenges and investigate their technical significance. New research problems emerge due to mobility of users, narrow wireless bandwidth and limitations of battery power.
A multidatabase system (MDBS) is a database system which integrates pre-existing databases, called component local database systems (LDBSs), to support global applications accessing data at more than one LDBS. An important research issue in MDBS is query optimization. The query optimization problem in MDBS is quite different from the case of distributed database system (DDBS) since, due to schema...
Producing optimal left-deep trees is known to be NP-complete for general join graphs and a quite complex cost function counting disk accesses for a special block-wise nested-loop join [2]. Independent of any cost function is the dynamic programming approach to join ordering. The number of alternatives this approach generates is known as well [5]. Further, it is known that for some cost functions —...
In this paper we study the expressive power of major nonmonotonic formalisms — among them circumscription, default logic, and autoepistemic logic — used as query languages over disjunctive databases. For this aim, we define the semantics of query expressions formulated in different nonmonotonic logics. The expressive power of the languages that we consider has been explored in the context of relational...
This paper introduces a unified solution to the problem of extending stratified DATALOG to express DB-complexity classes ranging from P to D P. The solution is based on (i) stratified negation as the core of a simple, declarative semantics for negation, (ii) the use of a “choice” construct to capture non-determinism of stable models (iii) the ability to bind a query execution to the complexity...
We develop a Kolmogorov complexity based tool to measure expressive power of query languages over finite structures. It works for sentences (i.e., boolean queries), and gives a meaningful definition of the expressive power of a query language in a single finite model. The notion of Kolmogorov expressive power of a boolean query language L in a finite model A is defined by considering two values:...
We investigate and compare two forms of recursion on sets for querying nested collections. The first one is called sri and it corresponds to sequential processing of data. The second one is called sru and it corresponds to data-parallel processing. A uniform first-order translation from sru into sri was known from previous work. The converse translation is by necessity more difficult and we have obtained...
This paper discusses three successively extending versions of a set theoretic Δ-language, as a prototype for “nested” data bases query language. Corresponding finite set operations (data base queries) may be realized in NLOGSPACE under representation of sets by extensional well-founded (acyclic) graphs. (In a previous work for another version of Δ-language an exact correspondence to PTIME-computability...
Two-phase locking is a standard method for managing concurrent transactions in database systems. In order to guarantee good recovery properties, two-phase locking should be strict, meaning that locks can be released only after the transaction's commit or abort. In this paper we show that even exclusive locks can be released immediately after the commit request has arrived, without sacrificing any...
We present here a unified transaction model for database systems with semantically rich operations. Based on the work in [SWY93], we develop constructive correctness criteria that encompass both serializability and failure atomicity in a uniform manner. As it turns out, an exact characterization of the class of prefix reducible schedules that was introduced for the simple read/write model in [AVA+94]...
Since the Two Phase Commitment (2PC) protocol is an essential component for Distributed Transaction Processing, needed in the commit process of each distributed transaction, a substantial effort has been invested in optimizing its performance. The Dynamic Two Phase Commitment (D2PC) protocol is an enhancement of the common (static) Tree Two Phase Commitment (T2PC) protocols. Unlike T2PC, with D2PC...
We investigate queries in the presence of external functions with arbitrary inputs and outputs (atomic values, sets, nested sets etc). We propose a new notion of domain independence for queries with external functions which, in contrast to previous work, can also be applied to query languages with fixpoints or other kinds of iterators. Next, we define two new notions of computable queries with external functions...
We study languages for manipulating partially ordered structures with duplicates (e.g. trees, lists). As a general framework, we consider the pomset (partially ordered multiset) datatype. We introduce an algebra for pomsets, which generalizes traditional algebras for (nested) sets, bags and lists. This paper is motivated by the study of the impact of different language primitives on the expressive...
The expressive power of the family of ILOG(−) languages is investigated. The languages are rule based, with value invention and stratified negation. The chosen semantics for value invention is based on Skolem functor terms. We show that, in presence of value invention, the whole expressive power is achieved using programs made of two strata, and that ILOG≠ (i.e., the class of programs with non-equality...
We present a model for deductive object oriented query languages with inheritance and overriding. In this model, we consider a DAG like dynamic isa hierarchy and we account for both value or attribute inheritance and method inheritance or code sharing. We show that these two types of inheritance can be treated uniformly within an elegant declarative setting. We then propose a novel semantics for the...
We propose a new formal semantics of active databases based on a transaction rewriting technique in the context of the relational model. A user defined transaction, which is viewed here as a sequence of atomic database updates forming a semantic unit, is translated by means of active rules into induced one(s). Those transactions embody active rule semantics which can be either immediate or deferred...