Databases

Publications on databases

Data Warehouses and OLAP

Publications on Data Warehousing and OLAP

A Generic and Customizable Framework for the Design of ETL Scenarios

P. Vassiliadis, A. Simitsis, M. Georgantas, P. Terrovitis, and S. Skiadopoulos
In Information Systems, 30(7):492--525, 2005.

Abstract:
Extraction-Transformation-Loading (ETL) tools are pieces of software responsible for the extraction of data from several sources, their cleansing, customization and insertion into a data warehouse. In this paper, we delve into the logical design of ETL scenarios and provide a generic and customizable framework in order to support the DW designer in his task. First, we present a metamodel particularly customized for the definition of ETL activities. We follow a workflow-like approach, where the output of a certain activity can either be stored persistently or passed to a subsequent activity. Also, we employ a declarative database programming language, LDL, to define the semantics of each activity. The metamodel is generic enough to capture any possible ETL activity. Nevertheless, in the pursuit of higher reusability and flexibility, we specialize the set of our generic metamodel constructs with a palette of frequently-used ETL activities, which we call templates. Moreover, in order to achieve a uniform extensibility mechanism for this library of built-ins, we have to deal with specific language issues. Therefore, we also discuss the mechanics of template instantiation to concrete activities. The design concepts that we introduce have been implemented in a tool, ARKTOS II, which is also presented.

Note:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Research area: 
Year: 

Advanced Visualization for Mobile OLAP

A. Maniatis, P. Vassiliadis, S. Skiadopoulos, G. Mavrogonatos, and I. Michalarias
International Journal of Data Warehousing and Mining, 1(1):1--36, 2005.

Abstract:
Data visualization is one of the major issues of database research and OLAP, being a decision support technology, is clearly in the center of this effort. Still, so far, visualization has not been incorporated in the abstraction levels of DBMS architecture (conceptual, logical, physical), neither has it been formally treated in this context. In this paper we start by reconsidering the separation of the aforementioned abstraction levels to take visualization into consideration. Then, we present the Cube Presentation Model (CPM), a novel presentational model for OLAP screens. The proposal lies on the fundamental idea of separating the logical part of a data cube computation, from the presentational part of the client tool. Then, CPM can be naturally mapped on the Table Lens, which is an advanced visualization technique from the Human-Computer Interaction area, particularly tailored for cross-tab reports. Based on the particularities of Table Lens, we propose automated proactive support to the user for the interaction with an OLAP screen. Finally, we discuss implementation and usage issues in the context of an academic prototype system (CubeView) that we have implemented.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 

Advanced Visualization for OLAP

A. Maniatis, P. Vassiliadis, S. Skiadopoulos, and Y. Vassiliou
In Proceedings of the ACM 6th Int'l Workshop on Data Warehousing and OLAP (DOLAP'03), pages 9--16. ACM Press, November 2003.

Abstract:
Data visualization is one of the big issues of database research. OLAP as a decision support technology is highly related to the developments of data visualization area. In this paper we demonstrate how the Cube Presentation Model (CPM), a novel presentational model for OLAP screens, can be naturally mapped on the Table Lens, which is an advanced visualization technique from the Human-Computer Interaction area, particularly tailored for cross-tab reports. We consider how the user interacts with an OLAP screen and based on the particularities of Table Lens, we propose an automated proactive users support. Finally, we discuss the necessity and the applicability of advanced visualization techniques in the presence of recent technological developments.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Year: 

Arktos: A Tool For Data Cleaning and Transformation in Data Warehouse Environments

P. Vassiliadis, Z. Vagena, N. Skiadopoulos, S. Karayannidis, and T. Sellis
IEEE Data Engineering Bulletin, 23(4):42--47, 2000.

Abstract:
Extraction-Transformation-Loading (ETL) and Data Cleaning tools are pieces of software responsible for the extraction of data from several sources, their cleaning, customization and insertion into a data warehouse. To deal with the complexity and efficiency of the transformation and cleaning tasks we have developed a tool, namely ARKTOS, capable of modeling and executing practical scenarios, by providing explicit primitives for the capturing of common tasks. ARKTOS provides three ways to describe such a scenario, including a graphical point-and-click front end and two declarative languages: XADL (an XML variant), which is more verbose and easy to read and SADL (an SQL-like language) which has a quite compact syntax and is, thus, easier for authoring.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Arktos: Towards the Modeling, Design, Control and Execution of ETL Processes

