Recent advances in AI techniques, as well as enabling hardware and infrastructure, has led to the integration of AI in wide-ranging domains and tasks. In particular, AI has been used to handle various types of data (including numerical, textual and graphical data) and has been adopted in large-scale distributed systems. From a data management perspective, this calls for the harnessing of state-of- the-art AI solutions for data management tasks and systems. aiDM is a full-day workshop that offers a stage for innovative interdisciplinary research that studies the interaction between AI and data management and develops new AI technologies for data-related tasks. This year, aiDM'22 particularly focuses on the transparent exploitation of AI techniques in existing enterprise-level data management workloads.

Recently, the Artificial Intelligence (AI) field has been experiencing a resurgence. AI broadly covers a wide swath of techniques which include logic-based approaches, probabilistic graphical models, and machine learning/deep learning approaches. Advances in hardware capabilities, such as Graphics Processing Units (GPUs), software components (e.g., accelerated libraries, programming frameworks), and systems infrastructures (e.g., GPU-enabled cloud providers) has led to a wide-spread adaptation of AI techniques to a variety of domains. Examples of such domains include image classification, autonomous driving, automatic speech recognition (ASR) and conversational systems (chatbots). AI techniques not only support multiple datatypes (e.g., free text, images, or speech), but are also available in various configurations, from personal devices to large-scale distributed systems.

XML is based on a tree-structured data model. Naturally, the most popular XML querying language (XPath) uses patterns of selection predicates, on multiple elements related by a tree structure, which often may be abstracted by twig patterns. Finding all occurrences of such a twig pattern in an XML database is a basic operation for XML query processing. We present the parallel path stack algorithm (PPS) and the parallel twig stack algorithm (PTS). PPS and PTS are novel and efficient algorithms for matching XML query twig patterns in a parallel multi-threaded computing platform. PPS and PTS are based on the PathStack and TwigStack algorithms [1]. These algorithms employ a sophisticated search technique for limiting processing to specific subtrees. We conducted extensive experimentation with PPS and PTS. We compared PPS and PTS to the standard (sequential) PathStack and TwigStack algorithms in terms of run time (to completion). We checked their performance for varying numbers of threads. Experimental results indicate that using PPS and PTS significantly reduces the running time of queries in comparison with the PathStack/TwigStack algorithm (up to 44 times faster for DBLP queries and up to 22 times faster for XMark queries).

The Query Network [12] is a model for query-based social networks automation features, motivated by the rise of social networks as a central internet application. This work generalizes the model to consist of a proposal query and an acceptance query for each participant. As a result, addition of edges is done by coordination between participants, simulating interactions between participants. We designed, implemented and experimented with evaluation algorithms for this new model. Experiments with both synthetic and real datasets show the high effectiveness of our methods.

We study a novel data management scenario, in which social networks participants use protocols in order to manage their activities and the ever-growing data available to them in the network. In particular, we study protocols which operate on a consistent network (that we define), and transform it into another consistent state by atomically performing a set of changes. Multiple protocol instances, which work on intersecting parts of the network graphs are able to operate concurrently.

We introduce and study concurrent One-Way Protocols in social networks. The model is motivated by the rise of online social networks and the fast development of automation features in them. In a One-Way architecture, used, e.g., by Twitter, participants can publish status updates and send messages only to their followers. Based on this asymmetric model, we define network consistency, and consider the scenario in which participants make consistent decisions based on their friends' decisions, like in Facebook 'Events'.

In this study, we present experiences of parallelizing XPath queries using the Xalan XPath engine on shared-address space multi-core systems. For our evaluation, we consider a scenario where an XPath processor uses multiple threads to concurrently navigate and execute individual XPath queries on a shared XML document. Given the constraints of the XML execution and data models, we propose three strategies for parallelizing individual XPath queries: Data partitioning, Query partitioning, and Hybrid (query and data) partitioning. We experimentally evaluated these strategies on an x86 Linux multi-core system using a set of XPath queries, invoked on a variety of XML documents using the Xalan XPath APIs. Experimental results demonstrate that the proposed parallelization strategies work very effectively in practice; for a majority of XPath queries under evaluation, the execution performance scaled linearly as the number of threads was increased. Results also revealed the pros and cons of the different parallelization strategies for different XPath query patterns.

