SIGMOD Record

Bài viết này trình bày một bản dịch của một tập con của ngôn ngữ truy vấn quan hệ SQL sang phép tính tuple nổi tiếng. Nói một cách tổng quát, phép tính tuple tương ứng với phép tính đệ nhất thứ tự. Tập con SQL là đầy đủ về mặt quan hệ và đại diện cho một “cốt lõi quan hệ” của ngôn ngữ. Tuy nhiên, bản dịch của chúng tôi lại đơn giản và tinh tế. Do đó, nó đặc biệt phù hợp làm khóa học cho người mới bắt đầu vào các nguyên lý của định nghĩa chính thức về SQL.

Ghi chú này trình bày một bản dịch của một tập hợp con của ngôn ngữ truy vấn quan hệ SQL sang tính toán tuple nổi tiếng. Nói một cách đơn giản, tính toán tuple tương ứng với tính toán mệnh đề bậc nhất. Tập hợp con SQL này là đầy đủ theo quan hệ và đại diện cho một 'trái tim quan hệ' của ngôn ngữ. Tuy nhiên, bản dịch của chúng tôi lại đơn giản và thanh lịch. Do đó, nó đặc biệt phù hợp như một khóa học cho người mới bắt đầu về các nguyên tắc của một định nghĩa chính thức về SQL.

Ghi chú này cố gắng tóm tắt ngắn gọn các hoạt động nghiên cứu và kết quả liên quan đến sự tích hợp của các khái niệm lập trình hướng đối tượng và các ngôn ngữ cơ sở dữ liệu suy diễn.

Xác thực kết quả phân cụm là một chủ đề quan trọng trong bối cảnh nhận dạng mẫu. Chúng tôi xem xét các phương pháp và hệ thống trong bối cảnh này. Trong phần đầu của bài báo này, chúng tôi trình bày các phương pháp kiểm tra tính hợp lệ của phân cụm dựa trên các tiêu chí nội tại và ngoại tại. Trong phần thứ hai, chúng tôi trình bày một cái nhìn tổng quan về các phương pháp tính hợp lệ phân cụm dựa trên các tiêu chí tương đối. Ngoài ra, chúng tôi cũng thảo luận về kết quả của một nghiên cứu thực nghiệm dựa trên các chỉ số hợp lệ nổi tiếng. Cuối cùng, bài báo minh họa những vấn đề còn thiếu được đề cập bởi các phương pháp gần đây và đề xuất các hướng nghiên cứu trong lĩnh vực này.

Một tóm tắt phân vị xấp xỉ ∈ của một chuỗi N phần tử là một cấu trúc dữ liệu có thể trả lời các truy vấn về phân vị đối với chuỗi với độ chính xác là ∈ N .

Chúng tôi trình bày một thuật toán trực tuyến mới để tính toán các tóm tắt phân vị xấp xỉ ∈ của các chuỗi dữ liệu rất lớn. Thuật toán này có yêu cầu không gian trong trường hợp tồi tệ nhất là Ο (1÷∈ log(∈ N )). Kết quả này tốt hơn so với kết quả tốt nhất trước đây là Ο (1÷∈ log ² (∈ N )). Hơn nữa, trái ngược với các thuật toán xác định trước đây, thuật toán của chúng tôi không yêu cầu kiến thức a priori về độ dài của chuỗi đầu vào.

Cuối cùng, các giới hạn không gian thực tế thu được trên dữ liệu thử nghiệm tốt hơn đáng kể so với các đảm bảo trường hợp tồi tệ nhất của thuật toán của chúng tôi cũng như các yêu cầu không gian quan sát được của các thuật toán trước đó.

Chương trình hướng đối tượng rất phù hợp với các miền ứng dụng có tính dữ liệu cao như CAD/CAM, AI và OIS (hệ thống thông tin văn phòng) với các tài liệu đa phương tiện. Tại MCC, chúng tôi đã xây dựng một hệ thống cơ sở dữ liệu hướng đối tượng nguyên mẫu, gọi là ORION. Nó thêm tính bền vững và khả năng chia sẻ cho các đối tượng được tạo ra và thao tác trong các ứng dụng được triển khai trong môi trường lập trình hướng đối tượng. Một trong những yêu cầu quan trọng của những ứng dụng này là tiến hóa lược đồ, tức là khả năng thay đổi linh hoạt nhiều loại hình khác nhau của lược đồ cơ sở dữ liệu. Trong bài báo này, sau khi xem xét ngắn gọn mô hình dữ liệu hướng đối tượng mà chúng tôi hỗ trợ trong ORION, chúng tôi thiết lập một khuôn khổ để hỗ trợ tiến hóa lược đồ, định nghĩa ngữ nghĩa của tiến hóa lược đồ và thảo luận về việc thực hiện nó.