P. Vassiliadis, Z. Vagena, N. Skiadopoulos, S. Karayannidis, and T. Sellis
In Information Systems, 26(8):537--561, 2001.

Abstract:
Extraction-Transformation-Loading (ETL) tools are pieces of software responsible for the extraction of data from several sources, their cleansing, customization and insertion into a data warehouse. Literature and personal experience have guided us to conclude that the problems concerning the ETL tools are primarily problems of complexity, usability and price. To deal with these problems we provide a uniform metamodel for ETL processes, covering the aspects of data warehouse architecture, activity modeling, contingency treatment and quality management. The ETL tool we have developed, namely ARKTOS, is capable of modeling and executing practical ETL scenarios by providing explicit primitives for the capturing of common tasks. provides three ways to describe an ETL scenario: a graphical point-and-click front end and two declarative languages: XADL (an XML variant), which is more verbose and easy to read and SADL (an SQL-like language) which has a quite compact syntax and is, thus, easier for authoring.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Blueprints for ETL workflows

P. Vassiliadis, A. Simitsis, M. Terrovitis, and S. Skiadopoulos
In Proceedings of the 24th International Conference on Conseptual Modeling (ER'05), volume 3716 of LNCS, pages 385--400. Springer, 2005

Abstract:
Extract-Transform-Load (ETL) workflows are data centric workflows responsible for transferring, cleaning, and loading data from their respective sources to the warehouse. Previous research has identified graphbased techniques that construct the blueprints for the structure of such workflows. In this paper, we extend existing results by explicitly incorporating the internal semantics of each activity in the workflow graph. Apart from the value that blueprints have per se, we exploit our modeling to introduce rigorous techniques for the measurement of ETL workflows. To this end, we build upon an existing formal framework for software quality metrics and formally prove how our quality measures fit within this framework.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

CPM: A Cube Presentation Model for OLAP

A. Maniatis, P. Vassiliadis, S. Skiadopoulos, and Y. Vassiliou
Abstract:

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Conceptual Modelling for ETL Processes

P. Vassiliadis, A. Simitsis, and S. Skiadopoulos
In Proceedings of the ACM 5th Int'l Workshop on Data Warehousing and OLAP (DOLAP'02), pages 14--21. ACM Press, July 2002.

Abstract:
Extraction-Transformation-Loading (ETL) tools are pieces of software responsible for the extraction of data from several sources, their cleansing, customization and insertion into a data warehouse. In this paper, we focus on the problem of the definition of ETL activities and provide formal foundations for their conceptual representation. The proposed conceptual model is (a) customized for the tracing of inter-attribute relationships and the respective ETL activities in the early stages of a data warehouse project; (b) enriched with a 'palette' of a set of frequently used ETL activities, like the assignment of surrogate keys, the check for null values, etc; and (c) constructed in a customizable and extensible manner, so that the designer can enrich it with his own re-occurring patterns for ETL activities.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Graph-Based Modeling of ETL Activities with Multi-Level Transformations and Updates

A. Simitsis, P. Vassiliadis, M. Terrovitis, and S. Skiadopoulos
In Proceedings of the 7th Int'l Conference on Data Warehousing and Knowledge Discovery (DaWaK'05), volume 2589 of LNCS, pages 43--52. Springer, 2005

Abstract:
Extract-Transform-Load (ETL) workflows are data centric workflows responsible for transferring, cleaning, and loading data from their respective sources to the warehouse. In this paper, we build upon existing graph-based modeling techniques that treat ETL workflows as graphs by (a) extending the activity semantics to incorporate negation, aggregation and self-joins, (b) complementing querying semantics with insertions, deletions and updates, and (c) transforming the graph to allow zoom-in/out at multiple levels of abstraction (i.e., passing from the detailed description of the graph at the attribute level to more compact variants involving programs, relations and queries and vice-versa).

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Modelling ETL Activities as Graphs

P. Vassiliadis, A. Simitsis, and S. Skiadopoulos
In Proceedings of the 4th Int'l Workshop on the Design and Management of Data Warehouses (DMDW'02), pages 52--61. CEUR Workshop Proceedings, May 2002