We consider a near future scenario in which users of a Web 2.0 application, such as a social network, contribute to the application not only data, but also rules which automatically query, utilize and create the data. For example, a user of a social network can define rules that automatically manage the user's friends list, the sending of various announcements, filtering of messages and more.We examine the probable case of automated addition of connections by a participant. The connections to be added are defined using a query, associated to each participant. For this, we introduce and study the Query Network model, a graph-based model in which every node models a network participant and is associated with a Datalog rule. The union of all these individual user rules constitutes a very large, recursive, Datalog program whose size is of the order of magnitude of the size of the data being queried (data whose size in a social network can easily exceed 1TB). This greatly differs from the traditional assumption that queries are small and data are large. In particular, traditional optimizers will be hard pressed to handle such queries. This is the case even if queries are 'translated' to SQL (using views) and their union is transformed to a very large SQL query.We have designed, built and experimented with evaluation algorithms for such query networks. Experiments with both synthetic and real datasets demonstrate the usefulness and high effectiveness of our methods. Extensions to the model are proposed, their implementation and testing are the subject of on-going work.

We present SoQL (social networks query language), a new language for querying and creating data in social networks. The language is designed to meet the growing need of social networks participants to efficiently manage the large, and quickly growing, amounts of data available to them, as well as automate processes of creating new data. This need is increasingly pressing as social networks gradually become an important working tool for business development and management. SoQL is a step in the direction of meeting the challenges of providing an expressive querying mechanism and automating processes in social networks.SoQL is an SQL-like language which enables the user to retrieve paths to other participants in the network, and use a retrieved path in order to attempt to create a connection with the participant at the end of the path. The language can specify complex conditions that a desired path should satisfy. The language also supports retrieving a group of participants which satisfy conditions as a group, and connecting its members to each other. SoQL uses the path and group as data types. This work presents the SoQL language and discusses implementation issues.

We study the problem of schema revalidation where XML data known to conform to one schema must be validated with respect to another schema. Such revalidation algorithms have applications in schema evolution, query processing, XML-based programming languages, and other domains. We describe how knowledge of conformance to an XML Schema may be used to determine conformance to another XML Schema efficiently. We examine both the situation where an XML document is modified before it is revalidated and the situation where it is unmodified

The increased importance of XML as a data representation format has led to several proposals for facilitating the development of applications that operate on XML data. These proposals range from runtime API-based interfaces to XML-based programming languages. The subject of this paper is XJ, a research language that proposes novel mechanisms for the integration of XML as a first-class construct into Java™. The design goals of XJ distinguish it from past work on integrating XML support into programming languages --- specifically, the XJ design adheres to the XML Schema and XPath standards. Moreover, it supports in-place updates of XML data thereby keeping with the imperative nature of Java. We have built a prototype compiler for XJ, and our preliminary experiments demonstrate that the performance of XJ programs can approach that of traditional low-level API-based interfaces, while providing a higher level of abstraction.

This work explores (semi-)automated EC on the WWW. The EContracts framework enables EC WWW sites and EC automated tools to present standardized information. This information (1) allows each party to decide whether it wishes to engage in an EC activity with the other party, (2) enables automated negotiation between the parties, and (3) enables the establishment of an electronic contract, i.e. a formal description of an agreed upon EC transaction. The EContracts framework defines the basic software components of an EC party and their interconnections. Based on the EContracts framework, various applications can be built. Examples are deal making applications, deal feasibility checkers, brokers etc. Furthermore, the definitions of the data structures and the algorithms enable a theoretical investigation of automated commerce.

We consider the problems of containment, equivalence, satisfiability and query-reachability for datalog programs with negation. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are decidable for programs with stratified negation provided that negation is applied only to EDB predicates or that all EDB predicates are unary. In the latter case, we show that equivalence is also decidable. The algorithms we present can also be used to push constraints from a given query to the EDB predicates. In showing our decidability results we describe a powerful tool, the query-tree, which is used for several optimization problems for datalog programs. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠.

This work explores (semi-) automated EC on the WWW. The EContracts framework enables EC WWW sites and EC automated tools to present standardized information. This information (1) allows each party to decide whether it wishes to engage in an EC activity with the other party, (2) enables automated negotiation between the parties, and (3) enables the establishment of an electronic contract, i.e., a formal description of an agreed upon EC transaction. The EContracts framework defines the basic software components of an EC party and their interconnections. Based on the EContracts framework, various applications can be built. Examples are deal making applications, deal feasibility checkers, brokers etc. Furthermore, the definitions of the data structures and the algorithms enable a theoretical investigation of automated commerce.

