共查询到20条相似文献,搜索用时 0 毫秒
1.
Peter A. Boncz Martin L. Kersten 《The VLDB Journal The International Journal on Very Large Data Bases》1999,8(2):101-119
In query-intensive database application areas, like decision support and data mining, systems that use vertical fragmentation
have a significant performance advantage. In order to support relational or object oriented applications on top of such a
fragmented data model, a flexible yet powerful intermediate language is needed. This problem has been successfully tackled
in Monet, a modern extensible database kernel developed by our group. We focus on the design choices made in the Monet interpreter
language (MIL), its algebraic query language, and outline how its concept of tactical optimization enhances and simplifies
the optimization of complex queries. Finally, we summarize the experience gained in Monet by creating a highly efficient implementation
of MIL.
Received November 10, 1998 / Accepted March 22, 1999 相似文献
2.
Praveen Seshadri 《The VLDB Journal The International Journal on Very Large Data Bases》1998,7(3):130-140
The explosion in complex multimedia content makes it crucial for database systems to support such data efficiently. This
paper argues that the “blackbox” ADTs used in current object-relational systems inhibit their performance, thereby limiting
their use in emerging applications. Instead, the next generation of object-relational database systems should be based on
enhanced abstract data type (E-ADT) technology. An (E-ADT) can expose the semantics of its methods to the database system, thereby permitting advanced query optimizations. Fundamental architectural changes
are required to build a database system with E-ADTs; the added functionality should not compromise the modularity of data
types and the extensibility of the type system. The implementation issues have been explored through the development of E-ADTs
in Predator. Initial performance results demonstrate an order of magnitude in performance improvements.
Received January 1, 1998 / Accepted May 27, 1998 相似文献
3.
Summary. We set out a modal logic for reasoning about multilevel security of probabilistic systems. This logic contains expressions
for time, probability, and knowledge. Making use of the Halpern-Tuttle framework for reasoning about knowledge and probability,
we give a semantics for our logic and prove it is sound. We give two syntactic definitions of perfect multilevel security
and show that their semantic interpretations are equivalent to earlier, independently motivated characterizations. We also
discuss the relation between these characterizations of security and between their usefulness in security analysis. 相似文献
4.
MiniCon: A scalable algorithm for answering queries using views 总被引:5,自引:0,他引:5
Rachel Pottinger Alon Halevy 《The VLDB Journal The International Journal on Very Large Data Bases》2001,10(2-3):182-198
The problem of answering queries using views is to find efficient methods of answering a query using a set of previously
materialized views over the database, rather than accessing the database relations. The problem has received significant attention
because of its relevance to a wide variety of data management problems, such as data integration, query optimization, and
the maintenance of physical data independence. To date, the performance of proposed algorithms has received very little attention,
and in particular, their scale up in the presence of a large number of views is unknown. We first analyze two previous algorithms,
the bucket algorithm and the inverse-rules, and show their deficiencies. We then describe the MiniCon, a novel algorithm for
finding the maximally-contained rewriting of a conjunctive query using a set of conjunctive views. We present the first experimental
study of algorithms for answering queries using views. The study shows that the MiniCon scales up well and significantly outperforms
the previous algorithms. We describe an extension of the MiniCon to handle comparison predicates, and show its performance
experimentally. Finally, we describe how the MiniCon can be extended to the context of query optimization.
Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001 相似文献
5.
Steve Jones Shona McInnes Mark S. Staveley 《International Journal on Digital Libraries》1999,2(2-3):207-223
Online information repositories commonly provide keyword search facilities through textual query languages based on Boolean
logic. However, there is evidence to suggest that the syntactic demands of such languages can lead to user errors and adversely
affect the time that it takes users to form queries. Users also face difficulties because of the conflict in semantics between
AND and OR when used in Boolean logic and English language. Analysis of usage logs for the New Zealand Digital Library (NZDL)
show that few Boolean queries contain more than three terms, use of the intersection operator dominates and that query refinement
is common. We suggest that graphical query languages, in particular Venn-like diagrams, can alleviate the problems that users
experience when forming Boolean expressions with textual languages. A study of the utility of Venn diagrams for query specification
indicates that with little or no training users can interpret and form Venn-like diagrams in a consistent manner which accurately
correspond to Boolean expressions. We describe VQuery, a Venn-diagram based user interface to the New Zealand Digital Library
(NZDL). In a study which compared VQuery with a standard textual Boolean interface, users took significantly longer to form
queries and produced more erroneous queries when using VQuery. We discuss the implications of these results and suggest directions
for future work.
Received: 15 December 1997 / Revised: June 1999 相似文献
6.
A structured operational semantics for UML-statecharts 总被引:3,自引:0,他引:3
Michael von der Beeck 《Software and Systems Modeling》2002,1(2):130-141
The Unified Modeling Language (UML) has gained wide acceptance in very short time because of its variety of well-known and
intuitive graphical notations. However, this comes at the price of an unprecise and incomplete semantics definition. This
insufficiency concerns single UML diagram notations on their own as well as their integration. In this paper, we focus on
the notation of UML-statecharts. Starting with a precise textual syntax definition, we develop a precise structured operational
semantics (SOS) for UML-statecharts. Besides the support of interlevel transitions and in contrast to related work, our semantics
definition supports characteristic UML-statechart features like the history mechanism as well as entry and exit actions.
Initial submission: 19 February 2002 / Revised submission: 28 October 2002 Published online: 2 December 2002 相似文献
7.
Algebraic query optimisation for database programming languages 总被引:1,自引:0,他引:1
Alexandra Poulovassilis Carol Small 《The VLDB Journal The International Journal on Very Large Data Bases》1996,5(2):119-132
A major challenge still facing the designers and implementors of database
programming languages (DBPLs) is that of query optimisation. We investigate
algebraic query optimisation techniques for DBPLs in the context of a purely
declarative functional language that supports sets as first-class objects.
Since the language is computationally complete issues such as
non-termination of expressions and construction of infinite data structures
can be investigated, whilst its declarative nature allows the issue of side
effects to be avoided and a richer set of equivalences to be developed.
The language has a well-defined semantics which permits us to reason
formally about the properties of expressions, such as their equivalence with
other expressions and their termination. The support of a set bulk data
type enables much prior work on the optimisation of relational languages to
be utilised.
In the paper we first give the syntax of our archetypal DBPL and briefly
discuss its semantics. We then define a small but powerful algebra of
operators over the set data type, provide some key equivalences for
expressions in these operators, and list transformation principles for
optimising expressions. Along the way, we identify some caveats to
well-known equivalences for non-deductive database languages. We next
extend our language with two higher level constructs commonly found in
functional DBPLs: set comprehensions and functions with known inverses. Some
key equivalences for these constructs are provided, as are transformation
principles for expressions in them. Finally, we investigate extending our
equivalences for the set operators to the analogous operators over bags.
Although developed and formally proved in the context of a functional
language, our findings are directly applicable to other DBPLs of similar
expressiveness.
Edited by
Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received
September 15, 1994 / Accepted September 1, 1995 相似文献
8.
Chiang Lee Chi-Sheng Shih Yaw-Huei Chen 《The VLDB Journal The International Journal on Very Large Data Bases》2001,9(4):327-343
Traditional algorithms for optimizing the execution order of joins are no more valid when selections and projections involve
methods and become very expensive operations. Selections and projections could be even more costly than joins such that they
are pulled above joins, rather than pushed down in a query tree. In this paper, we take a fundamental look at how to approach
query optimization from a top-down design perspective, rather than trying to force one model to fit into another. We present
a graph model which is designed to characterize execution plans. Each edge and each vertex of the graph is assigned a weight
to model execution plans. We also design algorithms that use these weights to optimize the execution order of operations.
A cost model of these algorithms is developed. Experiments are conducted on the basis of this cost model. The results show
that our algorithms are superior to similar work proposed in the literature.
Received 20 April 1999 / Accepted 9 August 2000 Published online 20 April 2001 相似文献
9.
Answering queries using views: A survey 总被引:25,自引:0,他引:25
Alon Y. Halevy 《The VLDB Journal The International Journal on Very Large Data Bases》2001,10(4):270-294
The problem of answering queries using views is to find efficient methods of answering a query using a set of previously
defined materialized views over the database, rather than accessing the database relations. The problem has recently received
significant attention because of its relevance to a wide variety of data management problems. In query optimization, finding
a rewriting of a query using a set of materialized views can yield a more efficient query execution plan. To support the separation
of the logical and physical views of data, a storage schema can be described using views over the logical schema. As a result,
finding a query execution plan that accesses the storage amounts to solving the problem of answering queries using views.
Finally, the problem arises in data integration systems, where data sources can be described as precomputed views over a mediated
schema. This article surveys the state of the art on the problem of answering queries using views, and synthesizes the disparate
works into a coherent framework. We describe the different applications of the problem, the algorithms proposed to solve it
and the relevant theoretical results.
Received: 1 August 1999 / Accepted: 23 March 2001 Published online: 6 September 2001 相似文献
10.
Navin Kabra David J. DeWitt 《The VLDB Journal The International Journal on Very Large Data Bases》1999,8(1):55-78
In this paper we describe the design and implementation of OPT++, a tool for extensible database query optimization that
uses an object-oriented design to simplify the task of implementing, extending, and modifying an optimizer. Building an optimizer
using OPT++ makes it easy to extend the query algebra (to add new query algebra operators and physical implementation algorithms
to the system), easy to change the search space, and also to change the search strategy. Furthermore, OPT++ comes equipped
with a number of search strategies that are available for use by an optimizer-implementor. OPT++ considerably simplifies both,
the task of implementing an optimizer for a new database system, and the task of evaluating alternative optimization techniques
and strategies to decide what techniques are best suited for that database system. We present the results of a series of performance
studies. These results validate our design and show that, in spite of its flexibility, OPT++ can be used to build efficient
optimizers.
Received October 1996 / Accepted January 1998 相似文献
11.
Akira Maeda Koji Wakimoto Hiroto Nagahisa Itsuji Nakamura 《Machine Vision and Applications》1998,11(1):24-36
In electric power supply, railway, and other companies with many facilities, facility management is a laborious task. To
realize a computerized facility management system, numerous paper-based facility maps should be stored in a database. In this
paper, we present a system that constructs a facility management database by interpretation of paper-based facility maps.
This system can automatically recognize structured figures with variable shapes on maps, while conventional methods cannot
recognize these figures. And this system can easily generate relational data between facilities and character strings on maps.
We compare our recognition method of structured figures with variable shapes with a conventional recognition method, and show
the effectiveness of our system.
Received: 18 November 1996 / Accepted: 16 February 1998 相似文献
12.
Shuhua Wang Yang Cao Shijie Cai 《International Journal on Document Analysis and Recognition》2001,4(1):27-34
The most noticeable characteristic of a construction tender document is that its hierarchical architecture is not obviously
expressed but is implied in the citing information. Currently available methods cannot deal with such documents. In this paper,
the intra-page and inter-page relationships are analyzed in detail. The creation of citing relationships is essential to extracting
the logical structure of tender documents. The hierarchy of tender documents naturally leads to extracting and displaying
the logical structure as tree structure. This method is successfully implemented in VHTender, and is the key to the efficiency
and flexibility of the whole system.
Received February 28, 2000 / Revised October 20, 2000 相似文献
13.
一、引言一个数据库通常包括两个部分:数据资源和推导规则。数据资源是指存储在数据库中的事实。例如在一个家庭关系数据库中,Jonsson是Pater的父亲father(Jonsson,Peter),Mary是Peter的母亲mother(Mary,Peter)是数据资源。在计算机理论科学中又把数据库的这一部分称为外延数据库(EDB)。推导规则则是用户为数据演算定义的一种规则,或者也可以理解为数据之间的一种关系。例如祖父规则grandfather(X,Y)←father(X,Z),father(Z,Y),它规定若X为Z 相似文献
14.
Query processing and optimization in Oracle Rdb 总被引:2,自引:0,他引:2
Gennady Antoshenkov Mohamed Ziauddin 《The VLDB Journal The International Journal on Very Large Data Bases》1996,5(4):229-237
This paper contains an overview of the technology used in the query processing and optimization component of Oracle Rdb, a
relational database management system originally developed by Digital Equipment Corporation and now under development by Oracle
Corporation. Oracle Rdb is a production system that supports the most demanding database applications, runs on multiple platforms
and in a variety of environments.
Edited by C. Mohan / Received August 1994 / Acceped August 1995 相似文献
15.
Summary. In a Distributed System with N sites, the precise detection of causal relationships between events can only be done with
vector clocks of size N. This gives rise to scalability and efficiency problems for logical clocks that can be used to order
events accurately. In this paper we propose a class of logical clocks called plausible clocks that can be implemented with
a number of components not affected by the size of the system and yet they provide good ordering accuracy. We develop rules
to combine plausible clocks to produce more accurate clocks. Several examples of plausible clocks and their combination are
presented. Using a simulation model, we evaluate the performance of these clocks. We also present examples of applications
where constant size clocks can be used.
Received: January 1997 / Accepted: January 1999 相似文献
16.
R. Braumandl M. Keidl A. Kemper D. Kossmann A. Kreutz S. Seltzsam K. Stocker 《The VLDB Journal The International Journal on Very Large Data Bases》2001,10(1):48-71
We present the design of ObjectGlobe, a distributed and open query processor for Internet data sources. Today, data is published
on the Internet via Web servers which have, if at all, very localized query processing capabilities. The goal of the ObjectGlobe
project is to establish an open marketplace in which data and query processing capabilities can be distributed and used by any kind of Internet application. Furthermore, ObjectGlobe integrates cycle providers (i.e., machines) which carry out query processing operators. The overall picture is to make it possible to execute a query
with – in principle – unrelated query operators, cycle providers, and data sources. Such an infrastructure can serve as enabling
technology for scalable e-commerce applications, e.g., B2B and B2C market places, to be able to integrate data and data processing
operations of a large number of participants. One of the main challenges in the design of such an open system is to ensure
privacy and security. We discuss the ObjectGlobe security requirements, show how basic components such as the optimizer and
runtime system need to be extended, and present the results of performance experiments that assess the additional cost for
secure distributed query processing. Another challenge is quality of service management so that users can constrain the costs
and running times of their queries.
Received: 30 October 2000 / Accepted: 14 March 2001 Published online: 7 June 2001 相似文献
17.
Query processing over object views of relational data 总被引:2,自引:0,他引:2
Gustav Fahl Tore Risch 《The VLDB Journal The International Journal on Very Large Data Bases》1997,6(4):261-281
This paper presents an approach to object view management for relational databases. Such a view mechanism makes it possible for users to transparently work with data in
a relational database as if it was stored in an object-oriented (OO) database. A query against the object view is translated
to one or several queries against the relational database. The results of these queries are then processed to form an answer
to the initial query. The approach is not restricted to a ‘pure’ object view mechanism for the relational data, since the
object view can also store its own data and methods. Therefore it must be possible to process queries that combine local data
residing in the object view with data retrieved from the relational database. We discuss the key issues when object views
of relational databases are developed, namely: how to map relational structures to sub-type/supertype hierarchies in the view,
how to represent relational database access in OO query plans, how to provide the concept of object identity in the view,
how to handle the fact that the extension of types in the view depends on the state of the relational database, and how to
process and optimize queries against the object view. The results are based on experiences from a running prototype implementation.
Edited by: M.T. ?zsu. Received April 12, 1995 / Accepted April 22, 1996 相似文献
18.
Optimizing multiple dimensional queries simultaneously in multidimensional databases 总被引:1,自引:0,他引:1
Weifa Liang Maria E. Orlowska Jeffrey X. Yu 《The VLDB Journal The International Journal on Very Large Data Bases》2000,8(3-4):319-338
Some significant progress related to multidimensional data analysis has been achieved in the past few years, including the
design of fast algorithms for computing datacubes, selecting some precomputed group-bys to materialize, and designing efficient
storage structures for multidimensional data. However, little work has been carried out on multidimensional query optimization
issues. Particularly the response time (or evaluation cost) for answering several related dimensional queries simultaneously
is crucial to the OLAP applications. Recently, Zhao et al. first exploited this problem by presenting three heuristic algorithms.
In this paper we first consider in detail two cases of the problem in which all the queries are either hash-based star joins
or index-based star joins only. In the case of the hash-based star join, we devise a polynomial approximation algorithm which
delivers a plan whose evaluation cost is $ O(n^{\epsilon }$) times the optimal, where n is the number of queries and is a fixed constant with . We also present an exponential algorithm which delivers a plan with the optimal evaluation cost. In the case of the index-based
star join, we present a heuristic algorithm which delivers a plan whose evaluation cost is n times the optimal, and an exponential algorithm which delivers a plan with the optimal evaluation cost. We then consider
a general case in which both hash-based star-join and index-based star-join queries are included. For this case, we give a
possible improvement on the work of Zhao et al., based on an analysis of their solutions. We also develop another heuristic
and an exact algorithm for the problem. We finally conduct a performance study by implementing our algorithms. The experimental
results demonstrate that the solutions delivered for the restricted cases are always within two times of the optimal, which
confirms our theoretical upper bounds. Actually these experiments produce much better results than our theoretical estimates.
To the best of our knowledge, this is the only development of polynomial algorithms for the first two cases which are able
to deliver plans with deterministic performance guarantees in terms of the qualities of the plans generated. The previous
approaches including that of [ZDNS98] may generate a feasible plan for the problem in these two cases, but they do not provide
any performance guarantee, i.e., the plans generated by their algorithms can be arbitrarily far from the optimal one.
Received: July 21, 1998 / Accepted: August 26, 1999 相似文献
19.
Heuristic and randomized optimization for the join ordering problem 总被引:11,自引:0,他引:11
Michael Steinbrunn Guido Moerkotte Alfons Kemper 《The VLDB Journal The International Journal on Very Large Data Bases》1997,6(3):191-208
Recent developments in database technology, such as deductive database systems, have given rise to the demand for new, cost-effective
optimization techniques for join expressions. In this paper many different algorithms that compute approximate solutions for
optimizing join orders are studied since traditional dynamic programming techniques are not appropriate for complex problems.
Two possible solution spaces, the space of left-deep and bushy processing trees, are evaluated from a statistical point of
view. The result is that the common limitation to left-deep processing trees is only advisable for certain join graph types.
Basically, optimizers from three classes are analysed: heuristic, randomized and genetic algorithms. Each one is extensively
scrutinized with respect to its working principle and its fitness for the desired application. It turns out that randomized
and genetic algorithms are well suited for optimizing join expressions. They generate solutions of high quality within a reasonable
running time. The benefits of heuristic optimizers, namely the short running time, are often outweighed by merely moderate
optimization performance. 相似文献
20.
UnQL: a query language and algebra for semistructured data based on structural recursion 总被引:5,自引:0,他引:5
Peter Buneman Mary Fernandez Dan Suciu 《The VLDB Journal The International Journal on Very Large Data Bases》2000,9(1):76-110
Abstract. This paper presents structural recursion as the basis of the syntax and semantics of query languages for semistructured data
and XML. We describe a simple and powerful query language based on pattern matching and show that it can be expressed using
structural recursion, which is introduced as a top-down, recursive function, similar to the way XSL is defined on XML trees.
On cyclic data, structural recursion can be defined in two equivalent ways: as a recursive function which evaluates the data
top-down and remembers all its calls to avoid infinite loops, or as a bulk evaluation which processes the entire data in parallel
using only traditional relational algebra operators. The latter makes it possible for optimization techniques in relational
queries to be applied to structural recursion. We show that the composition of two structural recursion queries can be expressed
as a single such query, and this is used as the basis of an optimization method for mediator systems. Several other formal
properties are established: structural recursion can be expressed in first-order logic extended with transitive closure; its
data complexity is PTIME; and over relational data it is a conservative extension of the relational calculus. The underlying
data model is based on value equality, formally defined with bisimulation. Structural recursion is shown to be invariant with
respect to value equality.
Received: July 9, 1999 / Accepted: December 24, 1999 相似文献