Abstract:
Extraction-Transformation-Loading (ETL) tools are pieces of software responsible for the extraction of data from several sources, their cleansing, customization and insertion into a data warehouse. In this paper, we focus on the logical design of the ETL scenario of a data warehouse. Based on a formal logical model that includes the data stores, activities and their constituent parts, we model an ETL scenario as a graph, which we call the Architecture Graph. We model all the aforementioned entities as nodes and four different kinds of relationships (instance-of, part-of, regulator and provider relationships) as edges. In addition, we provide simple graph transformations that reduce the complexity of the graph. Finally, in order to support the engineering of the design and the evolution of the warehouse, we introduce specific importance metrics, namely dependence and responsibility, to measure the degree to which entities are bound to each other.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Modelling ETL Processes as Graphs

P. Vassiliadis, A. Simitsis, and S. Skiadopoulos
In Proceedings of the Hellenic Data Management Symposium (HDMS'03), September 2003.

Abstract:
Το άρθρο αυτό αφορά στο λογικό σχεδιασμό ΕΜΦ (Εξαγωγής-Μετασχηματισμού-Φόρτωσης) σεναρίων για αποθήκες δεδομένων. Με βάση ένα τυπικό λογικό μοντέλο που αποτελείται από σημεία αποθήκευσης δεδομένων, διεργασίες και τα συστατικά τους μέρη, ένα ΕΜΦ σενάριο μοντελοποιείται ως γράφος, που ονομάζεται Γράφος Αρχιτεκτονικής. Όλες οι προαναφερθείσες οντότητες αποτελούν τους κόμβους του γράφου και τα τέσσερα διαφορετικά είδη σχέσεων που έχουν μεταξύ τους (όπως σχέσεις στιγμιότυπου, μέρους, ρύθμισης και παροχής) τις ακμές. Με σκοπό να υποστηριχτεί ο σχεδιασμός και η εξέλιξη της ΑΔ, ορίζονται συγκεκριμένες μετρήσεις σπουδαιότητας: η εξάρτηση και η υπευθυνότητα, για τον υπολογισμό του βαθμού κατά τον οποίο είναι συνδεδεμένες μεταξύ τους οι οντότητες του σεναρίου.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Modelling and Language Support for the Management of Pattern-Bases

M. Terrovitis, P. Vassiliadis, E. Skiadopoulos, S. Bertino, B. Catania, and A. Maddalena
In Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), pages 265--274. IEEE Computer Society, 2004

Abstract:
In our days knowledge extraction methods are able to produce artifacts (also called patterns) that concisely rep- resent data. Patterns are usually quite heterogeneous and require ad-hoc processing techniques. So far, little empha- sis has been posed on developing an overall integrated en- vironment for uniformly representing and querying dif- ferent types of patterns. Within the larger context of mod- elling, storing, and querying patterns, in this paper, we: (a) formally de¯ne the logical foundations for the global setting of pattern management through a model that cov- ers data, patterns and their intermediate mappings; (b) present a pattern speci¯cation language for pattern man- agement along with safety restrictions; and (c) intro- duce queries and query operators and identify interest- ing query classes.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Modelling and Optimization Issues for Multidimensional Databases

P. Vassiliadis and S. Skiadopoulos.
In Proceedings of CAiSE'00, volume 1789 of LNCS, pages 482--497. Springer, June 2000.

Abstract:
It is commonly agreed that multidimensional data cubes form the basic logical data model for OLAP applications. Still, there seems to be no agreement on a common model for cubes. In this paper we propose a logical model for cubes based on the key observation that a cube is not a self-existing entity, but rather a view over an underlying data set. We accompany our model with syntactic characterisations for the problem of cube usability. To this end, we have developed algorithms to check whether (a) the marginal conditions of two cubes are appropriate for a rewriting, in the presence of aggregation hierarchies and (b) an implication exists between two selection conditions that involve different levels of aggregation of the same dimension hierarchy. Finally, we present a rewriting algorithm for the cube usability problem.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Modelling and Querying Multidimensional Databases