Quo is a framework for the development of applications that use WWW data. Quo models the WWW accessible data using a dynamic semistructured data model called Quom (Quasi-Object Model). Within a semistructured model, Quom introduces (I) Object-Oriented features, (2) a structure declaration which is a "lightweight" schema definition. On the other hand, Quom relaxes the requirement, of Object-Oriented data models, of a strict schema definition. This enables dealing with the irregularities of WWW extracted data and with self-describing data formats "a la" XML. Data extraction rules are defined using Quodl, the Quasi-Object Definition Language. Quodl data extraction rules use XSL to analyze and extract HTML/XML data and regular expressions are used for the analysis of and extraction from, raw data.

The World Wide Web (WWW) is a fast growing global information resource. It contains an enormous amount of information and provides access to a variety of services. Since there is no central control and very few standards of information organization or service offering, searching for information and services is a widely recognized problem. To some degree this problem is solved by “search services,” also known as “indexers,” such as Lycos, AltaVista, Yahoo, and others. These sites employ search engines known as “robots” or “knowbots” that scan the network periodically and form text-based indices. These services are limited in certain important aspects. First, the structural information, namely, the organization of the document into parts pointing to each other, is usually lost. Second, one is limited by the kind of textual analysis provided by the “search service.” Third, search services are incapable of navigating “through” forms. Finally, one cannot prescribe a complex database-like search. We view the WWW as a huge database. We have designed a high-level SQL-like language called W3QL to support effective and flexible query processing, which addresses the structure and content of WWW nodes and their varied sorts of data. We have implemented a system called W3QS to execute W3QL queries. In W3QS, query results are declaratively specified and continuously maintained as views when desired. The current architecture of W3QS provides a server that enables users to pose queries as well as integrate their own data analysis tools. The system and its query language set a framework for the development of database-like tools over the WWW. A significant contribution of this article is in formalizing the WWW and query processing over it.

Summary form only given. W3QL is a SQL like, high level language for accessing World-Wide Web (WWW) resident data and services, W3QL is declarative. A W3QL query specifies a graph to be matched with portions of the WWW (graph nodes corresponding to WWW pages, edges to hypertext links). A query can specify complex conditions on node contents and their relationships. A W3QL query may use existing search services (e.g. Alta Vista). W3QL is extensible as users may use their own data analysis tools (e.g. image analysis). W3QS is a system that manages W3QS queries. W3QS is accessible via the WWW or by using a programming based interface (API). On the WWW, W3QS provides several interfaces: intuitive graphic interfaces, templates of frequently posed queries, and direct programming.

The problem of determining whether, for every extensional database, a given predicate in a given program has a finite number of derivations is called the universal finiteness problem. The problem of determining whether a given predicate in a given program has a non-empty extension for some extensional database is called the satisfiability problem. We show that the universal finiteness problem can be reduced to the satisfiability problem. Thus all decidability results for satisfiability can be applied to universal finiteness—for example, we can infer that the universal finiteness problem is decidable for Datalog extended with negation on base predicates. The satisfiability problem can be easily reduced to the universal finiteness problem, so that all undecidability results for satisfiability can be applied to universal finiteness. For example we can infer that the universal finiteness problem is undecidable for Datalog extended with stratified negation.

Consider the problem of maintaining large indices (or secondary memory indices) in a multiprocessor multidisk environment in which each processor has a dedicated secondary memory (one disk or more). The processors either reside in the same site and communicate via shared memory, or reside in different sites and communicate via a local broadcast network. The straightforward method (SFM) for maintaining such an index, which is commonly called declustering, is to partition the index records equally among the processors, each of which maintains its part of the index in a local B/sup +/-tree. In prior work (Inform. Processing Lett., vol. 34, pp. 313-321, May 1990), we have presented another method, called the "totally distributed B/sup +/-tree" (TDB) method, in which all processors together implement a "wide" B/sup +/-tree. There are settings in which the second method is better than the first method, and vice versa. In this paper, we present a new method, called the combined distribution method (CDM), that combines the ideas underlying SFM and TDB. In tightly coupled environments, CDM outperforms both SFM and TDB in almost all practical settings (in many settings by more than 30%). This is shown by an approximate analysis and verified by simulations. Note that CDM's approach can improve performance in database systems that use a RAID (redundant array of inexpensive disks).>

We consider the problems of equivalence, satisfiability and query-reachability for datalog programs with negation and dense-order constraints. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are decidable for programs with stratified negation provided that negation is applied only to EDB predicates or that all EDB predicates are unary. In the latter case, we show that equivalence is also decidable. The algorithms we present are also used to push constraints from a given query to the EDB predicates. Finally, we show that satisfiability is undecidable for datalog programs with unary IDB predicates, stratified negation and the interpreted predicate ≠