Nhiều hệ thống cơ sở dữ liệu thương mại duy trì các biểu đồ để tóm tắt nội dung của các quan hệ và cho phép ước lượng hiệu quả kích thước kết quả truy vấn và chi phí kế hoạch truy cập. Mặc dù đã có nhiều loại biểu đồ được đề xuất trong quá khứ, nhưng chưa có một nghiên cứu hệ thống nào về tất cả các khía cạnh của biểu đồ, các lựa chọn có sẵn cho từng khía cạnh và tác động của những lựa chọn đó đến hiệu quả của biểu đồ. Trong bài báo này, chúng tôi cung cấp một phân loại các biểu đồ phản ánh tất cả các loại biểu đồ đã được đề xuất trước đó và chỉ ra nhiều khả năng mới. Chúng tôi giới thiệu các lựa chọn mới cho một số chiều của phân loại, và phát triển các loại biểu đồ mới bằng cách kết hợp các lựa chọn theo cách hiệu quả. Chúng tôi cũng cho thấy cách mà các kỹ thuật lấy mẫu có thể được sử dụng để giảm chi phí xây dựng biểu đồ. Cuối cùng, chúng tôi trình bày kết quả từ một nghiên cứu thực nghiệm về các loại biểu đồ được đề xuất trong ước lượng tính chọn lọc của các điều kiện phạm vi và xác định các loại biểu đồ có hiệu suất tổng thể tốt nhất.

Chúng tôi được cung cấp một cơ sở dữ liệu lớn về các giao dịch của khách hàng. Mỗi giao dịch bao gồm các mặt hàng mà một khách hàng đã mua trong một lần ghé thăm. Chúng tôi giới thiệu một thuật toán hiệu quả để sinh ra tất cả các quy tắc liên kết đáng kể giữa các mặt hàng trong cơ sở dữ liệu. Thuật toán này tích hợp quản lý bộ đệm và các kỹ thuật ước lượng và cắt tỉa mới. Chúng tôi cũng trình bày kết quả áp dụng thuật toán này cho dữ liệu bán hàng thu được từ một công ty bán lẻ lớn, cho thấy hiệu quả của thuật toán.

Bài báo này xem xét vai trò của Jim Gray trong việc xác định tiêu chuẩn debit/credit. Việc công bố tiêu chuẩn này trong một bài báo năm 1985 đã khởi đầu một cuộc chiến tiêu chuẩn giữa các nhà cung cấp, dẫn đến những cải tiến đáng kể về hiệu suất hệ thống cơ sở dữ liệu trong những năm tiếp theo sau khi được công bố. Đây là nguồn gốc của TPC, một liên minh ngành công nghiệp đã thay đổi bộ mặt của các tiêu chuẩn. Những hậu duệ của tiêu chuẩn này đến nay vẫn là một chỉ số quan trọng của các hệ thống xử lý giao dịch hiện đại.

Một lớp hệ thống quản lý cơ sở dữ liệu mới (DBMSs) được gọi là NewSQL tự hào về khả năng mở rộng các khối lượng công việc xử lý giao dịch trực tuyến hiện đại (OLTP) theo cách mà các hệ thống kế thừa không thể thực hiện. Thuật ngữ NewSQL lần đầu tiên được sử dụng bởi một trong các tác giả của bài báo này trong báo cáo phân tích kinh doanh năm 2011 nói về sự trỗi dậy của các hệ thống cơ sở dữ liệu mới như những đối thủ cạnh tranh với các nhà cung cấp đã thiết lập (Oracle, IBM, Microsoft). Tác giả còn lại đã làm việc về những gì trở thành một trong những ví dụ đầu tiên của một DBMS NewSQL. Kể từ đó, một số công ty và dự án nghiên cứu đã sử dụng thuật ngữ này (đúng và sai) để mô tả các hệ thống của họ.

Xét rằng các DBMS quan hệ đã tồn tại hơn bốn thập kỷ, điều hợp lý là đặt câu hỏi rằng liệu tuyên bố về sự vượt trội của NewSQL có thực sự đúng hay đó chỉ là một chiêu thức tiếp thị. Nếu thực sự chúng có khả năng đạt được hiệu suất tốt hơn, thì câu hỏi tiếp theo là liệu có điều gì mới về mặt khoa học mà cho phép chúng đạt được những lợi ích này, hay chỉ đơn giản là phần cứng đã tiến bộ đến mức mà các nút thắt cổ chai từ những năm trước không còn là vấn đề.

Để làm điều này, chúng tôi trước tiên thảo luận về lịch sử của cơ sở dữ liệu để hiểu cách mà các hệ thống NewSQL ra đời. Sau đó, chúng tôi cung cấp một giải thích chi tiết về thuật ngữ NewSQL và các loại hệ thống khác nhau thuộc định nghĩa này.