P. Vassiliadis and S. Skiadopoulos
In Proceedings of the Hellenic Data Management Symposium (HDMS'02), July 2002.

Abstract:
Η Σύγχρονη Αναλυτική Επεξεργασία Δεδομένων (On-Line Analytical Processing - OLAP) είναι μια τάση στην τεχνολογία των βάσεων δεδομένων, που στηρίζεται στη θεώρηση της πληροφορίας με πολυδιάστατο τρόπο στο επίπεδο των πελατών. Παρά την κοινή αποδοχή των πολυδιάστατων κύβων σαν το κεντρικό λογικό μοντέλο για OLAP και την πληθώρα των ερευνητικών προτάσεων, υπάρχει μικρή συμφωνία στην εύρεση μιας κοινής ορολογίας και σημασιολογίας για το λογικό μοντέλο δεδομένων. Στο άρθρο αυτό προτείνεται ένα επιπλέον λογικό μοντέλο για κύβους, με βάση την παρατήρηση ότι ένας κύβος δεν είναι μια αυθύπαρκτη οντότητα, αλλά μια όψη πάνω σε ένα υποκείμενο σύνολο δεδομένων. Το προτεινόμενο μοντέλο είναι αρκετά ισχυρό στο να καλύπτει όλες τις συνηθισμένες πράξεις OLAP όπως επιλογή, συναθροιστική άνοδος και αναλυτική κάθοδος σε επίπεδα αδρομέρειας, μέσω μιας συνεπούς και πλήρης άλγεβρας. Δείχνεται επίσης πώς αυτό το μοντέλο μπορεί να χρησιμοποιηθεί σαν η βάση για την επεξεργασία λειτουργιών στους κύβους και παρουσιάζονται συντακτικοί χαρακτηρισμοί για τα προβλήματα της χρησιμότητας κύβων (ήτοι, του προβλήματος χρησιμοποιήσεως δεδομένων από κάποιον κύβο για να υπολογιστεί ένας άλλος κύβος).

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

On the Logical Modelling of ETL Processes

P. Vassiliadis, A. Simitsis, and S. Skiadopoulos
In Proceedings of the 14th Conference on Advanced Information Systems Engineering (CAiSE'02), short paper, volume 2348 of LNCS, pages 782--786. Springer, May 2002

Abstract:
Extraction-Transformation-Loading (ETL) tools are pieces of software responsible for the extraction of data from several sources, their cleansing, customization and insertion into a data warehouse. Research has only recently dealt with the above problem and provided few models, tools and techniques to address the issues around the ETL environment [1,2,3,5]. In this paper, we present a logical model for ETL processes. The proposed model is characterized by several templates, representing frequently used ETL activities along with their semantics and their interconnection. In the full version of the paper [4] we present more details on the aforementioned issues and complement them with results on the characterization of the content of the involved data stores after the execution of an ETL scenario and impact-analysis results in the presence of changes.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Parallel and Distributed Databases

Publications on Parallel and Distributed Databases

A Cost Model for the Estimation of Query Execution Time in a Parallel Environment Supporting Pipeline

M. Spiliopoulou, M. Hatzopoulos and C. Vassilakis
in Journal Computers and Artificial Intelligence, Vol. 14, 1996, No. 1, pp. 341-368

Abstract:
We propose a model for the estimation of query execution time in an environment supporting bushy and pipelined parallelism. We consider a parallel architecture of processors having private main memories, accessing a shared secondary storage and communicating to each other via a network. For this environment, we compute the cost of query operators when processed in isolation and when in pipeline mode. We use those formulae to incrementally compute the cost of a query execution plan from its components. Our cost model can be incorporated to any optimizer for parallel query processing that considers parallel and pipelined execution of the query operators.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon cost-model-95.pdf259.36 KB
Year: 

Parallel Optimisation of Join Queries Using a Technique of Exhaustive Nature

M. Spiliopoulou, M. Hatzopoulos and C. Vassilakis
in Computers and Artificial Intelligence, Vol. 12, 1993, No. 2.

Abstract
In this study we present a technique for the parallel optimisation of join queries, that uses the offered coarse-grain parallelism of the underlying architecture in order to reduce the CPU-bound optimisation overhead. The optimisation technique performs an almost exhaustive search of the solution space for small join queries and gradually, as the number of joins increases, it diverges towards iterative improvement. This technique has been developed on a low-parallelism transputer-based architecture, where its behaviour is studied for the optimisation of queries with many tenths of joins.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon cai-93.pdf248.77 KB
Year: 

Using Parallelism and Pipeline for the Optimisation of Join Queries

M. Spiliopoulou, M. Hatzopoulos and C. Vassilakis
Proceedings of the PARLE Conference, Paris, June 1992

Abstract
In this study we present a technique for the parallel optimisation of join queries, that uses the offered coarse-grain parallelism of the underlying architecture in order to reduce the CPU-bound optimisation overhead. The optimisation technique performs an almost exhaustive search of the solution space for small join queries and gradually, as the number of joins increases, it diverges towards iterative improvement. This technique has been developed on a low-parallelism transputer-based architecture, where its behaviour is studied for the optimisation of queries with many tenths of joins.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon parle-paper.pdf495.03 KB
Year: 

Spatiotemporal databases

Publications on Spatiotemporal databases

A Comparative Study of Temporal DBMS Architectures

C. Vassilakis, P. Georgiadis, A. Sotiropoulou
in Proceedings of DEXA 96 workshop, Zurich, September 1996.

Abstract:
In the past years, a number of implementations of temporal DBMSs has been reported. Most of these implementations share a common feature, which is that they have been built as an extension to a snapshot DBMS. In this paper, we present three alternative design approaches that can be used for extending a snapshot DBMS to support temporal data, and evaluate the suitability of each approach, with respect to a number of design objectives.

Note:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Research area: 
Year: 

A Flexible Framework for Managing Temporal Clinical Trial Data

Michael Souillard , Carine Souveyet, Costas Vassilakis, Anya Sotiropoulou
International Journal of Electronic Healthcare, Volume 1, Number 4, 2005.

Abstract:
Clinical trials are processes that produce large volumes of complex data, with inherent temporal requirements, since the state of patients evolves during the trials, and the data acquisition phase itself needs to be monitored. Additionally, since the requirements for all clinical trials have a significant common portion, it is desirable to capture these common requirements in a generalised framework, which will be instantiated for each specific trial by supplementing the trial-specific requirements. In this paper, we present an integral approach to clinical trial management, using a temporal object-oriented methodology to capture and model the requirements, a temporal OODBMS for data storage and a generalised template application, through which trial-specific applications may be generated.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

An Optimization Scheme for Coalesce/Valid Time Selection Operator

Costas Vassilakis
SIGMOD Record, vol. 29, number 1, March 2000, pp. 38-43.

Abstract:
Queries in temporal databases often employ the coalesce operator, either to coalesce results of projections, or data which are not coalesced upon storage. Therefore, the performance and the optimisation schemes utilised for this operator is of major importance for the performance of temporal DBMSs. Insofar, performance studies for various algorithms that implement this operator have been conducted, however, the joint optimisation of the coalesce operator with other algebraic operators that appear in the query execution plan has only received minimal attention. In this paper, we propose a scheme for combining the coalesce operator with selection operators which are applied to the valid time of the tuples produced from a coalescing operation. The proposed scheme aims at reducing the number of tuples that a coalescing operator must process, while at the same time allows the optimiser to exploit temporal indices on the valid time of the data.

Article available through the ACM Author-izer service:

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Composing Cardinal Direction Relations

S. Skiadopoulos and M. Koubarakis
In Artificial Intelligence, 152(2):143--171, 2004

Abstract:
We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our efforts on the composition operator for two cardinal direction relations. We consider two interpretations of the composition operator: consistency-based and existential composition. We point out that the only published method to compute the consistency-based composition does not always work correctly. Then, we consider progressively more expressive classes of cardinal direction relations and give consistency-based composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. When we consider existential composition, we demonstrate that the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer. Finally, we discuss some extensions to the basic model and consider the composition problem for these extensions.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Composing Cardinal Directions Relations

S. Skiadopoulos and M. Koubarakis
In Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD'01), volume 2121 of LNCS, pages 299--317. Springer, July 2001

Abstract:
We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our eorts on the operation of composition for two cardinal direction relations. We point out that the only published method to compute the composition does not always work correctly. Then we consider progressively more expressive classes of cardinal direction relations and give composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. Finally, we demonstrate that in some cases, the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Composition Algorithm for Cardinal Direction Relations

S. Skiadopoulos and M. Koubarakis
In Proceedings of the 2nd Hellenic Conference on Artificial Intelligence (SETN'02), short paper, April 2002.

Abstract:
We present a formal model for qualitative spatial reasoning with cardinal directions that is based on a recent proposal in the literature. We use our formal framework to study the composition operation for the cardinal direction relations of this model. We consider progressively more expressive classes of cardinal direction relations and give composition algorithms for these classes. Finally, when we consider the problem in its generality, we show that the binary relation resulting from the composition of some cardinal direction relations cannot even be expressed using the relations which are currently employed by the related proposal.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Computing and Handling Cardinal Direction Information

S. Skiadopoulos, C. Giannoukos, P. Vassiliadis, T. Sellis, and M. Koubarakis
In Proceedings of the 9th Int'l Conference on Extending Database Technology (EDBT'04), volume 2992 of LNCS, pages 329--347. Springer, 2004

Abstract:
Qualitative spatial reasoning forms an important part of the commonsense reasoning required for building intelligent Geographical Information Systems (GIS). Previous research has come up with models to capture cardinal direction relations for typical GIS data. In this paper, we target the problem of efficiently computing the cardinal direction relations between regions that are composed of sets of polygons and present the first two algorithms for this task. The first of the proposed algorithms is purely qualitative and computes, in linear time, the cardinal direction relations between the input regions. The second has a quantitative aspect and computes, also in linear time, the cardinal direction relations with percentages between the input regions. The algorithms have been implemented and embedded in an actual system, CarDirect, that allows the user to annotate regions of interest in an image or a map, compute cardinal direction relations and retrieve combinations of interesting regions on the basis of a query.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Computing and Managing Cardinal Direction Relations

S. Skiadopoulos, C. Giannoukos, N. Sarkas, P. Vassiliadis, T. Sellis, and M. Koubarakis
in IEEE Transaction on Knowledge and Date Engineering, 17(12):1610--1623, 2005

Abstract:
Qualitative spatial reasoning forms an important part of the commonsense reasoning required for building intelligent Geographical Information Systems (GIS). Previous research has come up with models to capture cardinal direction relations for typical GIS data. In this paper, we target the problem of efficiently computing the cardinal direction relations between regions that are composed of sets of polygons and present two algorithms for this task. The first of the proposed algorithms is purely qualitative and computes, in linear time, the cardinal direction relations between the input regions. The second has a quantitative aspect and computes, also in linear time, the cardinal direction relations with percentages between the input regions. Our experimental evaluation indicates that the proposed algorithms outperform existing methodologies. The algorithms have been implemented and embedded in an actual system, CARDIRECT, that allows the user to 1) specify and annotate regions of interest in an image or a map, 2) compute cardinal direction relations between them, and 3) pose queries in order to retrieve combinations of interesting regions.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Consistency Checking for Qualitative Spatial Reasoning with Cardinal Directions