Suppose a database schema D is extended to D¯ by adding new relation schemas, and states for D are extended to states for D¯ by applying joins and projections to existing relations. It is shown that certain desirable properties that D¯ has with respect to D . These properties amount to the ability to compute efficiently the join of all relations in a state for D from an extension of this state over D¯ . The equivalence is proved for unrestricted (i.e., both finite and infinite) databases. If D¯ is obtained from D by adding a set of new relation schemas that form a tree schema, then the equivalence also holds for finite databases. In this case there is also a polynomial time algorithm for testing the existence of a tree projection of D¯ with respect to D .

The concept of a trigger is central to any active database. Upon the occurrence of a trigger event, the trigger is “fired”, i.e, the trigger action is executed. We describe a model and a language for specifying basic and composite trigger events in the context of an object-oriented database. The specified events can be detected efficiently using finite automata.

We propose compilation methods for supporting set terms in Horn clause programs, without using general-purpose set matching algorithms, which tend to run in times exponential in the size of the participating sets Instead, we take the approach of formulating specialized computation plans that, by taking advantage of information available in the given rules, limit the number of alternatives explored. Our strategy is to employ compile time rewriting techniques and to transform the problem into an “ordinary” Horn clause compilation problem, with minimal additional overhead. The execution cost of the rewritten rules is substantially lower than that of the original rules and the additional cost of compilation can thus be amortized over many executions

This paper presents a methodology for testing a general logic program containing function symbols and built-in predicates for safety and effective computability. Safety is the property that the set of answers for a given query is finite. A related issues is whether the evaluation strategy can effectively compute all answers and terminate. We consider these problems under the assumption that queries are evaluated using a bottom-up fixpoint computation. We also approximate the use of function symbols by considering Datalog programs with infinite base relations over which finiteness constraints and monotonicity constraints are considered. One of the main results of this paper is a recursive algorithm, check_clique, to test the safety and effective computability of predicates in arbitrarily complex cliques. This algorithm takes certain procedures as parameters, and its applicability can be strengthened by making these procedures more sophisticated. We specify the properties required of these procedures precisely, and present a formal proof of correctness for algorithm check_clique. This work provides a framework for testing safety and effective computability of recursive programs, and is based on a clique by clique analysis. The results reported here form the basis of the safety testing for the LDL language, being implemented at MCC.

In this paper we extend LDL, a Logic Based Database Language, to include finite sets and negation. The new language is called LDL1. We define the notion of a model and show that a negation-free program need not have a model, and that it may have more than one minimal model. We impose syntactic restriction in order to define a deterministic language. These restrictions allow only layered (stratified) programs. We prove that for any program satisfying the syntactic restrictions of layering, there is a minimal model, and that this model can be constructed in a bottom-up fashion. Extensions to the basic grouping mechanism are proposed. We show that these extensions can be translated into equivalent LDL1 programs. Finally, we show how the technique of magic sets can be extended to translate LDL1 programs into equivalent programs which can often be executed more efficiently

This paper addresses some basic problems regarding logic programming based queries over relational databases. We re-examine the query classes H and YE+ defined by Chandra and Harel [2] We define H+ and YE++ which differ from H and YE+ in that the use of equality (=) and inequality (≠) is prohibited. We show that H+ is more expressive than YE++ and that any H+ program can be transformed into an equivalent H+ program containing a single recursive predicate without using the equality or inequality operators. As a corollary we obtain a fixpoint formula characterization of H+ queries.

In relational databases a view definition is a query against the database, and a view materialization is the result of applying the view definition to the current database. A view materialization over a database may change as relations in the database undergo modifications. Several problems concerning views are considered, many of which are shown to be hard (NP-complete or even $\Sigma _2^p $-complete). Each problem was treated for general databases and for the much simpler tree databases (also called acyclic databases). View related problems over fixed schemas, in which only the data is allowed to vary, were examined. Methods to handle this case were presented; their complexity is polynomial: for tree schemas the degree of the polynomial is independent of the schema structure while for cyclic schemas the degree depends on the schema structure. These methods may present a practical possibility for dynamic view maintenance.

Parallel distributed algorithms are presented for adding and deleting edges in a directed graph without creating a cycle. Such algorithms are useful for a variety of problems in distributed systems such as preventing deadlock or ordering priorities. The algorithms operate in a realistic asynchronous computer network environment in which there are numerous possible interactions among overlapping instances of the algorithms.

