10188867
A query language for a Web-site management system
We have designed a system, called STRUDEL, which applies familiar concepts from database management systems, to the process of building web sites. The main motivation for developing STRUDEL is the observation that with current technology, creating and managing large sites is tedious, because a site designer must simultaneously perform (at least) three tasks: (1) choosing what information will be available at the site, (2) organizing that information in individual pages or in graphs of linked pages, and (3) specifying the visual presentation of pages in HTML. Furthermore, since there is no separation between the physical organization of the information underlying a web site and the logical view we have on it, changing or restructuring a site are unwieldy tasks. In STRUDEL, the web site manager can separate the logical view of information available at a web site, the structure of that information in linked pages, and the graphical presentation of pages in HTML. First, the site builder defines independently the data that will be available at the site. This process may require creating an integrated view of data from multiple (external) sources. Second, the site builder defines the structure of the web-site. The structure is defined as a view over the underlying information, and different versions of the site can be defined by specifying multiple views. Finally, the graphical representation of the pages in the web site is specified. This paper describes the query language that lies at the heart of the STRUDEL system. In STRUDEL, we model the da ta at the different levels as graphs. That is, the data in the external sources, the da ta in the integrated view and the web-site itself are modeled as graphs. A graph model is appropriate because site da ta may be derived from multiple sources, such as existing database systems and HTML files. Consequently, our system requires a query language for (1) defining the integrated view of the data, and (2) defining the structure of web sites. An important requirement of our query language is that it be able to construct graphs. Our query processor needs to be able to answer queries tha t involve accessing different da ta sources. Even though we model the sources as containing graphs, we cannot assume they have a uniform representation of graphs. Hence, our query processor needs to adhere to possible limitations on access to data in the graphs, and should be able to exploit additional querying capabilities that an external source may have. We have designed a general framework for processing STRUDEL queries over multiple unstructured data sources, and are designing optimizations that use the capabilities of external sources whenever possible. The purpose of this paper is to describe the syntax and semantics of STRUQL, the query language at the core of STRUDEL. We believe that STRuQL is a language of independent interest, and is useful for other applications involving the management of semistructured data, as well as a view definition language for such data. We discuss the relationship of STRUQL to other languages proposed in the li terature in Section 6: see [Abi97, Bun97].
278836
Efficient evaluation of XML middle-ware queries
We address the problem of efficiently constructing materialized XML views of relational databases. In our setting, the XML view is specified by a query in the declarative query language of a middle-ware system, called SilkRoute. The middle-ware system evaluates a query by sending one or more SQL queries to the target relational database, integrating the resulting tuple streams, and adding the XML tags. We focus on how to best choose the SQL queries, without having control over the target RDBMS.
2076813
Adding Structure to Unstructured Data
We develop a new schema for unstructured data. Traditional schemas resemble the type systems of programming languages. For unstructured data, however, the underlying type may be much less constrained and hence an alternative way of expressing constraints on the data is needed. Here, we propose that both data and schema be represented as edge-labeled graphs. We develop notions of conformance between a graph database and a graph schema and show that there is a natural and efficiently computable ordering on graph schemas. We then examine certain subclasses of schemas and show that schemas are closed under query applications. Finally, we discuss how they may be used in query decomposition and optimization.
1399759
Warehousing and incremental evaluation for Web Site management
Recently, several systems have been proposed for building Web sites from declarative spec-iications. The salient feature of these systems is that they model both the structure and the content of a Web site as a view over some existing raw data. In this \Web site as view" paradigm, a critical issue is when to compute the site. One approach is to materialize the site completely before the users browse it: the disadvantages of this approach are high maintenance costs and stale data. Moreover, this approach is not applicable if the Web site has forms, because then the queries deening the Web site depends on user input. The other extreme approach is to precompute only the root(s) of the Web site, and then compute dynamically (at \click time") the queries that retrieves the information required to display the next page. In this paper we address the problem of choosing the optimal connguration for run-time management of a declaratively speciied Web site, trading oo the beneets of precomputation and incremental evaluation. First, we identify several novel optimizations that need to be considered in addition to optimizations obtained by precomputing views. These optimizations include simplifying queries based on contexts that can be derived from the browsing patterns, and lookahead computation. Second, we describe an algorithm for cost based search of a space of conngurations which include the above optimizations. Finally, given a connguration we show how to reformulate our Web-site deenition to exploit the views and data being cached.
7426500
UnQL: a query language and algebra for semistructured data based on structural recursion
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.
6149937
Publishing Relational Data in XML: the SilkRoute Approach
Xyleme is a dynamic warehouse for XML data of the Web supporting query evaluation, change control and data integration. We briefly present our motivations, the general architecture and some aspects of Xyleme. The project we describe here was completed at the end of 2000. A prototype has been implemented. This prototype is now being turned into a product by a start-up company also called Xyleme [14]. Xyleme: a complex tissue of wood cells, functions in conduction and storage ...
1019046
Implementing Nominal Unification
Nominal matching and unification underly the dynamics of nominal rewriting. Urban, Pitts and Gabbay gave a nominal unification algorithm which finds the most general solution to a nominal matching or unification problem, if one exists. Later the algorithm was extended by Fernandez and Gabbay to deal with name generation and locality. In this paper we describe first a direct implementation of the nominal unification algorithm, including the extensions, in Maude. This implementation is not efficient (it is exponential in time), but we will show that we can obtain a feasible implementation by using termgraphs.
14181773
Nominal rewriting
Nominal rewriting is based on the observation that if we add support for @a-equivalence to first-order syntax using the nominal-set approach, then systems with binding, including higher-order reduction schemes such as @l-calculus beta-reduction, can be smoothly represented. Nominal rewriting maintains a strict distinction between variables of the object-language (atoms) and of the meta-language (variables or unknowns). Atoms may be bound by a special abstraction operation, but variables cannot be bound, giving the framework a pronounced first-order character, since substitution of terms for variables is not capture-avoiding. We show how good properties of first-order rewriting survive the extension, by giving an efficient rewriting algorithm, a critical pair lemma, and a confluence theorem for orthogonal systems.
16649053
Coinductive techniques for operational equivalence of interaction nets
In this paper we study a notion of operational equivalence for interaction nets, following the recent success of applying methods based on bisimulation to functional and object oriented programming languages. We set up notions of contextual equivalence and bisimilarity and show that they coincide. A coinduction principle then gives a simple and robust way of showing when two interaction nets are contextually equivalent. We include several examples to demonstrate the usefulness of the approach, in particular for optimizing interaction nets.
6993516
A Theory of Operational Equivalence for Interaction Nets
The notion of contextual equivalence is fundamental in the theory of programming languages. By setting up a notion of bisimilarity, and showing that it coincides with contextual equivalence, one obtains a simple coinductive proof technique for showing that two programs are equivalent in all contexts. In this paper we apply these (now standard) techniques to interactions nets, a graphical programming language characterized by local reduction. This work generalizes previous studies of operational equivalence in interaction nets since it can be applied to untyped systems, thus all systems of interaction nets are captured.
12283254
Iterator Types
System L is a linear λ-calculus with numbers and an iterator, which, although imposing linearity restrictions on terms, has all the computational power of Godel's System τ. System L owes its power to two features: the use of a closed reduction strategy (which permits the construction of an iterator on an open function, but only iterates the function after it becomes closed), and the use of a liberal typing rule for iterators based on iterative types. In this paper, we study these new types, and show how they relate to intersection types. We also give a sound and complete type reconstruction algorithm for System L.