S. Skiadopoulos and M. Koubarakis
In Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming (CP'02), volume 2470 of LNCS, pages 341--355. Springer, September 2002.

Abstract:
We present a formal model for qualitative spatial reasoning with cardinal directions and study the problem of checking the consistency of a set of cardinal direction constraints. We present the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm we prove that the consistency checking of a set of basic cardinal direction constraints can be performed in O(n^5) time while the consistency checking of an unrestricted set of cardinal direction constraints is NP-complete. Finally, we briefly discuss some extensions to the basic model.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Function Oriented History Representation in Databases

L. Kovacs and C. Vassilakis
Computers and Artificial Intelligence, vol. 19, 2000, pp. 417-444.

Abstract:
In the past years the management of temporal data has attracted numerous researchers resulting to a large number of temporal data extensions to the relational and object oriented data models. In this paper, the proposed temporal data model focuses on the functional characteristics of the histories. The paper introduces a set oriented description of the calendars together with a function oriented history concept with a history-algebra. The completeness of the proposed model with respect to the reduced temporal algebra TA is also proven. The expressive power of the proposed model is demonstrated at the end of the paper by a hospital example.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Implementation of Transaction and Concurrency Control Support in a Temporal DBMS

C. Vassilakis, N. Lorentzos and P. Georgiadis
Information Systems, vol. 23, No 5, pp. 335-350, 1998.

Abstract:
Transactions and concurrency control are significant features in database systems, facilitating functions both at user and system level. However, the support of these features in a temporal DBMS has not yet received adequate research attention. In this paper, we describe the techniques developed in order to support transaction and concurrency control in a temporal DBMS which was implemented as an additional layer to a commercial DBMS. The proposed techniques make direct use of the transaction mechanisms of the DBMS. In addition, they overcome a number of limitations such as automatic commit points, lock release and log size increment, which are imposed by the underlying DBMS. Our measurements have shown that the overhead introduced by these techniques is negligible, less than 1% in all cases. The approach undertaken is of general interest, it can also be applied to non-temporal DBMS extensions.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Implementing Embedded Valid Time Query Languages

C. Vassilakis, P. Georgiadis, T. Selis
Proceedings of the DEXA '98 Conference, pp. 561-572.

Abstract:
Application development on top of database systems is heavily based on the existence of embedded and 4GL languages. However, the issue of designing and implementing embedded or 4GL temporal languages has not been addressed insofar. In this paper, we present a design approach for implementing an embedded temporal language that supports valid time. Furthermore, we introduce implementation techniques that can be used for implementing any embedded temporal language that supports valid time on top of a DBMS.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

On the Consistency of Cardinal Directions Constraints

S. Skiadopoulos and M. Koubarakis
In Artificial Intelligence, 163(1):91--135, 2005

Abstract:
We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Using the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n^5) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Querying Indefinite Spatial and Temporal Information: The New Frontier