Article The equivalence of solving queries and producing tree projections (extended abstract) Share on Authors: Yehoshua Sagiv View Profile , Oded Shmueli View Profile Authors Info & Claims PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systemsJune 1985 Pages 160–172https://doi.org/10.1145/6012.15413Online:01 June 1985Publication History 3citation309DownloadsMetricsTotal Citations3Total Downloads309Last 12 Months2Last 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 SiteGet Access

Database schemes with functional dependencies are considered.The satisfying states of these schemes are those having representative instances that satisfy all the xfunctional dependencies.All states are assumed to be finite.A database scheme is fdacyclic if all its pairwise consistent satisfying states are also join consistent.If the relation schemes of a database scheme are closed under the functional dependencies, then the database scheme is fd-acyclic if and only if it is acyclic (i.e., its corresponding hypergraph is acyclic).If a cover of the functional dependencies is embedded in the database scheme, then fd-acyclicity can be tested in polynomial time.

In relational databases a view definition is a query against the database, and a view materialization is the result of applying the view definition to the current database A view materialization over a database may change as relations in the database undergo modificationsIn this paper a mechanism is proposed in which the view is materialized at all times The problem which this mechanism addresses is how to quickly update the view in response to database changes A structure is maintained which provides information useful in minimizing the amount of work caused by updatesMethods are presented for handling both general databases and the much simpler tree databases (also called acyclic database) In both cases adding or deleting a tuple can be performed in polynomial time For tree databases the degree of the polynomial is independent of the schema structure while for cyclic databases the degree depends on the schema structure The cost of a sequence of tuple additions (deletions) is also analyzed

Database schemas may be partitioned into two sub-classes tree schemas and cyclic schemas. The analysis of tree vs cyclic schemas introduced the concepts of GYO reductions, canonical connections and tree projections. This paper investigates the intricate relationships among these concepts in the context of universal relation databases.

A database schema in the relational data model is a hypergraph whose nodes represent attributes (or column headings) and whose edges represent relations over those attributes (or tables with those column headings).Tree schemas are database schemas with a simple, treelike structure.Tree schemas are called acyclic schemes or acyclic hypergraphs in parts of the hterature.The simple structure of tree schemas is used to advantage in dwerse areas of database management, including query processing and dependency theory.This paper provides several characterizations of tree schemas.It is proved that cyclic (i.e., nontree) schemas are built from simple building blocks, called Arings and Acliques; these play a role in the theory analogous to the role of simple cycles in graph theory.It is proved that a schema is a tree schema ff and only ff it is a conformal hypergraph and a natural graph representation (the 2-section) is chordal.Indeed, conformality is equivalent to the absence of Achques, and chordality is equivalent to the absence of Axings.The present characterizations are also related to ones that appear elsewhere: acyclic hypergraphs, Graham reductions, the running intersection property, and maximal weight qual trees.

One can partition the class of relational database schemas into tree schemas and cyclic schemas. In this paper we examine query processing implications of the partitioning; other areas impacted include dependency theory, schema design and graph theory.We consider a class of queries that compute the join of all relations in the database projected onto a prescribed set of attributes. We show that solving such queries (using the join, project and semijoin operators) is tantamount to creating an "embedded" tree schema which we call a tree projection. This lends further credibility to the pivotal nature of the tree/cyclic partitioning.Using the tree projection concept we analyze the problem of determining how many joins are needed to solve a query.

Article Transforming cyclic schemas into trees Share on Authors: N. Goodman Harvard University Harvard UniversityView Profile , O. Shmueli Harvard University Harvard UniversityView Profile Authors Info & Claims PODS '82: Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1982 Pages 49–54https://doi.org/10.1145/588111.588120Online:29 March 1982Publication History 15citation257DownloadsMetricsTotal Citations15Total Downloads257Last 12 Months4Last 6 weeks1 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 SiteGet Access

One can partition the class of relational database schemas into tree schemas and cyclic schemas. (These are called acyclic hypergraphs and cyclic hypergraphs elsewhere in the literature.) This partition has interesting implications in query processing, dependency theory, and graph theory. The tree/cyclic partitioning of database schemas originated with a similar partition of equijoin queries. Given an arbitrary equijoin query one can obtain an equivalent query that calculates the natural join of all relations in (an efficiently) derived database; such a query is called a natural join (NJ) query. If the derived database is a tree schema the original query is said to be a tree query, and otherwise a cyclic query. In this paper we analyze query processing consequences of the tree/cyclic partitioning. We are able to argue, qualitatively, that queries which imply a tree schema are easier to process than those implying a cyclic schema. Our results also extend the study of the semijoin operator.