M. Koubarakis and S. Skiadopoulos
In Proceedings of the IJCAI Workshop on Hot Topics in Spatial and Temporal Reasoning, August 1999.

Abstract:
Temporal and spatial constraint networks do not live alone in the wilderness. In many cases they are components of larger systems e.g., temporal database systems, spatial database systems, knowledge representation systems, natural language systems, planning systems, scheduling systems, multimedia systems and so on. We believe that an interesting new frontier for temporal and spatial reasoning research is the formalisation, analysis and possible re-implementation of systems where temporal or spatial reasoners are an important component. In this paper we will make a first contribution to this exciting area of research. We will consider temporal constraint networks complemented by a database for storing the information typically used to label network nodes. We will then study the computational complexity of querying the combined system using a first order modal query language.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Querying Temporal Constraint Networks in PTIME

M. Koubarakis and S. Skiadopoulos
In Proceedings of AAAI'99, pages 745--750, July 1999.

Abstract:
We start with the assumption that temporal knowledge usually captured by constraint networks can be represented and queried more effectively by using the scheme of indefinite constraint databases proposed by Koubarakis. Although query evaluation in this scheme is in general a hard computational problem, we demonstrate that there are several interesting cases where query evaluation can be done in PTIME. These tractability results are original and subsume previous results by van Beek, Brusoni, Console and Terenziani.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Querying Temporal and Spatial Constraint Networks in PTIME

M. Koubarakis and S. Skiadopoulos
Artificial Intelligence, 123(1-2):223--263, 2000.

Abstract:
We start with the assumption that temporal and spatial knowledge usually captured by constraint networks can be represented and queried more effectively by using the scheme of indefinite constraint databases. Because query evaluation in this scheme is in general a hard computational problem, we seek tractable instances of query evaluation. We assume that we have a class of constraints C with some reasonable computational and closure properties (the computational properties of interest are that the satisfiability problem and an appropriate version of the variable elimination problem for C should be solvable in PTIME). Under this assumption, we exhibit general classes of indefinite constraint databases and first-order modal queries for which query evaluation can be done with PTIME data complexity. We then search for tractable instances of C among the subclasses of Horn disjunctive linear constraints over the rationals. From previous research we know that the satisfiability problem for Horn disjunctive linear constraints is solvable in PTIME, but not the variable elimination problem. Thus we try to discover subclasses of Horn disjunctive linear constraints with tractable variable elimination problems. The class of UTVPI^{\ne} constraints is the largest class that we show to have this property. Finally, we restate our general tractability results with C ranging over the newly discovered tractable classes. Interesting tractable query answering problems for indefinite temporal and spatial constraint databases are identified in this way. We close our complexity analysis by precisely outlining the frontier between tractable and possibly intractable query answering problems

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Spatiotemporal Models and Languages: An Approach Based on Constraints

S. Grumbach, M. Koubarakis, M. Scholl, and S. Skiadopoulos
In M. Koubarakis, T. Sellis, A. Frank, S. Grumbach, R.-H. Gueting, C. Jensen, N. Lorentzos, Y. Manolopoulos, E. Nardelli, B. Pernici, B. Theodoulidis, N. Tryfona, H.-J. Schek and M. Scholl (eds.) Spatiotemporal Databases: The CHOROCHRONOS Approach, volume 2520 of LNCS. Springer, 2003.

Abstract:

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

TOOBIS: Application of the Management of Temporal Data in Clinical Research

M. Souillard, C. Vassilakis, A. Sotiropoulou
INFORSID '98 Actes des Conferences, pp. 145-168 (in French).

Abstract:
Temporal data, i.e. data varying over time dimension whose history of evolutions is maintained, are not used in the industrial world. But, far from managing only non-temporal data, numerous and various applications and industrial sectors such as banking, insurance, disease management in medicine, booking and so on, face the management of temporal data. These applications often use results of own developments, simulating temporal data in a more or less effective ways. This paper presents the results of the European project TOOBIS - Temporal Object Oriented dataBase within Information System - underlying an application using and managing temporal data, in the domain of Clinical Research. TOOBIS offers an extension of the object-oriented database standard in order to provide a full temporal object-oriented database management system, as well as a temporal methodology of analysis and design.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Temporal Extension to ODMG

A. Sotiropoulou, M. Souillard, C. Vassilakis
in Proceedings of the 3rd Biennial World Conference on Integrated Design and Process Technology, Vol. 2, Issues and Applications of Database Technology (IADT), Berlin, Germany, 1998, pp. 304-311.

Abstract:
In the past years a number of temporal extensions to the different database models have been proposed. Extensions to the relational model have been following the different SQL standards, while no attempts have been made to extend the OO-databases' standard, defined by ODMG. In this paper we present a temporal extension to the ODMG standard, as this has been specified in the TOOBIS project. A Temporal Object Data Model, a Temporal Object Definition Language and a Temporal Object Query Language have been specified and have been proposed as extensions to the ODM, ODL and OQL of ODMG. This extension has been implemented over a commercial OODBMS, reinforcing and validating the effort of standardisation and portability of this extension.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon temporal-extension-odmg.pdf247.68 KB
Research area: 
Year: 

Tractable Query Answering in Indefinite Constraint Databases: Basic Results&Applications to Querying SpatioTemporal Information

M. Koubarakis and S. Skiadopoulos
T. In Proceedings of Int'l Workshop on Spatio-Temporal Database Management (STDBM'99), volume 1678 of LNCS, pages 204--223. Springer, September 1999

Abstract:
We consider the scheme of indefinite constraint databases proposed by Koubarakis. This scheme can be used to represent indefinite information arising in temporal, spatial and truly spatiotemporal applications. The main technical problem that we address in this paper is the discovery of tractable classes of databases and queries in this scheme. We start with the assumption that we have a class of constraints C with satisfiability and variable elimination problems that can be solved in PTIME. Under this assumption, we show that there are several general classes of databases and queries for which query evaluation can be done with PTIME data complexity. We then search for tractable instances of C in the area of temporal and spatial constraints. Classes of constraints with tractable satisfiability problems can be easily found in the literature. The largest class that we consider is the class of Horn disjunctive linear constraints over the rationals. Because variable elimination for Horn disjunctive linear constraints cannot be done in PTIME, we try to discover subclasses with tractable variable elimination problems. The class of UTVPI^{\ne} constraints is the largest class that we show to have this property. Finally, we restate the initial general results with C ranging over the newly discovered tractable classes. Tractable query answering problems for indefinite temporal and spatial constraint databases are identified in this way.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Research area: 
Year: 

Transaction Support in a Temporal DBMS

C. Vassilakis, N. Lorentzos and P. Georgiadis
in Proceedings of International Workshop on Temporal Databases, Zürich, September 1995

Abstract:
Transactions are a significant concept in database systems, facilitating functions both at user and system level. However transaction support in temporal DBMSs has not yet received enough research attention. In this paper, we present techniques for incorporating transaction support in a temporal DBMS, which is implemented as an additional layer to a commercial RDBMS. These techniques overcome certain limitations imposed by the underlying RDBMS, and avoid excessive increment of the log size.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon transaction-support-in-tdbms.pdf203.19 KB
Research area: 
Year: 

Other

Other publications on databases

An Object-Oriented Data Model for Hypermedia Systems

M. Hatzopoulos, D. Gouscos, M. Spiliopoulou, C. Vassilakis and M. Vazirgiannis
in Proceedings of the DELTA Conference in Research and Development, pp. 483-493, The Hague, October 1990.

Abstract
Our main objective is the definition of a design model for a hypermedia database, dedicated to accomodating multimedia information and to promote navigation as a means of information processing. We prefered the object-oriented paradigm to the relational one, because it provides generic modelling constructs and supports property inheritance. We observe the hyperbase as a network of items and links, where items contain multimedia information and links represent the relationship among them. So, we define a class hierarchy containing both the information pieces and the interconnections among them as objects in the same level of functionality. In this environment, we support typed and weighted links to enhance the declaration of semantic relationships, and keywords to allow for querying as an alternative tool for information processing.

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
AttachmentSize
PDF icon delta-conf-paper.pdf161.15 KB
Research area: 
Year: